2.1 GENERAL INTRODUCTION OF OPERATING SYSTEM

2.1  GENERAL INTRODUCTION OF OPERATING SYSTEM

We have described the components of a computer system, which consists of hardware system and software system. In this chapter, we will embark on a discussion of operation system.

Let us first divide the software system into two broad categories: application software and system software. Application software consists of the program for performing tasks particular to the machine's utilization. Examples of application software include spreadsheets, managing database system, desktop publishing systems, developing gaphics, and games. In contrast to application software, system software comprises a large number of programs. These programs start up the computer and function as the principal coordinator of all hardware components and application software. Without system software loaded into RAM of your computer, your hardware and application software are useless.

1. Operating System Overview

System software can be grouped into three basic parts: operating system, utility software, and language translators. The majority of an installation's utility software consists of programs for performing activities that are fundamental to computer installations yet not included in the operating system. In a sense, utility software consists of software units that extend the capabilities of the operating system. For example, the ability to format a disk or to copy a file is often not implemented within the operating system itself but instead is provided by means of a utility program. Other instances of utility software include software for communicating through a modem over telephone lines, software to compress and decompress data, and software for handling network communication.

The distinction between application software and utility software is often vague. From our point of view, the distinction is whether the package is part of the software infrastructure. Thus a new application may evolve into a utility if it becomes a fundamental tool. The distinction between utility software and the operating system is equally vague. Some systems implement the software for providing such basic services as listing files in mass storage as utility software; others include it within the operating system. The operating system (OS), the most important system software component, consists of the master programs, called the supervisor, that controls the execution of application programs and acts as an interface between the user of a computer and the computer hardware.

2. Operating System Objectives and Functions

（1）The operating system as a user/computer interface.

The portion of an operating system that defines the interface between the operating system and its users is often called the shell. The job of the shell is to communicate with the user, or users, of the computer. Modern shells perform this task by means of a graphical user interface (GUI) in which objects to be manipulated, such as files and programs, are represented pictorially on the monitor screen as icons. These systems allow users to issue commands by pointing to and pushing these icons on the screen by mouse. older shells communicate via users through textual messages using a keyboard and monitor screen.

（2）The operating system as resource manager.

A computer is a set of resources for the movement, storage, and processing of data and for the control of these functions. An operating system's kernel is responsible for managing these resources. In contrast to an operating system's shell, the internal pad of an operating system is often called its kernel. A kernel contains those software components that perform the very basic functions required by the computer installation. An operating system's kernel consists of the file management, memory management, I/O management, and thescheduler.

3. The Evolution of Operating Systems

（1）Serial Processing.

With the earliest computers, from the late 1940s to the mid-1950s, the programmer inter- acted directly with the computer hardware; there was no operating system. These computers were run from a console consisting of display lights, toggle switches, some form of input device, and a printer. Programs in computer code were loaded with the input device. If an error halted the program, the error condition was indicated by the lights. The programmer could proceed to examine registers and main memory to determine the cause of the error. If the program proceeded to a normal completion, the output appeared on the printer.

These early systems presented two main problems.

·    Scheduling: Most installations used a sign-up sheet to reserve machine time. Typically, a user could sign up for a block of time in multiples of a half hour or so. A user might sign up for an hour and finish in 45minutes; this would result in wasted computer idle time. On the other hand, the user might run into problems, not finish in the allotted time, and be forced to stop before resolving the problem.

·    Setup time: A single program, called a job, could involve loading the compiler plus the high level language program (source program) into memory, saving the compiled program (object program), and then loading and linking together the object program and common functions. Each of these steps could involve mounting or dismounting tapes or setting up card decks. If an error occurred, the hapless user typically had to go back to the beginning of the setup sequence. Thus, a considerable amount of time was spent just in setting up the program to run.

This mode of operation could be termed serial processing, reflecting the fact that users had access to the computer in series. Over time, various system software tools were developed to attempt to make serial processing more efficient. These included libraries of common functions, linkers, loaders, debuggers, and I/O driver routines that were available as common software for all users.

（2）Simple Batch Systems.

Early machines were very expensive and therefore it was important to maximize machine use. The wasted time caused by scheduling and setup time was unacceptable.

