Chapter 4: Memory management
IV.1 Introduction
Memory is an important resource that must be managed carefully. The memory manager must
- know the free and occupied parts of memory,
- allocate memory to processes that need it,
- recover the memory used by a process when it terminates
- and process of swapping between the disk and the main memory when the latter cannot contain all the processes.
Memory management systems fall into two categories:
- systems that move processes between main memory and disk (swapping),
- and those which do not and are simpler than the first.
IV-2 Memory management without swapping nor paging
IV-2-1 Mono-programming
The simplest memory management is to have a single process in memory at a given time and allow it to control all available space.
On MS-DOS microcomputers, memory was shared between the OS and a single user process.
- the OS could be located at the bottom of the RAM (a),
- or in ROM above RAM (b),
- you can also place the drivers in ROM at the top of the memory (BIOS) and the OS at the bottom of the RAM. As shown in the figure below.
IV-2-2 Multi-programming with fixed partitions
The memory is divided into n partitions (possibly of unequal sizes). This partitioning can be done by the operator at system startup.
Each new task is placed in the queue of the smallest partition that can hold it. Any unused space in a fixed partition is therefore lost. We then speak of internal fragmentation.
Sorting tasks according to their sizes in multiple queues (see the figure below) has a disadvantage when the queue of large partitions is empty and that of small partitions is full.
An alternative is to use a single queue. As soon as a partition becomes free, we place the first task in the queue that can fit there and execute it.
As it is not interesting to allocate a large partition to a small task, we can also browse the queue and choose the largest task that the partition can contain. This strategy puts small tasks at a disadvantage.
A first solution consists of keeping at least one small partition for the execution of small tasks. A second solution consists of prohibiting the non-selection of a ready task more than k times. Each time a task is not selected it gets a point. After k points it cannot be discarded again.
IV-3 Swapping
Organizing memory into fixed partitions is a simple method to implement for batch processing systems.
With time-sharing systems, the memory cannot contain the processes of all users. We need to place some processes on disk. These processes must be brought back to main memory before executing them. The movement of processes between main memory and disk is called swapping.
IV-3-1 Multiprogramming with variable partitions
Rather than dividing memory into a fixed set of partitions an OS can choose to place processes in any usable memory location.
The volume of allocated space corresponds exactly to the volume of space it needs, thus eliminating the problem of internal fragmentation.
We will partition the memory dynamically according to demand. Each program is allocated a partition exactly equal to its size[1]. When a program finishes its execution its partition will be recovered by the OS to be allocated to another program completely or partially depending on the request.
V-3-1-1 External fragmentation
If a proc process of size M and if any free partition of size Pi with Pi < M then the proc process cannot be loaded into any partition. Although the sum of free partitions is greater than the space requested by proc. This situation is known as the external fragmentation problem.
In a variable partition organization, the placement of processes in the partitions is done according to different strategies. Then the memory manager keeps track of occupied partitions and free partitions in tables dedicated to each of them.
IV-3-1-2 Placing strategies
First Fit strategy: in this strategy the table of free partitions is sorted in order of increasing addresses. To allocate a given partition we will start with the free partition with the lowest address and the search continues until we encounter the first partition whose size is at least equal to that of the waiting program.
Best Fit strategy: in this case the free partition table is sorted by increasing size. To allocate a given partition we will start with the free partition of the smallest size. The search continues until the first partition is found whose size is at least equal to that of the waiting program.
Worst Fit strategy: In this case, the largest partition is allocated to the process. We must traverse the entire table unless it is sorted.
Next Free Area Strategy (Next Fit): In the First Fit strategy, partitions at the beginning of the memory are more frequently taken into account. In the Next Fit strategy we tried to improve performance by distributing our searches more equitably across the entire memory space.
To do this, the search for the partition starts from the last allocated partition and not at the beginning of the memory.
Note: The simulations showed that first fit and best fit are better than worst fit in terms of time reduction as well as memory usage. Neither first fit nor best fit are significantly better in terms of memory usage but first fit is generally faster.
-------------------------------------------------------------------------------
[1] The memory space of a process can vary during its execution so we have 4 possible solutions: use neighboring free space, move it to a memory location likely to contain it move one process or more on the disk to create sufficient space if the back and forth is saturated kill it.