MEMORY MANAGEMENT

In a multiprogramming system, in order to share the processor, a number of processes must be kept in memory. Memory management is achieved through memory management algorithms. Each memory management algorithm requires its own hardware support. In this chapter, we shall see the fixed partitioning, paging and segmentation methods.

In order to be able to load programs at anywhere in memory: the compiler must generate relocatable object code. Also we must make it sure that a program in memory, addresses only its own area, and no other programs area. Therefore, some protection mechanism is also needed.. 

1. Fixed Partitioning

Using fixed partitions in IBM's Multiprogramming with a Fixed Number of Tasks (MFT):

Memory is divided into partitions whose sizes are fixed.

 Processes are classified on entry to the system according to the memory they require. We need one PQ (process queue) for each class of process. If a process is selected to be allocated memory, then it goes into memory and competes for the CPU.

The number of fixed partitions gives the degree of multiprogramming (for the above example it is 3).

Each queue has its own memory region, so there is no competition between the queues for memory. For the following case:

Shall we keep the 12K region sit idle?. Or, do we use it for a smaller process? (say p4). If we keep it sit idle, this is called a best-fit-only policy. If we use it for a smaller process, this is called a best-available-fit policy.

a. Fixed partitioning with swapping 

Use RRS with some time quantum. When time quantum for a process expires, it is swapped out of memory to disk and the next process in the corresponding process queue is swapped in to the memory.

Normally a process which is swapped out will eventually be swapped back in to the same partition. If we are using static relocation, this is a must! With dynamic relocation this restriction can be relaxed.

In some systems a process executing in memory may request more memory. Say we have a 6K process running in a 6K partition. If it requires 1 more K of memory:

                 a)  Return control to the user program. Let the program decide either to quit or modify its operation so that it                     can  run (possibly slowly) in less space.

                 b) Abort the process. (the user states the maximum amount of memory that the process will need, so it is his/her                   responsibility to stick to that limit.)

                 c) If dynamic relocation is being used, swap the process out to the next largest process queue. When it is to be                   swapped in to the 12K region, relocate it as necessary and go on.

The main problem with the fixed partitioning method is how to determine the no. of partitions, and how to determine the size of each partition.

Another important problem is the memory fragmentation problem. Memory fragmentation can be external or internal. Assume a process needs k words. Then, it may be run in a partition of m words where K £ m. If k = m, then (m-k) is internal fragmentation.

On the other hand, if one partition is currently not being used at all, then this is external fragmentation.

Now, although there is enough total free space in memory, we can not run the new process, because the free space is fragmented. 

2. Variable Partitioning

With fixed partitions we have the important problem of determining the number and sizes of partitions to minimize internal and external fragmentation. If we use variable partitions instead, then partition sizes may vary dynamically.

In the variable partitioning method, we keep a table indicating used/free areas in memory. Initially, the whole memory is free and it is considered as one large block. When a new process arrives, we search for a block of free memory, large enough for that process. We keep the rest available (free) for future requests. If a block is freed we try to merge it with its neighbors if they are also free.

There are three algorithms for searching the list of free blocks for a specific amount of memory.

A. FIRST FIT:

Allocate the first free block that is large enough for the new process. This is a fast algorithm.

B. BEST FIT:

Allocate the smallest block among those that are large enough for the new process. We have to search the entire list, or we can keep it sorted and stop when we hit an entry which has a size larger than the size of new process. This algorithm produces the smallest left over block.

C. WORST-FIT:

Allocate the largest block among those that are large enough for the new process. Again we have to search the entire list. This algorithm produces the largest leftover block.

a. First-fit: allocates from the 10K block.

b. Best -fit: allocates from the 4K block.

c. Worst-fit: allocates from the 16K block.

Now if a 16K process arrives with worst-fit it will have to wait.

As an exercise, find out what will be the resulting memory map internal, external fragmentation values if the following processes arrive in order (and no previous process leaves the system) (10K, 9K, 1K, 5K) [ Do it for FF, BF, WF].

Simulation studies by Knuth showed that worst fit is the worst and in some cases, first-fit has a better performance than best-fit. Variable partitioning generally results in better memory utilization than fixed partitioning.

 Compaction:

Compaction is a method used to overcome the external fragmentation problem. All free blocks are brought together as one large block of free space. Compaction requires dynamic relocation. Of course compaction has a cost. Also selection of an optimal compaction strategy is difficult.

Next process arriving into system: P4 requires 30K. It will have to wait although the total amount of free memory is 37K!

One method that can be used for compaction is swapping out those process that are to be moved within memory, and swapping them in to different memory locations.

 3. PAGING

Paging permits a program to be allocated noncontiguous blocks of memory. We divide programs into pages which are blocks of small, fixed size. We then divide the physical memory into frames which are blocks of size equal to page size. We use a page-table to map program pages to memory frames.

