Chapter 18
The Internal Operating Systems
18.1(BL1+) Users represent processes in a preemptive multitasking system. The method used to switch from one user to the next is the same as that used for switching processes. Each user is granted CPU execution time by the dispatcher, according to whatever dispatching algorithm is employed. The keyboards are managed by interrupt routines. Most user processes are idle most of the time, waiting for keyboard input in an I/O blocked state. Each user process that is ready to execute receives its quantum of time, then control returns to the dispatcher. A round-robin system, for example, would service each user process in turn, then return that user process to a ready state to await its next turn.
18.2(BL2) The process state value would normally be "running", "ready", or "blocked" (or, more realistically, some binary number representing each of these three conditions). There might also be a "start but not yet ready" state and a "suspended" state. The program counter and register save area is used to hold the context of a process when the process is not actually executing.
18.3(all BL1)
a.When a process moves from ready state to running state the dispatcher or process controller reloads its registers from its process control block, the PCB processor state is marked “running”, and control jumps to its program counter value. Processing proceeds.
b.When a process moves from running to blocked state, the program counter and registers are saved in the appropriate locations in the process’ PCB, the processor state is marked “blocked”, and the dispatcher selects another process for execution.
c.When a processor moves from running to ready state, its program counter and registers are saved, the process' state is marked “ready” to indicate its availability, and the dispatcher selects another process for execution.
d.A process usually moves from blocked to ready state as the result of an interrupt that indicates the completion of an I/O task. At that time, the PCB state is marked “ready”, and a pointer to the location of the I/O data, if any, is provided in the process' PCB pointer area.
18.4(BL1+) There is no path from the blocked state to the running state because the decision to execute a process must remain under the control of the dispatcher. The dispatcher selects a process from those in the ready state. A process that is no longer blocked becomes available for execution by returning to the ready state, not to the running state.
18.5(BL2) Interrupt routines operate outside the normal duties of the scheduler. Interrupts must be enabled, whether the operating system is preemptive or nonpreemptive, because many interrupts are of high priority importance to the operation of the system. For example, there must be a way for the operator to stop the system in an emergency. When a user types a keystroke on a multiuser system, it interrupts the system. The interrupt handler echoes the keystroke back to the screen, and, assuming that the keystroke does not alter the current processing state, makes the keystroke available to the user's process. Unless the keystroke is intended to stop the currently executing process, the operating system will return control to the executing process at the completion of the interrupt operation.
18.6(BL2) The multilevel feedback queue scheduling algorithm takes advantage of the best features of both FIFO and round-robin and avoids the disadvantages of each. FIFO scheduling is attractive in that it assures every process a shot at execution in the order requested. This is also true for the multilevel feedback queue, but, because the multilevel feedback queue is preemptive and limits the time to one quantum, it does not suffer the penalty of the FIFO algorithm in stalling short processes behind long ones. Instead, it completes short jobs quickly, and eliminates them from the queue. As short jobs complete, more time quanta are available to longer jobs, so that they may complete also. Finally, the longest jobs end up in a round-robin, where each will share the CPU equally until it is complete. The multilevel feedback queue algorithm is fair, it degrades gracefully under heavy system loads, it provides consistency, and it makes starvation unlikely, although not impossible.
18.7(BL2) The shortest job first algorithm attempts to execute jobs nonpreemptively based on the estimated time to completion. When successful, the SJF algorithm maximizes throughput, since the shortest jobs are completed ahead of any job that would tie up the CPU. However, maximum throughput comes at a high cost. Long jobs may never be run if short jobs keep jumping in ahead of them, so starvation is possible. The method is also unfair to long jobs, since they will always be kept waiting. SJF will not minimize turnaround time on average, again because long jobs are held. In fact turnaround time is highly inconsistent. The system will perform even worse when the load is heavy.
18.8(BL2+) Linux operating system modules are executed nonpremptively. This means that they must be tested to the level that there is NO chance that they can "hang" the system. They must also run extremely quickly and exit, so as not to prevent other, high priority applications from executing efficiently. If the module is a device driver, problems with the device can also freeze the system, if the module isn't designed with great care to take such possibilities into consideration.
18.9(BL2) The VSOS scheduling algorithm is similar to the multilevel feedback queue with only a single level of feedback. This algorithm exhibits a slight improvement in maximizing throughput over round-robin, since a process gets an immediate shot at the CPU. This is paid for by a slight increase in the risk of starvation, or at least delay under heavy load, or if a lot of short jobs enter the system at about the same time. In other respects its behavior is similar to the ordinary round-robin algorithm.
18.10(BL2) While this method works under ideal conditions, it has two major shortcomings: lack of cooperation and bugs in application programs. A program that refuses to cooperate can prevent other programs from executing. This is a fairly common occurrence with game programs. More serious is the issue of bugs. Since the system cannot preempt a program that is executing, an application with, say, an infinite loop will lock up the system entirely, causing data loss, and necessitating rebooting of the system. Most users of earlier versions of Windows are familiar with this event.
18.11(BL2+) When virtual storage is used, relocation is unnecessary because the program addresses are considered logical, rather than physical. The translation from logical address to physical memory location is handled automatically by hardware during the execution of each instruction.
18.12(BL2+) The operating system must work in synergy with the virtual storage hardware for the execution of each instruction. The operating system must keep track of available physical space for the loading of new processes, as well as for the replacement of pages. It must maintain current images of each logical program in an image store. It must establish working sets for each process. It must maintain page tables for each process. It must implement a page replacement policy that will enable processes to continue to execute when there are no available frames and that will prevent thrashing. This includes writing pages back to the current image store when they have been modified. It must notify the hardware of the location of the applicable page table each time a process is moved to its ready state for execution.
18,13(BL2+) The major hardware factor affecting virtual storage performance is the amount of installed physical memory. This sets the number of frames available for virtual storage. More frames results in fewer page faults, and therefore less need for disk access to replace missing pages. Other hardware factors include disk speed, special features that support various page replacement algorithms, and the presence of a translation lookaside buffer. Faster disk speed makes page replacement faster. The presence of hardware access and modified bits make it possible to implement fast determination of pages suited for replacement. The TLB makes frame lookup faster.
Operating system factors include the size of the working sets and the ability to manipulate working set size dynamically to optimize the page table for each process, the choice of page replacement algorithms, the method used to maintain free frame lists, and the ability of the system to control thrashing. Larger working sets minimize the number of page faults in a process; however, they can make it more difficult to support all of the processes executing, and can contribute to thrashing if made too large. The choice of page replacement algorithms affects the time needed for page replacement and the control of thrashing. The effective management of free frame lists means that the OS has a clear and consistent picture of the frames available for use in replacement. Some frame list methods also allow the fast replacement of pages directly from memory without accessing the disk.
18.14(BL1+) Each student will have a different drawing, however each drawing is essentially the same as figure 18.8, except for the choice of frames in each page table and the fact that there are two processes instead of three.
18.15(BL2-) Each student will have a different drawing. The key to this drawing is that the page table for each program will have the same frames for the pages that contain program code and different frames for the data. (Note that location 100 is a special situation, since it falls in a page that also contains data, and must be located in a data page.) A typical answer might resemble the following. For convenience, this example assumes a page size of 50.
18.16(BL1+) This page table contains 20 entries, numbered 0 to 19. Pages 0 through 9 correspond to frames 31 to 40, respectively. Pages 10 through 14 correspond to frames 45 to 49, respectively, and pages 15 through 19 correspond to frames 8 through 12, respectively.
18.17(BL2) The installation of additional physical memory increases the number of pages available to the system. If the system load remains constant, this means more pages available to each process, thereby reducing the number of page faults. Since page faults usually require disk access, (unless solid state memory is used to hold the page images), which is observably slow, the reduction of page faults can result in noticeable improvement in system performance.
18.18(BL2+) This is, of course, an exercise with a multitude of possible solutions. One solution has three processes, each with four pages in memory. The memory maps and page tables for each process at a given point in time are shown in the accompanying figure. Now suppose that process-1 is executing, needs page 2, and declares a page fault. The system notes that page 2 in process-2 is the least recently used page in the system, and removes that page to satisfy process-1. Process-1 is blocked, waiting for its page, and process-2 starts to execute. Now process-2 needs its page 2, and declares a page fault. The system removes page 5 from process-3 to satisfy process-2’s request. Process-3 starts to execute, notes that its page 5 is missing, and declares a page fault, which removes a page from process-1. Now, process-1 is ready to run, but can't, because the page it needed was taken while it was waiting for another page transfer. The process repeats, and no process can execute. The system is thrashing.
18.19(BL2+) For most virtual systems, physical memory is divided into pages of fixed size, and any logical page can fit into any physical page, therefore, the only fragmentation would be the small amount of internal fragmentation that occurs when a page is not full. Since logical storage is usually used from location 0–upward, perhaps with a separate region for data, there would only be one or two partial pages. Fragmentation is not a problem with virtual storage. As the page size is increased, the amount of fragmentation increases, since there would be more unused space, on average, on a partial page, but the fragmentation is still minor.
18.20(BL3) With page sharing, several processes are sharing the same physical page. Since the page is being shared, it incurs heavy usage, and becomes an unlikely candidate for page replacement. With several processes using that page, the number of page faults is reduced from the level that would occur if each process required its own copy of the page. A further reason is that there are fewer overall pages in physical memory, which means that the system can offer each process more pages at a time.
18.21(BL2) If the users are sharing programs, their processes are sharing the pages that hold the program code. The number of pages in physical memory are reduced, which makes those pages available to processes that represent an increased number of users. This illustrates that the number of pages required by users that are executing common utilities and programming tools is small, since each user's process requires its own pages only to hold its individual data.
18.22(BL2) Deadlocking occurs when a process cannot continue execution because it requires a resource that is held by another process. The other process, in turn, is also blocked, because it requires a resource held by the first process. The deadlock can extend to multiple processes, blocked in a circular fashion. Deadlock cannot occur in MS-DOS because there is only one process operating at a time, so there is no resource sharing.
18.23a.(BL3)This algorithm favors jobs that require substantial amounts of I/O. While these jobs are blocked, real time increases without an equivalent use in CPU time. This will increase the priority of the job, so that when the job returns to ready state it will be chosen almost immediately for the additional CPU time that it needs. If the CPU time it requires is short, just enough to require another I/O operation, the job will run with high efficiency, because its priority will be high whenever it needs the CPU. This is characteristic of I/O bound jobs with this algorithm.
b.(BL2+) If every process running is CPU bound, the priority of a process will drop immediately when it times out, because it has just used CPU time, raising its ratio. At that point, the process that has been waiting the longest will have the highest priority, since its real time is the longest in relationship to its last CPU time. Extending this idea, the lowest priority will go to the process that most recently executed, and the priority will grow as every other process executes, at which point it will again be able to execute. Thus, every process executes in turn until it times out, then returns to the end of the line, which is the definition of a round-robin algorithm.
c.(BL2+) This algorithm meets many of the dispatching objectives well. Starvation is not possible because a process will eventually be of highest priority to execute. It balances resources by favoring I/O bound jobs. It maximizes CPU utilization by assuring that I/O bound jobs get CPU time whenever they need it, and using the remaining CPU time for CPU bound jobs. It provides reasonably consistent response time. It degrades gracefully under heavy loads, because every process in the system still receives its round-robin time. It is fair. The algorithm does not address the issues of turnaround time, response time, or throughput. The results will vary, based on the process mix.
18.24(BL1+) The working set concept is an attempt to balance the optimum use of memory in a virtual storage system with a minimum amount of paging. The working set is the fraction of a process resident in memory, of sufficient size that the process will execute with a minimum number of page faults, yet not wasteful of memory that could be used by other processes. The principle of locality states that well-designed programs generally execute in a small area of their logical memory at any given time, although the actual area will shift with time. This principle indicates that is possible to execute most programs with a small working set.
18.25(BL2-) Different programs have different working set requirements, and there is no way to determine the optimum working set in advance. Furthermore, the amount of space required can change during execution, as different parts of a program are executed. A system that assigns a working set dynamically can adjust the working set size as the program progresses. A program that needs more space can get it, while a program that does not need the space can yield it to other processes that do.
18.26(BL2-) Deadlock prevention is designed to prevent deadlock by eliminating the conditions that make deadlock possible. Implementation is simple, but the cost is high, because it prevents the sharing of resources even when sharing would be possible. Deadlock prevention is the safest method, and under some conditions is necessary, just as deadlock would be prevented on a road that carries only emergency vehicles.