CS411/511. Operating Systems

CS411/511. Operating Systems
Homework 1 - Solutions



1.1. What are the three main purposes of an operating system?
To provide a convenient environment for users to execute programs on computer hardware.
To allocate, fairly and efficiently, the computer resources needed to execute the program safely (without adversely affecting other users or the OS itself).
To provide a foundation for evolution to future services, while still supporting existing services.Note that "convenience," "efficiency," etc. are not acceptable answers, since they don't explain "convenient/efficient for whom to do what."

1.4. In a multiprogramming and time-sharing environment, several users share the system simultaneously. This siguation can result in various security problems.
(a) What are two such problems?
(b) Can we ensure the same degree of secutiry in a time-shared machine as we have in a dedicated machine? Explain your answer.
Stealing or copying a user's files; writing over another program's (belonging to another user or to the OS) area in memory; using system resources (CPU, disk space) without proper accounting; causing the printer to mix output by sending data while some other user's file is printing.
Probably not, since any protection scheme devised by a human can also be broken -- and the more complex the scheme is, the more difficult it is to be confident of its correct implementation.

1.6. What are the main differences between operating systems for mainframe computers and personal computers?


PC OS's are not concerned with fair use or maximal use of computer resources. Instead, they try to optimize the usefulness of the computer for an individual user, usually at the expense of overall efficiency. Mainframe OS's need more complex scheduling and I/O algortihms to keep the various system components efficiently occupied.1.7. Define the essential properties of the following types of operating systems:BatchInteractiveTime-sharingReal-timeDistributed
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.
Interactive: Composed of many short transactions with input and output read/written on the screen; the results and timing of the next transaction may be unpredictable. Note that a purely interactive system (no time-sharing) only has one user; e.g., a PC).
Time-sharing: Uses CPU scheduling and multiprogramming to provide economical interactive use of a system. The CPU switches rapidly from one user to another.
Real-time: The system must respond to inputs/commands within a fixed amount of time to ensure correct performance. Input is typically read from sensors.
Distributed: Divides computation up among several computers. The computers do not share memory or a clock; they communicate with each other over communication lines (e.g., high-speed bus, telephone line).

1.10. Describe the differences between symmetric and asymmetric multiprocessing. What are three advantages and one disadvantage of multiprocessor systems?
Symmetric processing treats all processors as equals; I/O can be processed on any of them. Asymmetric processingdesignates one CPU as the master, which is the only one capable of performing I/O; the master distributes computational work among the other CPUs.
advantages: Multiprocessor systems can save money, by sharing power supplies, housings, and peripherals. Can execute programs more quickly and can have increased reliability.
disadvantages: Multiprocessor systems are more complex in both hardware and software. Additional CPU cycles are required to manage the cooperation, so per-CPU efficiency goes down.



2.3. What are the differences between a trap and an interrupt? What is the use of each function?
An interrupt is a hardware-generated signal that changes the flow within the system. A trap is a software-generated interrupt.
An interrupt can be used to signal the completion of I/O so thatthe CPU doesn't have to spend cycles polling the device. A trap can be used to catch arithmetic errors or to call system routines.

2.5. Which of the following instructions should be privileged?Set value of timerRead the clockClear memoryTurn off interruptsSwitch from user to monitor mode
Should be privileged.
Doesn't need to be.
Should be privileged.
Should be privileged.
Should be privileged.



Answer the following questions about policies and mechanisms:
(a) What is an advantage of separating policy from mechanism in designing any piece of software (including OSs)?

(b) Give three examples of software policies versus mechanisms.
Clean separation makes systems easier to modify and port. Another answer: Clearer thinking allowing you to differentiate the desired properties of a solution from the best solution you've thought of so far. Another answer: Mechanisms can be changed without affecting the policy.
Hint: You should always be able to name at least 2 different mechanisms that could be used to implement a so-called policy.Some examples:
policy: share CPU resource fairly among processes. mechanism: timer interrupts. alternate mechanism: enforce a limit on how long programs can be.
policy: some processes are more important or more critical than others. mechanism: base scheduling upon process priority. alternate mechanism: force processes to use "nice()" values.
policy: data values must be kept in order of priority. mechanism: heap. alternate mechanism: priority-sorted vector.