The page size (S) is defined by the hardware. Generally it ranges from 512 words/page to 4096 words/page.

Every logical address produced is formed of :

a. a page number p p = logical addr div S

b. an offset d d = logical addr mod S

A page table entry contains the following information:

a. logical page number (optional)

b. corresponding physical frame number

c. attributes (including protection bits, dirty bits, etc.)

Some pages are denoted as "ready-only" by special protection bits associated with each page. Any attempt to write to a read-only page causes a memory protection violation trap to the OS.

Also bounds or limit/base registers may be used to check whether the logical address generated is within the addressing range of the current process.

In paging systems, the logical address space may be smaller than the physical address space.

Example:

Use a page size of 8 words (2**3)

Let physical memory size be 128 words (16 frames=2**4 frames)

Let us have a 3-page program:

program PAGE TABLE MEMORY

-------- .....

word 0 --------

word 1 PAGE FRAME word 0

word 2 PAGE-0 ---------- word 1

... 0 3 FRAME-3 ....

word 7 1 6 word 7

-------- 2 4 --------

word 8 ---------- word 16

word 9 FRAME-4 word 17

... PAGE-1 ......

... word 23

word 15 ---------

--------- .......

word 16 ---------

... word 8

... PAGE-2 FRAME-6 word 9

... ......

word 23 word 15

--------- ---------

.......

program logical offset page frame physical

line address no no address

word 0 00 000 000 00 0011 0011 000

word 1 00 001 001 00 0011 0011 001

word 7 00 111 111 00 0011 0011 111

word 8 01 000 000 01 0110 0110 000

word 9 01 001 001 01 0110 0110 001

word23 10 111 111 10 0100 0100 111

Paging is a form of dynamic relocation.

Every logical address is mapped by the paging hardware to some physical address.

A new process arrives. Assume it is formed of n pages. So, it requires n frames in memory. We check the free frames list. If there are more than or equal to n free frames, we allocate n of them to the new process and put it into memory. We also prepare its page table. It is now a process ready for execution and it may compete for the CPU.

If there are less than n frames, the new process waits. Each process will have its own page table.

How to implement the page table?

Every access to memory should go through the page table. Therefore, it must be implemented in an efficient way. There are various ways of implementing the page table in a paging system. Some of these methods are discussed below.

a. Use fast dedicated registers.

Load/store fast dedicated registers as you load/store other registers. Only the OS should be able to modify these registers.

However, if the page table is large, this method becomes very inefficient. (e.g. IBM 370 can support 4096 pages. Using 4096 registers for the page table would be every inefficient).

b. Keep the page table in main memory.

In this method, we keep a page table base register (PTBR) to point to the first entry of the page table in memory. This is a time consuming method, because, for every logical memory reference, two memory accesses are required. 1) Use PTBR to find page table, and accessing the appropriate entry of the page table, find the frame number corresponding to the page number in the logical address, 2) Access the memory word in that frame.

c. Use content-addressable associative registers.

These are small, high speed registers built in a special way so that they permit an associative search over their contents. That is, all registers may be searched in one machine cycle, simultaneously.

However, associative registers are quite expensive. So, we use a small number of them.

When a logical memory reference is made:

1. Search for the corresponding page number in associative registers.

2. If that page number is found in one associative register:

. get the corresponding frame number,

. access the memory word.

(This is almost as fast as an unmapped memory reference).

3. If that page number is not in any associative register:

. access the page table to find the frame number,

. access the memory word.

(This time, we need two memory accesses).

. also add that page number - frame number pair to one associative register.

In using associative registers, we base our calculations on an important parameter called the hit ratio. The hit ratio is defined as the percentage of times that a page number is found in the associative registers.

For example, a 80% hit ratio means 80% of the time we find the desired page number in associative registers. With only 8 to 16 associative registers, a hit ratio higher than 80% can be achieved.

Let us assume we have a paging system which uses associative registers. Assume associative registers have an access time of 30 nanoseconds, and the memory access time is 470 nanoseconds.

Now, if the page number referenced in the logical address is in associative registers, then the effective access time will be 30+470=500 nanoseconds.

On the other hand, if the page number is not found in associative registers, then the effective access time will be 30+470+470=970 nanoseconds. Here, we are assuming that loading the page number - frame number pair to an associative register can be done in parallel with the last memory access.

If the hit ratio is 90%, then the effective memory access time can be calculated as follows :

Effective memory access time = 0.90*500 + 0.10*970

= 450+97=547 nanoseconds.

So, on the average, there is a 547-470=77 nanosecond slowdown, which is about 15%.

Sharing pages

Sharing pages is possible in a paging system, and this is an important advantage of paging. It is possible to share system procedures or programs, user procedures or programs, and data area. Sharing pages is especially advantageous in time-sharing systems.

