操作系统概念_第六版_重点部分_中文答案 3

1.1What are the three main purposes of an operating system?

1 To provide an environment for a computer user to execute programs on computer hardware in a convenient and ef?cient manner.

2 To allocate the separate resources of the computer as needed to solve the problem given. The allocation process should be as fair and ef?cient as possible.

3 As a control program it serves two major functions: (1) supervision of the execution of user programs to prevent errors and improper use of the computer, and (2) manage-

ment of the operation and control of I/O devices.

●环境提供者，为计算机用户提供一个环境，使得能够在计算机硬件上方便、高效的执行程序

●资源分配者，为解决问题按需分配计算机的资源，资源分配需尽可能公平、高效

●控制程序

监控用户程序的执行，防止出错和对计算机的不正当使用

管理I/O设备的运行和控制

1.2 List the four steps that are necessary to run a programon a completely dedicatedmachine. Answer: Generally, operating systems for batch systems have simpler requirements than for personal computers. Batch systems do not have to be concerned with interacting with a user as much as a personal computer. As a result, an operating system for a PC must be concerned with response time for an interactive user. Batch systems do not have such requirements.

A pure batch system also may have not to handle time sharing,whereas an operating systemmust switch rapidly between different jobs.

a. Reserve machine time.

b. Manually load program into memory.

c. Load starting address and begin execution.

d. Monitor and control execution of program from console

1.6 Define the essential properties of the following types of operating systems:

a. Batch

b. Interactive

c. Time sharing

d. Real time

e. Network

f. Distributed

a. Batch. Jobs with similar needs are batched together and run through the computer

as a group by an operator or automatic job sequencer. Performance is increased by attempting to keep CPU and I/O devices busy at all times through buffering, off-line operation, spooling, and multiprogramming. Batch is good for executing large jobs

that need little interaction; it can be submitted and picked up later.

b. Interactive. This system is composed of many short transactions where the results of the next transactionmay be unpredictable. Response time needs to be short (seconds) since the user submits and waits for the result.

c. Time sharing.Thissystemsuses CPU scheduling and multiprogramming to provide economical interactive use of a system. The CPU switches rapidly from one user to another. Instead of having a job de?ned by spooled card images, each program readsits next control card from the terminal, and output is normally printed immediately

to the screen.

d. Real tim

e. Often used in a dedicated application, this system reads information from sensors and must respond within a ?xed amount of time to ensure correct perfor- mance.

e. Network.

f. Distributed.This system distributes computation among several physical processors. The processors do not share memory or a clock. Instead, each processor has its own local memory. They communicate with each other through various communication

lines, such as a high-speed bus or telephone line.

a. Batch

相似需求的Job分批、成组的在计算机上执行，Job由操作员或自动Job程序装置装载；

可以通过采用 buffering, off-line operation, spooling, multiprogramming 等技术使CPU 和I/O不停忙来提高性能

批处理适合于需要极少用户交互的Job。

b. Interactive

由许多短交易组成，下一次交易的结果可能不可预知

需要响应时间短

c. Time sharing

使用CPU调度和多道程序提供对系统的经济交互式使用，CPU快速地在用户之间切换

一般从终端读取控制，输出立即打印到屏幕

d. Real time

在专门系统中使用，从传感器读取信息，必须在规定时间内作出响应以确保正确的执行

e. Network

在通用OS上添加

联网、通信功能

远程过程调用

文件共享

f. Distributed

具有联网、通信功能

提供远程过程调用

提供多处理机的统一调度调度

统一的存储管理

分布式文件系统

1.7 We have stressed the need for an operating system to make efficient use of the computing hardware. When is it appropriate for the operating system to forsake this principle and to“waste” resources? Why is such a system not really wasteful?

We have stressed the need for an operating system to make ef?cient use of the computing hardware. When is it appropriate for the operating system to forsake this principle and to “waste” resources? Why is such a system not really wasteful?

Answer: Single-user systems should maximize use of the system for the user. A GUI might “waste” CPU cycles, but it optimizes the user’s interaction with the system. 木有中文答案

2.2 How does the distinction between monitor mode and user mode function as a rudimentary form of protection (security) system?

Answer: By establishing a set of privileged instructions that can be executed only when in the monitor mode, the operating system is assured of controlling the entire system at all Times.

通过建立一组只能在monitor mode才能执行的特权指令集，OS能够确保总是能控制整个系统。

2.3 What are the differences between a trap and an interrupt? What is the use of each function?

