| 1. |
What are the differences between the following pairs?(12%) |
| |
1) |
External fragmentation, Internal fragmentation |
| |
2) |
Thread, Process |
| |
3) |
Deadlock, Starvation |
| |
|
|
| 2. |
Consider the single CPU computer, please answer the following
questions.(14%) |
| |
1) |
Draw a diagram of Process State.(4%) |
| |
2) |
Explain the transitions between each state.(4%) |
| |
3) |
Which kinds of data structure are used for each state?(3%) |
| |
4) |
How many processes would stay at each state for any instant?(3%) |
| |
|
|
| 3. |
Please answer the following questions.(12%) |
| |
1) |
What is the File Allocation Table (FAT)? |
| |
2) |
What is the i-node? |
| |
3) |
Which of the following file allocation methods is used for
each of the FAT and i-node? (Contiguous allocation, Linked allocation, Indexed
allocation) |
| |
|
|
| 4. |
The algorithm uses the test-and-set instruction is shown in
the following.(12%) |
| |
waiting[i] = true;
key = true;
while(waiting[i] and key) do key = test-and-set(lock);
waiting[i] = false; |
|
| |
|
CRITICAL SECTION |
| |
j=i+1 mod n;
while ((j<>i) and (not waiting[j])) doj=j+1 mod n; 
if j=i then
lock=false;
else waiting[j]=false; |
|
| |
1) |
Please give the comments for each . |
| |
2) |
Can we remove waiting[i]=true statement? Why? |
| |
3) |
Can we remove waiting[i]=false statement? Why? |
| |
4) |
Prove the algorithm is correct. |
| |
|
|
| 5. |
Consider a six-stage pipeline for a load/store machine, the
six stages and the associated functions are listed below.(15%) |
| |
| Stage |
Operation |
| IF |
instruction fetch |
| ID |
instruction decode |
| RF |
register fetch |
| EX |
ALU operation |
| MEM |
memory access for load/store |
| WB |
write the result into register |
|
| |
1) |
Identifies all possible hazards in the following program segment: |
| |
 |
| |
2) |
How to solve the hazards found in 1)? |
| |
|
|
| 6. |
Consider a virtual memory system with the following properties:38-bit
virtual byte address, 8-KB pages, 32-bit physical byte address.(15%) |
| |
1) |
What is the total size of the page table for each process
on this machine, assuming that the management related information take a
total of 5bits and that all virtual pages are in use? (Assume that disk
addresses are not stored in the page table.) |
| |
2) |
How can we have a cache with size 32-KB if we wish address
translation is performed in parallel with cache access? |
| |
3) |
What performance factor(s) is(are) affected in your solution? |
| |
|
|
| 7. |
Given a computation algorithm as follows, express
the algorithm using algorithmic-state-machine(ASM) chart, design a datapath
for the algorithm with control input(s) and status signal(s) identified,
and devise the state transition diagram for the corresponding control unit.(10%) |
| |
|
 |
| |
|
|
| 8. |
Given the state transition diagram of a control
unit as follows, implement the control unit with microprogramming method.
Your answer should include the microinstruction format, the microprogram,
and the logic diagram of the circuit.(10%) |
| |
|
| |
|
|
|
--- END ---
|
