101清大資工計系[參考解答]

1. (8%) Consider the following C program

#include <stdio.h>
#include <unistd.h>

int value = 2;

int main()
{
    pid_t pid;
    
    do {
        /* fork a child process */
        pid = fork();
        
        if (pid == 0) { /* child process */
            value--; 
        }
        else { /* parent process */
            printf("parent: value = %d", value); /* line A */
            fork();
            execlp("\bin\ls");
            /* execlp() loads a new program into memory (destroying the memory image of the program containing the execlp() system call). */
        }
    } while(value >= 0);
    return 0;
}

(a) After the initial parent process creates the first child process (in the do-while loop), what is the output at line A? Justify your answer.
(b) Including the initial parent process, how many processes are created by the program? Justify your answer.

參考解答：(a) parent: value = 2 (b) 7

---

2. (10%) Consider a single-CPU system with the processes listed below.

Process	Arrival Time (seconds)	Average Burst Time (seconds)
$P_1$	0	5
$P_2$	10	4

Suppose both the burst time and the remaining time of each process are non-deterministic. The system runs the Shortest-Expected-Remaining-Time-First scheduling to allocate the CPU to processes. That is, the CPU is allocated to the process whose expected remaining time is shortest among all the processes. Suppose that the context-switch time is zero. Assume that the burst times of all these processes are exponentially distributed with their means shown in the above table.
Hint 1: The probability density function of an exponential random variable with mean $1 / \lambda$ is $f(t) = \lambda e^{- \lambda t}, t \geq 0.$ Its cumulative distribution function is $F(t) = 1 – e^{- \lambda t}, t \geq 0.$
Hint 2: A property of the exponential distribution is that it is memoryless. That is, for an exponential random variable $X$ and any positive constant $k, \, E[X – k | X > k] = E[X].$
(a) Given that $P_1$ completes after $P_2$ arrives, what is the average waiting time of $P_1?$ (The waiting time is the amount of time during which a process spends waiting in the ready queue.)
(b) Given that $P_1$ completes after $P_2$ arrives, what is the average turnaround time of $P_1?$
(c) What is the probability that $P_1$ completes after $P_2$ arrives?
(d) What is the average turnaround time for these processes?

參考解答：略

---

3. (8%) Consider a byte-addressable computer system with a 32-bit virtual address and total physical memory size 64GB. Let paging be implemented for the system with page size 1KB, and each page entry in the page table takes 4 bytes. Answer the following questions:

(a) If inverted page table is used, what is the memory space required for the page table?
(b) If one-level page table is used, what is the memory space required for the page table?
(c) Given a one-level paging, let the memory access time and TLB access time be 300ns and 20ns, respectively. If the TLB hit ratio is 95%, what is the effective memory access time?
(d) Let’s change paging to segmentation. Let the maximum segment size be 1GB. What is the maximum number of segments per process?

參考解答：(a) 256MB (b) 16MB (c) 335ns (d) 4

---

4. (10%) Answer the following questions regarding paging:

(a) What is thrashing? What is the reason for causing thrashing?
(b) Suppose there is only one process executed by CPU. Given a reference string “012034224”, if LRU is used with 3 available frames, which reference causes a page fault and which page is replaced when page fault occurs?
(c) What is the working set by the end of the above reference string if the working-set window size is 5?

參考解答：
(a) Thrashing occurs when the virtual memory of the system is overused, causing a constant state of paging and page-fault.
(b)

Reference string	0	1	2	0	3	4	2	2	4
Page fault	✓	✓	✓	✕	✓	✓	✓	✕	✕
Replaced page	–	–	–	–	1	2	0	–	–

(c) Working set = {2, 3, 4}

---

5. (4%) Consider an operating system which avoids deadlock by using banker’s algorithm. Assume the system has four types of resources A, B, C, and D. The total number of instances in the system for A, B, C, D is 4, 14, 14, 10, respectively. The following is a snapshot of the current system-state. (“Allocation” is the number of resource instances currently allocated to each processes. “Max” is the maximum number of instances that can be requested by each of the processes.)

	Allocation				Max
	A	B	C	D	A	B	C	D
