FINAL EXAM: Operating Systems 416 Sample Final Exam
1. Quickies (30 points)
a. (14 points) Answer these with a yes or no (True or False) , or with a single term or
phrase, as appropriate
i. Which bit in the PTE (Page table Entry) does the operating system use for
approximating LRU replacement?
ii. The layout of the disk blocks for a file using Fast File system is
always/sometimes/never contiguous on disk?
iii. Does a TLB miss always/sometimes/never result in a pagein from disk?
iv. Without TLB, the memory access time of a virtual memory system will be
same/double/triples compared to memory access time with TLB
v. Multilevel page table always/never takes less space than single level page table
vi. In SSD, prior to a write a block has to be erased always/sometimes.
vii. What are the two components of virtual address of a pure segmented virtual
memory?
viii. Larger page sizes implies smaller/larger page tables
ix. Larger pages results in higher external/internal fragmentation
x. In general, there are more/same/fewer inodes than directories in a file system
in UNIX.
xi. The layout of virtual pages for a virtual address space is
always/sometimes/never contiguous in physical memory.
xii. Condition variables can be initialized to any arbitrary integer.
xiii. In operating systems, passwords of users are stored in encrypted form in a file.
xiv. Number of writes to disk is lower/higher when a file is modified than when a
file is created
b. Compare and contrast (16 points)
i. Binary semaphore and general semaphore
ii. Semaphore and condition variable
iii. SSD and HDD
iv. Striping and Mirroring
v. Seek vs rotation delay in Hard Disk Drives
vi. Access control list vs Capabilities
vii. Internal fragmentation vs external fragmentation
viii. File creation vs File modification in Unix file system
2. Synchronization (30 points) .
a. (10 points) Implement operations on binary semaphores using test-and-set
instruction.
b. (20 points) A two way (two-lane) east-west road contains a narrow bridge with only one lane.
An eastbound (or westbound) car can pass over the bridge only if, when it arrives, there are no
oncoming cars on the bridge. Write the appropriate conditions in each of the IF statements in
enter and leave functions of the synchronization code, below, to achieve the necessary
synchronization that will prevent collisions. Note that two cars are allowed to cross the bridge
simultaneously provided that they are heading in the same direction. Are there any undesirable
consequences of this solution?
direction=enum{east,west}
int eastbound = 0, westbound = 0; // # of cars in each direction
mutex_t lock;
condition_t busy; //condition variable
cross (direction dir){
mutex_lock(lock)
// check for any cars already going in the opposite direction
if ( )
// wait on approp cond variable
_______________________
mutex_lock(lock)
// now increment counter of cars heading in my direction
if ( )
eastbound++;
else
westbound++;
// signal approp cond variable
________________________
mutex_unlock(lock)}
leave (direction dir) {mutex_lock(lock)
// if we’re the last car off heading east,
// signal all westbound traffic that it’s ok to proceed
if ( )
//signal approp variable
________________________________
// if we’re the last car off heading west,
// signal all eastbound traffic that it’s ok to proceed
if ( )
// signal approp cond variable
______________________________
mutex_unlock(lock)}
}
3. Memory management (20 points)
4. Virtual memory (30 Points)
a. (15 points) A system has 12 bit virtual address space and 256 bytes-pages. The Page
table is as shown (- indicates page is not in memory). For the following virtual
addresses: 9EF, 111, 700, 0FF, 212, indicate the corresponding physical address :
E
2
–
–
–
–
–
D
–
0
–
–
—
–
–
–
i. 9EF ➔
ii. 111➔
iii. 700➔
iv. 0FF➔
v. 212➔
b. (15 Points)
5. File Systems (30 points)
Contiguous linked indexed
a
b
c
d
e
f
6. Virtual Machines (10 points)
a. Explain why would it be useful to run different versions of the same operating system on
a given virtual machine
b. Explain why would it be useful to run different operating systems on a given virtual
machine