To improve use, the concept of a batch operating system was developed. The central idea behind the simple batch processing scheme was the use of a piece of software known as the monitor. With the use of this type of operating system, the user no longer has direct access to the machine. Rather, the user submits the job on cards or tape to a computer operator, who batches the jobs together sequentially and places the entire batch on an input device for use by the monitor. Each program is constructed to branch back to the monitor when it completes processing, at which point the monitor automatically begins loading the next program.

With a batch operating system, machine time alternates between execution of user programs and execution of the monitor. There have been two sacrifices: some main memory is now given over to the monitor and some machine time is consumed by the monitor. Both of these are forms of overhead. Even with this overhead, the simple batch system improves the use of the computer.

（3）Multiprogrammed Batch Systems.

Even with the automatic job sequencing provided by a simple batch operating system, the processor is often idle. The problem is that I/O devices are slow compared to the processor. The calculation concerns a program that processes a file of records and performs 100 machine instructions per record on average. In this example, the computer spends more than 96 percent of its time waiting for I/O devices to finish transferring data! The processor spends a certain amount of time executing until it reaches an I/O instruction. It must then wait until that I/O instruction concludes before proceeding.

This inefficiency is not necessary. We know that there must be enough memory to hold the operating system (resident monitor) and one user program. Suppose that there is room for the operating system and two user programs. Now when one job needs to wait for I/O, the processor can switch to the other job, which likely is not waiting for I/O. Furthermore, we might expand memory to hold more programs and switch among all of them. The process is known as multiprogramming, or multitasking. It is the central theme of modern operating systems.

As with a simple batch system, a multiprogramming batch system is a program that must rely on certain computer hardware features. The most notable additional feature that is useful for multiprogramming is the hardware that supports I/O interrupts and DMA with interrupt-driven I/O or DMA, the processor can issue an I/O command for one job and proceed with the execution of another job while the I/O is carried out by the device controller. When the I/O operation is completed, the processor is interrupted and control is passed to an interrupt-handling program in the operating system. The operating system will then pass control to another job.

Multiprogramming operating systems are fairly sophisticated compared to single-program, or uniprogramming, systems. To have several jobs ready to run, they must be kept in main memory, requiring some form of memory management. In addition, if several jobs are ready to run, the processor must decide which one to run, which requires some algorithm for scheduling.

（4）Time-Sharing Systems.

With the use of multiprogramming, batch processing can be quite efficient. However, for many jobs, it is desirable to provide a mode in which the user interacts directly with the compute. Indeed, for some jobs, such as transaction processing, an interactive mode is essential.

The requirement for an interactive computing facility can be, and often is, met by the use of a dedicated microcomputer. That option was not available in the 1960s, when most computers were big and costly. Instead, time-sharing was developed.

Just as multiprogramming allows the processor to handle multiple batch jobs at a time, multiprogramming can be used to handle multiple interactive jobs. In this latter case, the technique is referred to as time sharing, reflecting the fact that the processor's time is shared among multiple users. The basic technique for a time-sharing system is to have multiple users simultaneously using the system through terminals, with the operating system interleaving the execution of each user program in a short burst, or quantum, of computation. Thus, if there are n users actively requesting service at one time, each user wi1l see on the average only 1/n of the effective computer speed, not counting operating system overhead. However, given the relatively slow human reaction time, the response time on a properly designed system should be comparable to that on a dedicated computer.

（5）Both batch multiprogramming and time sharing multiprogramming.

Time sharing and multiprogramming raise a host of new problem for operating system. If multiple jobs are in memory, then they must be protected from interfering with each other by, for example, modifying each other's data. With multiple interactive users, the file system must be a protected so that only authorized users have access to a particular file. The contention for resources, such as printers and mass storage devices, must be handled. These and other problems, with possible solutions, will be encountered throughout the text.

4. Major Achievements

Operating systems are among the most complex pieces of software yet developed. This reflects the challenge of trying to meet the difficult and in some cases competing objectives of convenience, efficiency, and ability to evolve. The major achievements of operating systems are as follows.

（1）Process management.

The most fundamental building block in a modern operating system is the process. The principal function of the operating system is to create, manage, and terminate processes. While processes are active, the operating system must see that each is allocated time for execution by the processor, coordinate their activities, manage conflicting demands, and allocate system resources to processes.

To perform its process-management functions, the operating system must maintain a description of each process. Each processor represented by a process image, which includes the address space within which the process executes and a process control block. The latter contains all the information that is required by the operating system to manage the processor, including its current state, resources allocated to it, priority and other relevant data.

