CMSC 412 Midterm #2 (Spring 2004)

1.) (20 points) Define and explain the following terms:

a) TLB

Translation Look-aside Buffer. A type of cache that speeds up translation of virtual to physical locations (each entry covers an entire page).

b) Multi-level Indexed (File) Allocation

A way to represent the set of allocated blocks in a file using indirect blocks containing pointers to direct blocks that contain pointers to the actual blocks. Allows random access and space efficient storage of both large and small files.

c) Seek Time

The time required to move the disk head over the desired track (or cylinder).

d) Working Set

The set of pages in use by the currently running processes. Keeping this set of pages in memory prevents trashing.

2.) (20 points) Memory Systems

a) (10 points) Give two disadvantages of using FIFO page allocation?

Ignores temporal locality

Subject to Bleadly’s anomaly (more page frames can increase number of page faults).

b) (10 points) What advantage of inverted page tables increases on 64-bit processors compared to 32-bit systems?

Page tables are arranged by physical page frame and thus grow in size proportional to physical member in the system not the size of the virtual address system.

3.) (20 Points) Synchronization: Given an implementation of binary semaphores, implement counting semaphores.

Declarations:

Typedef struct {

Semaphore mutex = 1

Semaphote ready = 0;

Int count = 0;

} countingSemaphore;

P(countingSemaphore *sem) {

            P(sem->mutex)
      if (sem->count > 0)
            sem->count—-;
            V(sem->mutex)’
      else
            V(sem->mutex)
            P(sem->ready)

}

V(countingSemaphore *sem) {
            P(sem->mutex)
      if (sem->count == 0)
            V(sem->ready)
      else
            sem->count++;
      V(sem->mutex)

}

4.) (20 points) File Systems

a) (10 points) Assuming no data is cached in memory, what is the best-case (minimum) number of disk accesses to read the 1 millionth byte of a file located in the root directory of a UNIX file System using 4096 byte blocks. For full credit explain what each read is for.

1) read root inode

2) read root chunck (gets inode location of target block)

3) read files inode

4) read indirect block

5) read data block

b) (10 points) Give two advantages of adding a log (or journal) to a traditionally organized file system

Faster recovery (no need to check whole filesystem, just log)

No windows of corruption/lost data during update

5.) (20 points) Project

a) (6 points) When you paged out a page, why did your code need to call flushTLB?

To clear the cached translation for the page being sent to disk, otherwise the hardware could access an invalid location.

b) (7 points) Why did you need to call getPagingFileInfo to find the first disk block of the paging file, instead of using 0?

The paging file is a normal file in the pfat filesystem and therefore it’s starting block is not likely to be a the first block on the disk.

c) (7 points) What changes would you need to make to your project to make page tables pageable?

Page table allocation: use alloc_pageable_page

Page fault handler: update to handle new faulting location

On page out: clear present bit in page directory for that page table