Consider a system which supports 10 users. Assume that each user executes an editor program (say, 120K in size), with a 30K data space.

To support 10 users, the OS must allocate 10*150=1500K space! However if the editor program is reentrant ( non-self-modifying code, in other words, read-only. ), then it can be shared among the users, and only one copy of the editor is sufficient. Therefore, only 120+10*30=420K of memory space is needed for this case.

A reentrant program never changes during execution. So more, than one process can execute the same code at the same time. Each process will have its own data storage and its own copy of registers to hold the data for its own execution of the shared program.

4. SEGMENTATION  

User's view their programs as a collection of variable-sized segments.The segmentation method is based upon this view of a program. In segmentation, programs are divided into variable size segments, instead of fixed size pages. Every logical address is formed of a segment name and an offset within that segment. In practice, segments are numbered. Programs are segmented automatically by the compiler or assembler.

For example: a PASCAL compiler will create separate segments for:

a. The code of each procedure or function.

b. The local variables for each procedure or function.

c. The global variables.

Then the loader will assign unique segment numbers to all these segments.

For logical to physical address mapping, a segment table (ST) is used. When a logical address <segment #, d> is generated by the processor,

a. Check if (0 <= d <= limit) in ST.

b. If O.K., then the physical address is calculated as base + d, and the physical memory is accessed at memory word (base + d).

For example, assume the logical address generated is <1, 123>

a. Check ST entry for segment 1. The limit for segment 1 is 200. Since 123 < 200, we carry on.

b. The physical address is calculated as : 5500 + 123 = 5623, and the memory word 5623 is accessed.

How to implement segment tables?

Each segment table entry: 

Modern systems allow a large number of (thousands of) segments with large sizes (~ 64K, or so).

1. Keep the ST in memory

This method requires a STBR (Segment Table Base Register), and a STLR (Segment Table Length Register), since the number of segments used by the program may vary. This means that every logical memory reference requires two memory accesses, one for the ST, one for the physical address found by using the ST.

Example :

logical address: <seg #, d>

a. check if seg # < STLR ( Is it a valid segment number?)

b. if valid, than calculate the address of the corresponding ST in memory as (STBR + seg #).

c. access the ST:

i. check if d < limit ( Is it a valid displacement?)

ii. if valid, compute the physical address as : base + d.

2. Use associative registers as with paging.

Use a small number of them to keep the most recently used ST entries.

Segments are of variable length. For allocating memory space to segments, we can use a first-fit or best-fit algorithm with a free segments list. This means we shall have the external fragmentation problem when all free blocks are too small for a new segment (s). So, the new process either waits or we have to do compaction. A smaller average segment size means less amount of external fragmentation.

Note that if we define every program as one segment, then segmentation becomes equivalent to variable partitioning.

Sharing Segments

Example : Sharing an editor between three users. 

It is also possible to share common procedures. However there are some important things one has to consider in order to provide sharing of procedures between processes.

For example, consider an if-then-else statement. We shall evaluate a condition and depending on whether the condition evaluates to true or false we shall create the address of the then part or the else part as the next instruction to execute. This means a reference to the current segment number. This means that all sharing processes must define the shared procedure segment with the same segment number. We have a single copy of the segment so, we need a unique segment number. As the number of users sharing the segment increases so does the difficulty of finding an acceptable common segment number.

Read only segments may be shared with different segment numbers, as long as they don't contain any self-reference.

 Paged segmentation

Idea: page the segments and eliminate the external fragmentation problem.

 The ST entry for segment S now, contains:

a. the length of segment S

b. the base address of the PT for segment S.

There is a separate PT for every segment. On the average, now there is half a page of internal fragmentation per segment. However, more table space is needed. In the worst case, again three memory accesses are needed for each memory reference. If segment number field is 18-bits, we can have up to

2¹⁸ = 262,144 segments.

This means a very large segment table and the segment table is segmented.

 QUESTIONS

  1. Why do we need memory management and CPU scheduling algorithms for a multiuser system ? Can we do without these algorithms? Explain briefly.

2. a. Explain the terms: internal fragmentation and external fragmentation.

b. List the memory management methods discussed, and indicate the types of fragmentation caused by each method.

3. Consider a multiuser computer system which uses paging. The system has four associative registers. the content of these registers and page table for user_12 are given below:

Page table for user_12							associative registers
0	9					user #		page #	frame #
1	6					12		3	7
2	15					5		2	18
3	7					12		4	42
4	42					9		0	10

PTLR[12]:5 PTBR[12]:50000

PAGE SIZE :1000 words

For the following logical addresses generated by user_12's program, calculate the physical addresses, explain how those physical addresses are found, and state the number of physical memory accesses needed to find the corresponding word in memory. If a given logical address is invalid, explain the reason.

i. <2,1256> ii. <3,290>

iii. <4,572> iv. <5,290>

v. <0,14>

  

4. The following memory map is given for a computer system with variable partitioning memory management.

0
		50K	Job Requested memory
	J1
		45K	1) J4 arrives 10K
	free		2) J5 arrives 20K
		40K	3) J6 arrives 15K
	J2		4) J7 arrives 20K
	free	10K	5) J3 leaves
	J3	20K	6) J8 arrives 50K
		30K
	free

