Description
1 Part 1: OS overview and system calls
11 1. (5%) Some OS like Palm OS provides no means of concurrent processing. Briefly discuss three
12 major complications (in a bullet format) that concurrent processing adds to an operating
13 system.
14 2. (10%) In the following example, assume all system and library calls complete without error.
15 #define OUTPUT printf(‘‘%d ’’, i)
16
17 main() {
18 int i=10; OUTPUT;
19
20 if (fork()) {
21 i+=5; OUTPUT;
22 } else {
23 i+=3; OUTPUT; return(0);
24 }
25 }
26 (a) Please write down all possible outputs when running this program.
27 (b) Add one system call in the pseudo code to ensure that the output values are always in
28 increasing order.
1
29 2 Part II: IPC, Process Synchronization and CPU schedul30 ing
31 3. (5%) How does the signal() operation associated with monitors differ from the corresponding
32 operation defined for semaphores?
33 4. (15%) Consider a system consisting of processes P1, P2, . . . , Pn, each of which has a unique
34 priority number. Write the pseudo-code of a monitor that allocates three identical line printers
35 to these processes, using the priority numbers for deciding the order of allocation.
36 5. (15%) A clinic consists of a waiting room with n chairs and a doctor. If there is no patient to
37 be served, the doctor becomes idle. If a patient comes to the clinic and all chairs are occupied,
38 the patient leaves the clinic. If the doctor is busy but chairs are available, the patient sits in
39 one of the free chairs. Of course, we require that the doctor cannot be idle if there are waiting
40 patients. Write the pseudo-code to coordinate the doctor and the patients.
41 3 Part III: File Systems
42 6. (5%) Assume we are using the Rhinopias disk drive discussed in class (refer to the lecture
43 slides for specification).
44 (a) What is the maximum transfer rate for a single track?
45 (b) What is the maximum transfer rate for accessing five tracks consecutively (assume head
46 skewing)?
47 7. (5%) Would log-structured file systems have been feasible in the early 1980s when FFS was
48 designed? Explain. (Hint: Consider the motivation of log-structured F.S.)
49 8. (5%) Explain how renaming a file can be done using the consistency-preserving approach so
50 that a crash will not result in the loss of the file. Be sure to take into account the link count
51 stored in the file’s inode. Note that there may have to be a temporary inconsistency; if so,
52 explain why it will not result in lost data.
53 9. (5%) What are your recommendations if you were required to support long file names in
54 FAT12?
55 4 Part IV: Main Memory and Virtual Memory
56 10. (5%) Explain the difference between internal and external fragmentation.
57 11. (5%) Given five memory partitions of 100 KB, 500 KB, 200 KB, 300 KB, and 600 KB (in
58 order), how would each of the first-fit, best-fit, and worst-fit algorithms place processes of 212
59 KB, 417 KB, 112 KB, and 426 KB (in order)? Which algorithm makes the most efficient use
60 of memory?
61 12. (5%) Assuming a 1 KB page size, what are the page numbers and offsets for the following
62 address references (provided as decimal numbers):
2
63 (a) 2375
64 (b) 19366
65 (c) 30000
66 (d) 256
67 (e) 16385
68 13. (5%) Explain why we need Inverted Page Tables and how they work?
69 14. (10%) A computer whose processes have 1024 pages in their address spaces keeps its page
70 tables in memory. The time required for one word reading via the page table is 10 nsec. To
71 reduce the access time, the computer uses a TLB. The time required for one word reading
72 via the TLB is 3 nsec, which includes 1 nsec for TLB lookup. If we assume there are no page
73 faults, what TLB hit rate is needed to reduce the mean one word reading time to 5 nsec?
3
