Sample Final Exam	Comp 374	Dordal	Fall 2000

The final exam is 10:20 am, Wednesday May 13, in our usual room.

The exam will cover the following sections; starred* sections are the most 
important.

Chapter 8: synchronization basics
 	8.3 semaphores (yes, this was on the midterm, but it overlaps with ch9)

Chapter  9: synchronization
	9.1 (alternative synchronization)
	9.2* Monitors
	Synchronization in Java*
		wait(), notify(), notifyall(), synchronized
	9.3 Message passing (especially 9.3.2)
Chapter 10: deadlock
	10.1 Basics
	10.3* Prevention
	10.4* Avoidance: Banker's algorithm
	10.5.1* Detection (reusable resources only)
Chapter 11: Memory management
	11.2: older (pre-VM) schemes
	11.3 relocation registers
	11.4.2* Virtual memory
	11.4.3* shared memory issues
Chapter 12: Virtual memory
	12.1* 12.2*: basics, page tables, etc
	12.3* replacement policies (OPTIMAL, LRU, FIFO, clock)
	12.4.2* clock algorithm (ignore the "working set" stuff)
Chapter 13: Files
	13.2.2* block management: linked, indexed, FAT, unix
	Unix* (p 379): inodes, direct, single indirect, double indirect
	13.5 directories
Chapter 14: Security
	We covered little bits of this:
	14.3.1: protection model in terms of subjects and objects
	14.4.2.2: Access Control Lists
	unix setuid bit
	privileged service/daemon software acting on your behalf

======================================================

1. Why are page sizes always a power of 2?


2. Suppose a computer has five physical pages and a process uses
seven virtual pages in the following order:

	1 2 3 4 5 2 6 7 6 5 4 3 2 1

Give the number of page faults, and which page is brought in,
for FIFO, LRU, and CLOCK page replacement schemes. For CLOCK,
indicate where the pointer is, and the state of the use bit.


3. Suppose a 512x512 matrix is loaded into memory. 
Each entry is 4 bytes; the page size is 4KBytes. 
The array is stored in row-major order; that is, the 2KB rows
of the matrix follow one another in memory.

Give the number of page faults if:
(a). There is *one* free physical page, and the matrix is traversed
row by row: 
    for (row=0; row<512; row++) 
        for (col=0; col<512; col++)
            A[row,col]=0; 
(b). There is one free physical page, but we traverse col by col.
(c). There are 500 free physical pages, and we traverse col by col.


4. Draw a picture of the page tables of processes A, B, and C
if A asks for 2 pages, B asks for 3 pages, A asks for 1 more page, 
C asks for 4 pages, and A asks for 1 more page again. 
Is A's virtual memory fragmented?


5. Use a monitor and two condition variables, A and B,
to cause three threads to print out their messages in sequence:
	thread1
	thread2
	thread3

P1() {                  P2() {                 P3() {


    print("thread1");       print("thread2");       print("thread3");


}                       }                      }

Hint: have P2 wait for A (ie call wait(A) or A.wait()) 
and P3 wait for B.


6. Do the safe-state exercise #2 on page 280.


7. Suppose in a Unix system that an inode contains 10 pointers 
to direct blocks, and an indirect block has room for 256 block 
pointers.
(a) How many data blocks would there be in the largest file 
with no double indirect blocks?
(b) How many data blocks would there be in the largest file 
with no triple indirect blocks?
(c). Draw a sketch of the layout of a 20-block file.


8. A professor plans to have students submit project directories
electronically, by copying them into a "submit" directory.
Explain in detail the permissions that would be necessary 
in order for this to work and so that the following would hold:
  * the submitting student would still own the file
  * the professor should be able to read and delete the files 
  * other students should neither be able to read nor delete the files

(b). Why is this very hard on a Unix filesystem?


9. When you move a file from one location to the other using the Unix
"mv" command, a link is established in the new location and then
the old link is removed.
(a). What happens if Unix crashes in between the link and unlink?
(b). What would happen if "mv" did the unlink first and then the link,
and the system crashed in between?


10. Determine the deadlocked processes, if any, in exercises #6 and #7
on page 281.


11. For a unix-like filesystem, describe the differences between
the following two calls:
	open(char * filename)	// returns an int file descriptor
      read(int FD, char * buf, int size);
Assume that the read() corresponds to exactly one disk block
of data. What disk operations are involved in each case?