Chapter 2

Question 1

What are the four memory allocation schemes?

Answer 1

Single-user systems, fixed partitions, dynamic partitions, and relocatable dynamic partitions.

Question 2

Describe the characteristics of single-user contiguous scheme?

Answer 2

1. The program is entirely loaded into memory
2. If a program doesn’t fit, then either the size of the
   main memory must be increased, or the program must be modified to fit
3. Once execution begins, it remains in memory until execution is complete, either by finishing its work or through the intervention of the operating system, such as when an error is detected
4. The amount of work required from the operating
   system’s Memory Manager is minimal

Question 3

What is the major limitation of single-user systems’ memory allocation?

Answer 3

It doesn’t support multiprogramming (multiple jobs or processes occupying memory at the same
time); it can handle only one at a time.

Question 4

Describe the characteristics of fixed-partition scheme?

Answer 4

1. It was the first attempt to allow for multiprogramming
2. Each partition could be used by only one program.
   The size of each partition was set in advance by the computer operator, so sizes couldn’t be changed without restarting the system.
3. This scheme required that the entire job be loaded into memory before execution could begin.
4. This partition scheme is more flexible than the single-user scheme because it allows more than one program to be in memory at the same time.

Question 5

What are limitations of fixed-partition memory allocation scheme?

Answer 5

1. It works well if all of the jobs that run on the system
   are of similar size or if the sizes are known ahead of time and don’t vary between reconfigurations.
2. If the partition sizes are too small; large jobs will
   need to wait if the large partitions are already booked, and they will be rejected if they’re too big to fit into the largest partition
3. If the partition sizes are too big, memory is wasted
4. Internal fragmentation

Question 6

What is internal-fragmentation in fixed-partition scheme?

Answer 6

A major drawback where less-than-complete use of memory space inside a fixed partition

Question 7

Describe the characteristics of dynamic partitions’ scheme?

Answer 7

1. Memory is allocated to an incoming job in one contiguous block, and each job is given only as much memory as it requests when it is loaded for processing
2. It enforces a fist-come, first-served policy for jobs incoming

Question 8

What are limitations of dynamic partitions memory allocation scheme?

Answer 8

1. Allocation of memory is done efficiently for first set of jobs; newer jobs are allocated into partitions on a priority basis which subsequently leads to external fragmentation.

Question 9

What is external-fragmentation in dynamic partition scheme?

Answer 9

Allocation of memory creates fragments of free memory between partitions (outside memory)

Question 10

What is best-fit allocation and what is its major advantage?

Answer 10

The goal is to find the smallest memory block into which the job will fit. Extra processing time is used to find the suitable memory block. Best-fit scheme yields better memory utilization.

Question 11

What is first-fit allocation and what is its major advantage?

Answer 11

The goal is to find a large enough memory block to fit the job. Less processing time is wasted on finding smallest block for the job. First-fit offers fast allocation.

Question 12

What is deallocation?

Answer 12

The release of memory space

Question 13

How is memory deallocated in fixed-partitions system?

Answer 13

When the job is completed, the Memory Manager immediately deallocates it by resetting the status of the
entire memory block from “busy” to “free.”

Question 14

How is memory deallocated in dynamic partition system?

Answer 14

It combines free areas of memory whenever possible creating three unique scenarios:
1. Joining two adjacent blocks
2. Joining three blocks
3. Deallocating an isolated block

Question 15

In a dynamic partition system, what happens when the block to be deallocated is adjacent to another free block ?

Answer 15

The sizes of the two free partitions must be combined and the total stored with the smaller beginning address

Question 16

In a dynamic partition system, what happens when the block to be deallocated is between two free blocks ?

Answer 16

The sizes of the three free partitions must be combined and the total stored with the smallest beginning address. This creates a null entry with no beginning address and no memory block size

Question 17

In a dynamic partition system, when the block to be deallocated is isolated from other free blocks?

Answer 17

The system must search the free list for a null entry which creates null entries in both the busy and the free lists during the process of allocation or deallocation of memory

Question 18

Describe the characteristics of a relocated dynamic partition scheme?

Answer 18

It solves the issues of fragmentation in fixed and dynamic partition by:
1. The compaction of memory, sometimes referred to as memory defragmentation, is performed by the operating system to reclaim fragmented space
2. The Memory Manager relocating programs
to gather together all of the empty blocks and compact them to make one block of memory

Question 19

What lists have to be updated when compaction of memory occurs in a relocated dynamic partition scheme?

Answer 19

1. The free list is changed to show the partition for the new block of free memory located in memory starting after the last location used by the last job
2. The busy list is changed to show the new locations for all of the jobs already in progress that were relocated.

Question 20

What keeps track of how far each job has moved from its original storage area in a relocated dynamic partition scheme?

Answer 20

A special-purpose register, relocation register, contains the value that must be added to each address referenced in the program so that the system will be able to access the correct memory addresses after relocation.

Question 21

What goes on behind the scenes when relocation and compaction take place?

Answer 21

Bound registers ensures that during execution, a program won’t try to access memory locations that don’t belong to it and relocation registers ensures all of the addresses will be adjusted accordingly when the program is executed.

Question 22

Benefits of a relocated dynamic partition scheme?

Answer 22

The Memory Manager optimizes the use of
memory and thus improves throughput.

Question 23

What are limitations of of a relocated dynamic partition scheme?

Answer 23

An unfortunate side effect is that this memory allocation scheme requires more overhead than with the previous schemes.

Question 24

What are the three options to be considered when deciding on the timing of compaction in a relocated dynamic partition scheme

Answer 24

1. To perform compaction when a certain percentage of memory becomes busy
2. To compact memory only when there are jobs waiting to get
   in.
3. To compact memory after a prescribed amount of time has
   elapsed

Question 25

What is the disadvantage of performing compaction when a certain percentage of memory becomes busy?

Answer 25

The disadvantage of this approach is that the system would incur unnecessary overhead if no jobs were waiting to use the remaining percent.

Question 26

What is the disadvantage of performing compaction only when there are jobs waiting to get in?

Answer 26

This would entail constant checking of the entry queue, which might result in unnecessary overhead and thus slow down the processing of jobs already in the system.

Question 27

What is the disadvantage of performing compaction after a prescribed amount of time has elapsed?

Answer 27

1.If the amount of time chosen is too small, then the system will spend more time on compaction than on processing.
2. If it’s too large, too many jobs will congregate in the waiting queue and the advantages of compaction are lost.