Embry–Riddle Aeronautical University



The FSL is just a linked list of “holes” (unused blocks) of main memory: FSLWe only need two pieces of information about a hole: its size and its base physical address in memory. Not that it really matters we’re not going to be coding this stuff but here’s what the key declarations might look like in the C code of the operating system:typedef struct hole{ unsigned int sizeOfHole; unsigned int baseOfHole; struct hole *nextHole; /* pointer to the next hole in the FSL */} HOLE;HOLE *FSL;A process’s physical address space, you should remember, comes in four sections:Text section (a.k.a. code section), containing the instructions produced by the compilerData section, containing global and static variables produced by the compilerStack section, where local variables and function arguments are placed and removed dynamically (by your program during its execution) as blocks or functions are entered and exited dynamicallyHeap section, where storage dynamically requested by the program (e.g., malloc) is allocatedWhenever a new process applies for admission, the amount of memory it needs is equal to the size of the load module for the program that will execute in the process plus the OS default for the stack section plus the OS default for the heap section. (The load module created by the compiler and linker already contains the text and data sections.)The long term scheduler asks the free space manager if there’s enough memory for the new process. The free space manager searches the free space list. Assuming a big enough hole exists, it is removed from the free space list and its base address supplied to the loader. The free space manager than creates a new, smaller hole whose size is what was left over after some of the old hole was allocated to the new process and whose base address is the old hole’s base plus the size of the new process. E.g., if the old hole started at address 15000 and was of size 4K and the new process needed 3K, the new process will be loaded at 15000 and the new hole of size 1K starts at 18000. The new hole must then be inserted into the free space listWhen a process is terminated, the free space manager reclaims its memory by creating a new hole where the process used to be, searching the FSL to see if the new hole is adjacent to some existing hole and, if so, merging them into a bigger new hole, and then inserting the new (possibly now bigger) hole into the free space list. FSL AlternativesFSL ManagementAdvantagesDisadvantagesFirst-FitThe FSL is an unordered listWhen a process needs memory for admission, the list is searched from the beginning and the first hole found that’s big enough is the one that gets used.When a new hole is created (after a new process’s required memory is taken from a bigger hole or after a process terminates and its memory is released), it doesn’t matter where it goes in the list, we can put it (the new hole) wherever is easiest (usually the front of the list)Fastest insertion into FSL whenever a new hole is created, it can go right at the front of the list, no searching for the right spot to insert it.Less likely than best fit to create stupidly small holes, so it delays external fragmentation better than best-fitNot as good as worst-fit at delaying external fragmentation Best-FitThe FSL is an ordered list, ordered by ascending size, smallest hole at the front. When admitting a new process and thus searching for the best fit, the first hole that’s big enough is the best fit (since the list is ordered). Inserting a new hole also requires searching for the right spot to keep the list ordered.Preserves big holes the longest of these three alternatives, so a big job arriving later, after a bunch of smaller jobs is more likely to be admitted.Creates smaller holes than the other alternatives so excessive fragmentation (unusable memory in many small holes) happens earliest. Searching to find the right spot to admit a new process or to insert a new hole usually takes longer than first fit since the list must be searched from the front and the front fills up with the unusable small holes.Worst-FitThe FSL is an ordered list, ordered by descending size, largest hole at the front. Admitting a new process uses the first hole on the list.Inserting a new hole still requires searching the list to find the right spot (to keep the list ordered)Fastest at finding the right hole to admit a new process, it’s memory is always taken from the biggest hole which is always at the front, so the list doesn’t have to be searched at all to admit a process.Least likely to create a useless small hole so it delays excessive external fragmentation the longestGobbles up the biggest holes very quickly so later arriving big jobs may not get admitted. ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download