Exercises

Approach

Start from the origin of each address, then describe how the two are tied together.

Steps

1. Identify where the logical address comes from.
2. Identify where the physical address comes from.
3. Explain the mechanism that maps one onto the other.

Answer

• Logical address: produced by the program, a relative address within the program
• Physical address: the actual address of the memory cell, accessed directly by the hardware
• Translation process: the address translation hardware turns the logical address into the physical address

Approach

Group the functions by what they do to the memory of a process, and cover the full life cycle of an allocation.

Steps

1. Think about the moment a process starts and needs memory.
2. Think about the moment the process releases memory.
3. Think about how the process addresses that memory in the first place.
4. Think about how one process is kept from touching the memory of another.

Answer

1. Memory allocation: hand memory space to processes
2. Memory deallocation: take back the memory space a process has released
3. Address translation: turn the logical address into the physical address
4. Memory protection: stop a process from reaching the memory space of another process

Approach

Walk through the free partition table in address order and give each process the first free partition that is large enough.

Steps

1. List the free partitions in the order they appear in memory.
2. For each process, scan the partitions from the first one onwards.
3. Take the first partition whose size is at least the size the process needs.
4. Mark that partition as allocated and continue with the next process.

Answer

• Free partitions: 100K, 200K, 50K, 300K
• Process requests: 80K, 120K, 60K

Allocation result:

• Process 1 (80K) → the 100K partition
• Process 2 (120K) → the 200K partition
• Process 3 (60K) → the 300K partition

Approach

Examine every free partition for each process and pick the smallest one that still satisfies the request, so that the leftover waste stays minimal.

Steps

1. List the free partitions in the order they appear in memory.
2. For each process, compute the leftover of every partition that is large enough.
3. Choose the partition with the smallest leftover.
4. Mark that partition as allocated and continue with the next process.

Answer

• Free partitions: 100K, 200K, 50K, 300K
• Process requests: 80K, 120K, 60K

Allocation result:

• Process 1 (80K) → the 100K partition, leftover 20K
• Process 2 (120K) → the 200K partition, leftover 80K
• Process 3 (60K) → the 300K partition, leftover 240K

Approach

Split the logical address into a page number and a page offset, then map the page number through the page table.

Steps

1. Divide the logical address by the page size to get the page number.
2. Take the remainder of the same division to get the offset inside the page.
3. Look the page number up in the page table to get the physical frame number.
4. Combine the frame number with the offset to get the physical address.

Answer

• Page size: 4KB
• Logical address: 12345
• Page number: 12345 / 4096 = 3
• Page offset: 12345 % 4096 = 57

Approach

Judge segmentation against the two criteria that matter most for a memory manager: how well it matches the program, and what it costs the system.

Steps

1. Ask whether segmentation reflects the logical structure of a program.
2. Ask whether the protection and sharing of data work naturally.
3. Ask how the variable-length segments affect the free space in memory.
4. Ask how much work the address translation itself requires.

Answer

Advantages:

• Fits modular programming well
• Supports dynamic growth
• Makes sharing and protection easy

Disadvantages:

• Prone to external fragmentation
• Complicated address translation
• Low memory utilization

Approach

Compare the two algorithms along the same three axes: the information they need, how hard they are to implement, and how well they perform.

Steps

1. State the rule each algorithm uses to pick the victim page.
2. Describe the bookkeeping each algorithm needs.
3. Weigh the practical cost of that bookkeeping.

Answer

The FIFO algorithm:

• Simple to implement
• Poor performance
• Ignores how often a page is used

The LRU algorithm:

• Better performance
• Complex to implement
• Takes how often a page is used into account

Approach

Define the model in one sentence, then explain what the operating system does with the number it produces.

Steps

1. Define the working set as a set of pages over a window of time.
2. Explain how it reflects the locality of the process.
3. Explain how the operating system uses it to make allocation decisions.

Answer

• Definition: the set of pages a process has accessed during a recent period of time
• Purpose: predicts the memory a process actually needs
• Application: drives page allocation and page replacement decisions

Approach

Describe the memory as a list of blocks that record their size and whether they are in use, and then allocate by scanning that list.

Steps

1. Model each region of memory as a block with a start address, a size, and an allocation flag.
2. Keep the blocks in an array that the allocator can walk over.
3. Scan the array for a free block that is large enough for the request.
4. Mark the block as allocated and return its start address, or report failure.

Answer

// Structure of a memory block
struct memory_block {
    int start_address;
    int size;
    int is_allocated;
};

// Allocation function
int allocate_memory(int size) {
    for (int i = 0; i < block_count; i++) {
        if (!blocks[i].is_allocated && blocks[i].size >= size) {
            blocks[i].is_allocated = 1;
            return blocks[i].start_address;
        }
    }
    return -1; // allocation failed
}

Approach

Work along the four layers of the system: how memory is divided, how pages are chosen, how addresses are translated, and how much is loaded in advance.

Steps

1. Look at the way memory is divided and allocated, which decides how much is wasted.
2. Look at the page replacement algorithm, which decides how often a page fault happens.
3. Look at the address translation path, which decides how expensive each memory access is.
4. Look at what can be predicted in advance, which decides how many faults can be avoided.

Answer

1. Reduce fragmentation: use a suitable allocation algorithm
2. Raise the hit rate: optimize the page replacement algorithm
3. Reduce the translation overhead: use a TLB cache
4. Preallocate strategically: predict the demand from historical data