Answer: An interrupt is a hardware-generated change-of-?ow within the system. An interrupt handler is summoned to deal with the cause of the interrupt; control is then re-turned to the interrupted context and instruction. A trap is a software-generated interrupt

An interrupt can be used to signal the completion of an I/O to obviate the need for device polling. A trap can be used to call operating system routines or to catch arithmetic errors.

An interrupt是硬件产生的系统内的流的改变

A trap是软件产生的“中断”。

interrupt可以被I/O用来产生完成的信号，从而避免CPU对设备的轮询

A trap可以用来调用OS的例程或者捕获算术错误

2.5 Which of the following instructions should be privileged?

a. Set value of timer.

b. Read the clock.

c. Clear memory.

d. Turn off interrupts.

e. Switch from user to monitor mode.

Answer: The following instructions should be privileged:

a. Set value of timer.

b. Clear memory.

c. Turn off interrupts.

d. Switch from user to monitor mod

e.

2.8 Protecting the operating system is crucial to ensuring that the computer system operates correctly. Provision of this protection is the reason behind dual-mode operation, memory protection, and the timer. To allow maximum flexibility, however, we would also like to place minimal constraints on the user.

The following is a list of operations that are normally protected. What is the minimal set of instructions that must be protected?

a. Change to user mode.

b. Change to monitor mode.

c. Read from monitor memory.

d. Write into monitor memory.

e. Fetch an instruction from monitor memory.

f. Turn on timer interrupt.

g. Turn off timer interrupt.

Answer: The minimal set of instructions that must be protected are:

a. Change to monitor mode.

b. Read from monitor memory.

c. Write into monitor memory.

d. Turn off timer interrupt.

3.6 List five services provided by an operating system. Explain how each provides convenience to the users. Explain also in which cases it would be impossible for user-level programs to provide these services.

Answer:

Program execution. The operating system loads the contents (or sections) of a ?le

into memory and begins its execution. A user-level program could not be trusted to properly allocate CPU time.

I/O operations. Disks, tapes, serial lines, and other devices must be communicated with at a very low level. The user need only specify the device and the operation to performon it, while the system converts that request into device- or controller-specic commands. User-level programs cannot be trusted to only access devices they should have access to and to only access them when they are otherwise unused.

File-systemmanipulation. There are many details in ?le creation, deletion, allocation, and naming that users should not have to perform. Blocks of disk space are used by

?les and must be tracked. Deleting a ?le requires removing the name ?le information and freeing the allocated blocks. Protections must also be checked to assure proper ?le access. User programs could neither ensure adherence to protection methods nor be trusted to allocate only free blocks and deallocate blocks on ?le deletion. Communications. Message passing between systems requires messages be turned

into packets of information, sent to the network controller, transmitted across a com- munications medium, and reassembled by the destination system. Packet ordering

and data correction must take place. Again, user programs might not coordinate ac- cess to the network device, or they might receive packets destined for other processes. Error detection. Error detection occurs at both the hardware and software levels. At the hardware level, all data transfers must be inspected to ensure that data have not been corrupted in transit. All data on media must be checked to be sure they have not changed since they were written to the media. At the software level, media must be checked for data consistency; for instance, do the number of allocated and unallocated blocks of storage match the total number on the device. There, errors are frequently process-independent (for instance, the corruption of data on a disk), so theremust be a global program(the operating system) that handles all types of errors. Also, by having errors processed by the operating system, processes need not contain code to catch and correct all the errors possible on a system.

3.7 What is the purpose of system calls?

Answer: System calls allow user-level processes to request services of the operating sys- Tem.

让用户级进程可以请求操作系统所提供的服务

3.10 What is the purpose of system programs?

Answer: System programs can be thought of as bundles of useful system calls. They provide basic functionality to users and so users do not need to write their own programs to solve common problems.

为程序开发和运行提供了方便的环境

给用户提供基本的公共功能函数，为用户在不用自己写代码的情况下解决公用问题

4.1 MS-DOS provided no means of concurrent processing. Discuss three major complications that concurrent processing adds to an operating system.

Answer:

A method of time sharing must be implemented to allow each of several processes to have access to the system. This method involves the preemption of processes that do not voluntarily give up the CPU (by using a system call, for instance) and the kernel being reentrant (somore than one processmay be executing kernel code concurrently).

Processes and system resources must have protections and must be protected from each other. Any given process must be limited in the amount of memory it can use

and the operations it can perform on devices like disks.

