What is Paging in memory management?

Question

I was just reading Operating System Principles by Silberschatz et al when I came across paging in memory management.I'm slightly confused about it.
It states that Physical Memory(I assume it's RAM) is divided into frames, and logical memory is divided into pages. CPU generates logical addresses containing page number and an offset. This page number is used to retrieve the frame number from a page table which gives the base address
so the physical address is calculated as base+offset.
My question is:

is the page table maintained for every process?

I logically think that the answer would be yes as every process will need to map its own pages to frames. I may be wrong. Please clarify.

Also:

paging and segmentation(where 'holes' are created in memory) are two totally different techniques that are not used in combination. Correct?

Answer 1

Segmentation yields Linear Addresses, Paging yields Physical Addresses

Regarding logical and physical addresses, from Bovet & Cesati (Understanding the Linux Kernel), I've got this:

As you can see, paging and segmentation are carried out by separate units of the hardware. Although they may take place at the same time, the OS can disable the segmentation unit (so addresses are effectively treated not as logical but linear ones).

Generalities

You may already know this stuff, but I put it here anyway for completeness.

Pages occupy Frames: Swapping

As far as Silberschatz chapters 8,f is concerned, frames refer to the layout of the physical memory. The OS divides RAM into areas of equal and conveniently sized (e.g. 4K) frames. Pages are frame-sized pieces of data, the basic unit of page replacement.

There may be more pages than available frames. Some pages occupy frames, some pages are swapped out on disk.

If a page is swapped in from disk, it is aligned with a certain frame in memory (whichever the page replacement algorithm saw fit).

Operating Systems and the Hardware co-operate

As with many OS objectives, memory management always works in concert with the hardware: both the OS and hardware co-operate, to get the job done. How they do it in a realistic scenario depends on

1. the set of memory management primitives the hardware provides (paging, segmentation, and what the heck there exists), and
2. which subset thereof the OS really uses on the particular architecture and situation (Linux@zArchitecture is different from Linux@Intel is different from Windows@Intel is different from Window@Intel@Boot-up)

For example, only a few architectures provide segmentation and the figure above applies to x86. Linux, for portability reasons, does not very much exploit it. If I remember it correctly from Tanenbaum, OS/2 was the only operating system to exploit Intel's segmentation to its full extent.

So far this Answer.

Depending on why you need to know this, the following approach might help you (it has helped me).

I suggest you first get familiar with the hardware and the individual primitives. If Silberschatz is to vague on this point, try Tanenbaum (Modern Operating Systems) or Hennessy&Patterson (Computer Architechture, A Quantitative Approach). If your curiosity is not satisfied by then, see how a particular OS uses it in various situations on a particular platform.

Answer 2

is the page table maintained for every process?

If the system has to provide a secure virtual address space for each process, then yes.

paging and segmentation(where 'holes' are created in memory) are two totally different techniques that are not used in combination. Correct?

No, there is a virtual memory scheme called paged segmentation. (I recall this concept causing exasperation by my classmates when introduced by the prof. If Silberschatz et al didn't mention this, then that textbook is incomplete.) The original goal of paged virtual memory was to provide a large address space for executing a large program on a computer with limited RAM. In a simple paged virtual memory with multiprocessing, there would be no restriction on having two processes sharing one page. But a segmented virtual memory is intended for multiprocessing, and would isolate each process to its own segments.

While it may seem redundant, the typical virtual memory scheme used in a secure OS uses both pages and segments, where the segments are the processes' binary images. The typical HW will probably only support fixed-sized pages. The segmentation is implemented in the OS. The concept of segments facilitate management of multiple processes in memory. The concept of pages facilitates a minimal memory footprint by each process. A shared runtime library would be a special case of a write-protected, execute-only segment that was shareable among processes.

Be aware that "segment" in virtual memory schemes typically refer to a chunk of memory that is logically cohesive and has an arbitrary length. This type of "segment" should not be confused with the Intel 8086/88 (aka x86) "segment" that starts on a 16-byte address boundary (i.e. a "paragraph") and is restricted to 64 KB in size. X86 segments are a variation of memory banking rather than virtual memory.

Memory banking schemes are for systems that have a small address size (e.g. 16 bits) but larger physical memory space (e.g. up to 1 MB of adressable memory). Virtual memory is (or was intended for) for the opposite situation: the address size is large (e.g at least 32 bits) and the installed memory is less than the address space (not always true nowadays). Virtual memory is typically completely invisible to user programs, whereas the Intel 8086/88 programer must be aware of small/medium/large memory models and far versus near pointers. BTW that lecture where I first learned of virtual memory and "paged segmentation" occurred before Intel designed the i8086.

As supporting text, Wikipedia also mentions that segmentation and paging can be combined (in hardware).

Answer 3

At first, your definitions are correct.

For your first question, in Simple Paging, it's yes. Operating system maintains page table for each process and that brings one of the problems of simple paging. It uses a lot of RAM to keep these page tables.

Process table count is not limited which means 100 process brings 100 different process table, 1000 process brings 1000 different process table and for your information I assume there's enough available RAM, otherwise process won't work.

Also, process table length is not limited which means one of page tables can have 100 pages, other one can have 1000, another one can have 10 pages. Depends on process.

That's the result.

The second one is, they can be combined well but depends on the era which book is written in, they might say it's not.