NEW MEXICO STATE UNIVERSITY
Department of Computer Science

Operating Systems Qualifying Examination
January 11th, 1999 -- 12-16pm

1. It should be possible to implement general semaphores using binary semaphores. We can use the operations waitB and signalB and two binary semaphores, delay and mutex. Please consider the following example:

procedure Wait(var s, semaphore);
	begin
	WaitB(mutex);
	s = s -1;
	if s < 0 then begin
		SignalB(mutex);
		WaitB(delay);
	end;
	else
		SignalB(mutex);
end;

procedure Signal(var s: semaphore);
	begin
	WaitB(mutex);
	s = s + 1;
	if s ¾ 0 the SignalB(delay);
	SignalB(mutex);
end;

At first, s is set to the desired semaphore value. Each Wait decrements the semaphore s, and each Signal increments it. The binary semaphore mutex, which is initially set to 1, assures that we have mutual exclusion for the operations on s. The binary semaphore delay, which is initialized to 0, is used to suspend processes. Looks great - eh? Well, there is a serious flaw in the code provided above. Your task is to find and explain the flaw and then to suggest the change in the code that will remedy it. Hint: The number of lines of code that must be changed is quite small.

2. We generally agree that the following are valid reasons to use threads in processes.

a.

there is less work involved in creating a new thread in a process than "forking" another process

b.

communications between threads within a process are simpler than communications between processes

Please describe at least two other reasons that threads are an attractive alternative to "forking" off new processes.

3. Consider a UNIX file system represented by the following skelital INODE:

	file name
	date created
	date modified
	...
	block 0 pointer (direct)
	block 1 pointer (direct)
	...
	block 11 pointer (direct)
	singly indirect block pointer
	doubly indirect block pointer
	triply indirect block pointer

Assume also that the disk sector and block sizes are both 8K. If the disk pointers are 32-bits with 8 bits to identify the physical disk and 24 bits to identify the physical block, then

1)

what is the largest file size supported?

2)

assuming that no information other than the file inode is already in main memory, how many disk accesses are required to access the byte at location 13,423,956 in the file?

3)

what is the max partition size supported?

4. What sorts of file organization would you choose to get the best speed of access, use of storage and ease of updating when the data are

1)

updated infrequently and accessed frequently in random order?

2)

update frequently and accessed relative infrequently?

3)

updated frequently and accessed frequently in random order?

5. Most round robin schedulers used fixed size quanta.

1)

Give an argument in favor of small quantum.

2)

Give an argument for large quantum

3)

What types of systems and jobs benefit by each of the above?

4)

Are there any for which both would work well?