注：本教材为安德鲁 S.塔嫩鲍姆的《现代操作系统》（第4版），汤书可供参考。

第一章

一. 多选题（共1题，0.5分）

1. (多选题, 0.5分)

Which of the following instructions should be allowed only in kernel mode？

• A.

  Disable all interrupts

  
  

  
  

• B.

  Read the time-of-day clock

  
  

  
  

• C.

   Set the time-of-day clock

  
  

  
  

• D. Change the memory map

正确答案: ACD

二. 简答题（共5题，1.5分）

2. (简答题, 0.3分)

What are the two main function s of an operating system?

• 正确答案：

• OS as an extended machine.

  OS as a resource manager.

3. (简答题, 0.3分)

What is a trap instruction? Explain its use in operating systems.

• 正确答案：

• Trap is an instruction from the internal of CPU. A trap is caused by the program and is synchronous with it. If the program is run again and again, the trap will always occur at exactly the same position in the instruction stream.

4. (简答题, 0.3分)

What is the difference between kernel and user mode?

• 正确答案：

• In kernel mode, it has complete access to all the hardware and can execute any instruction the machine is capable of execution.

  In user mode, only a subset of the machine instructions is available.

  
  

5. (简答题, 0.3分)

What is the key difference between a trap and an interrupt?

• 正确答案：

• Trap is an instruction from the internal of CPU. A trap is caused by the program and is synchronous with it. If the program is run again and again, the trap will always occur at exactly the same position in the instruction stream.

  Interrupt is an instruction from the external of CPU. An interrupt is caused by an external event and its timing is not reproducible.

  
  

6. (简答题, 0.3分)

What is the same point and difference between trap and library procedure?

• 正确答案：

• Same:  they are all taken from a distant location and the return addresses are all saved on the stack for use later.

  Different: ①TRAP switches into kernel mode; The procedure call instruction does not change the mode. ②If giving a relative or absolute address, the procedure can be located; the TRAP instruction can‘t’ jump to an arbitrary address.

  
  

第二章

一. 简答题（共1题，0.4分）

1. (简答题, 0.4分)What’s the biggest advantage of implementing thread in user space? What’s the biggest disadvantage?

• 正确答案：

• Solution: The first advantage is that a user-level package can be implemented on an operating system that does not support threads. The second advantage is that they allow each process to have its own customized scheduling algorithm.

  The disadvantage is the problem of how blocking system calls are implemented. Another problem is that if a thread starts running, no other thread in that process will ever run unless the first thread voluntarily gives up the CPU.

二. 计算题（共4题，1.6分）

2. (计算题, 0.4分)

 For the processes listed in the following table, please write out the processes’ average turnaround time for the following algorithms. 1) Shortest job first；2) Shortest remaining time next；3) Round robin (quantum=2s)；4) Priority scheduling (Preemptive, with 1 being the highest priority). You must write out the computing course.

 

正确答案：

3. (计算题, 0.4分)

Five batch jobs A through E, arrive at a computer center at almost the same time. They have estimated running times of 10, 6, 2, 4, and 8 minutes. Their (externally determined) priorities are 3, 5, 2, 1, and 4, respectively, with 5 being the highest priority. For each of the following scheduling algorithms, determine the mean process turnaround time. Ignore process switching overhead.

(a) Round robin

(b)Priority scheduling

(c)First-come, first-served (run in order 10, 6, 2, 4, 8)

(d)Shortest job first

For (a), assume that the system is multiprogrammed, and that each job gets its fair share of the CPU. For (b) through (d) assume that only one job at a time runs, until it finishes. All jobs are completely CPU bound.

正确答案：

4. (计算题, 0.4分)A soft real-time system has four periodic events with periods of 50, 100, 200, and 250 msec each. Suppose that the four events require 35, 20, 10, and x msec of CPU time, respectively. What is the largest value of x for which the system is schedulable?

• 正确答案：

• 35/50+20/100+10/200+x/250<=1 max(x)=12.5

  
  

5. (计算题, 0.4分)

Measurements of certain system have shown that the average process runs for a time T before blocking on I/O. A process switch requires a time S, which is effectively wasted (overhead). For round-robin scheduling with quantum Q, give a formula for the CPU efficiency for each of the following:

(a) Q=∞         CPU efficiency=（     ）

(b) Q>T          CPU efficiency= （       ）

(c) S<Q<T       CPU efficiency= （    ）

(d) Q=S          CPU efficiency= （        ） 

(e) Q nearly 0      CPU efficiency= （       ）

• 正确答案：

• (a) Q=∞         CPU efficiency=T/ (T+S)

  (b) Q>T          CPU efficiency= T/ (T+S)

  (c) S<Q<T        CPU efficiency=T/ (T+ST/Q)

  (d) Q=S          CPU efficiency=50%

  (e) Q nearly 0      CPU efficiency is nearly 0

  
  

第三章

1. (论述题, 0.5分)

