中原大學九十一學年度碩士班入學招生考試

91年 4月12日　14:00 ~ 15:30　　資工系 誠實是我們珍視的美德，
我們喜愛「拒絕作弊，堅守正直」的你！
科目：計算機系統  

一、作業系統
 
1.
 (6%) There are two kinds of kernels in operating systems: micro kernel and monolithic kernel. Micro kernel provides as few services as possible while monolithic kernel provides most services itself. List and explain the advantages of each kernel.
 
2.
 (10%)
(a) List and explain at least four shared-variable methods for synchronization.
(b) List and explain at least three message passing methods for synchronization.
(c) Explain why synchronization in distribute systems is based on message passing.
 
3.
 A process can allocate and de-allocate memory from its heap using malloc() and free() in most systems. When malloc() is called, the heap is searched for a free and big enough segment that is then divided into an allocated segment (at the beginning) and a free segment. When free() is called, the corresponding segment should merge with its neighboring segments, when they are free.
(a)(8%) Now suppose a process has an initially empty heap of 17KB. The process issues the following memory calls (pi is a pointer):

p1 = malloc(5KB)
p2 = malloc(6KB)
p3 = malloc(3KB)
free(p2)
p4 = malloc(2KB)
free(p3)
p5 = malloc(2KB)
Show what the heap is like after the above calls, using best-fit and worst-fit algorithms respectively.
(b)(6%) Give the drawbacks of the best-fit and worst-fit algorithms. Can these drawbacks be identified from part a) above?
(c)(4%) What will happen if the process issues the following calls after those in part a) above?

p6 = malloc(3KB)
p7 = malloc(5KB)
 
4.
 Suppose that we have 5 processes for execution. The priority, arrival time, and behavior of each process is in the following table:
 
All the time in this problem is given in milliseconds. Process P1 consists of a period of CPU computation (3ms), followed by a period of I/O operation (6ms), and then a period of CPU computation(3ms). Scheduling decisions are made based on the information available at the time that the decisions must be made.
(a)(8%) Give two Gantt charts to illustrate the scheduled execution of these processes using

(i) Round Robin (quantum = 2 ms) and

(ii) preemptive priority (a smaller priority number implies a higher priority).
(b)(8%) Calculate the average turnaround time for every process under each of the scheduling algorithms in part a) above.
 
 
二、計算機組織
 
5.
 (5%) Design a sign-magnitude-to-2's-complement converter which takes a 4-bit sign-magnitude number as input and gives a 4-bit 2's complement number as output.
a. Construct the truth table for the converter.
b. Find the minimized Boolean expression for each output bit.
 
6.
 (15%) Design a digital circuit which computes the sum of a stream of input numbers and counts the number of input received.
a. Develop an algorithm for the processing procedure.
b. Design a simple datapath with control signals identified.
c. Define the controller using finite-state machine and give an implementation.
 
7.
 (10%) Consider a 2-way set associative cache with 8 1-word blocks that is initially empty. Here is a series of address references given as byte addresses: 0, 12, 16, 20, 32, 8, 20, 0, 52, 60. Label each reference in the list with the cache block number where the data is stored and the tag of the block as well as whether the reference is a hit or a miss.
 
8.
 (20%) Consider a 7-stage pipeline of a load-store machine:
Assume all data forwarding circuits are presented. Given the following code fragment, illustrate, using timing diagram, how each instruction progress the pipeline until the execution leaves the loop. Identify all the hazards and indicate how they are resolved in your answer.

--- END---