Find and draw the resulting memory maps, after each step of the above job sequence is processed, for :

a. first-fit b. best-fit c. worst-fit

5. Consider a computer system which uses paging. Assume the system also has associative registers.

a. Explain how logical addresses are translated to physical addresses.

b. Calculate the effective memory access time given:

assoc. register access time = 50 nanosec.

memory access time = 250 nanosec.

hit ratio = 80%

c. With the above associative register and memory access times, calculate the minimum hit ratio to give an effective memory access time less than 320 nanoseconds.

6. A system which utilizes segmentation gives you the ability to share segments. If the segment numbers are fixed, then a shared segment table is needed, and the ST must be modified. We shall assume that the system is capable of dynamic relocation, but to reduce the overhead, we want to avoid it unless it is absolutely necessary. The following example is given for such a system :

ST-6					ST-9
s#	base	size	shares		s#	base	size	shares
0	-	-	256		0	190	100	-
1	0	100	-		1	-	-	256
2	100	90	-		2	290	10	-
3	600	15	-

SST
s#	base	size	no. of sh.
256	400	200	2

Assume maximum number of segments per process is 256, and segments are numbered starting with 0.

a. What would be done when a segment previously unshared, becomes a shared segment?

b. When do we need dynamic relocation in this system?

c. Assume segment-2 of process 6 is being executed. A reference is made to segment-0 of process 6. How is the corresponding physical address going to be found?

d. How would self-references within shared segments be handled?

e. What is the no. of sharers field in SST used for?

7. In the X-2700 computer, logical addresses are 24 bits long. The machine implements paged segmentation with a maximum segment size of 64K words and 4K-word pages:

a. Show the logical address structure indicating the segment, page and displacement bits.

b. How many segments can a user process contain?

c. If a process has to be fully loaded into memory to execute, what is the minimum physical memory capacity?

d. If the memory unit contains 65536 frames, show the physical address structure.

e. Show the functional block structure of a suitable architecture for implementing paged segmentation in the X-2700. Indicate the sizes of all necessary tables.

8. Given the memory map in the figure, where areas not shaded indicate free regions, assume that the following events occur:

-----------

Step event required contiguous -----------

memory size (K) 30 K

----------------------------------------------- -----------

i) process A arrives 16 -----------

ii) process B arrives 40 20 K

iii) process C arrives 20 -----------

iv) process D arrives 14 -----------

v) process A leaves - 50 K

vi) process E arrives 30 -----------

-----------

a. Draw the memory maps after step (iv) and (vi) using first fit

best-fit and worst-fit allocation techniques, without compaction

b. Draw the same memory maps as in part (a) if compaction is performed whenever required. also show the maps after each compaction.

9. In a paging system , the logical address is formed of 20 bits. the most significant 8 bits denote the page number, the least significant 12 bits denote the offset. Memory size is 256K bits.

a. What is the page size (in bits)?

b. What is the maximum number of pages per process?

c. How many frames does this system have?

d. Give the structure of the page table of a process executing in this system. assume a dirty bit is also used.

e. How many bits are required for each page table entry?

f. If physical memory is upgraded to 'M bits, how will your answer to c and e change?

10. Consider a segmentation system with the following data given:

STBR=1000 ST Assoc. Reg.'s

STLR= 5 ----------------- ------------------

0 10000 1000 0 10000 1000

1 12000 2000 1 12000 2000

2 25000 4000 ------------------

3 15000 8000

4 38000 4000

-----------------

Associative Reg. access time = 50 nsec

Memory Access time = 500 nsec

Assume data can be written into associative registers in parallel with a memory read or write operation. For replacement of data in associative registers, LRU policy is used.

For each of the following logical addresses, find the corresponding physical address to be accessed, and the total execution time required for that access, including the time spent for address translation operations. Also indicate which memory locations are accessed during address translation. Clearly show all changes made in associative registers.

a. <0,150> b. <0,3700> c. <2,900>

d. <2,3780> e. <5,200> f. <1,200>

11. Explain paged segmentation.

12.

Consider the memory map given in the figure. If worst fit policy is to be applied, then what will be the memory map after arrival of the processes P1=3K, P2=5K, P3=7K P4=6K. Indicate if compaction is needed.

13. The following memory map is given for a computer system with variable partitioning memory management.

Find and draw the resulting memory maps after the above job sequence is processed completely for

a.     first fit b. best fit c. worst fit indicating whenever a compaction is needed.