paging
Imagine you are moving house and you have a pile of belongings that must go into a storage warehouse. The old way was to demand one big unbroken run of shelf space exactly the size of your whole pile — but the warehouse already has bits and pieces of free shelf scattered everywhere, never one big enough run, so you are turned away even though plenty of space exists. Paging is the clever fix: cut your belongings into identical-sized boxes, and let each box go onto ANY free shelf slot, in any order. The boxes do not have to sit next to each other; a separate little notebook records, for box 1, which slot it went to; for box 2, which slot; and so on. Now any scattering of free slots is usable.
Concretely, paging is a memory-management scheme that breaks a process's logical (virtual) address space into fixed-size blocks called PAGES, and breaks physical memory into blocks of the SAME size called FRAMES. A page can be loaded into any free frame; the mapping is recorded in a per-process PAGE TABLE, one entry per page giving the frame that holds it. Because pages and frames are the same fixed size, allocation is trivial bookkeeping (keep a list of free frames; hand out any of them), and a process's pages can be sprinkled all over physical memory while still looking like one continuous address space to the program. The hardware quietly translates every logical address the program uses into the real physical address using the page table.
Paging matters because it ELIMINATES EXTERNAL FRAGMENTATION — the wasted slivers of free memory that contiguous allocation leaves behind — since any free frame is as good as any other. The honest cost is a little INTERNAL fragmentation: the last page of a process is usually not completely full, so on average about half a page is wasted per process. Paging is the dominant scheme in modern operating systems and is the foundation virtual memory is built on, but note that paging by itself is just the address-mapping mechanism; bringing pages in from disk on demand is a separate idea (demand paging) covered elsewhere.
A process needs 13 KB of memory and the page size is 4 KB. Paging gives it 4 pages: pages 0, 1, 2 are full (12 KB) and page 3 holds only 1 KB. The operating system finds any 4 free frames — say frames 9, 2, 17, 5 — and records the mapping page 0 -> frame 9, page 1 -> frame 2, page 2 -> frame 17, page 3 -> frame 5. The frames need not be adjacent.
Four equal pages scattered into four non-adjacent frames; page 3 is only one-quarter full, the internal fragmentation.
Paging removes EXTERNAL fragmentation but creates a little INTERNAL fragmentation (the last partial page). It is a common mistake to think paging wastes no memory at all — on average about half a page per process is lost.