中山大学2011年操作系统 期末考试题A

中山大学软件学院2009级软件工程专业（2010学年春季学期）

《SE-223操作系统》期末考试试卷（A）

(考试形式：闭卷考试时间:2小时)

考试作弊不授予学士学位

方向：姓名：______ 学号：

一、 E xplain following terms（15 pts）

Cache coherency, PCB (Process Control Block), Medium-term scheduling, VFS (Virtual File System), DMA (Direct Memory Access)

二、 S hort Answer（25 pts, select 5 from 6）

1.List at least two advantages of User-Level Thread over Kernel-Level Thread.

2.What are the four necessary conditions of deadlock? Please briefly describe the

meaning of each condition.

3.List and briefly describe three common schemes for defining the logical structure of

a directory.

4.What is the difference between simple paging and virtual memory paging?

5.What are the three major methods of allocating disk space? Describe their

advantages and disadvantages respectively.

6.List three basic process states and describe the meaning of each state.

三、 C onsider the following page reference string:

1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6.

How many page faults would occur for the following replacement algorithms, assuming two or three frames? All frames are initially empty.（15 pts）

（1）LRU replacement（5 pts）

（2）FIFO replacement（5 pts）

（3）Optimal replacement（5 pts）

四、 C onsider a simple paging system with the following parameters: 232bytes of physical

memory; page size of 210 bytes; 216 pages of logical address space.（10 pts）

（1）How many bits are in a logical address?（2 pts）

（2）How many bytes in a frame?（2 pts）

（3）How many bits in the physical address specify the frame?（2 pts）

（4）How many entries in the page table?（2 pts）

（5）How many bits in each page table entry? Assume each page table entry contains a valid/invalid bit.（2 pts）

五、 F ive batch jobs, A through E, arrive at a computer center at essentially the same time. They

have an estimated running time of 15, 9, 3, 6, and 12 minutes, respectively. Their priorities are 6, 3, 7, 9, and 4 respectively, with a lower value corresponding to a higher priority. For each of the following scheduling algorithms, determine the turnaround time for each process and the average turnaround for all jobs. Ignore process switching overhead. Explain how you arrived at your answers. In the last three cases, assume that only one job at a time runs until it finishes and that all jobs are completely processor bound.（20 pts）

（1）round robin with a time quantum of 1 minute;（5 pts）

（2）priority scheduling;（5 pts）

（3）FCFS (run in order A, B, C, D, and E);（5 pts）

（4）shortest job first.（5 pts）

六、 J urassic Park consists of a dinosaur museum and a park for safari riding. There are m

passengers and n single-passenger cars. Passengers wander around the museum for a while, then line up to take a ride in a safari car. When a car is available, it loads the one passenger it can hold and rides around the park for a random amount of time. If the n cars are all out riding passengers around, then a passenger who wants to ride waits; if a car is ready to load but there are no waiting passengers, then the car waits. Use semaphores, wait() and signal() to synchronize the m passenger processes and the n car processes.（15 pts）