During its lifetime, a process moves among a number of states. The most important of these are Ready, Running, and Blocked. A Ready process is one that is not currently executing but that is ready to be executed as soon as the operating system dispatches it. The Running process is that process which is currently being executed by the processor. In a multiple-processor system, more than one process can be in this state. A blocked process is waiting for the completion of some event, such as I/O operation.

A Running process is interrupted either by an interrupt, which is an event that occurs outside the process and which is recognized by the processor, or by executing a supervisor call to the operating system. In either case, the processor perform a context switch, transferring control to an operating system routine. After it has completed necessary work, the operating system may resume the interrupted process or switch to some other process.

（2）Mutual exclusion.

The central themes of modern operating system are multiprogramming, multiprocessing, and distributed processing. Fundamental to these themes, and fundamental to the technology of operating system design, is concurrency. When multiple processes are executing concurrency, either actually in the case of a multiprocessor system or virtually in the case of a single-processor multiprogramming system, issues of conflict resolution and cooperation arise.

Concurrent processes may interact in a number of ways. Processes that are unaware of each other may nevertheless compete for resources, such as processor time and access to I/O devices. Processes may be indirectly aware of one another because they share access to a common object, such as a block of main memory or a file. And processes may be directly aware of each other and cooperate by the exchange of information. The key issues that arise in these interactions are mutual exclusion and deadlock.

Mutual exclusion is a condition in which there is a set of concurrent processes, only one of which is able to access a given resource or perform a given function at any time. Mutual exclusion techniques can be used to resolve conflicts, such as competition for resources, and to synchronize processes so that they can cooperate. An examp1e of the latter is the producer/ consumer model, in which one process is putting data into a buffer, and one or more processes are extracting data from that buffer.

A number of software algorithms for providing mutual exclusion have been developed, of which the best known is Dekker's algorithm. The software approach is likely to have high processing overhead, and the risk of logical errors is high. A second approach to supporting mutual exclusion involves the use of special purpose machine instructions. This approach reduces overhead, but it is still inefficient because it uses busy-waiting.

Another approach to supporting mutual exclusion is to provide features within the operating system. Two of the most common techniques are semaphores and message facilities. Semaphores are used for signaling among processes and can be used readily to enforce a mutual-exclusion discipline. Messages are useful for the enforcement of mutual exclusion and also provide an effective means of interprocess communication.

（3）Deadlock.

Deadlock is the blocking of a set of processes that either compete for system resources or communicate with each other. The blockage is permanent unless the operating system takes some extraordinary action, such as killing one or more processes or forcing one or more processes to backtrack. Deadlock may involve reusable resources or consumable resources. A consumable resource is one that is destroyed when it is acquired by a process; examples include messages and information in I/O buffers. A reusable resource is one that is not depleted or destroyed by use, such as an I/O channel or a region of memory.

There are three general approaches to dealing with deadlock: prevention, detection, and avoidance. Deadlock prevention guarantees that deadlock will not occur by assuring that one of the necessary conditions for deadlock is not met. Deadlock detection is needed if the operating system is always willing to grant resource requests; periodically, the operating system must check for deadlock and take action to break the deadlock. Deadlock avoidance involves the analysis of each new resource request to determine if it could lead to deadlock, and granting it only if deadlock is not possible.

（4）Memory management.

One of the most important and most complex tasks of an operating system is memory management. Memory management involves treating main memory as a resource to be allocated to and shared among a number of active processes. To efficiently use the processor and the I/O facilities, it is desirable to maintain as many processes in main memory as possible. In addition, it is desirable to free programmers from size restriction in program development.

The way to address both of these concerns is to use virtual memory. With virtual memory, all address references are logical references that are translated at run time to real addresses. This use allows a process to be located anywhere in main memory and for that location to change over time. Virtual memory also allows a process to be broken up into pieces. These pieces need not be contiguously located in main memory during execution, and indeed it is not even necessary for all the pieces of the process to be in main memory during execution.

Two basic approaches to providing virtual memory are paging and segmentation. With paging, each process is divided into relatively small, fixed-size pages. Segmentation provides for the use of pieces of varying sizes. It is also possible to combine segmentation and paging in a single memory-management scheme.

A virtual-memory-management scheme requires both hardware and software support. The hardware support is provided by the processor. The support includes dynamic translation of virtual addresses to physical addresses and the generation of an interrupt when a referenced page or segment is not in main memory. Such an interrupt triggers the memory-management software in the operating system.

