注：本教材為安德魯 S.塔嫩鮑姆的《現(xiàn)代操作系統(tǒng)》（第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.

二. 計(jì)算題（共4題，1.6分）

2.?(計(jì)算題, 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.?(計(jì)算題, 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.?(計(jì)算題, 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.?(計(jì)算題, 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.?(計(jì)算題, 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.?(計(jì)算題, 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.?(計(jì)算題, 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

二. 計(jì)算題（共2題，1分）

3.?(計(jì)算題, 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.?(計(jì)算題, 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

  ?

第六章

一. 計(jì)算題（共1題，2分）

1.?(計(jì)算題, 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.