Swapping

If a process has a probability of p of being idle while waiting for I/O, then for N processes the probability that all are idle is p^N - which will never be zero.

This time is wasted, especially if other processes would be able to execute if there was room in memory for them to run.

A solution is ``swapping''. When a process is idle, the program itself and all data areas that it is using can be copied out to disk, freeing the main memory for use by other processes.

Choosing which processes to swap, etc belong to ``process management''. What we need now is to see the effect on memory management.

In order to swap processes to disk, there must be a swap area on the disk. This is usually of fixed size, and larger than RAM, so that it can hold many more non-running processes than fit into RAM.

For example, my Sun has 24M RAM, 64M swap. My Linux PC at home has 4M RAM, 16M swap.

This swap area will have free space as well as used space, and so must be managed just like RAM. It will have free and used lists, and some memory allocation scheme will be needed.

When a running process requests more RAM, it can be given it if there is some available, or non-running processes can be swapped out to disk to create this extra space. If there is no space on the disk, the memory request will probably fail. In this case, the user often has to reduce the number of processes using RAM and swap space before enough processes can be swapped out to allow this program to get enough RAM.

Windows uses swapping. In most uses it creates a temporary dynamically-sized swap file on startup and deletes it on exit (\windows\win386.swp). It can also use fixed size swap files or use a disk partition.

Overlays

A main part runs all the time. Overlay instructions cause the O/S to replace part of a program with another. The permanently running part calls procedures in the overlays, which return back to it after completion.

This requires the programmer to structure their program into separate modules, communicating only through the resident program. Once structured, the O/S can do the rest.

This method was once commonly used in MSDOS.

Segments

The 80x86 series offer hardware support for segments. Segments have a maximum size of 64k. An address is composed of two parts: a 16-bit segment address and a 16-bit offset address.

To find the actual address, the segment is shifted left by four bits and then the offset is added. The actual address is then a 20-bit address with a 1M address space.

Relocation is easy for addressing within a segment with this scheme, as the segment address just needs to be reset.

This leads to different ``memory models'' for the PC:

• tiny model. Program and data in one 64k segment.
• small model. Program in one, data in another.
• medium model. Program in many, data in one.
• compact model. Program in one, data in many.
• large model. Program in many, data in many.

Virtual addressing

The program then just uses these virtual addresses, and the hardware and the O/S between them worry about the physical addresses.

This makes it easy as far as an application is concerned, because it does not have to worry about how much physical memory is available, about swapping or about relocation problems.

Paging

When loading a program any page of the program can be placed in any unused page frame. This requires a page table to keep track of the mapping between pages and page frames.

This shows that page 0 (logical/virtual) maps into page frame 3 (physical), page 2 (logical) maps into page frame 0 (physical). Page 1 (logical) has no mapping into a physical address.

If the page size is 1k, this can also be written

• LA 0k-1k -> PA 3k-4k
• LA 1k-2k -> ?
• LA 2k-3k -> PA 0k-1k
• LA 3k-4k -> PA 1k-2k

There is one page table per process - the pages belong to each individual process. The page frames are the real memory.

This mapping must be performed by hardware, and must be fast because it affects every memory reference.

The way this is done depends on the hardware. For example, there may be a page table register holding the base of the table as a table in RAM, and this gets set for each process.

The hardware has to translate addresses. The other thing it has to do is to generate a page fault interrupt when there is no entry for the logical address.

The O/S has to trap that interrupt and take appropriate action. The actions are twofold: remove a page from memory if neccessary, and load the missing page into memory.

Page removal

Which is the best frame to remove? The one that will not ever be used again, or failing that the one that will not be used for the longest time. Requires clairvoyance.

Least recently used

This is because of sequential code and loops, which tend to re-execute the same or close bits of program code.

So remove something that has not been used for the longest time, hoping that it will not be needed soon.

This requires that a list be kept of usage of each page, in order of last use. Whenever a memory reference occurs, this list must be updated, moving pages around to keep the list up to date.

This makes this system prohibitively expensive in general.

Not recently used

If a page should be removed, one with the bit unset is a good candidate.

To ensure that there are pages with bits unset, on a periodic basis all pages have their used bit set to zero.

FIFO (first in first out)

Removal to where?

Supervisor mode

Page loading

In demand paging pages are only loaded from the original files when needed. So the answer is: not if demand page loading is used. Otherwise, all pages possibly required would have to be loaded into either memory or swap when the program is first started.

Shared pages

Pages can be shared if they have readable data only - if the data can be changed then separate copies are needed. A compiler may divide the data areas into read-only that can be shared, and writeable that cannot.

This technique is also extended to dynamic linking of libraries. Libraries are strong candidates for shared pages across different programs. They are also in every compiled program.

Both to save disk space and to allow easier indentification of sharing, these are often not linked in until load time.

Unix Memory

• text - relocatable program code (fixed size)
• data - fixed data such as static variables, strings (fixed size)
• stack - user stack (grows downwards)
• bss - unitialised data for the heap (grows upwards)

Windows NT Memory

It uses a virtual memory system of 4Gbytes for each process. Of this, 2Gb is reserved for use by the O/S, and the remaining 2Gb for the process (and its threads). The process cannot access the O/S space except by switching to a different protection ring.

The O/S kernel is based on the micro-kernel Mach system (see later).

Each MSDOS application runs as a single thread in a 16M virtual address space. This is organised so that MSDOS occupies the lowest portion, sharing the bottom 640k with an MSDOS application. The device drivers are above the 16M boundary. Each MSDOS application looks like

The entire set of Windows 3.1 applications all run within one of these MSDOS virtual spaces. Each runs as a separate Windows NT thread.

A set of applications will look like

The process scheduler for Windows NT is pre-emptive, so no thread can hog the system. The scheduler is a priority scheduler. However, Windows 3.1 threads are scheduled cooperatively amongst themselves.

Windows 95 Memory

The primary difference between the memory models is the protection given to the system space within each processes address space. In Windows NT this can only be accessed by switching to supervisor mode. In Windows 95 this can be accessed by a simple function call without a switch. This is for speed. The space is actually occupied by system device drivers, Windows DLLs, and shared objects including nonsystem DLLs. So a Windows 95 application can still trash quite a lot of important stuff.

Layered model

Client Server Model

C Coding Standard

Preamble

This is from xmfm:

Function declaration

This is from xmfm:

Inline comments

Indentation

Consistency