CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 2 of 7 · 3 min read

Frame allocation

Think of it this way. A school with 100 desks must seat several classes. Each class needs a few desks to work at all, and beyond that the school must decide who gets more. The analogy stops in one place: a class stays the same size, while the need of a process changes from minute to minute.

In plain words: Two limits come first. At the top, a process cannot use more frames than it has pages. At the bottom, each process needs a minimum number of frames. An instruction can touch several pages at once, such as the page of the instruction, the page of a source operand and the page of a destination. If fewer frames than that are available, the instruction can never finish, because a fault on one page removes another page that the same instruction needs. The minimum depends on the processor, and it is small.

Between the limits there are two simple policies, shown for 100 frames and three processes of 20, 80 and 300 pages (made up to show the idea):

Policy Rule Frames for the three processes
Equal allocation Each process gets the same share 33, 33, 33 (one frame left over)
Proportional allocation The share follows the size of the process 5, 20, 75

For proportional allocation, each process gets 100 × (its pages) / 400. So 100 × 20 / 400 = 5, 100 × 80 / 400 = 20, and 100 × 300 / 400 = 75. Equal allocation wastes frames on the small process, which has only 20 pages, and starves the big one. Proportional allocation follows the size, although a big process may not need all its pages at once. Some systems also add a priority, so that an important process gets more.

A second question is where a victim may come from when a process faults. In local replacement, the victim must be one of the pages of the faulting process, so each process keeps its own set of frames. In global replacement, the victim may be any page in memory, including a page of another process. Global replacement uses frames well, since a process that needs more can take them from one that needs less. Its weakness is that the fault rate of a process now depends on the others: a process that touches a lot of memory can take frames from its neighbours and slow them down. Most general-purpose systems, Linux included, use global replacement.

Global replacement

Global replacement is a page replacement policy in which the victim is chosen from all the frames in memory, so a process can take a frame from another process, while in local replacement the victim must come from the faulting process.

Example: if process A faults and the oldest page in memory belongs to process B, global replacement removes B's page, and local replacement does not.

Check yourself: 1. Why does a process need at least a few frames? 2. Find the proportional shares for 60 frames and processes of 10 and 50 pages. 3. What is the main risk of global replacement?