Consider a swapping a system in which memory consists of the following hole sizes in memory order: 10KB, 4KB, 20KB, 18KB, 7KB, 9KB, 12KB and 15KB. Which hole is taken for successive segment requests of

(a) 12KB   (b) 10KB  (c)9KB

For first fie? Now repeat the question for best fit, worst fit and next fit.

• 正确答案：

  
  

2. (计算题, 0.5分)For each of the following decimal virtual addresses, compute the virtual page number and offset for a 4-KB page and for an 8-KB page: 20000, 32768, 60000.

• 正确答案：

• page size: 4K=4*1024=4096

  (1) 20000/4096=4…3616       page number is 4, offset is 3616

  (2) 32768/4096=8             page number is 8, offset is 0

  (3) 60000/4096=14…2656      page number is 14, offset is 2656

  page size: 8K=8*1024=8192

  (1) 20000/8192=2…3616       page number is 2, offset is 3616

  (2) 32768/8192=4             page number is 4 offset is 0

  60000/8192=7…2656       page number is 7, offset is 2656

3. (计算题, 0.5分)If FIFO page replacement is used with four page frames and eight pages, how many page faults will occur with the reference string 0172327103 if the four frames are initially empty? Now repeat this problem for LRU.

正确答案：

4. (计算题, 0.5分)

 A computer has four page frames. The time of loading, time of last access, and the R and M bits for each page are as shown below (the timesa re in clock ticks):

(a) Which page will NRU replace?

(b) Which page will FIFO replace?

(c) Which page will LRU replace?

(d) Which page will second chance replace?

• 正确答案：

• (a) Page 2 (2)     (b) Page 3 (3)      (c) Page 1 (1)       (d) Page 2 (2)

  
  

第四、五章

一. 简答题（共2题，1分）

1. (简答题, 0.5分)
Consider the firectory tree of Fig.4-8. IF /usr/jim is the working directory, what is the absolute path name for the file whose relative path name is ../ast/x?

• 正确答案：

• Solution: /usr/ast/x

2. (简答题, 0.5分)

In which of the four I/O software layers is each of the following done.

(a) Computing the track, sector and head for a disk read.

(b) Writing commands to the device registers.

(c) Checking to see if the user is permitted to use the device.

(d) Converting binary integers to ASCII for printing

• 正确答案：

• Solution:

  (a)      Device driver

  (b)      Device driver

  (c)      Device-independent IO software

  (d)      User-level IO software

二. 计算题（共2题，1分）

3. (计算题, 0.5分)

The beginning of a free space bitmap looks like this after the disk partition is first formatted: 1000 0000 0000 0000 (the first block is used by the root directory). The system always searches for free blocks starting at the lowest-numbered blcok, so after writing file A , which uses six blocks, the bitmap looks like this: 1111 1110 0000 0000. Show the bitmap after each of the following additional actions:

(a) File B is written, using five blocks

(b) File A is deleted

(c) File C is written, using eight blocks

(d) File B is deleted

• 正确答案：

• Solution:

  (a)      1111 1111 1111 0000

  (b)      1000 0001 1111 0000

  (c)      1111 1111 1111 1100

  (d)      1111 1110 0000 1100

4. (计算题, 0.5分)

 Disk requests come in to the disk driver for cylinders 10, 22, 20, 2, 40, 6 and 38 in that order. A seek takes 6 msec per cylinder moved. How much seek time is needed for？

(a) First-come, firs server.

(b) Closest cylinder next.

(c) Elevator algorithm (initially moving upward).

In all cases, the arm is initially at cylinder 20.

• 正确答案：

• (a) 20-10-22-20-2-40-6-38 seek time= (10+12+2+18+38+34+32)*6=146*6=876ms

  (b) 20-20-22-10-6-2-38-40 seek time= (0+2+12+4+4+36+2)*6=360ms

  (c) 20-20-22-38-40-10-6-2 seek time= (0+2+16+2+30+4+4)*6=348ms

   

第六章

一. 计算题（共1题，2分）

1. (计算题, 2分)

Take a careful look at Fig.6-11(b). If D asks for one more unit, does this lead to a safe state or an unsafe one? What if the request came from C instead of D?

Solution: D requests one unit, it will lead to an unsafe state; C requests one unit, it will lead to a safe state.

 

• 正确答案：

• Request matrix:

  A 0 1 0 0 1

  B 0 2 1 0 0

  C 1 0 3 0 0

  D 0 0 1 1 1

  Process D runs

  x>=1 (1)

  Available: 1 1 x+1 2 1

  Process A runs

  x+1>=0 x>=-1 x>=0 (2)

  Available: 2 1 x+3 3 2

  Process C runs

  x+3>=3 x>=0 (3)

  Available: 3 2 x+3 4 2

  Process B runs

  x+3>=1 x>=-2 x>=0 (4)

  Available: 5 2 x+4 5 2

  So, x>=1 and x>=0

  So, x>=1

  The smallest value of x for which this is a safe state is 1.