Caremust be taken in the kernel to prevent deadlocks between processes, so processes aren’t waiting for each other’s allocated resources.

4.6 The correct producer–consumer algorithm in Section 4.4 allows only n-1 buffers to be full at any one time. Modify the algorithm to allow all buffers to be utilized fully. Answer: No answer.

5.1 Provide two programming examples of multithreading giving improve performance over

a single-threaded solution.

Answer: (1) A Web server that services each request in a separate thread. (2) A paral- lelized application such as matrix multiplication where different parts of the matrix may be worked on in parallel. (3) An interactive GUI program such as a debugger where a thread is used to monitor user input, another thread represents the running application, And at third thread monitors performance.

可以并发的多任务

Web浏览器，数据可并行处理

5.3 What are two differences between user-level threads and kernel-level threads? Under what circumstances is one type better than the other?

Answer: (1) User-level threads are unknown by the kernel, whereas the kernel is aware of kernel threads. (2) User threads are scheduled by the thread library and the kernel schedules kernel threads. (3) Kernel threads need not be associatedwith a process whereas every user thread belongs to a process.

内核可知与不可知

调度者不同

与进程的关系

6.3 Consider the following set of processes, with the length of the CPU-burst time given in

milliseconds:

Process Burst Time Priority

P1 10 3

P2 1 1

P3 2 3

P4 1 4

P5 5 2

The processes are assumed to have arrived in the order P1, P2, P3, P4, P5, all at time 0.

a. Draw four Gantt charts illustrating the execution of these processes using FCFS, SJF, a nonpreemptive priority (a smaller priority number implies a higher priority), and RR (quantum = 1) scheduling.

b. What is the turnaround time of each process for each of the scheduling algorithms in part a?

c. What is the waiting time of each process for each of the scheduling algorithms in part a?

d. Which of the schedules in part a results in the minimal average waiting time (over all processes)?

6.4 Suppose that the following processes arrive for execution at the times indicated. Each process will run the listed amount of time. In answering the questions, use nonpreemptive scheduling and base all decisions on the information you have at the time the decision must be made.

a. What is the average turnaround time for these processes with the FCFS scheduling algorithm?

b. What is the average turnaround time for these processes with the SJF scheduling algorithm?

c. The SJF algorithm is supposed to improve performance, but notice that we chose to run process P1 at time 0 because we did not know that two shorter processes would

arrive soon. Compute what the average turnaround time will be if the CPU is left

idle for the first 1 unit and then SJF scheduling is used. Remember that processes P1 and P2 are waiting during this idle time, so their waiting time may increase. This algorithm could be known as future-knowledge scheduling.

a. 10.53 ((8-0)+(12-0.4)+(13-1.0))/3 = 10.53

b. 9.53 ((8-0)+(13-0.4)+(9-1.0))/3 = 9.53

c. 6.86 ((14-0)+(6-0.4)+(2-1.0))/3 = 6.87

6.10 Explain the differences in the degree to which the following scheduling algorithms discriminate in favor of short processes:

a. FCFS

b. RR

c. Multilevel feedback queues

a. FCFS—discriminates against short jobs since any short jobs arriving after long jobs

will have a longer waiting time.

b. RR—treats all jobs equally (giving them equal bursts of CPU time) so short jobs will

be able to leave the system faster since they will ?nish ?rst.

c. Multilevel feedback queues—work similar to the RR algorithm—they discriminate

favorably toward short jobs.

木有中文答案

7.7 Show that, if the wait and signal operations are not executed atomically,

then mutual exclusion may be violated.

木有答案

7.8 The Sleeping-Barber Problem. A barbershop consists of a waiting room with n chairs and the barber room containing the barber chair. If there are no customers to be served,the barber goes to sleep. If a customer enters the barbershop and all chairs are occupied, then the customer leaves the shop.If the barber is busy but chairs are available, then the customer sits in one of the free chairs. If the barber is asleep, the customer wakes up the barber. Write a program to coordinate the barber and the customers.

理发师和顾客同步，理发师必须由顾客唤醒，理发师给一个顾客理发完，要让理发完的顾客退出，让等待顾客进入，顾客互斥的占用n个位置

//共享变量

semaphore Scuthair, Snumchair;// Scuthair制约理发师, Snumchair制约顾客Scuthair=0; Snumchair=0;

barber:

