>> Topic 6 <<<< Memory Management >> it intended to satisfy the following requirements : 1. Relocation > Programmers typically do not know in advance which other programs will be resident in main memory at the time of execution of their program active processes need to be able to be wapped in and out of main memory in order to maximise processor utilisation , Specifying that a process must be placed in the same memory region when it is swapped back in would be limiting , may need to relocate the process to a different area of memory . The os will need to know the location of : - process control information - the execution stack - the entry point to begin the execution of the program for the process. 2. Protection : Process need to acquire permission to reference memory locations for resaving or writing purposes , location of a program in main memory is unpredictable , Memory references generated by a process must be checked at run time mechanisms that support relocation also support protection . The protection requirement must be satisfied by the processor rather than os : os cannot anticipate all the memory references that a program will make - time consuming to screen each program in advance for possible memory referenced violation - it is only possible to assess the permissibility of a memory reference at the time of execution of the instruction making reference . 3. Sharing > Advantageous to allow each process access to the same copy of the program rather than have their own separate copy , Memory management must allow controlled access to shared areas of memory without compromising protection , 4. Logical Organisation > Memory is organised as linear one dimensional, address space, consisting of a sequence of bytes or words , similar to actual machine hardware does not correspond to the way in which program are typically constructed , Segmentation is the tool that most readily satisfies these requirements . 5. Physical Organisation > Computer memory is organised into at least two levels >> Main Memory : fast access at high cost ,volatile , small capacity holds programs and data currently in use _ Secondary Memory : slower and cheaper , not volatile , large capacity for long term storage of programs and data . The organisation of the flow of information between main and secondary memory is a major system concern , cannot leave the programmer with the responsibility to manage memory , memory available for a program plus its data may be insufficient <OVERLAYing> allows various modules to be assigned the dame region of memory but is time consuming to program , Programmer does not know how much space will be available . >>Partitioning << Divide the merry to small size partition> two types of partitioning > 1) fixed Partition 2) Dynamic partitioning >> equal size Partition > divide the memory into same size partition any process whose size is less than or equal to the portion size can be loaded into an available partition , the operating system can swap out a process if all partitions are full and no process in the Ready or running state .Disadvantages > A program may not fit in a partition (The programmer must design the program with overlays ) Memory use is inefficient < any program no matter how small will take entire partition ( Internal fragmentation ) - Unequal size > divide the memory into different partition size , helps lessen the problems of internal fragmentation . - Fixed partitioning > placement algorithm > equal-size partitions : if there is an available partition, a process can be loaded into the partition , because all partitions are equal size it does not matter which portion is used , if all partitions are occupied by locked processes, choose one process to swap out to make room for the new process - Unequal-size partitions : Two ways > Multiple queues assign each process to the smallest partition within which it will fit , a queue for each partition size , tries to minimise internal fragmentation ,problem some queues will be empty if no processes within a size range is present << Use of single queue , when its time to loas a process into memory the smallest available partition that will hold the process is selected , if all partitions is occupied , preference to swapping out the smallest partition that will hold the incoming process. Also have to consider other factors such as priority and blocked vs, ready process. Increases the level of multiprogramming at the expense of internal fragmentation .<Advantages > simple and require minimal os software and processing overhead , unequal-size portion provides a degree of flexibility to fixed portioning , < Disadvantages> the number of partitions specified at system generation time limits the number of active ( not suspended ) process in the system , because partition sizes are preset at system generation time , small jobs will not utilise partition space efficiently . >> Dynamic Partitioning : Partitions are of variable length and number , Each process is allocated exactly as much memory as it requires , used in ibm os ,Eventually holes are formed in the memory and memory will become more and more fragmented, and utilisation declines.this hole is called ( External fragmentation ) to overcome external fragmentation we have to use(compaction ) , time to time os shifts the processes so that they are contiguous and so that all of free memory is together in on block, DisAdvantages: time consuming and wast cpu time. We can loas process in memory on three levels > 1) Best-fit : chooses the block that is closest in size to the request , chooses smallest hole . 2) first-fit: begins to scan memory form the beginning and chooses the first available block that is large enough chooses first hole form beginning . 3) next-fit : begins to scan memory from the location of the last placement and chooses the next available block that is large enough , chooses first hole form last placement . << Buddy System >> Both fixed and dynamic partitioning schemes have drawbacks , an interesting compromise is th buddy system , space available for allocation is treated as a single block , memory locks are available of size 2^k words . >> Relocation : when program loaded into memory the actual ( physical /absolute address ) memory locations are determined , a process may occupy different partitions which means different physical memory locations during execution , compaction will also cause a program to occupy a different partition which means different physical memory locations , thus the locations os instruction and data referenced by a process are not fixed .there are three type of address <1>logical /virtual : reference to a memory location independent of the current assignment of data to memory . < Relative> address is expressed as a location relative to some known point . <Physical /absolute> actual location in main memory .Hardware mechanism is needed for translating relative addressed to physical memory addresses at the time of execution of the instruction that contain the reference. When a Process assign to the running state > Base register - loaded with the starting address in memory of the process . <Bounds register _ loaded with the address of the ending location of the process . These values must be set when the program is loaded into memory or when the process image is swapped in , during execution of the process, relative address are encountered , Each relative address goes through two steps of manipulation by the processor: <Address translation : the value in the vase register is added to the relative address to produce an absolute address . < Check either address valid or not : The resulting address in compared to the value in the bound register if the address within bounds, then instruction execution may proceed, otherwise and interrupt is generated to the os which must respond to the error . >> Paging << Partition memory into equal fixed-size chunks , processionals is also divided into equal fixed-size of the same size as memory .(Page>chunks of a process ) (frames > available chunks of memory ) paging within the program , each logical address consists of a page number and an offset within the page , logical to physical address translation s done by processor and the processor must know how to access the page table of current process, presented with a logical address ( page# offset ) the processor uses the page table to produce a physical address ( frame # offset) simple paging similar to fixed partitioning but the different are > in paging the partitions are rather small , program may occupy more than one partitions and no need to be contiguous . For simple paging : Memory is divided into small equal-size frames ,each process is divided into frame-size pages , smaller processes require fewer pages, larger processes require more , , all of its pages are loaded into available frames, and a page table is set up this approach saves many problems inherent in portioning .< segmentation > A program can bae subdivided into segments , segments vary in length , have the maximum segment , addresses consists of segment # offset similar to dynamic partitioning the different is that with segmentation a program may occupy more than one partition and these partitions does not need to be contiguous.The segmentation eliminates internal fragmentation but external fragmentation still exist ,however because a process is broken up into a number of smaller pieces the external fragmentation should be less , paging is invisible for the programmer but segmentation is visible and is provide as aand data : programer or compile will adding programs and data to different segments , program or data may be further broken down into multiple segments and the programmer must be aware of the maximum segment size limitation .for address translation every process will have segment table : length > length of the segment > Base : starting address