操作系统英⽂版课后习题答案整理
1.1What are the three main purpos of an operating system?
(1) Interface between the hardware and ur;
(2) manage the resource of hardware and software;
(3) abstraction of resource;
1.2 List the four steps that are necessary to run a program on a completely dedicated machine. Preprocessing > Processing > Linking > Executing.
1.6 Define the esntial properties of the following types of operating systems:
a. Batch
b. Interactive
c. Time sharing
d. Real time
e. Network
f. Distributed
1.7 We have stresd the need for an operating system to make efficient u 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?
2.2 How does the distinction between monitor mode and ur mode function as a rudimentary form of protection (curity) system?
2.3 What are the differences between a trap and an interrupt? What is the u of each function?
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 ur to monitor mode.
2.8 Protecting the operating system is crucial to ensuring that the computer system operates correctl
y. 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 ur.
The following is a list of operations that are normally protected. What is the minimal t of instructions that must be protected?
a. Change to ur 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.
3.6 List five rvices provided by an operating system. Explain how each provides convenience to the urs. Explain also in which cas it would be impossible for ur-level programs to provide the rvices.
3.7 What is the purpo of system calls?
3.10 What is the purpo of system programs?
that concurrent processing adds to an operating system.
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.
5.1 Provide two programming examples of multithreading giving improve performance over
a single-threaded solution.
5.3 What are two differences between ur-level threads and kernel-level threads? Under what circumstances is one type better than the other?
6.3 Consider the following t of process, with the length of the CPU-burst time given in
milliconds:
Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 3
P4 1 4
P5 5 2
The process 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 the process 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 process)?
Answer:
6.4 Suppo that the following process arrive for execution at the times indicated. Each
process will run the listed amount of time. In answering the questions, u nonpreemptive scheduling and ba all decisions on the information you have at the time the decision must be made.
a. What is the average turnaround time for the process with the FCFS scheduling algorithm?
b. What is the average turnaround time for the process with the SJF scheduling algorithm?
c. The SJF algorithm is suppod to improve performance, but notice that we cho to run process P1 at time 0 becau we did not know that two shorter process 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 ud. Remember that process P1 and P2 are waiting during this idle time, so their waiting time may increa. This algorithm could be known as future-knowledge scheduling.
6.10 Explain the differences in the degree to which the following scheduling algorithms discriminate in favor of short process:
a. FCFS
b. RR
c. Multilevel feedback queues
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 rved,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 avai lable, 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.
8.2 Is it possible to have a deadlock involving only one single process? Exp lain your answer.
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 questions using th e 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?
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 process of 212K, 417K, 112K, and 426K (in order)? Which algorithm makes the most efficient u of memory?
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?
9.16 Consider the following gment table:
Segment Ba Length
0219 600
12300 14
290 100
31327 580
41952 96
What are the physical address for the following logical address?
a. 0,430
b. 1,10
c. 2,500
d. 3,400
e. 4,112
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?
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 ven 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 purpo of the open and clo operations.
11.9 Give an example of an application in which data in a file sho uld be accesd in the following order:
a. Sequentially
b. Randomly
11.12 Consider a system that supports 5000 urs. Suppo that you want to allow 4990 of the urs 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 ud more effectively for this purpo than the scheme provided by UNIX?
12.1 Consider a file currently consisting of 100 blocks. Assume that the file control block (and
the index block, in the ca 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 ca, 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.
