Requirements, Partitioning, paging, and segmentationMemory Management Subdividing memory to accommodate multiple processes Memory needs to be allocated efficiently to pack as many processes into memory as possible2Big Picture3DataStackText (shared)kernel stack/u areaDataStackText (shared)kernel stack/u areaDataStackText (shared)kernel stack/u areaproc structkernel memoryMemory mgnt requirements  Relocation Protection Sharing Logical organization Physical organization4Relocation Why/What: Programmer does not know where the program will be placed in memory when it is executed While the program is executing, it may be swapped to disk and returned to main memory at a different location Consequences/Constraints: Memory references must be translated in the code to actual physical memory address5Protection Protection and Relocation are interrelated Why/What: Protect process from interference by other processes Processes require permission to access memory in another processes address space. Consequences/Constraints: Impossible to check addresses in programs since the program could be relocated Must be checked at run time6Sharing Sharing and Relocation are interrelated Allow several processes to access the same data Allow multiple process to share the same program text rather than have their own separate copy7Logical Organization Programs organized into modules  stack, text, uninitialized data, or logical modules such as libraries, objects, etc. Code modules may be compiled independently Different degrees of protection given to modules  read-only, execute-only Share modules8Unix Process Memory Layout9TextInitialized DataUninitialized Data(BSS)HeapStackLow AddressHigh Addressargv[ ], env[ ]Read fromprogram file byexecZeroed by execPhysical Organization Memory organized into two levels:  main and secondary memory. Memory available for a program plus its data may be insufficient Overlaying allows various modules to be assigned the same region of memory Main memory relatively fast, expensive and volatile Secondary memory relatively slow, cheaper, larger capacity, and non-volatile10Hardware support for memory mgnt How to partition memory How to keep track of which partition belongs to which process How to prevent a process from accessing a partition that has not been allocated to it11Memory Partitioning Virtual Memory Segmentation and/or Paging Non-Virtual memory approaches Partitioning - Fixed and Dynamic simple Paging simple Segmentation12Fixed Partitioning Partition available memory into regions with fixed boundaries Equal-size partitions Process size <= partition size can be loaded into available partition If all partitions are full, the operating system can swap a process out of a partition If program size > partition size, then programmer must use overlays13Fixed Partitioning - Equal Size Main memory use is inefficient Internal Fragmentation- Part of partition unused148 M8 M8 M8 M8 MOperating Systemprocess 1Unused3 MFixed partitioning - unequal sizes15 Lessons the problem of Internal FragmentationOperating System8 M12 M8 M8 M6 M3 M2 Mprocess 1Fixed partition: placement algorithm Equal-size partitions because all partitions are of equal size, it does not matter which partition is used Unequal-size partitions can assign each process to the smallest partition within which it will fit queue for each partition processes are assigned in such a way as to minimize wasted memory within a partition16One Process Queue per partition17NewProcessesOperatingSystemOne Process Queue for all partitions18Operating SystemNewProcessesPros and cons of fixed partitioning Pros: Fixed partitioning is simple and very little OS support is required. Cons: Since number of partitions is fixed, it limits the degree of multi-programming It is inefficient with small processes.  If the sizes of processes is known beforehand then a reasonable size can be decided on.19Dynamic Partitioning Partitions are created dynamically Partitions are of variable length and number Process is allocated exactly as much memory as required Disadvantages: External Fragmentation - small holes in memory between allocated partitions Placement is more complicated - Must use compaction to shift processes so they are contiguous and all free memory is in one block20Example Dynamic Partitioning21Dynamic partition: placement alg. Operating system must decide which free block to allocate to a process Best-fit algorithm Chooses block that is closest in size to the request Results in minimally sized fragments requiring compaction Worst performer overall22Dynamic partition: placement alg. First-fit algorithm Starts scanning from beginning and choose first available block that is large enough. May have many process loaded in the front end of memory Fastest Best23Dynamic partition: placement alg. Next-fit Scan memory from the location of the last allocation and chooses the next available block that is large enough More often allocate a block of memory at the end of memory where the largest block is found Compaction is required to obtain a large block at the end of memory Compaction is more frequent2425Lastallocatedblock (14K)BeforeAfter8K 8K12K 12K22K18K6K 6K8K8K14K 14K6K2K36K20KNext FitFree blockAllocated blockBest FitFirst Fitalloc 16K blockBuddy System Fixed and dynamic partitioning have their drawbacks Fixed partitioning Limits number of active processes Uses space inefficiently if the sizes of the processes don’t match with that of the partitions Dynamic partitioning More complex to maintain Includes overhead of compaction26Buddy System Entire space available is treated as a single block of size 2U If a request for a block of size s such that 2U-1 < s <= 2U Allocated entire block Otherwise  Split block into two equal buddies Continues until smallest block greater than or equal to s becomes available requests rounded to power of two27Buddy System Advantages: coalesces adjacent buffers Disadvantage: performance (recursive coalescing is expensive) poor api28Buddy System Allocation• Begin with one large block• Suppose we want a block of size 16292561286432168421Buddy System Allocation Begin with one large block Recursively