operating systems - Swaping, Paging, Segmentation, and Virtual memory on x86 PM architecture

Well, this may seem a common or already asked question but after searching various books, online tutorials and even here on SU, I am still puzzled at how these four beasts work together on a x86 protected mode system.

What is the correct terminology that can be used when discussing about these things?

As far as I understand, all these 4 concepts are completely different, but got related when we talk about protecting memory. This is where it got messed up for me!

I' ll begin with swapping first.

Swaping:

A process must be in physical memory for execution. A process can be swapped temporarily out of physical memory to a backing store and then brought back into memory for continued execution.

This applies specifically to multitasking environments where multiple processes are to be executed at the same time, and hence a cpu scheduler is implemented to decide which process to swap to the backing store.

Paging: aka simple paging:

Suppose a process have all addresses that it use/access in the range 0 to 16MB, say. We can call it the logical address space of the process, as the addresses are generated by the process.

Note that by this definiton, logical address space of a process can be different from that of another process, as the process may be larger or smaller.

Now we divide this logical address space of a process into blocks of same size called pages. Also divide physical memory into fixed-size blocks called frames.

By def. logical address = page# : offset in that page

When a process is chosen to be executed by the cpu scheduler, its pages are loaded from backing store into any available memory frames.

Note that all of the pages that belong to this process are loaded in memory, before control is transfered to this process from scheduler. When this process is to be swapped to backing store, all of its pages are stored on the backing store.

The backing store is divided into fixed size blocks that are of same size as physical memory frames.

This eases the swapping process, as we swap a page and not bytes. This decreases the fragmentation on backing store, as we need not find space for some bytes, instead we look whether the space is available for a page or not.

The paging technique also decreases the fragmentation of physical memory, as we keep a page in memory.

The main memory must have space for all of the pages that belong to a process in order to load that process in memory for execution. If there is space only for a few pages of this process then some other process(ie all pages belonging to process) must be swapped to backing store and then only all pages of the process to be executed, must be loaded in memory.

Thus paging technique gives better performance than simple swapping.

Thus swapping allows us to run multiple processes w/o purchasing too much memory, instead we can work with small amount of memory(this amount must be such that all of the pages of the largest program/process that is to be run on a PC can be loaded in memory - ie you must know how much memory your program requires before running it.) plus an additional backing store usually disk, which has very less cost for much larger capacity that main memory.

So swapping + paging allows efficient management of memory so that multiple processes can be run on a system.

Demand-paging:

But the physical memory installed in a system need not be same as the requirement of the process. Also multiple processes need to be run.

The solution is to load only some pages of a process into memory, and when the process accesses an address in a page that is not in memory then a page fault is generated and the OS loads that page on demand so that the process can continue executing. This save the time to loadd all pages of that process before transferring control to it - as was case in paging + swapping.

This technique of keeping only parts of a process in memory, and rest on backing store, such as disk, is called demand paging.

Thus demand-paging = paging + swapping + only keep some pages(not all) of a process in memory.

---

This is all about paging and swapping that I know. Please feel to correct me I am wrong in some place above.

Now my questions are:

1. 
   

   how exactly virtual memory and virtual address space(aka linear address space) terms are related to demand-paging in the context of x86 protected mode.

   
   


2. 
   

   Is "virtual memory of a process" is a correct term or virtual memory is defined for all processes currently running in a multitasking system ?

   
   


3. 
   

   Am I right in : virtual memory available to a process == highest address in the Virtual address space(aka Linear address space) of a process + 1 ?

   
   


4. 
   

   This is about segmentation: In a x86 protected mode, we are told that each process can have a 4GB virtual address space(VAS), this means that since segmentation is present on the x86 architecture, we can divide this VAS into two or more segments. In x86 Flat model, we create segments in the VAS of a process s.t they all overlap exactly, so effectively segmentation is disabled - there are no segments. But then if say at a virtual address in the VAS of some process, some cpu instructions are present, then it is possible that we overwrite these instructions while allocating memory(in this VAS) or when we create variables or arrays. How do we ensure that this does not occur. The protection bits in descriptor does not distinguish b/w the regions as in flat mode all segments overlap. These bit can only prevent reading code or executing data, and that too only becoz the segments are accessed via selectors.

   
   