A number of design issues relate to operating system support for memory management.

·    Fetch policy: Process pages can be brought in on demand, or a prepaging policy can be used; the latter clusters the input activity by bringing in a number of pages at once.

·    Placement policy: With a pure segmentation system, an incoming segment must be fit into an available space in memory.

·    Replacement policy: When memory is full, a decision must be made as to which page or pages are to be replaced.

·    Resident set management: The operating system must decide how much main memory to allocate to a particular process when that process is swapped in. This can be a static allocation made at process creation time, or it can change dynamically.

·    Cleaning policy: Modified process pages can be written out at the time of replacement, or a precleaning policy can be used; the latter clusters the output activity by writing out a number of pages at once.

·    Load control: Load control is concerned with determining the number of processes that will be resident in main memory at any given time.

（5）Uniprocessor scheduling.

The operating system must make three types of scheduling decisions with respect to the execution of processes. Long-term scheduling determines when new processes are admitted to the system. Medium-term scheduling is pad of the swapping function and determines when a program is brought partially or fully into main memory so that it may be executed. Short-term scheduling determines which ready process will be executed next by the processor. This section focuses on the issues relating to short-term scheduling.

A variety of criteria are used in designing the short-term scheduler. Some of these criteria relate to the behavior of the system as perceived by the individual user (user oriented), whereas others view the total effectiveness of the system in meeting the needs of all users (system oriented). Some of the criteria relate specifically to some quantitative measure of performance, whereas others are more qualitative in nature. From a user's point of view, response time is generally the most important. characteristic of a system, whereas from a system point of view, throughput or processor utilization is important.

A variety of algorithms have been developed for making the short-term scheduling decision among all ready processes. These include six aspects.

·    First-come, first-served: Select the process that has been waiting the longest for service.

·    Round-robin：Use time-slicing to limit any running process to a short burst of processor time, and route among all ready processes.

·    Shortest process next: Select the process with the shortest expected process time and do not preempt the process.

·    Shortest remaining time: Select the process with the shortest expected remaining process time. A process may be preempted when another process becomes ready.

·    Highest response ratio next: Base the scheduling decision on an estimate of normalized turnaround time.

·    Feedback: Establish a set of scheduling queues and allocate processes to queues based on execution history and other criteria.

The choice of scheduling algorithm will depend on expected performance and on implementation complexity.

（6）Multiprocessor and real-time scheduling.

With a tightly coupled multiprocessor, multiple processors have access to the same main memory. In this configuration, the scheduling structure is somewhat more complex. For example, a given process may be assigned to the same processor for its entire life, or it may be dispatched to any processor each time when it enters the running state. Performance studies suggest that the differences among various scheduling algorithms are less significant in a multiprocessor system.

A real-time process or task is one that is executed in connection with some process or function or set of events external to the computer system and that must meet one or more deadlines to interact effectively and correctly with the external environment. A real-time operating system is one that must manage real-time processes. In this context, the traditional criteria for choosing a scheduling algorithm do not apply. Rather, the key factor is the meeting of deadlines. Algorithms that rely heavily on preemption and on reacting to relative deadlines are appropriate in this context.

（7）I/O management.

The computer system’s interface to the outside world is its I/O architecture. This archi- tecture is designed to provide a systematic means of controlling interaction with the outside world and to provide the operating system with the information it needs to manage I/O activity effectively.

The I/O function is generally broken up into a number of layers, with lower layers dealing with details that are closer to the physical functions to be performed, and higher layers dealing with I/O in a logical and generic fashion. The result is that changes in hardware parameters need not affect most of the I/O software.

A key aspect of I/O is the use of buffers that are controlled by I/O utilities rather than by application processes. Buffering smooth out the differences between the internal speeds of the computer system and the speeds of I/O devices. The use of buffers also decouples the actual I/O transfer from the address space of the application process, which allows the operating system more flexibility in performing its memory-management function.

The aspect of I/O that has the greatest impact on overall system performance is disk I/O. Accordingly, there has been greater research and design effort in this area than in any other kind of I/O. Two of the most widely used approaches to improving disk I/O performance are disk scheduling and the disk cache.

At any time, there may be a queue of requests for I/O on the same disk. It is the object of disk scheduling to satisfy these requests in a way that minimizes the mechanical seek time of the disk and hence improves performance. The physical layout of pending requests plus considerations of locality come into play.

