| 所組別： | 資訊工程學系 | 科目： | 作業系統 | 考試時間： | 4月29日第4節 |
| 一、作業系統 |
| 填充題(20分) (答案請書寫於答案卷上) |
| 1. | One measure of work is the number of processes that are completed per time unit, called __________________ . |
| 2. | The interval from the time of submission of a process to the time of completion is called __________________ . |
| 3. | A deadlock situation can arise if the following four conditions hold simultaneously in a system: a) Hold and wait, b) No preemptive, c) _______________ and d) __________________ . |
| 4. | Segmentation causes __________________, when all blocks of free memory are too small to accommodate a segment. |
| 5. | A process is __________________ if it is spending more time paging than executing. |
| 6. | The job scheduler selects processes and loads them into memory for execution, while the _________________ scheduler selects from among the processes that are ready to execute, and allocates the CPU to one of them. |
| 7. | A _________________ process uses more of its time doing computation than generates I/O requests. |
| 8. | A solution to the critical-section problem must satisfy the following three requirements a) progress, b) _________________, and c) _________________ |
| 問答題(30分) |
| 1. |
Consider a paging system in which main memory has a capacity of three
pages.The execution of a program Q requires reference to five distinct pages Pi, where I
= 1, 2, 3, 4, 5, and i is the page address. The page address stream
(string) formed by executing Q is |
| Assume that the above twelve references occur at the times t1, t2, ? t12. | ||
| a) | Show which pages are in memory (page frames) during each of the time slots if FIFO page replacement is used? How many page faults and page hits occur during the 12 time slots. | |
| b) | Same as above, but for Optimal page replacement? | |
| 2. | Consider the following 3-process concurrent program which uses semaphores S1, S2, and S3.The semaphore operation, which are sometimes called “wait” and “signal”, are denoted here with the classical notation of “P” and “V”. |
| Process 1 | Process 2 | Process 3 | |
| L1:P(S3); | L2:P(S1); | L3:P(S2); | |
| print(“T”); | print(“U”); | print(“B”); | |
| V(S2); | V(S3); | V(S1); | |
| goto L1; | gotoL2 | goto L3; |
| a) |
Are there initial values that can be given to the semaphores so that the
processes cooperate to print the string BUTBUTBUTBU? If so, give the initial values (tell which value is to be used for which semaphore) and explain how the string is printed. |
b) | Suppose the initial values are S1=0, S2=0, S3=0. Is it possible for the processes to cooperate to produce a string that begins with BBTTUTT? Explain your answer. |
| 3. | Consider two processes P & Q running under control of a multiprogrammed operating system. Process P produces data and attaches the data item to a buffer (linked list) L. Process Q consumes (removes) the data items from the buffer L. Is there any problem if no process synchronization mechanism is used? |
| 二、計算機組織 |
| 簡答題(20分) |
| 1. | In what aspect are the Intel Pentium II processors and the AMD K-6 processors the same, and in what aspect are they different? |
| 2. | What is the issue, besides functionality and cost, that concerns a computer designer the most? To give a fair comparison between processors of different design, what are the factors that can be used to measure it quantitative? For each of the factors, briefly describe one event that would change the quantity of the factor. |
| 3. | How does pipelining improve performance in processor design? What determines the ideal speedup? What are the situations making a pipelined processor unable to obtain the ideal speedup? Illustrate each of the situation by a short example. |
| 4. | What is the problem that causes the development of memory hierarchy? Illustrate by examples the four different aspects of the principle which makes memory hierarchy a practical solution to the problem. |
| 問答題(30分) |
| 1. | The Booth’s algorithm that looks at 3 bits in performing multiplication is as follows: | |
| a. | Depending on the current and previous bits, do one of the following: | |
| 00 : no arithmetic operation | ||
| 01 : add multiplicand to the left half of the product | ||
| 10 : subtract multiplicand from the left half of the product | ||
| 11 : no arithmetic operation. | ||
| b. | Shift the product register right 1-bits. | |
| Design a multiplier circuit executing the algorithm by following the guidelines as follows: | ||
| 1) | Give a complete specification of the behavior of the multiplier using register transfer level description. | |
| 2) | Design the datapath accordingly. | |
| 3) | Derive the state transition diagram of the control unit. | |
| 4) | Implement the control unit as a microprogrammed control unit. (Describe the structure of the control unit, a format of the microcode and the corresponding microprogram.) | |
| 5) | Implement the control unit as a state machine using edge-triggered D flip-flop for the state variables. (Give the state/output table and Boolean expressions for the excitation logic.) | |
| 2. | Consider a six-stage pipeline for a load/store machine, the six stages and associated functions are listed below, |
| Stage | Operation | |
| IF | instruction fetch | |
| ID | instruction decode and register fetch | |
| EX1 | 1st cycle to perform ALU operation | |
| EX2 | 2nd cycle to perform ALU operation | |
| MEM | memory access for load/store | |
| WB | write the result into register |
| 1) | Identifies all possible hazards in the following program segment: |
| TARGET: | Sub $R1,$R1,$R2 | ;$R1=$R1-$R2 | |
| Add $R3,$R1,$R2 | ;$R3=$R1+$R2 | ||
| Store 8($R1),$R3 | ; M[$R1+8]=$R3 | ||
| Load $R4,100($R1) | ; $R4 =M[$R1+100] | ||
| Bnez $R1,Target | ; if$R1≠0 goto TARGET | ||
| Add $R6, $R4,$R5 | ; if $R1≠0 goto TARGET |
| 2) | How to solve the hazards found in 1)? |