5. 
   

   or, is it something like each segment is treated as its own VAS. But in that case the total virtual memory(or total VAS) available to a process in a flat mode, would then be : " no. of segments belonging to a process x virtual memory for a single segment ". For a x86 protected mode, this would translate to 6 x 4GB = 24GB of VAS ! assuming 6 segments pointed by CS, DS, ES, GS, FS, SS registers. Is this correct ?

   
   


6. 
   

   How does a environment that support simple paging(not demand-paging) but not virtual memory, will ensure protection b/w various segments in flat memory model? We have two cases here - a single tasking system and a multi-tasking system.

   
   

UPDATE: on 2012-07-29

So if I understand it correctly:

Virtual memory is a concept and it is implemented on x86 architecture by using demand-paging technique + some protection bits(U bit and W bit specifically).

IOWs, the VAS of a process is divided into pages, which are then used in demand-paging.

Virtual memory mechanism has basically two uses in a multi-tasking environemnt:

1. 
   

   Size of the program may exceed the amount of physical memory available for it. The operating system keeps those parts of the program currently in use in main memory, and the rest on the disk. This is implemented by demand-paging with each page having an associated 'present bit' and 'accessed bit' in its page table entry.

   
   


2. 
   

   To provide memory protection by giving each process its own virtual address space, so one process can't access other process's VAS. This is implemented by having some protection bits associated with each page. Specifically, 'User/Supervisor bit - U bit', read/write bit W bit' in the page table entry are used for page access protection.

   
   

Virtual memory is useful in both single-tasking system and multi-tasking system. For single-tasking systems, only Use#1 is relevant.

Page access protection has 2 aspects: privledge level protection and write protection. These are implemented by U bit(for prviledge) and W bit(for write) respectively. These bits are present in page table entry for that page.

Memory protection has 2 aspects: protecting programs from accessing each other and protecting programs from overwriting itself, in case segments overlap in VAS of that process/program.

Now former problem is solved by VAS or virtual memory concept, but what about latter ?

The page access protection scheme doesn't prevent the latter as far as I know. IOWs, virtual memory technique doesn't prevent the progams from overwriting itself, in case segments overlap in VAS of a process.

But it seems to me that even segment-level protection can't prevent the latter (overwriting itself) issue of memory protection.

x86 cpu always evaluates segment-level protection before performing the page-level protection check - no matter whether it is flat or multi-segment model - as there is no way to disable segmentation on x86 cpu.

Consider a flat model scenario:

Consider a virtual address referred to by CS:off. Now the DS:off will also refer to the same virtual address as referred by CS:off, if 'off' value is exactly same in both cases. This is true for SS:off also.

This also means that the page in which this virtual/linear address lies, is viewed by paging unit as simply a page as it doesn't know about segmentation.

Assume all segments of a program, in flat mode belong to same privilege level, say ring0.

Now what will happen if we try to write or execute data at CS:off = DS:off = SS:off.

Assume that this address does not belong to the OS code mapped in VAS of process - please just keep aside OS for simplicity, I'm talking about hardware-level protection!

First, segment-level protection will be passed, then the privilege level checks will be passed while accessing this page(the page containing CS:off or DS:off or SS:off) as all segments belong to same privilege here, but what about W bit for this page. This should be set to 1 to allow writes, otherwise say a data segment will not be able to do writes at his page. So this means that this page is writable too.

This means that we can read/write/execute the data at this virtual(linear) address: CS:off = DS:off = SS:off.?

I don't understand that how x86 hardware can provide protection on this issue in case segments overlap.