A disk cache is a buffer, usually kept in main memory, that functions as a cache of disk blocks between disk memory and the rest of main memory. Because of the principle of locality, the use of a disk cache should substantially reduce the number of block I/O transfers between main memory and disk.

（8）File management.

A file-management system is a set of system software that provides services to users and applications in the use of files, including file access, directory maintenance, and access control. The file-management system is typically viewed as a system service that itself is served by the operating system, rather than being part of the operating system itself. However, in any system, at least part of the file-management function is performed by the operating system.

A file consists of a collection of records. The way in which these records may be accessed determines its logical organization and to some extent its physical organization on disk. If a file is primarily to be processed as a whole, then a sequential file organization is the simplest and most appropriate. If sequential access is needed but random access to an individual file is also desired, then an indexed sequential file may give the best performance. If access to the file is principally at random, then an indexed file or hashed file may be the most appropriate.

Whatever file structure is chosen, a directory service is also needed to allow file to be organized in a hierarchical fashion. This organization is useful to the user in keeping track of file and is useful to the file-management system in providing access control and other services to user.

File records, even when of fixed size, generally do not conform to the size of a physical disk block. Accordingly, some sort of blocking strategy is needed. A trade-off among complexity performance, and use of space determines the blocking strategy to be used.

KEYWORDS

NOTES

（1）application software（应用软件）。它为利用计算机解决各种实际问题而编制的程序。

（2）system software（系统软件）。它是计算机的管理、控制、维护、使用以及程序安装等与硬件配套管理的基础软件。

（3）operating system（操作系统，可缩写为OS）。它负责管理和控制计算机系统的各种资源，合理地组织计算机的工作流程，以充分发挥计算机系统的效率；是用户和计算机之间的接口。

（4）shell（操作系统的外壳程序）。它是用户与操作系统间的一种软件接口。

（5）kernel（内核）。在计算机软件中，当装入操作系统的任何部分时，事先必须已经并总是存在于内存（主存）之中的操作系统中的那部分内容，主要包括一些经过严格测试而准确无误的例行程序，它们可以实现基本的装入和管理功能。

（6）batch processing（批处理）。以提交作业的方式把任务的执行过程集中起来，经过合理搭配，通过输入装置提交给计算机系统。

（7）multitasking（多任务）。在多道程序设计中，计算机内存中同时存放几道相互独立的程序，它们在管理程序的控制下，相互穿插地运行。

（8）time-sharing system（分时系统）。一般运行在一台主机带若干台终端的系统，即若干台终端共享一台CPU设备（即联机操作方式）。它采用分时技术，用时间轮流转的办法使一台计算机能够为多个终端用户服务，执行每个用户提出的任务。UNIX是个典型的分时操作系统。分时（Time-Sharing）是指操作系统按照一定的分配原则把CPU的整个机时划分为若干个极小的时间片，然后将其依次轮流地分配给各终端用户使用。

（9）process management（进程管理）。负责进程的创建、调度、执行和撤销。

（10）distributed processing（分布式处理）。将不同地点或具有不同功能的或拥有不同数据的多台计算机用通信网络连接起来，在控制系统的统一管理控制下，协调地完成信息处理任务。

（11）deadlock（死锁）。多个进程循环等待它方占有的资源而无限地僵持下去的局面。

（12）I/O buffers（输入/输出缓冲区）。一种无须主程序干预就可以将数据传输给内存或从内存调出的缓冲器。可通过编程的方法使得输入输出完成时计算机产生一个内部中断。

（13）I/O channel（输入/输出通道）。允许在内存储器和输入输出设备之间独立通信的一种设备，它控制所有的外部设备，并实现信息传输的正确性校验。

（14）paging（分页）。主存与辅存之间的页面传送过程。

（15）real-time process（实时处理）。指计算机可以随时对发生的外部事件做出及时的响应，在严格的时间内完成相应的处理。

（16）file management（文件管理）。负责向用户提供创建文件、撤销文件、读写文件、打开和关闭文件等功能。

EXERCISES

1．Fill in the following blank.

（1）The portion of an operating system that defines the interface between the operating system and its users is often called the             .

（2）An operating system's kernel consists of the file management,        , management, and the scheduler.

（3）       contains all the information that is required by the operating system to manage the process, including its current state, resources allocated to it, priority another relevant data.

（4）        A       process is waiting for the completion of some event, such as I/O operation.