CS411/511. Operating Systems
Homework 2 - Solutions



Chapter 4: Review Questions 4.2, 4.6, 4.7

4.2. Describe the differences among short-term, medium-term, and long-term scheduling.
Short-term (CPU scheduler): selects a process from those that are in memory and ready to execute, and and allocates the CPU to it.
Medium-term (memory manager): selects processes from the ready or blocked queue and removes them from memory, then reinstates them later to continue running.
Long-term (job scheduler): determines which jobs are brought into the system for processing.

4.6. Describe the actions taken by a kernel to switch context(a) Among threads

(b) Among processes
The thread context (registers, PC, and stack, plus accounting info if appropriate) must be saved and another thread's context must be loaded.
The same as (a), except that the memory and resource info must also be stored and that for the next process must be loaded.

4.7. What are the differences between user-level threads and kernel-supported threads? Under what circumstances is one type "better" than the other?


User-level threads have no kernel support, so they are very inexpensive to create, destroy, and switch among. Kernel-supported threads are more expensive because system calls are needed to create and destroy them and the kernel must schedule them.
In most current systems with threads, when a user-level thread blocks, the whole process blocks. Since kernel-supported threads are scheduled independently, they can block individually; that is, the fact that one blocks does not hold up the others.



Chapter 5

5.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. Process Arrival Time Burst Time ------------------------------------------------------ P1 0.0 8 P2 0.4 4 P3 1.0 1
(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
(b) 9.53
(c) 6.86Remember that turnaround time is completion time minus arrival time, so you have to subtract the arrival times to compute the turnaround. FCFS is 11 if you forget to subtract arrival time.

5.6. What advantage is there in having different time-quantum sizes on different levels of a multilevel queueing system?
Processes which need more frequent servicing, such as interactive processes, can be in a queue with a small q. Processes that are computationally intensive can be in a queue with a larger quantum, requiring fewer context switches to complete the processing, making more efficient use of the CPU.

5.7. Consider the following preemptive priority-scheduling algorithm based on dynamically changing priorities. Larger priority numbers imply higher priority. When a process is waiting for the CPU (in the ready queue, but not running), its priority changes at a rate alpha; when it is running, the priority changes at a rate beta. All processes are given a priority of 0 when they enter the ready queue for the first time. The parameters alpha and beta can be set to give many different scheduling algorithms.(a) What is the algorithm that results from beta > alpha > 0?

(b) What is the algorithm that results from alpha < beta < 0?
(a) Since processes start at 0, any processes that have been in the system (either running or waiting) have higher priority. Therefore, new processes go to the back of the queue. When a process runs, its priority keeps increasing at the rate of beta, which is more of an increase than for the processes in the ready queue. Therefore, every time the process has timerrunout, it goes to the front of the ready queue and gets dispatched again. This is the equivalent of FCFS.


(b) This time, any new processes entering the system have higher priority than any old ones, since priority starts at zero and then becomes negative when the process waits or runs. New processes go in at the front of the queue. When a process runs or waits, its priority decreases, with the waiting processes decreasing faster than the running process. This is a LIFO (last-in-first-out) algorithm. The question didn't promise that this would be an algorithm you would want to use in real life.

Other Question. Take the example that you just used for Question 5.4, and apply it to the following situations.(a) Calculate the average turnaround time for a Round-Robin algorithm with q set at 2. Ignore the effects of context-switching time.

(b) Calculate the average turnaround time for the same algorithm and q, taking into effect the fact that each context switch costs .5 units of time.

(c) Suppose that a fourth process, P4, enters the system at time 7.6 and needs 6 units of CPU time. Also suppose that P2 and P3 are interactive, but P1 and P4 are batch.

A multilevel queue (but not a multilevel feedback queue) is in effect. The first queue is for interactive processes only, and has a qof 1. The second queue is for batch processes, which get up to 4 units each time they are in the CPU. Processes are dispatched as follows: 2 processes are dispatched from the interactive queue, followed by 1 process from the batch queue, etc.

Calculate the average turnaround time.
(a)8.53
(b)10.53 (I didn't count the final context switch after a process leaves the CPU for the last time)
(c)11 (They run in the order P1-P2-P3-P1-P2-P4-P2-P4-P2)



CS411/511. Operating Systems
Homework 3 - Solutions



Chapter 8: Review Questions 8.4, 8.10, 8.11, 8.16511 students only: 8.17

8.4. When a process is rolled out of memory, it loses its ability to use the CPU (at least for a while). Describe another situation where a process loses its ability to use the CPU, but where the process does not get rolled out.


When an interrupt occurs the process loses the CPU, but regains it as soon as the handler completes. The process is never rolled out of memory.

Note that when timerrunout occurs, the process is returned to the ready queue, and it may later be rolled out of memory. When the process blocs, it is moved to a waiting queue, where it may also be rolled out at some point.8.10. Consider a paging system with the page table stored in memory.(a) If a memory reference takes 200 nanoseconds, how long does a paged memory reference take?

(b) If we add associative registers, and 75% of all page-table references are found in the associative registers, what is the effective memory reference time? (Assume that finding a page-table entry in the associative registers takes zero time, if the entry is there.)
400 nanoseconds. 200 ns to access the page table plus 200 ns to access the word in memory.


250 nanoseconds. 75% of the time it's 200 ns, and the other 25% of the time it's 400ns, so the equation is: e.a. = (.75*200)+(.25*400)


Try this, too: What if the time to access the associative registers is actually 2 ns -- how does your answer change? e.a. = 2 + (.75*200)+(.25*400)
Remember that you *always* have to perform the TLB lookup, whether or not the page is found there.8.11. What is the effect of allowing two entires in a page table to point to the same page frame in memory? Explain how this effect could be used to decrease the amount of time needed to copy a large amount of memory from one place to another. What would the effect of updating some byte in the one page be on the other page?
This allows users to shared code or data. If the code is reentrant, much memory space can be saved through the shared use of large programs (e.g., text editors, compilers, database systems). "Copying" large amounts of memory could be effected by having different page tables point to the same memory location.

However, sharing of non-reentrant code or data means that any user having access to the code can modify it and these modifications would be reflected in the other user's "copy."8.16. Consider the following segment table: Segment Base Length 0 219 600 1 2300 14 2 90 100 3 1327 580 4 1952 96
What are the physical addressed 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; traps to operating system
(d) 1327 + 400 = 1727
(e) illegal reference; traps to operating system8.17. Consider the Intel address translation scheme shown in Figure 8.28(a) Describe all the steps that are taken by the Intel 80386 in translating a logical address into a physical address.(b) What are the advantages to the OS of hardware that provides such complicated memory translation?(c) Are there any disadvantages to this address translation system?
(a) The selector is an index into the segment descriptor table. The segment descriptor result plus the original offset is used to produce a linear address with dir/page/offset. The dir is an index into a page directory; the entry from this directory selects the page table, and the page field is an index into that page table. The entry from the page table, plus the offset, is the physical address.


(b) Such a page translation mechanism offers the flexibility to allow most OS's to implement their memory scheme in hardware, instead of having to implement some parts in hardware and some in software. Because it can be done in hardware, it is more efficient -- and the kernel is simpler.


(c) Address translation can take longer due to the multiple table lookups it can involve. Caches help, but there will still be cache misses.



Chapter 9: Review Questions 9.3, 9.11, 9.18511 students only: 9.5, 22.8

9.3. A certain computer provides its users with a virtual memory space of 2**32 bytes. The computer has 2**18 bytes of physical memory. The virtual memory is implemented by paging, and the page size is 4K bytes. A user process generated the virtual address 11123456. Explain how the system establishes the corresponding physical location. Distinguish between software and hardware operations.
The virtual address in binary form is 0001 0001 0001 0010 0011 0100 0101 0110
Since the page size is 2**12, the page table size is 2**20. Therefore, the low-order 12 bits (0100 0101 0110) are used as the displacement into the page, while the remaining 20 bits (0001 0001 0001 0010 0011) are used as the displacement in the page table.

Consider the operations that are needed (a) for DAT, and (b) for page fault servicing. All the DAT operations are carried out in hardware. But of the list of operations for page faults, on pp. 297-298, *at*least* steps 2, 4, 5, 6, 8, 10, and 12 involve software operations.9.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, size, or seven frames? Remember that all frames are initially empty, so your first unique pages will all cost one fault each.LRU replacementFIFO replacementOptimal replacement
# Frames LRU FIFO Optimal
1 20 20 20
2 18 18 15
3 15 16 11
4 10 14 8
5 8 10 7
6 7 10 7
7 7 7 7


9.17 (not in the assignement, but I'll leave the solution here).
Consider a demand-paging system with a paging disk that has an average access and transfer time of 20 ms. Addresses are translated through a page table in main memory, with an access time of 1 us per memory access. Thus, each memory reference through the page table takes two accesses. To improve this time, we have added an associative memory that reduces access time to one memory reference, if the page-table entry is in the associative memory.

Assume that 80% of the accesses are in the associative memory, and that, of the remaining, 10% (or 2% of the total) cause page faults. What is the effective memory access time? e.a. = 1 us + (0.20 * 1 us) + (0.02 * 20,000 us) = 401.2 us
Or, if you prefer e.a. = (0.80 * 1 us) + (0.18 * 2 us) + (0.02 * 20,002 us) = .8 us + .36 us + 400.04 us = 401.2 us


9.18. Consider a demand-paged computer system where the degree
of multi-programming is currently fixed at four. The system
was recently measureed to determine utilization of CPU and the
paging disk. The results are one of the following alternatives.

For each case, what is happening? Can the degree of
multiprogramming be increased to increase the CPU utilization?
Is the paging helping?

a. CPU utilization 13 percent; disk utilization 97 percent

System is thrashing. The degree of multiprogramming should be
decreased. Paging is not helping.

b. CPU utilization 87 percent; disk utilization 3 percent

System is well utilized, CPU is being kept busy most of the time.
The degree of multiprogramming probably should stay the same,
increasing it may lead to thrashing. Paging is helping.

c. CPU utilization 13 percent; disk utilization 3 percent

System is under utilized, the CPU is not getting enough work.
The degree of multiprogramming should be increased. Paging is
not really helping or hurting.
9.5. Suppose we have a demand-paged memory. The page table is held in registers. It takes 8 ms to service a page fault if an empty page is available or the replaced page is not modified, and 20 m if the replaced page is modified. Memory access time is 100 ns.

Assume that the page to be replaced is modified 70% of the time. What is the maximum acceptable page-fault rate for an effective access time of no more than 200 ns? [note: everything shown in microseconds] 0.2 us = ((1-P) * 0.1 us) + (0.3P * 8,000 us) + (0.7P * 20,000 us) 0.1 = -01.P + 2,400P + 14,000P 0.1 ~ 16,400 P P ~ 0.000006
22.8. What are three advantages of dynamic (shared) linkage of libraries, compared to static linkage? What are two cases where static linkage is preferable?
The primary advantages are that they reduce the memory and disk space used by a system, and they enhance maintainability. (You should be able to describe in detail why this is so.) Other advantages are the fact that a program that uses shared libraries can often be adapted for other purposes simply by replacing one or more of its libraries (e.g., substituting a debugging library for the normal one in order to trace a problem in an application). Shared libraries also allow program binaries to be linked against commercial, proprietary library code without actually including any of that code in the program's final executable file -- so it's may be possible to distribute code to a third party without having to incur extra licensing charges.


Static linkage is more appropriate for "system administration rescue" situations, such as if a sysadmin makes a mistake while installing a new library that causes it to be corrupted. Therefore, it is common to provide a set of basic "rescue utilities" that are statically linked, so that the fault can be corrected without having to rely on shared libraries. Since dynamic linking adds to the execution time, there may be performance reasons for linking the libraries statically. Also, it's easier to distribute an executable file that is complete (i.e., statically linked) rather than having to count on the recipient having the appropriate shared librares.CS411/511. Operating Systems
Homework 4 - Solutions



Chapter 6: Review Questions 6.1, 6.4, 6.18511 students only: 6.19



6.1.

Busy waiting: A process is waiting for an event to occur and it does so by executing instructions.
Other types of waiting: A process is waiting for an event to occur in some waiting queue (e.g., I/O semaphore) and it does so without having the CPU assigned to it.
Busy waiting cannot be avoided altogether (see p. 170).

6.4.Note that this is the same principle as Dekker's Algorithm, which we studied in class. It was a slightly earlier version, and therefore is more complicated than it really needs to be.

To prove that this algorithm is correct, we need to show that mutual exclusion is preserved, the progress requirement is satisfied, and the bounded-waiting requirement is met.
To prove mutual exclusion, we note that each P enters its critical section only if flag[j]!=in-cs for all other processes. Since each process is the only one that can set its own flag value, and since each process waits to examine the other processes' flags until it has set its own flag to in-cs, it can't be possible for two processes not to know that each other's flag is set. Therefore, it's not possible for two processes to be in their critical sections at the same time.
To prove progress, we note that the turn value can only be modified when a process is just about to enter its critical section, or has just completed its critical section. The turn value remains constant whenever there is no process executing/leaving its critical section. If other processes want to enter their critical sections, one will always be able to (the "first" one in the cyclic ordering [turn, turn+1, ... n-1, 0, ... turn-1]).
To prove bounded waiting, we note that whenever a process leaves its critical section, it checks to see if any other processes want to enter their critical sections. If so, it always designates which one will go next -- the "first" one in the cyclic ordering. This means that any process wanting to enter its critical section will do so within n-1 turns.

6.18. Note that the authors are referring to "cost" very generally (as in cost/benefit analysis), rather than specifically to "price."
Volatile storage fails when there is a power failure. Cache, main memory, and registers require a steady power source; when the system crashes and this source is interrupted, the contents are lost. Access is very fast.
Non-volatile storage retains its content despite power failures. For example, disk and CDROM survive anything other than demagnetization or hardware/head crashes (and less likely things like fire, immersion in water, etc.). Access is much slower.
Stable storage theoretically survives any type of failure. It can only be approximated through techniques such as mirroring. Access is certainly slower than volatile, and possibly slower than non-volatile storage.

6.19. If there is no checkpointing, the entire log must be searched after a crash, and all transactions "redone" from the log. If checkpointing is used, most of the log can be discarded. Since checkpoints are very expensive, how often they should be taken depends upon how reliable the system is. The more reliable the system, the less often a checkpoint should be taken.

When no failure occurs, the cost of checkpointing is "pure overhead" and can degrade performance if checkpointing is done frequently. When a system crash occurs, recovery time is proportional to the number of transactions since the last checkpoint. Assuming that a disk crash means the checkpoint file has been lost, recovery will involve a full rollback and re-doing of all transactions in the log.



Chapter 7: Review Questions 7.4, 7.6, 7.8, 7.13
(hint for 7.4(b): this is what drivers are really supposed to do)511 students only: 7.14



7.4. Note that each section of the street (including each intersection) is considered to be a "resource."


Mutual exclusion: only one vehicle on a section of the street
Hold and wait: each vehicle is occupying a section of the street and is waiting to move to the next section
No preemption: a section of a street that is occupied by a vehicle cannot be taken away from the vehicle unless the car moves into the next section
Circular wait: each vehicle is waiting for the next vehicle in front of it to moveTo keep deadlocks from occurring, allow a vehicle to cross an intersection only if it is assured that the vehicle will not have to stop at the intersection.

7.6.

(a) anytime
(b) only if MAX demand of each process does not exceed total number of available resources, and the system remains in a safe state.
(c) only if MAX demand of each process does not exceed total number of available resources, and the system remains in a safe state.
(d) anytime
(e) anytime
(f) anytime

7.8. Suppose the system is deadlocked. This implies that each process is holding one resource and is waiting for one more. Since there are three processes and four resources, one process must be able to obtain two resources. This process requires no more resources, and therefore it will terminate, releasing its resources. This in turn frees sufficient resources for the other processes to complete, one at a time.

7.13.

(a) Since NEED=MAX-ALLOC, the content of NEED is as follows


A B C D
0 0 0 0
0 7 5 0
1 0 0 2
0 0 2 0
0 6 4 2



(b)Yes, the sequence [P0, P2, P1, P3, P4] satisfies the safety requirement.
(c)Yes. The request does not exceed either Available or Max. Further the new system state, which is


Alloc Max Need
P0 0 0 1 2 0 0 1 2 0 0 0 0
P1 1 4 2 0 1 7 5 0 0 3 3 0
P2 1 3 5 4 2 3 5 6 1 0 0 2
P3 0 6 3 2 0 6 5 2 0 0 2 0
P4 0 0 1 4 0 6 5 6 0 6 4 2


is safe, as demonstrated by the sequence [P0, P2, P1, P3, P4].

7.14.

(a) Deadlock cannot occur because preemption exists. That is, the criterion of "no preemption" has been prevented.
(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.



Chapters 22-23: 511 students only: 22.6, 23.11



22.6.

Advantages: The primary impact of disallowing paging of kernel memory is that the non-preemptibility of the kernel is preserved. (Any process taking a page fault, whether in kernel mode or in user mode, risks being preempted while the required data is paged in from disk.) Because the kernel is guaranteed not to be preempted, locking requirements to protect the integrity of its primary data structures are also greatly simplified.


Disadvantages: It imposes constraints on the amount of memory that the kernel can use, since it is unreasonable to keep very large data structures in non-pageable memory (that memory cannot be used for anything else). Two disadvantages that stem from this are:
The kernel must prune back many of its internal data structures manually, since it can't rely on virtual memory mechanisms to keep physical memory usage under control.
It is infeasible to implement features requiring very large amounts of memory in the kernel (such as the /tmp-filesystem, a fast virtual-memory based filesystem found in some UNIX systems).

Note that the complexity of managing page faults while running kernel code is not an issue. The Linux kernel code is already able to deal with page faults (which can occur in a system call whose arguments reference user memory, which may be paged out on disk).

23.11. A process in NT is limited to 2 GB address space for data. The two-stage process allows the access of much larger datasets, by reserving space in the process's address space first, and then committing the storage to a memory-mapped file. An application can thus "window" through a large database (by changing the committed section) without exceeding process quotas or utilizing a huge amount of physical memory.

CS411/511. Operating Systems
Homework 5 - Solutions



12.1.

advantages: Bugs are less likely to cause an operating system crash. Performance can be improved by utilizing dedicated hardware and hard-coded algorithms. The kernel is simplified by moving algorithms out of it.


disadvantages: Bugs are harder to fix - a new firmware version or new hardware is needed; improving algorithms likewise require a hardware update rather than just kernel or device driver update. Embedded algorithms could conflict with OS's priorities or with application's use of the device, causing decreased performance. Testing is harder, since the components are autonomous and each device may behave differently.

12.2.

(a) mouse: Buffering may be needed to record mouse movement during times when higher-priority operations are taking place. Spooling and caching are inappropriate. Interrupt-driven I/O is most appropriate.


(b) tape drive: 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 yield the best performance.


(c) disk: Buffering can be used to hold data while in transit from user space to the disk, and vice versa. Caching can be used to hold disk-resident data for improved performance. Spooling is not necessary because disks are shared-access devices. Interrupt-driven I/O is always good for devices -- such as disks -- that transfer data at relatively slow rates.


(d) graphics card: 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 nature 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.

12.4.

Generally, blocking I/O is appropriate when the process will only be waiting for one specific event. Examples include a disk, tape, or keyboard read by an application program.


Non-blocking I/O is particularly useful when I/O may come from more than one source and the order of the I/O arrivals is not predetermined. Examples include network daemons listening to more than one network socket, window managers that accept mouse movement as well as keyboard input, and I/O-management programs, such as a copy command that copies data between I/O devices. In the last case, the program could optimize its performance by buffering the input and output and using non-blocking I/O to keep both devices fully occupied.

Non-blocking I/O is also important where real-time or quasi-real-time responses are needed. Examples include the need to track mouse movements in a GUI window and controls over special devices (such as landing gear).


Blocking I/O is what makes multiprogramming possible (and we know that's good). Also, non-blocking I/O is more complicated for programmers, because of the asynchronous rendezvous that is needed when an I/O occurs. Also, busy waiting is less efficient than interrupt-driven I/O, so the overall system performance would decrease without blocking I/O.





13.2

FCFS: Order is (125-143)-86-1470-913-1774-948-1509-1022-1750-130
Total seek distance is 7081 cyls.


SSTF: Order is (125-143)-130-86-913-948-1022-1470-1509-1750-1774 Total seek distance is 1745 cyls.
Note that SSTF optimizes for immediate seek time, not total seek time.


LOOK: Order is (125-143)-913-948-1022-1470-1509-1750-1774-130-86 Total seek distance is 3319 cyls.


C-LOOK: Order is (125-143)-913-948-1022-1470-1509-1750-1774-86-130 Total seek distance is 3363 cyls.


N-Step LOOK: Order is (125-143)-913-1470-1774-86-130-948-1022-1509-1750 Total seek distance is 4983 cyls.13.10.

(a) SSTF would give good access for the high-demand cylinders, but could result in starvation for other requests if the rate of requests is high. FCFS would be fair, but could result in poor performance if references to the high-demand cylinders were interspersed with references to cylinders far away. LOOK and C-LOOK would be good performers, but again could cause starvation if the rate of requests is very high. N-Step LOOK or N-Step C-LOOK would have the performance advantages of LOOK/C-LOOK and also avoid the possibility of starvation.


(b) One suggestion would be to use multiple queues, just as we did in multiple-queue CPU scheduling. One queue would handle the high-demand cylinders only; if a limit is placed on how many of those are serviced before servicing the same number from the other queue, starvation would not be a problem. Each queue could be ordered in LOOK or C-LOOK order to maximize performance while that queue's requests are being processed.


(c) Locate the FAT or inodes in cache to maximize the performance of lookups. Another possibility is to use the FAT/inodes to implement the equivalent of the mapped disk space allocation we discussed as part of file systems. That is, while the entries in the FAT/inodes would reflect the logical ordering of blocks within a file, the actual data could be stored anywhere on disk. Thus, it would be possible to distribute the actual data blocks in order to maximize performance.

13.16.

(a) Using the simplest methods, a drive would fail approximately every month. That is, 1 of the 1000 drives would fail each750,000 hrs/failure * 1/1000 drives = 750 hrs/drive-failure = approx. 31 days.


(b) MTBF for 20-year-olds can be approximated as: MTBF = 24 hrs/day * 365 days/yr ------------------------ 1 / 1000 people
so MTBF=8760000 person-hrs = 1000 person-yrs. Note that this only makes sense because the MTBF drops for each year beyond 20 that an adult continues living. A 20-year-old can't really expect to live that long.


(c)This can be estimated as 1M hours/failure ---------------- 24 hrs/day ---------------------- 365 days/yr
or approximately 114 years.



15.4.

(a) Multiaccess bus LAN. That way, computers could be added or removed from the network (important if we assume that not all students will have them) without requiring network reconfiguration.


(b) Tree-structured or hierarchical LAN. Each building could be a sub-tree (or multiple ones, if there are multiple departments within a building). That way, if one department or building were cut off from the others, the rest of campus could still function.


(c) Double-link ring WAN supporting LANs (which could be a mix of configurations), or multiaccess bus WAN as a trunk-line supporting heterogeneous LANs. The ring would be more costly, but would provide better reliability.


(d) Multiaccess bus WAN supporting heterogeneous LANs. At this scale, a double-link ring would be much too costly. The problem of reliability might be solved by having multiple multiaccess bus trunk-lines, some of lesser capacity that would primarily serve as backups in case of network congestion or failures.

15.6. Faster systems may be able to send out more packets in a shorter amount of time. The network would then have more packets traveling on it, resulting in more collisions, and therefore less throughput relative to the number of packets being sent.

More networks can be used, with fewer systems per network, to reduce the number of collisions.