Storage Management (Memory)
In Chapter 2, we mentioned the physical memory, namely. DRAM, Video RAM and also cache memory. We also touched the virtual memory system and its operation. In this chapter, we will look at detailed memory strategies including Fetch (when to obtain page from disk), Place (where to place) and Replace (which page to disk). We also discussed virtual and non-virtual memory system. Upon completion of this module, you should understand
|Different memory strategy|
|Different placement scheme|
Storage (Memory) management determines how a storage organization should perform under different policies. The following questions are usually raised to determine the memory strategy.
|When do we get a new program to place in memory?|
|Where in the main memory do we place the next program to be run?|
|If the main memory is full, which program do we displace?|
If we can answer the above questions properly, we have already come up a well-defined memory management scheme.
The types of storage in a computer system include:
|Main memory, e.g. RAM, ROM|
|Secondary memory, e.g. Disk, Tape, Drum and CD-ROM|
The characteristics are:
|Programs to be executed must reside in the main memory (real or physical memory)|
|Secondary storage is less costly than main storage and have much greater capacity and is used to store the programme (Laser disk has capacity up to 600M)|
|Main memory may be accessed much faster than secondary storage.|
|Cache memory is a high-speed storage which is much faster than the main memory and is relatively expensive than main memory.|
|frequently used programs is recommended reside in cache memory to speed up operation as this will increase performance.|
In order to satisfy the above criteria, a manager of the storage (in Windows 95/98, it is called virtual memory manager) under the operating system must:
|Keep track of the status of all parts of allocable main store - either be free or allocated|
|Allocate portions of free store to a requesting process according to some store management policy|
|Ensure that the addresses generated by the process are routed to its own areas of store, and cannot be routed to another processs areas of store|
|Reclaim store areas from processes - either by preemptions, or when the process indicates that it has no further use for a store area, or when the process terminates|
It is concluded that the memory management strategies are defined to obtain the best possible use of the main memory for the following three operations:
|WHEN to obtain the next program|
a) Demand - Referenced by a running program
b) Anticipatory - as Anticipated
|WHERE in the main memory to place the program|
|WHICH program is to be displaced to make room for incoming programs|
Figure shows the three operations. Here, the main memory is partitioned into two blocks for operating system and user. A process is making a request from the disk to decide the placement.
Memory Management Schemes
This section discusses many allocation schemes that are broadly classified as virtual and non-virtual.
A set of schemes going from simple to complex will be presented. Each successive scheme attempts to achieve increase in throughput performance. The memory management schemes include:
|Single contiguous allocation|
|Fixed partitioning allocation|
|Variable partitioning allocation|
These schemes can be further divided into two main groups, namely, Nonvirtual Strategy and Virtual Strategy.
|It is termed what you see is what you get. For instance, DOS 6.2 is a non-virtual operating system. If your programme is greater than the conventional memory size, the operating system cannot execute it. @LIST = The computer organization restricts number of accessible memory locations e.g. 16-bit program counter = 216 = 65536|
|If the actual memory capacity installed is less than the maximum, then the program is limited by this capacity|
|Based on the above classification, it is a typical example of|
|Single contiguous allocation;|
|Fixed partitioning allocation; or|
|Variable partitioning allocation.|
It is termed what you want is what you get. For instance, Windows 3.1/Windows 95/98, Windows NT, Unix, VAX/VMS are non-virtual operating systems. If your programme is greater than the conventional memory size, the operating system still can execute it.
|This strategy emulates the maximum main storage capacity on computer systems where the actual capacity is much less.|
|Based on the above classification, it is a typical example of|
|Segmented allocation; or|
Single Contiguous Allocation
As shown in Figure , there is a memory block consisting of operating system and a single block (continuous) for user. The allocation for this is most advantageous in two ways:
|Program execution is simple the CPU does not have to modify the programmers memory references in order to find the correct memory location.|
|Protection of the OS is simple Any memory references beyond a certain threshold value imply possible destruction of OS|
The characteristics for single contiguous allocation are:
|one process (and its children) are given access to the whole of main store|
|main store contains the OS and the application codes|
|any part of the storage area not required by the process is unused (wasted)|
Advantages and Disadvantages
The advantages are:
|often found in small computer|
The disadvantage is under utilization of store and processor.
When an application is too large to be fitted in the memory, it must be overlayed. That is to say, it must load the programme piece by piece on internal programme call basis. The characteristics are:
|The application program must be structured into resident and non-resident sections.|
|Non-resident sections displace each other during program execution.|
|This method is time-consuming, complex, and makes program maintenance difficult.|
|It is not needed in Virtual Storage operating system.|
For a 10K main procedure A with following sub-procedures from B to G with programme size. Procedure A will call Procedure B, C and D. Procedure B will call E and F while Procedure C will call F and G.
What is the overlay structure? What is the minimum amount of memory required to run the program? Draw a block diagram for Overlay structure.
The overlay structure is shown in Figure . Based on this diagram, the minimum amount of storage is summation of Procedure A, B and E, which is equal to 28K.
Fixed Partitioning Allocation
It is also known as Fixed Partition Multiprogramming, or Multiprogramming with Fixed Number of Tasks. The characteristics are as follows:
|Main storage is divided into a number of fixed-size blocks, each of which may be of different size, in order to permit multiprogramming as shown in Figure . Here, it consists of three fixed memory blocks, namely, block 1, block 2 and block 3.|
|Each partition holds a single job, and the CPU switches rapidly between users to create the illusion of simultaneity.|
|Jobs are translated with absolute assemblers and compilers to run in specific partition.|
|If a partition is occupied, the job has to wait even if other partitions are free.|
|Two boundary registers for every partition permit operating system and interprocess protection.|
Advantages and disadvantages
The advantages are as follows:
|It avoids wastage of CPU idle time|
|Operating system is easy to implement|
The disadvantages are as follows:
|degree of multiprogramming is fixed|
|only 1 job per partition|
|waste of main storage|
|some partitions not used|
It causes internal fragmentation, which means that processes do not consume all the allocated storage has unused holes and fragments. Figure shows the internal fragmentation. Here, operating system allocates more storage block to P2, which is more than P2 needs. This leaves holes between P2 and P3.
Variable Partitioning Allocation
It is also known as Multiprogramming with Variable Number of Tasks, or Variable Partition Multiprogramming.
|Since Fixed Partitioning is too limited, the concept of Variable Size Partition is implemented.|
|Processes are allocated with memory as much as they required, provided that there is enough free memory available as shown in Figure . Here, the allocation of storage block is not fixed.|
|A relativity mechanism is used to make the program independent from its physical core memory location using Base-and-Limit Registers.|
|When a process is loaded, the physical address at which the processs store area begins is stored in the BASE Register.|
|a Limit Register stores the Base Register value + the length of the processs store area|
|There is no Internal fragmentation. However, it now has external fragmentation as shown in Figure . Here, the summation of holes is sufficient for a new process.|
|Fragmentation in Variable Partitioning is severe since completed processes leave holes|
|Garbage collection (Compaction) or Coalescing of free space necessary|
|To reduce external fragmentation is to perform Compaction as shown in Figure . Here, the hole after compaction is sufficient for a new process P4. It is achieved by|
|moving all occupied area to one end or the other of main storage leaving free storage as a single, large hole. However, there is a problem, which,|
|it will consume large amount of system resources.|
|maintain a free storage list|
|merge adjacent holes together to form a single large hole|
Storage Placement Strategies
It is about where to put programs and data in the main memory and consists of three strategies, namely, best-fit, first-fit and worst-fit.
|Place job in the smallest possible hole in which it will fit|
|Leave larger holes for larger segments|
|Use a linked list arranged in increasing order of size|
|it needs to search through the linked list of memory blocks|
|it is time consuming as it needs to go through the checking|
|will be left with many tiny holes as each size is not perfectly matched.|
|Place job in the first storage hole on free storage list in which it will fit|
|Observed to be as good as Best-fit|
|Linked list in increasing order of initial address of each hole|
|The placement decision can be made quickly|
|It can easily detect if two holes are adjacent to each other by using the following:|
if address+size = address stored in next node = adjacent holes
|Place jobs in the largest hole in which it will find|
|After placing the program in the largest hole, the remaining hole may still be large enough to hold another program.|
|Partitioning is undesirable in many respects|
Why let the physical capacity of the main memory limits the process?
The process will execute out of the predefined boundaries, which might corrupt the other processes.
|The organization, or architecture, of the CPU determines the upper limit of the addressable memory.|
|Memory allocation is contiguous|
Why not allocate memory for a process in pieces (Non-contiguous)?
Firstly, there is an overhead to keep track the free storage. Secondly, to arrange the memory like this is equivalent to a virtual system.
This chapter covered the memory storage strategies, namely, virtual and non-virtual. Non-virtual storage including single contiguous allocation, fixed partitioning allocation and variable partitioning allocation was discussed with example. External fragmentation and internal fragmentation leading to low utilisation of storage were also discussed. The commonly used three placement strategies, namely, best-fit, worst-fit and first-fit were included for comparison. There is no conclusion which placement strategy is the best as there are advantages and disadvantages for each of them. Virtual storage strategy will be covered in later chapter.
|A program is made up of a main program A with size 30K bytes and the following procedures:|
Size (K Bytes)
Size (K Bytes)
The program is written such that Main Program A will call procedures B, C, and D. Procedure B in turn calls E, F, H, and G, procedure C may call H,and E, and procedure D may call H, F, I and G. Draw a tree type structure and determine the minimum amount of memory required to run the program using Overlay Structure. If the whole program is loaded into the memory, what will be the minimum memory required? (Past examination question)
|Select the CORRECT statement(s) about storage strategy.|
Non-virtual storage refers to what you want is what you get.
Fixed partitioning allocation refers to virtual storage.
Page allocation is classified as a virtual system.
|Select the CORRECT statement(s) about storage placement strategies.|
The Best-Fit strategy places a job in the largest possible hole in which it will fit.
The advantage of First-Fit is that the placement decision can be made quickly.
The characteristic of Worst-Fit is that memory allocation is contiguous.
|There are three memory blocks, namely, B1, B2 and B3, each of which in size is 200K, 100K and 150K. Two processes each of which requires 50K and 70K respectively. After executing these processes, list the remaining memory size for each block using first-fit, best-bit and worst-fit respectively.|