Memory Management

Memory address 

A memory address points to a specific location in memory, usually denoted with a fixed length sequences of digits. CPU uses the memory address to track data stored on the main memory.

All forms of memory provide an array of bytes. Each byte has its own address. Interaction is achieved through a sequence of load or store instructions to specific memory addresses.

Memory addressing hardware ensures that a process can execute only within its own address space.

Memory word 

Memory word is the smallest unit of memory made of one or more bytes (Ex..32-bit memory addressing uses 32 words) Holders for memory address must be a size capable of values (not excessively large). Therefore the size used to hold a memory address is referred to as a word or word size. 

Logical  and  physical and address

Main difference between the logical and physical address is that while the logical address is generated by processor during program execution, physical address refers to an actual location in main memory.

The logical/vitual address can be viewed by the user but the physical address is not visible to the user. The virtual address process stored in the main memory. On the other hand , all physical addresses are mapped to a corresponding logical address. Physical address has no direct access and is generated by the memory management unit(MMU).

Memory protection by operating system

Protection of memory space is accomplished by having the CPU hardware compare every address generated in user mode with the registers. Any attempt by a program executing in user mode to access operating –system memory or other users memory results in a trap to the operating system , which treats the attempt as a fata error. This scheme prevents a user program form modifying the code or data structures of either the operating system or other users.

Role of memory management unit

The run-time mapping from virtual to physical addresses is done by a hardware devices called the memory-management unit (MMU). We can choose from many different methods to accomplish such mapping. We illustrate this mapping with a simple MMU scheme that is a generalization of the base-register scheme. The base register. The value in the relocation register is added to every address  generated by a user process at the time the address is sent to memory. For example, if the base is at 14000,then an attempt by  the user to address location 0 is dynamically relocated to location 14000, an access to location 364 is mapped to location 14346. The user program never sees the real physical addresses. The program can create a pointer to location 346,store it memory ,manipulate it , and compare it with other address- all as the number 346. Only when it is used as a memory address is it relocated relative to the bale register. The user program  deals with logical addresses. The memory- mapping hardware convets logical addresses into physical addresses.

First-fit, Best-fit and Worst-fit 

First-fit, Best-fit, Worst-fit are the three strategies for implementing contiguous memory    allocation. 

• Best fit - Allocator places a process in the smallest block of memory. 

  Ex:   A process request 12kB of memory. The memory manager has a list of unallocated bocks of 6kB,14kB,19kB,11kB blocks.Then best fit method allocate 12kB of 13kB block to the process.

• First fit - Allocate the first hole that is big enough. There are many holes in memory, so OS to minimize the time spent analyzing the available space staring at the start of primary memory and allocates memory from the first hole it counts large enough to satisfy request.

 Ex-: consider   above example of best fit   here 12KB  of  the 14KB  block to the process.

• Worst Fit  - All  the largest  here, must also search entire list.

 Ex-: Above  some example worst fit allocate  12KB  of the 19KB  block to     the  process  recuing a 7KB block for  future use.

Example

Given six memory partitions of 300 KB, 600 KB, 350 KB, 200 KB, 750 KB, and 125 KB (in order), how would the first-fit, best-fit, and worst-fit algorithms place processes of size 115 KB, 500 KB, 358 KB, 200 KB, and 375 KB (in order)?   

Both the first-fit and best-fit strategies for memory allocation suffer from following two issues.

            * External Fragmentation

            * Internal Fragmentation 

  

Internal Fragmentation	External Fragmentation
1.     In internal fragmentation fixed-sized memory blocks  square measure appointed to method	In external fragmentation variable-sized memory blocks square measure appointed to method
2.     Internal fragmentation happens when the method or process is   larger than the memory.	External  fragmentation happens when the method or process is  removed.
3.     The solution of internal  fragmentation is best-fit block.	Solution of external fragmentation is Compaction, paging, and segmentation
4.     Internal fragmentation occurs   when memory is divided into fixed sized partitions	External fragmentation occurs when memory is divided into variable size partitions based on the size of processes
5.     The difference between memory allocated and required space or memory is called Internal   fragmentation .	The unused spaces formed between non-contiguous memory fragments are too small to serve a new process, is called External fragmentation.

Solution to external fragmentation :

1) Compaction : shuffling the fragmented memory into one contiguous location.

2) Virtual memory addressing by using paging and segmentation

Contiguous Vs non-Contiguous

