私立中原大學八十八學年度研究所招生考試命題紙

所組別 :資訊工程學系 科目 :系統程式 考試時間 : 05月01日第4節
一.Please answer the following deadlock questions. (14%)
  1. Please list four necessary conditions for the deadlock. (4%)
  2. Is it possible to have a deadlock involving only one single process? Why? (3%)
  3. Why recovery from deadlock is made difficult? (4%)
  4. List one example of deadlock that is not related to a computer system environment. (3%)
二.Consider the reference page sequence is 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, and the number of page frames is 4. (9%)
  1. How many page faults for FIFO algorithm? (3%)
  2. Suppose we decrease page frames to 3, how many page faults for FIFO algorithm? (3%)
  3. What phenomenon will occur? (3%)
三.Under ETHERNET topology, stations use CSMA/CD method to send message. (8%)
  1. What is CSMA/CD? (4%)
  2. It needs 2t time to detect whether the message collision with the others, why? (4%)
四.How should a programmer decide whether to use a macro or a function to accomplish a given logical function? (6%)
五.Consider the precedence matrix and grammar of operator precedence parser. (14%)

Grammar G(E) :

Precedence Matrix :


  1. Parse the id + id * id and also show the parsing tree. (6%)
  2. Parse the id * id id. (4%)
  3. Is the grammar G(E) an unambiguous? Why? (4%)
六.Please answer the following multilevel feedback queue scheduling questions. (18%)
  1. Explain the multilevel feedback queue algorithm. (6%)
  2. What advantage is there in having different time slice on different levels? (3%)
  3. What would be the effect of setting the time slice at a very large value? (3%)
  4. What if the time slice is set to a very small value? (3%)
  5. What would be the effect of CPU bound processes? (3%)
七.Several new operating systems provide thread facility, and also provide traditional process facility. (16%)
  1. Describe the differences between thread and process. (6%)
  2. What major disadvantage do threads have? (3%)
  3. Give one example that would benefit from the use of threads, and one that would not. (4%)
  4. User level threads are faster to switch among than kernel threads, why? (3%)
八.The bakery algorithm is shown in the following. (15%) 

	choosing[i]:=true;
	number[i]:=max(number[0],number[1], …, number[n-1])+1;
	choosing[i]:=false;
	for j:= 0 to n-1
   		do begin
        		while choosing[j] do no-op;
        		while number[j]<>0 and (number[j],j) < (number[i],i) do no-op;
      		end;
   	CRITICAL SECTION
   	number[i]:=0;
  1. Please explain this algorithm. (8%)
  2. List three requirements to solve the critical section problem. (3%)
  3. Prove the bakery algorithm is correct. (4%)

--- END---