| 1. |
(10%)What are the differences between process
and thread? Please give two kinds of applications that use multithreads. |
| |
| 2. |
(15%)What is the page thrashing? To
prevent page thrashing, there are several solutions such as decrease the
degree of multiprogramming, provide a process as many frames as it needs,
… etc. Please describe the theoretical strategy (model) which looks at how
many frames a process is actually using. |
| |
| 3. |
(10%)Please describe buffering by using terminology
of logical record, physical record, block, buffer, sector, …etc. |
| |
| 4. |
(15%)The bakery algorithm is used to solve critical
section problem for n processes, which is shown in the following. Where
compare(number[j], number[i]) means if ((number[j] < number[i]) or (number[j]
= number[i] and Pj < Pi ). Please |
| |
a) |
Describe the bakery algorithm. |
| |
b) |
Prove the algorithm is correct. |
| |
c) |
Can we remove choosing[i]=true; choosing[i]=false;
while choosing[j] do no-op; statements? Why? |
| |
|
choosing[i] = true;
number[i] = max(number[0],number[1],…,number[n-1] )+ 1;
choosing[i] = false;
for j = 0 to n-1
{
while choosing[j] do no-op;
while（number[j] < > 0 and
compare(number[j],number[i])）do no-op;
}
|
|
| |
CRITICAL SECTION
|
| |
|
|
| |
|
| |
| 5. |
(15%) |
| |
a) |
List 4 architecture styles. For each of them
describe its characteristics in terms of operand locations and operating
style, and illustrate the idea using simple diagram. |
| |
b) |
Assume that instructions are an integral number
of bytes in length. The opcode is 1 byte. Memory access use direct addressing.
All variables are in memory initially. |
| |
|
i |
Invent your own assembly language mnemonics,
and for each architecture write the best assembly language code for the
following high-level language code sequence
A = A+B;
C = A-D; |
| |
|
ii |
Assume the memory address and the data operands
are both 16 bits in length. And, there are 16 registers for architecture(s)
with many general-purpose registers. For each architecture, answer the following
questions: How many instruction bytes are fetched? How many data bytes are
transferred between memory and the processor? |
| |
|
|
|
| 6. |
(10%) Dynamic scheduling allows hardware to rearrange
the instruction execution to reduce stalls while maintaining data flow and
exception behavior. Point out the main issues to be considered in designing
a scheme to realize the idea. |
| |
| 7. |
(15%) A processor is equipped one-cycle
delayed branch. The latencies of operations is listed below: |
| |
|
| Instruction
producing result |
Instruction
using result |
Latency in
clock cycles |
| FP ALU op |
Another FP ALU op |
2
|
| FP ALU op |
Store double |
1
|
| Load Double |
FP ALU op |
2
|
| Load double |
Store double |
0
|
| Integer ALU op |
Integer ALU op, load, or store |
0
|
|
| |
|
| |
Given the following code sequence |
| |
| Loop: |
L.D |
F2, 0(R1) |
|
L.D |
F4, 0(R2) |
|
ADD.D |
F0, F2, F4 |
|
S.D |
F0, 0(R1) |
|
DADDUI |
R1, R1, #-8 |
|
DADDUI |
R2, R2, #-8 |
|
BNE |
R1, R3, Loop |
|
| |
a) |
Show how the loop would
be executed without any optimization. |
| |
b) |
Try to optimize the performance
with loop unrolling using least number of copies. |
| |
|
| |
|
| 8. |
(10%) What are the three categories of cache
miss? For each of them use a simple example to demonstrate how it occurs,
list a reduction technique and discuss in detail how the technique works
and what are the drawbacks. |
| |
|
--- END---
|