The basic difference between contiguous and noncontiguous memory allocation is that contiguous allocation allocates one single contiguous block of memory to the process whereas, the noncontiguous allocation divides the process into several blocks and place them in the different address space of the memory.

CONTIGUOUS MEMORY ALLOCATION	NONCONTIGUOUS MEMORY ALLOCATION
Allocates consecutive blocks of memory to a process.	Allocates separate blocks of memory to a process.
Contiguous memory allocation does not have the overhead of address translation while execution of a process.	Noncontiguous memory allocation has overhead of address translation while execution of a process.
A process executes faster in contiguous memory allocation	A process executes quite slower comparatively in noncontiguous memory allocation.
The memory space must be divided into the fixed-sized partition and each partition is allocated to a single process only.	Divide the process into several blocks and place them in different parts of the memory according to the availability of memory space available.
A table is maintained by operating system which maintains the list of available and occupied partition in the memory space	A table has to be maintained for each process that carries the base addresses of each block which has been acquired by a process in memory.

External fragmentation

Paging helps with external fragmentation in two ways.

·       First, it subdivides memory into fixed-size adjacent chunks - the pages - that are "large enough" so they're never useless. Again the definition of "large enough" is not precise. But most applications will have lots of requirements satisfiable by a single 4k page. Since no external fragmentation problem can occur for allocations of a page or less, the problem has been mitigated.

·    Second, the paging hardware provides a level of indirection between application pages and physical memory pages. Therefore any free physical memory page can be used to help satisfy any application request, no matter how large.

Page and frame in relation to logical address and physical address of a process.

Page

Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory. This scheme permits the physical address space of a process to be non – contiguous.

Frame

The physical address space is conceptually divided into a number of fixed   

Size blocks called, frames.

           

Functionality of page table

A page table is the data structure used by a virtual memory system in a    computer operating system to store the mapping between virtual addresses and physical addresses. Virtual addresses are used by the program executed by the accessing process, while physical addresses are used by the hardware, or more specifically, by the RAM subsystem. The page table is a key component of virtual address translation which is necessary to access data in memory.

Mapping of ‘page’ and ‘frame’ in Address translation .  

                    

 In the mapping the first logical address shows the “page 0” so it checks the 0^th index of the frame table and get the corresponding frame number and locate the into that frame number in the physical memory it will be contain the real data that need to use in page 0 logical address.

When we consider the “page 2” it checks the 2^nd index of page table and get the corresponding frame number for 2^nd. As the above picture the number is 3 so after that it mapped to the 3^rd frame of the physical memory. Finally, the 3^rd frame in the physical memory will contain the data that should mapped to page 2

Size of the “page” and the size of the corresponding “frame” 

A page is a region of virtual address space, and a page frame is a region of physical memory. A page which maps a region of physical memory must have the same size as that piece of physical memory, otherwise there's no point.

    The main advantage of having TLB in paging

TLB is used to reduce effective memory access time as it is a high speed associative cache.

EMAT = h*(c+m) + (1-h)*(c+2m)

where, h = hit ratio of TLB

m = Memory access time

c = TLB access time

What do you mean by the hit ratio of TLB?

The percentage of times that the page number of interest is found in the TLB is called the hit ratio. An 80-percent hit ratio, for example, means that we find the desired page number in the TLB 80 percent of the time. 

·       Page number(p): Number of bits required to represent the pages in Logical Address       Space or Page number.

·       Page offset(d): Number of bits required to represent particular word in a page or page   size of Logical Address Space or word number of a page or page offset.

·     Frame number(f): Number of bits required to represent the frame of Physical        Address Space or Frame number.

·     Frame offset(d): Number of bits required to represent particular word in a frame or frame size of Physical Address Space or word number of a frame or frame offset.

When process is executing CPU create logical memory address and they are mapped to the real memory of the process in the Physical memory. As the above diagram shows logical memory is consist with p (page number) and d (page offset). First, The CPU check the page number inside the TLB if the correct page number exist inside the TLB (TLB hit). Frame number of that is copied and make the physical address with combining it with the d (page offset). But if the page number does not exist inside the TLB (TLB miss) CPU check it inside the page table that in the main memory. It uses p (page number) as the index for the page table and find the correct frame number inside that index. After that it combine with the d (page offset) and with the frame number and make the physical address of for the corresponding logical address. When TLB is miss the used index and frame number copies to the TLB for future references.