do {

wait(Scuthair);//检查是否有顾客，无就睡眠

给某个顾客理发

signal(Snumchair);//让理发完的顾客退出，让等待的一个顾客进入} while (1);

Customer i:

wait(Snumchair);//申请占用椅子

signal(Scuthair);//给理发师发一个信号

坐在椅子上等着理发//共享变量

semaphore Scuthair, Mutexchair;// Scuthair给理发师, Mutexchair制约顾客对椅子的互斥占领

int number = 0;//顾客的共享变量，记录已经有的顾客数

Scuthair=0; Mutexchair =1;

Customer i:

wait(Mutexchair);//申请对共享变量number的操作（申请占用椅子） if(number = = n-1){signal(Mutexchair); exit;}

number = number +1;

signal(Scuthair);//给理发师发一个信号

signal(Mutexchair);

等待理发…

理发完毕…

wait(Mutexchair);//申请对共享变量number的操作

number = number -1;

signal(Mutexchair);

离开理发店

barber:

do {

wait(Scuthair);//检查是否有顾客，无，就睡眠

给某个顾客理发

} while (1);

8.2 Is it possible to have a deadlock involving only one single process? Explain your answer. No. This follows directly from the hold-and-wait condition.

8.4 Consider the traffic deadlock depicted in Figure 8.11.

a. Show that the four necessary conditions for deadlock indeed hold in this example.

b. State a simple rule that will avoid deadlocks in this system.

8.13 Consider the following snapshot of a system:

Allocation Max Available

A B C D A B C D A B C D

P0 0 0 1 2 0 0 1 2 1 5 2 0

P1 1 0 0 0 1 7 5 0

P2 1 3 5 4 2 3 5 6

P3 0 6 3 2 0 6 5 2

P4 0 0 1 4 0 6 5 6

Answer the following ques tions using the banker’s algorithm:

a. What is the content of the matrix Need?

b. Is the system in a safe state?

c. If a request from process P1 arrives for (0,4,2,0), can the request be granted immediately?

a. Deadlock cannot occur because preemption exists.

b. Yes. A process may never acquire all the resources it needs if they are continuously preempted by a series of requests such as those of process C.

a. Need = Max – Allocation

0 0 0 0

0 7 5 0

1 0 0 2

0 0 2 0

0 6 4 2

b.安全算法找安全序列

c.先请求算法，再安全算法找安全序列，如果安全，请求可以响应。

9.5 Given memory partitions of 100K, 500K, 200K, 300K, and 600K (in order), how would each of the First-fit, Best-fit, and Worst-fit algorithms place processes of 212K, 417K, 112K, and 426K (in order)? Which algorithm makes the most efficient use of memory?

a. First-?t:

b. 212K is put in 500K partition

c. 417K is put in 600K partition

d. 112K is put in 288K partition (new partition 288

e. 426K must wait

f. Best-?t:

g. 212K is put in 300K partition

h. 417K is put in 500K partition

i. 112K is put in 200K partition

j. 426K is put in 600K partition

k. Worst-?t:

l. 212K is put in 600K partition

m. 417K is put in 500K partition

n. 112K is put in 388K partition

o. 426K must wait

In this example, Best-?t turns out to be the best.

First fit

212 ->500(288)

417 ->600(183)

112 ->288

426 ->none

Best fit

212 ->300

417 ->500

112 ->200

426 ->600

Worst fit

212 ->600(388)

417 ->500

112 ->388

426 ->none

9.8 Consider a logical address space of eight pages of 1024 words each, mapped onto a physical memory of 32 frames.

a. How many bits are there in the logical address?

b. How many bits are there in the physical address?

a. Logical address: 13 bits

b. Physical address: 15 bits

9.16 Consider the following segment table:

Segment Base Length

0219 600

12300 14

290 100

31327 580

41952 96

What are the physical addresses for the following logical addresses?

a. 0,430

b. 1,10

c. 2,500

d. 3,400

e. 4,112

a. 219 + 430 = 649

b. 2300 + 10 = 2310

c. illegal reference, trap to operating system

d. 1327 + 400 = 1727

e. illegal reference, trap to operating system

a. 430<600, 219+430 = 649

b. 10<14, 2300+10 = 2310

c. 500>100, illegal

d. 400<580, 1327+400 = 1727

e. 112>96, illegal

10.2 Assume that you have a page reference string for a process with m frames (initially all empty). The page reference string has length p with n distinct page numbers occur in it. For any page-replacement algorithms,

a. What is a lower bound on the number of page faults?

b. What is an upper bound on the number of page faults?

a. n

b. p

10.11 Consider 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 one, two, three, four, five, six, or seven frames? Remember all frames are initially empty,so your first unique pages will all cost one fault each.

LRU replacement

FIFO replacement

Optimal replacement

11.7 Explain the purpose of the open and close operations.

The open operation informs the system that the named ?le is about to become active. The close operation informs the system that the named ?le is no longer in active use by the user who issued the close operation

11.9 Give an example of an application in which data in a file should be accessed in the following order:

a. Sequentially

b. Randomly

a. Print the content of the ?le.

b. Print the content of record i. This record can be found using hashing or index tech- Niques.

11.12 Consider a system that supports 5000 users. Suppose that you want to allow 4990 of these users to be able to access one file.

a. How would you specify this protection scheme in UNIX?

b. Could you suggest another protection scheme that can be used more effectively for this purpose than the scheme provided by UNIX?

a. There are two methods for achieving this:i. Create an access control list with the names of all 4990 users.

ii. Put these 4990 users in one group and set the group access accordingly. This scheme cannot always be implemented since user groups are restricted by the

system.

b. The universe access information applies to all users unless their name appears in the access-control list with different access permission. With this scheme you simply put the names of the remaining ten users in the access control list but with no access privileges allowed.

12.1 Consider a file currently consisting of 100 blocks. Assume that the file control block (and

the index block, in the case of indexed allocation) is already in memory. Calculate how many disk I/O operations are required for contiguous, linked, and indexed (single-level) allocation strategies, if, for one block, the following conditions hold. In the contiguousallocation case, assume that there is no room to grow in the beginning, but there is room to grow in the end. Assume that the block information to be added is stored in memory.

a. The block is added at the beginning.

b. The block is added in the middle.

c. The block is added at the en

d.

d. The block is removed from the beginning.

e. The block is removed from the middle.

f. The block is removed from the end.

13.2 Consider the following I/O scenarios on a single-user PC.

a. A mouse used with a graphical user interface

b. A tape drive on a multitasking operating system (assume no device preallocation is available)

c. A disk drive containing user files

d. A graphics card with direct bus connection, accessible through memory-mapped

I/O

For each of these I/O scenarios, would you design the operating system to use buffering, spooling, caching, or a combination? Would you use polled I/O, or interrupt-driven I/O? Give reasons for your choices.

a. A mouse used with a graphical user interface

Buffering may be needed to record mouse movement during times when higher-

priority operations are taking place. Spooling and caching are inappropriate. Inter- rupt driven I/O is most appropriate.

b. A tape drive on a multitasking operating system (assume no device preallocation is available)

Buffering may be needed to manage throughput difference between the tape drive

and the source or destination of the I/O, Caching can be used to hold copies of data that resides on the tape, for faster access. Spooling could be used to stage data to the device when multiple users desire to read from or write to it. Interrupt driven I/O

is likely to allow the best performance.

c. A disk drive containing user ?les

Buffering can be used to hold data while in transit from user space to the disk, and visa versa. Caching can be used to hold disk-resident data for improved perfor- mance. Spooling is not necessary because disks are shared-access devices. Interrupt- driven I/O is best for devices such as disks that transfer data at slow rates.

d. A graphics card with direct bus connection, accessible through memory-mapped

I/O

Buffering may be needed to control multiple access and for performance (double- buffering can be used to hold the next screen image while displaying the current one). Caching and spooling are not necessary due to the fast and shared-access

natures of the device. Polling and interrupts are only useful for input and for I/O completion detection, neither of which is needed for a memory-mapped device.

14.2 Suppose that a disk drive has 5000 cylinders, numbered 0 to 4999. The drive is currently serving a request at cylinder 143, and the previous request was at cylinder 125. The queue of pending requests, in FIFO order, is

86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130

Starting from the current head position, what is the total distance (in cylinders) that the disk arm moves to satisfy all the pending requests, for each of the following diskscheduling

algorithms?

a. FCFS

b. SSTF

c. SCAN

d. LOOK

e. C-SCAN

a. The FCFS schedule is 143, 86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130. The total

seek distance is 7081.

b. The SSTF schedule is 143, 130, 86, 913, 948, 1022, 1470, 1509, 1750, 1774. The total

seek distance is 1745.

c. The SCAN schedule is 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 4999, 130, 86. The

total seek distance is 9769.

d. The LOOK schedule is 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 130, 86. The total

seek distance is 3319.

e. The C-SCAN schedule is 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 4999, 86, 130. The

total seek distance is 9813.

f. (Bonus.) The C-LOOK schedule is 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 86, 130.

The total seek distance is 3363.