2002년 1학기 기말고사.

1. race condition 에 대해 설명하시오.

2. Java 를 이용하여 다음 class를 완성하시오.

• countable semaphore class 를 구현. 단, default 생성자에서 세마포어 값은 0으로 설정.
  
• 앞에서 완성된 class를 상속받아서 binary semaphore class 를 구현.
  
  

3. 다음 코드를 수행시 나타날 수 있는 문제점에 대해 자유롭게 기술하시오.

~cpp 
class Mutex
{  }

class A extends Thread
{
	private Mutex first, second;

	public A(Mutex f, Mutex s) {
		first = f;
		second = s;
	}

	public void run () {
		synchronized (first) {
			// do something
			try {
				Thread.sleep(( (int)(3*Math.random()) )*1000);
			}
			catch (InterruptedException e) { }
			System.out.println("threadA got first mutex");
			synchronized (second) {
				// do something
				System.out.println ("threadA got second mutex");
			}
		}
	}
}

class B extends Thread
{
	private Mutex first, second;

	public B(Mutex f, Mutex s) {
		first = f;
		second = s;
	}

	public void run () {
		synchronized (second) {
		// do something
		try {
			Thread.sleep(( (int)(3*Math.random()) )*1000);
		}
		catch (InterruptedException e) {} 
		System.out.println ("threadB got second mutex");
		synchronized (first) {
			// do something
			System.out.println ("threadB got first mutex");
		}
	}
}

public class TestProgram
{
	public static void main (String[] args) {
		Mutex mutexX = new Mutex ();
		Mutex mutexY = new mutex ();

		A threadA = new A(mutexX, mutexY);
		B threadB = new B(mutexX, mutexY);

		threadA.start ();
		threadB.start ();
	}
}

4. Consider a paging system with the page table stored in memory.

• If a memory reference takes 200 nanoseconds, how long does a paged memory reference take?
  
• If we add associative registers and 75 percent of all page-table references are found in the associative regsters, what is the effective memory time? (Assume that finding a page-table entry in the associative registers takes zero time, if the entry is there)
  
  

5. Consider the following page reference string:
How many page faults would occur for the following replacement algorithm, assuming one, three, five, seven frames? Remember all frames are initially empty, so your first unique pages will all cost one fault each.

• LRU replacement
  
• FIFO replacement
  
• Optimal replacement
  
  

6. Consider a file currently consisting of 100 blocks. Assume that the file control block(and the index block, in the case of indexed allocation) is already in memory, Calculate how many disk I/O operations are required for contiguous, linked and indexed (single-level) allocation strategies, if for one block, the following conditions hold. In the contiguous allocation case, assume that there is no room to grow in the beginning, but there is room to grow in the end. Assume that the block information to be added in stored in memory.

• The block is added at the beginning.
  
• The block is added in the middle.
  
• The block is added at the end.
  
• The block is removed from the beginning.
  
• The block is removed from the middle.
  
• The block is removed from the end.
  
  

7. Suppose that a disk drive has 5000 cylinders, numbered 0 to 4999. The drive is currently serving a request at cylinder 143, and the previous requrest was at cylinder 125. The queue of pending requests, in FIFO order, is

86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130

Starting from the current head position, what is the total distance (in cylinders) that the disk arm moves to satisfy all the pending requrests, for each of the following disk scheduling algorithms?

• FCFS
  
• SSTF
  
• SCAN
  
• LOCK
  
• C-SCAN