$P_0$	2	3	4	4	2	3	5	6
$P_1$	0	3	1	2	3	6	5	6
$P_2$	0	0	1	2	0	0	1	2
$P_3$	1	4	3	0	4	7	5	0
$P_4$	0	1	3	2	0	9	5	2

If $P_3$ makes a request of (1, 3, 2, 0), can the request be granted immediately? Why?

參考解答：Yes, because we found a safe sequence: $P_2 \to P_0 \to P_3 \to P_1 \to P_4.$

---

6. (5%) For the following tree independent file systems, draw the final file system of U after the following two mountings:

(1) mounting S1:/user/shared over U:/user/local
(2) mounting S2:/user/dir2 over U:/user/local/dir1

參考解答：
(1)

(2)

---

7. (5%) Explain and compare the features of RAID level 0+1 and 1+0. For the following figure, explain what happends when RAID 0+1 has a single disk failure and RAID 1+0 has a single disk failure, respectively.

參考解答：In RAID 0+1, we first stripe then do the mirror, so when a single disk failure occurs, we cannot access with the mirror disk, while in RAID 1+0, we can access thru the mirror disk when a single disk failure occurs.

---

8. (10%) Hexadecimal (base 16) is a popular number system in computers. Hexadecimal numbers are often prefixed with 0x. Let x = 0xBA09 and y = 0x3456. Answer the following questions:

(a) If x and y represent 16-bit unsigned numbers, what is x + y in hexadecimal?
(b) If x and y represent 16-bit unsigned numbers, what is x – y in hexadecimal?
(c) If x and y represent 16-bit sign-magnitude numbers, where the most significant bit is the sign bit (1 means negative), what is x – y in hexadecimal?
(d) Why hexadecimal is popular among programmers, compared to other number systems?

參考解答：(a) 0xEE5F (b) 0x85B3 (c) -0x6E5F
(d) Computer count in binary. Converting from binary to our normal base 10 is not easy while converting binary to hexadecimal is easy.

---

9. (10%) When each corresponding stage of the CPU shown below is executing the load instruction “lw \$s1, 4(\$t0)”, the following control values should be:

參考解答：1 / 0 / 0 / 0 / Off

---

10. (8%) Given a 32-bit machine, determine the values of the labels ELSE and DONE of the following segment of instructions. Assume that the first instruction is loaded into memory location 8000$_{hex}.$

      slt $t2, $t0, $t0    # set if less than
      bne $t2, $zero, ELSE # branch if not equal
      j DONE               # jump to
ELSE: addi $t2, $t2, 2     # add immediate
DONE: ...

參考解答：ELSE: 800C$_{hex},$ DONE: 8010$_{hex}.$

---

11. (12%) Consider a 4-way set-associative write-back cache with 8-byte blocks in a processor that uses 32-bit addresses for a byte-addressable memory. Suppose the cache uses 6-bit indices.

(a) Explain how the write-back strategy is implemented.
(b) How many sets are there in the cache?
(c) How many bits are there in each cache tag?
(d) How many bits of storage are required to implement the cache (which include all data, tag, and control items)?

參考解答：
(a) When data is updated, it is written only to the cache. The modified data is written to the back-end storage only when data is removed from the cache.
(b) 64 sets
(c) 23 bits
(d) 22784 bits

---

12. (10%) MTBF stands for Mean Time Between Failure, MTTR stands for Mean Time To Repair, and MTTF stands for Mean Time To Failure. These three metrics are important for evaluating reliability and availability of storage devices. Answer the following questions:

(a) Define MTBF, MTTR, and MTTF.
(b) Considering a disk with an MTTF of 1 year and an MTTR of 1 day, compute its MTBF.
(c) Following the previous question, what’s the availability of this disk?
(d) What’s the implication as the MTTR approaches 0? Describe a technique in disk arrays that may result in very low MTTR.

參考解答：
(a) MTBF = MTTR + MTTF
(b) 8784HR
(c) $\text{Avail} = \dfrac{365}{366} \approx 0.99$
(d) When MTTR approches 0, the availability will approch to 100%. RAID 5.

---

試題(pdf)：連結

有任何問題，或想要完整解釋的，歡迎在下方留言唷！