Tutorial Week 6

Questions and Answers

Memory Management

Q1: Describe internal and external fragmentation.?

External Fragmentation: total memory space exists to satisfy a request, but it is not contiguous.

Internal Fragmentation: allocated memory may be slightly larger than requested memory; this size difference is memory internal to a partition, but is not being used.

Q2: What are the problems with multiprogrammed systems with fixed-partitioning?

• Internal fragmentation.
• Inability to run processes greater in size than a partition, but smaller then memory.

Q3: Assume a system protected with base-limit registers. What are the problems with such a protected system (compared to a paged or segmented VM system)?

• Partitions must be contiguous - external fragmentation.
• Entire process must be in memory.
• Cannot practically share memory with other processes.

Q4: A program is to run on a multiprogrammed machine. Describe at which points in time during program development to execution time where addresses within the program can be bound to the actual physical memory it uses for execution? What are the implication of using each of the three binding times?

• Compile/Link time binding.

  The executable itself contains the actual physical addresses it will use during execution. It can only run at one location, and only a single copy can run at a time, unless the executable is recompiled/relinked to a new location in physical memory prior to each execution.

• Load time binding

  Addresses within the executable are annotated such that when the program is loaded into physical memory, the loader can bind the addresses to the correct location within physical memory as the program is loaded (copied) into memory. This process slows loading (increases startup latency), and increases executable file size (to hold annotations, minor point).

• Run-time binding

  The compiler/linker generated addresses are bound to a logical address space (an abstract memory layout). The program executes using the logical addresses independent of where it is loaded into physical memory. At run-time the logical addresses are translated to the appropriate physical addresses by specialised hardware on each memory reference.

  Run-time binding is the most flexible (depending of the translation hardware available, e.g. page VM MMU), but it incurs the cost of translation on every memory reference, which can be significant.

Q5: Describe four algorithms for allocating regions of contiguous memory, and comment on their properties.

1. First-Fit

   Scan memory region list from start for first fit.

   Must always skip over potentially many regions at the start of list.

2. Next-Fit

   Scan memory region list from point of last allocation to next fit.

   Breaks up large block at end of memory, needs compaction.

3. Best-Fit

   Pick the closest free region in the entire list.

   Tends to leave small unusable regions, and slower due to requirement of search the entire list.

4. Worst-Fit

   Find the worst fit in the entire list

   Slower as it searches the entire list, fragmentation still an issue.

Q6: What is compaction? Why would it be used?

Moving all the allocated regions of memory next to each other (e.g. to the bottom of memory) to free up larger contiguous free regions.

Virtual Memory

Q7: What is swapping?

Swapping is where a process is brought into main memory in its entirety, run for a while, and then put completely back on disk.

Page last modified: 1:17pm on Tuesday, 21st of April, 2009

Print Version