CITS2002 Systems Programming
1 next ¡ú CITS2002 CITS2002 schedule
Allocating primary memory to processes
The important task of allocating memory to processes, and efficiently ensuring that processes have their instructions and data in main memory when needed, is termed memory management.
We’ll need to consider the role that memory plays from two (conflicting?) perspectives:
the operating system’s perspective of how to allocate and manage all memory fairly and
efficiently, and
the process’s perspective of how to access the memory allocated to it, and how to
obtain more.
An important goal of the operating system is to keep as many processes executable as possible, and it will achieve this only when processes have available the memory they require.
Processes requiring specific memory (holding either instructions or data) cannot execute, and are blocked until that memory is available (to them).
For simplicity, we’ll initially assume that a process’s image occupies a contiguous region of main memory.
CITS2002 Systems Programming, Lecture 11, p1, 30th August 2021.
CITS2002 Systems Programming
¡ûprev 2 next¡ú CITS2002 CITS2002schedule
Requirements of Memory Management
Logical Organisation:
Although processes in memory often occupy linear sequences of addresses, programs are seldom written this way.
Structured programming and, more recently, object-oriented techniques, encourage/enforce programming using modules which are developed and compiled independently.
Ideally, all references from one module to another are resolved at run-time, maintaining their independence (termed late binding).
Physical Organisation:
The relationship between primary memory (RAM) and secondary memory (disk) is straightforward, but not one that programmers wish to manage. Old techniques termed overlays permitted reuse of a process’s memory, but (today) are unnecessarily complex.
Moreover, in a multi-programmed system, the programmer cannot predict the size nor location of a process’s memory. The task of moving information between main and secondary memory is clearly the responsibility of the operating system.
CITS2002 Systems Programming, Lecture 11, p2, 30th August 2021.
CITS2002 Systems Programming
¡ûprev 3 next¡ú CITS2002 CITS2002schedule
Requirements of Memory Management, continued Sharing:
Even with protection, there is also a need to allow processes to share memory. For example, multiple processes running the same program can share the (read+execute only) instructions for the program, and co-operating processes may wish to share and communicate via memory containing data structures.
Relocation:
In a multi-programming system, the execution of a single process is often unrelated to others. When a process is first created, it is difficult (if not impossible) to know where its image will be placed when initially loaded into memory.
Similarly, when a process is swapped-out (Suspended), it is unlikely that the process will be swapped-in back to exactly the same memory location.
Memory management determines where both instructions and data are located, i.e. how a process’s memory references (requests) translate into actual physical memory addresses.
Protection:
Each process must be protected from either accidental or deliberate “interference” from other processes. Although compilers for high-level programming languages offer some support (e.g. constrained control flow, static array bound references), most data references are dynamic (array access and pointer following).
Memory references made by a process must be checked (at run-time) to ensure that they lie within the bounds of memory allocated by the operating system.
Checks are performed by hardware at run-time, and invalid references generate an access violation interrupt, trap, or exception, for the operating system software to handle.
The memory protection must be performed by the processor (hardware) rather than the operating system (software), because the operating system cannot anticipate all the memory references that a program will make. Even if this were possible, it would be prohibitively time-consuming to screen each program in advance for possible memory violations.
CITS2002 Systems Programming, Lecture 11, p3, 30th August 2021.
CITS2002 Systems Programming
¡ûprev 4 next¡ú CITS2002 CITS2002schedule
Initial Memory Allocation Using Partitioning
In modern operating systems offering memory management, the operating system itself occupies a (fixed?) portion of main memory. The remainder is available for multiple user/application processes.
The simplest technique is to consider main memory being in fixed-sized partitions, with two clear choices:
equal sized partitions, or
unequal sized partitions.
Any new process whose size is less than or equal to a partition’s size may be loaded into that partition.
Example of Fixed Partitioning of a 64-Mbyte Memory
CITS2002 Systems Programming, Lecture 11, p4, 30th August 2021.
CITS2002 Systems Programming
¡ûprev 5 next¡ú CITS2002 CITS2002schedule
Initial Memory Allocation Using Partitioning, continued Equal sized partitions introduce two
1. a process’s requirements may exceed the partition size, and
2. a small process still occupies a full partition. Such wastage of memory is termed internal memory fragmentation.
The initial choice of partition – the placement algorithm – is, of course, trivial with equal-sized partitions.
Unequal sized partitions offer obvious advantages with respect to these problems, but they complicate the placement algorithm. Either:
1. a process is placed in the largest (large-enough) partition, to minimise internal memory fragmentation, or
2. a process is placed in the smallest (large-enough) available partition.
The initial placement algorithm is again simple, but also introduces excessive internal memory fragmentation.
Example of Fixed Partitioning of a 64-Mbyte Memory
CITS2002 Systems Programming, Lecture 11, p5, 30th August 2021.
CITS2002 Systems Programming
¡ûprev 6 next¡ú CITS2002 CITS2002schedule
Dynamic Memory Partitioning
Dynamic partitioning overcomes some shortcomings of fixed partitioning: partitions are of variable length and number.
When a process commences, it occupies a partition of exactly the required size, and no more.
The Effect of Dynamic Partitioning
As the above figure shows, dynamic partitioning introduces the problem of external memory fragmentation, where there is insufficient contiguous free memory to hold a new process,even though sufficient free memory exists in the system.
CITS2002 Systems Programming, Lecture 11, p6, 30th August 2021.
CITS2002 Systems Programming
¡ûprev 7 next¡ú CITS2002 CITS2002schedule
Dynamic Partitioning Placement Algorithms
One obvious question suggested by dynamic partitioning is “Where do we place a new process” Three simple algorithms exist:
Memory Configuration Before and After Allocation of 16 Mbyte Block
First-fit:
find the first unused block of memory that can contain the process, searching from Address 0,
find the smallest unused block that can contain the process, or
remember where the last process’s memory was allocated (say Address k), and find the first unused block that can contain the process, searching from Address k.
CITS2002 Systems Programming, Lecture 11, p7, 30th August 2021.
CITS2002 Systems Programming
¡ûprev 8 next¡ú CITS2002 CITS2002schedule
The Need for Address Relocation
Simple memory management schemes share one significant assumption: that, when a process is swapped-out, it will always be swapped back into memory, having access to the same memory locations as before.
This assumption actually complicates the memory management task, and contributes to memory fragmentation.
We need to define three terms:
A logical address
is a reference to a memory location independent of any current assignment of data to main memory.
A relative address
is a logical address expressed relative to a fixed (logical) location, such as the beginning of the process’s image.
A physical address, or absolute address
is an actual location in main (physical) memory.
We’ve previously (implicitly) assumed that when a process is initially loaded (from disk), its relative addresses are replaced by absolute addresses.
More realistically, we enable processes to be swapped-in to any feasible range of physical memory: and this location is unlikely to be the same as before.
CITS2002 Systems Programming, Lecture 11, p8, 30th August 2021.
CITS2002 Systems Programming
¡ûprev 9 next¡ú CITS2002 CITS2002schedule
Hardware Address Translation
If a process may be swapped-in (back) to a different range of physical addresses, we need to update its relative addressing. We could have software modify all addresses found (slow), or have hardware translate all addresses, on-the-fly, as/if they are required.
While a process is executing, we employ a hardware base register to indicate the beginning of the process’s partition, and a hardware bounds register to indicate the partition’s extent.
Hardware Support for Relocation
Each process requires a pair of (hardware) base and bound registers, and the pair must be saved and restored as each process is swapped-out, and later swapped back in.
CITS2002 Systems Programming, Lecture 11, p9, 30th August 2021.
CITS2002 Systems Programming
¡ûprev 10 next¡ú CITS2002 CITS2002schedule
Simple Paging of Memory
We have just seen that fixed-sized partitions introduce internal fragmentation, and variable- sized partitions introduce external fragmentation.
However, internal fragmentation is bounded by the maximum size of a partition, and so if we allocate to a process several small fixed-sized fragments, we’ll see minimal internal fragmentation only within the last fragment, and no external fragmentation.
Assignment of Process Pages to Free Page Frames
We term the small, equal-sized ‘chunks’ of a process’s image pages, and place them in equal- sized ‘chunks’ of main memory, variously termed frames, or page frames.
We can now also remove the restriction (the assumption) that a process’s sections of memory must be contiguous. Clearly a single base register is insufficient – we need a large number of base registers, one for each page, to identify the starting address of that page. (We do not need multiple bounds registers; Why not?)
Data Structures for the previous figure at Time Epoch (f)
CITS2002 Systems Programming, Lecture 11, p10, 30th August 2021.
CITS2002 Systems Programming
¡û prev 11 CITS2002 CITS2002 schedule
Page Registers and Page Tables
So, the operating system now maintains a set of page registers, or a page table. The page table holds the (physical, absolute) frame location for each page of the Running process. Within each process, a logical address now consists of a page number and an offset within that page’s frame.
In the following figure, 6 bits from each 16-bit logical address indicate which page table entry to use. The remaining 10 bits of the logical address are appended to the contents of the page table entry to provide the actual physical address.
Logical-to-Physical Address Translation using Paging
The Logical-to-Physical mapping can still be performed in hardware, provided that hardware knows how to access the page table of the current process.
CITS2002 Systems Programming, Lecture 11, p11, 30th August 2021.