1)     Consider the contiguous memory allocation of a computer system.

a)     Briefly explain first-fit, best-fit, and worst-fit algorithms in contiguous memory allocation.

First fit – in contiguous memory allocation. When the 

memory is partitioned into different size partitions. 

The first memory that enough to allocate the data

Best fit – analyze the whole memory and allocate the 

smallest hole that big enough to the process

Worst fit – analyze the whole memory and allocate the 

largest hole from the available spaces

b)     Given six memory partitions of 300 KB, 600 KB, 350 KB, 200 KB, 750 KB, and 125 KB  (in order), how would the first-fit, best-fit, and worst-fit algorithms place processes of size 115KB, 500 KB, 358 KB, 200 KB, and 375 KB (in order) ?

First fit

Process	Memory partition
115KB	300KB
500KB	600KB
358KB	750KB
200KB	350KB
375KB	-

Best Fit

Process	Memory partition
115KB	125KB
500KB	600KB
358KB	750KB
200KB	200KB
375KB	-

Worst Fit

Process	Memory partition
115KB	750KB
500KB	600KB
358KB	-
200KB	350KB
375KB	-

2)     Consider a paging system with the page table stored in memory.

a)     Define the term “hit ratio” of TLB.

The percentage of time that a page number is found in the TLB.

Hit Ratio= Total Number of  TLB hits             * 100%

                   Total Number of TLB hits + Total number of TLB miss 

b)     If a memory reference takes 500 nanoseconds, how long does a paged memory reference take?

memory reference time          = 500*2 ns

                                                =1000ns

c)     If we add a TLB and if the hit ratio is 90%, what is the effective memory reference time?

(Assume that finding a page-table entry in the TBL takes 50 nanoseconds, if the entry is present.)

Memory reference time          = (0.9*50) + (0.1*1000)

                                                = 145ns

d)     Calculate the percentage of the reduction of memory reference time when the TLB is available.

Percentage of the reduction of memory reference time         = (1000 - 145) * 100%

                                                                                                = 85.5%

3)     Consider a paging system that uses 32-bit virtual addresses and has 128MB (2²⁷) main memory with 4KB (2¹²) page size.

a)      How many frames does the system contains?

Frame size = page size

Total number of frames in the system=Main memory size

                                                              Frame size(page size)

Total number of frames in the system=  2²⁷   /   2¹²                                                                

Total number of frames in the system                        =2¹⁵

b)     How many bits does the system use for the displacement (d)?

2¹² bits is the page size

The bits that needed to represent 2¹²   = 12

The bits that use to displacement       = 12bits

c)     How many bits does the system use as the page number?

Total number of bit in the virtual memory     = 32bits

Bits that use as the page number                    = 32-12

                                                                        = 20bits

d)     Following virtual address and page table is given. What is the physical address of this?

e)     virtual address: 0000 0000 0000 0000 0101 1101 0110 1010

Page #	Frame #
0	4
3	3
5	2

Page number of the virtual memory   = 0000 0000 0000 0000 0101             = 5

The equivalent frame number            = 2 = 0000 0000 0000 0000 0010

The physical address

            0000 0000 0000 0000 0010 1101 0110 1010

4)     Consider a logical address space of 256 pages with a 4-KB page size, mapped onto a physical memory of 64 frames.

a)     How many bits are required in the logical address?

Logical memory address = page number + page offset

Number bits that requires to represent 256 page numbers                 = 8

Number of bits requires to represent 4KB offset                                           = 12

Total number of bits requires to logical memory address                  = 8+12

                                                                                                            = 20

b)     How many bits are required in the physical address?

Frame size = page size

Physical memory address = frame number + frame offset

Number of bits that requires to represent 64 frames                          = 6

Number of bits that requires to represent 4KB offset                        = 12

Total number of bits that requires to physical address                       = 12 + 6

                                                                                                            = 18

c)     Assuming a 1-KB page size, what are the page numbers and offsets for the following address references (provided as decimal numbers). Use the following table to structure the answers.

i.	2375
ii.	16311
iii.	30000
iv.	256
v.	16385

 

Logical address (decimal)	Logical Address (Binary)	Page number (Binary)	Offset (Binary)	Page number (Decimal)	Offset (Decimal)
2375	0010 0011 0111 0101
16311	0001 0110 0001 0001
30000	0011 0000 0000 0000
256	0010 0101 0110
16385	0001 0110 0011 1000 0101