（5）       There are three general approaches to dealing with deadlock:       ,        ,

         and         .

（6）Two basic approaches to providing virtual memory are        and        .

（7）       smooth out the differences between the internal speeds of the computer system and the speeds of I/O devices.

2．Label each of the following statements as either true or false.

（1）        A blocked process is one that is not currently executing but that is ready to be executed as soon as the operating system dispatches it.

（2）        Semaphores are used for signaling among processes and can be used readily to enforce a mutual-exclusion discipline.

（3）        A consumable resource is one that is not depleted or destroyed by use, such as an I/O channel or a region of memory.

3．List algorithms for making the short-term scheduling decision among all ready processes.

READING MATERIALS

PROCESS MODEL AND DEADLOCK

1. Five-state Process Model

Fig. 2-1 shows the five-state process model. The five states of process are the following.

Fig. 2-1  five-state process model

·    Running: The process that is currently being executed. For a computer with a single processor, so at most one process can be in this state at a time.

·    Ready: Processes that are prepared to execute when given the opportunity.

·    Blocked: A process that cannot execute until some event occurs, such as the completion of an I/O operation.

·    New: A process that has just been created but has not yet been admitted to the pool of executable processes by the operating system.

·    Exit: A process that has been released from the pool of executable processes by the operating system, either because it halted or because it aborted for some reason.

Let us look at each possibility in turn.

·    Null→New: A new process is created to execute a program.

·    New→Ready: The operating system will move a process from the New state to the Ready state when it is prepared to take on an addition process. Most systems set some limit based on the number of existing processes or the amount of virtual memory committed to existing processes. The purpose of the limit is to assure that there are not so many active processes as to degrade performance.

·    Ready→Running: When it is time to select a new process to run, the operating system chooses one of the processes in the Ready state.

·    Running→Exit: The currently running process is terminated by the operating system if the process indicates that it has completed, or if it aborts.

·    Running→Ready: The most common reason for this transition is that the running process has reached the maximum allowable time for uninterrupted execution; virtually all multiprogramming operating systems impose this type of time discipline. There are several other alternative causes for this transition that are not implemented in all operating systems. For example, if the operating system assigns different levels of priority to different processes, then it is possible for a process to be preempted. Suppose, for example, that process A is running at a given priority level and that process B, at a higher priority level, is blocked. If the operating system learns that the event upon which process B has been waiting has occurred, moving B to a Ready state, then it can interrupt process A and dispatch process B. Finally, a process may voluntarily release control of the processor.

·    Running→Blocked: A process is put in the Blocked state if it requests something for which it must wait. A request to the operating system is usually in the form of a system service call, that is, a call from the running program to a procedure that is part of the operating system code. For example, a process may request a service from the operating system that the operating system is not prepared to perform immediately. It can request a resource, such as a file or a shared section of virtual memory, that is not immediately available. Or the process may initiate an action, such as an I/O operation, that must be completed before the process can continue. When processes communicate with each other, a process may be blocked when it is waiting for another process to provide input or waiting for a message from another process.

·    Blocked→Ready: A process in the Blocked state is moved to the Ready state when the event for which it has been waiting occurs.

2. Deadlock

Another problem that can arise during resource allocation is deadlock, the condition in which two or more processes are blocked from progressing because each is waiting for access to resources allocated to another. For example, one process may have access to the machine's printer but be waiting for the tape drive, while another process has access to the tape drive but is waiting for the printer. Another example occurs when processes create new processes to perform subtasks. If the scheduler has no space left in the process table and each process in the system must create an additional process before it can complete its task, then no process can continue. Such conditions, as in other settings, can severely degrade a system's performance.

Analysis of deadlock has revealed that it cannot occur unless all three of the following conditions are satisfied.

·    There is competition for non-shareable resources.

·    The resources are requested on a partial basis; that is, having received some resources, a process will return later to request more.

·    Once a resource has been allocated, it cannot be forcibly retrieved.

The point of isolating these conditions is that the deadlock problem can be removed by attacking any one of the three. In general, techniques that attack the third condition tend to fall in the category known as deadlock detection and correction schemes. In these cases, the occurrence of deadlock is considered so remote that no effort is made to avoid the problem. Instead, the approach is to detect when should it occur and then correct it by forcibly retrieving some of the allocated resources. Our example of a full process table falls in this class. A system administrator will usually establish a process table that is large enough for that particular installation. however, deadlock should occur due to a full table, the administrator merely uses his or her power as “super-user” to remove some of the process, which releases space in the process table so that the remaining processes can continue their tasks.

