Lecture Notes for Operating Systems

Memory Management, 30 October 2003

1. early memory

   1. physical connections - pegs, holes, wires

   2. delay lines

   3. crt

   4. magnetic drum

   5. vacuum tubes, relays

   6. core

2. the memory hierarchy

   1. registers - one cycle, 64-512 bytes

   2. on-chip cache (l1 or l2) - 2 cycles, 1-32 kb

   3. off-chip cache (l2) - 5 cycles, 32-512 kb

   4. main (primary) memory - 30 cycles, 1 mb - 8 gb

   5. secondary memory - 10⁶ cycles, 100 mb - 1 tb

   6. tertiary memory - 100-500 ms, 600 mb and up

   7. off-line memory - 1s - 10 m, whatever

   8. principle concern is with primary-secondary memory

3. memory manager

   1. problem - ten pounds of process in five pounds of memory

   2. issues - latency, sharing, protection

4. basic memory management

   1. monoprogramming

      1. no sharing - except os and program

      2. the structure of primary storage

   2. multiprogramming

      1. primary storage shared among several processes - partitioning

      2. fixed partitions - possibly of different sizes

      3. assigning incoming processes to partitions

         1. queues of waiting processes - single vs. multiple queues

         2. finding the best fit between process and partition size - any, best, worst

      4. relocation

         1. compile - link - load

         2. absolute and relative addresses

         3. relocation - adjusting absolute addresses to match assigned addresses

            1. linking - modifying the program

            2. base register - addresses are absolute relative to a base

      5. protection - preventing concurrent processes from accessing each other's storage

         1. key bits - capabilities

         2. base register and limit registers - segments

5. remove partitions

   1. pack processes more tightly

   2. eliminate process size restrictions (up to the size of primary storage)

   3. really big idle processes

   4. fragmentation - holes of idle storage

   5. swapping - move processes into and out of primary storage

      1. big idle processes - move them to disk

      2. fragmentation - compress running processes to one end of primary storage

      3. but, it's slow and cpu intensive

      4. what is a process's storage requirements

         1. static process growth - real time system, fortran programs

         2. dynamic process growth - everything else

            1. stack and heap storage

         3. allocate near holes

         4. overestimate requirements and manage extra space within the process itself.

      5. free-space management - where are the holes?

         1. allocation - return a block of free space of at least k units

            1. minimize fragmentation

         2. deallocation

            1. coalescing - reassemble fragments

         3. bit maps

            1. block storage into chunks - allocation unit; bit count vs. wasted space

            2. fast and simple for small amounts of storage

            3. deallocation is easy

            4. allocation can be difficult - look for a k-unit chunk

         4. linked lists

            1. alternating sequences of allocated and free storage

            2. small allocation units - bytes even

            3. allocation is easy

            4. deallocation is a bit less easy - free-space coalescing

         5. free space allocation

            1. what's the relation between the size of the request and the size of the allocated block

            2. first fit - fast

            3. next fit - fast, larger-grain fragmentation (in theory)

            4. best fit - slow, prone to fine-grain fragmentation

            5. worst fit - ha ha ha

            6. buddy system allocation - allocate one-half a hole

         6. multiple free lists

            1. process and free space

            2. by size

               1. quick fit - allocation very fast, deallocation very slow

This page last modified on 30 October 2003.