Techniques that attack the first two conditions tend to be known as deadlock avoidance schemes. One, for example, attacks the second condition by requiring each process to request all its resources at one time. Another perhaps more imaginative technique attacks the first condition, not by removing the competition directly but by converting non-shareable resources into shareable ones. For example, suppose the resource in question is a printer and a variety of processes require its use. Each time a process requests the printer, the operating system grant the request. However, instead of connecting the process with the printer's device driver, the operating system connects it to a device driver that stores the information to be printed on a disk rather than sending it to the printer. Thus each process, thinking it has access to the printer, executes in its normal way. Later, when the printer is available, the operating system can transfer the data from the disk to the printer. In this manner, the operating system has made the non-shareable resource appear shareable by creating the illusion of more than one printer. This technique of holding data for output at a later but more convenient time is called spooling and is quite popular on systems of all sizes.

Of course, when processes compete for a machine's resources, other problems arise. For example, a file manager should normally grant several processes access to the same file if the processes are merely reading data from the file, but conflicts can occur if more than one process tries to alter a file at the same time. Thus a file manger may allocate file access according to the needs of the processes, allowing several processes to have read access but only one having write access at any given time. Other system may divide the file into pieces so that different processes can alter different parts of the file concurrently. Additional problems must still be resolved, however. How, for example, should those processes with only read access to a file be notified when a process with write access alters the file?

A CACHING MODEL OF OPERATING SYSTEM

KERNEL FUNCTIONALITY

Micro-kernels to date have not provided compelling advantages over the conventional monolithic operating system kernel for several reasons.

First, micro-kernels are larger than desired because of the complications of a modern virtual memory system (such as the copy-on-write facility), the need to support many different hardware devices, and complex optimizations in communication facilities, all of which have been handled inside most micro-kernels. Moreover, performance problems have tended to force services originally implemented on top of a micro-kernel back into the kernel, increasing its size. For example, the Mach inter machine network server has been added back into some versions of Mach for this reason.

Second, micro-kernel do not support domain-specific resource allocation policies any better than monolithic kernels, an increasingly important issues with sophisticated applications and application systems. For example, the standard page-replacement policies of UNIX-like operating systems perform poorly for applications with random or sequential access. Placement of conventional operating system kernel services in a micro-kernel-based does not generally give the applications more control because the server is a fixed protected system service. Adding a variety of resource management policies to the micro-kernel fails to achieve the efficiency that application-specific knowledge allows and increases the kernel size and complexity.

Finally, micro-kernels are bloated with exception-handling mechanisms for the failure and unusual cases that can arise with the hardware and with other server and application modules. For example, the potential page-in exception conditions with external pagers introduce complications into Mach.

In this paper, we present an alternative approach to kernel design based on a caching model, as realized in the V++ Cache Kernel. The V++ Cache Kernel caches the active objects associated with the basic operating system facilities, namely the address spaces and threads associated with virtual memory, scheduling and IPC. In contrast to conventional micro-kernel design, it does not fully implement all the functionality associated with address spaces and threads. Instead, it relies on higher-level application kernels to provide the management functions required for a complete implementation, including the loading and write-back of these objects to and from the Cache Kernel. For example, on a page fault, the application kernel associated with the faulting thread loads a new page mapping descriptor into the Cache Kernel as part of a cached address space object. This new descriptor may cause another page mapping descriptor to be written back to another application kernel to make space for the new descriptor. Because the application kernel selects the physical page frazzle to use, it fully controls physical page selection, the page replacement policy and paging I/O.

The following sections argue that this caching model reduces supervisor-level complexity, provides application control of resource management and provides application control over exception conditions and recovery, addressing the problems with micro-kernel designs to date (including a micro-kernel that we developed previously).

The next section describes the Cache Kernel programming interface, illustrating its use by describing how an emulator application kernel would use this interface to implement standard UNIX-like services. Section 3 describes how sophisticated applications can use this interface directly by executing as part of their own application kernel. Section 3 describes how resources are allocated among competing applications. Section 4 describes our Cache Kernel implementation, and Section 5 describes its performance, which appears to provide competitive performance with conventional monolithic kernels. Section 6 describes previous research we see as relevant to this work. We close with a summary of the work, our conclusions and some indication of future directions.