UNIT I OS PDF - Operating Systems Concepts

UNIT I Introduction to Operating System Concept: Types of operating systems, operating systems concepts, operating systems services, Introduction to System call, System call types. Process Management– Process concept, the process, Process State Diagram, Process control block, Process Scheduling- Sc...

UNIT I Introduction to Operating System Concept: Types of operating systems, operating systems concepts, operating systems services, Introduction to System call, System call types. Process Management– Process concept, the process, Process State Diagram, Process control block, Process Scheduling- Scheduling Queues, Schedulers, Operations on Processes, Inter process Communication, Scheduling- Basic Concepts, Scheduling Criteria, and Scheduling Algorithms. Operating Systems concepts What is an Operating System?  An Operating System is a program that manages the computer hardware. It also provides a basis for application programs and acts as an intermediary between the computer user and the computer hardware.  An operating System is a collection of system programs that together control the operations of a computer system. Some examples of operating systems are UNIX, Mach, MS-DOS, MS-Windows, Windows/NT Operating system goals:  Execute user programs and make solving user problems easier.  Make the computer system convenient to use.  Use the computer hardware in an efficient manner. What Operating Systems Do or Computer System Components: A computer system can be divided roughly into four components: the hardware, the operating system, the application programs, and the users as shown in following figure: The hardware – the central processing unit(CPU), the memory, and the input/output(I/O) devices- provides the basic computing resources for the system. The application programs such as word processors, spreadsheets, compilers, and Web browsers define the ways in which these resources are used to solve users’ computing problems. The operating system controls the hardware and coordinates its use among the various application programs for the various users. We can also view a computer system as consisting of hardware, software, and data. The operating system provides the means for proper use of these resources in the operation of the computer system. Operating systems can be explored from two view points: the user and the system. User View: From the user’s point view, the OS is designed for one user to monopolize its resources. The goal is to maximize the work that the user is performing. In this case, OS is designed mostly for ease of use with some attention paid to performance and none paid to resource utilization-how various hardware and software resources are shared. System View: From the computer's point of view, an operating system is the program most intimately involved with the hardware. In this context, we can view an operating system as a resource allocator. A computer system has many resources that may be required to solve a problem: CPU time, memory space, file-storage space, I/O devices, and so on. The operating system acts as the manager of these resources. Types of operating systems Operating Systems can be categorized according to different criteria like whether an operating system is for mobile devices (examples Android and iOS) or desktop (examples Windows and Linux). we are going to classify based on functionalities an operating system provides: 1. Batch Operating System: This type of operating system does not interact with the computer directly. There is an operator which takes similar jobs having the same requirements and groups them into batches. It is the responsibility of the operator to sort jobs with similar needs. Batch Operating System is designed to manage and execute a large number of jobs efficiently by processing them in groups. 2. Multi-Programming Operating System: Multiprogramming Operating Systems can be simply illustrated as more than one program is present in the main memory and any one of them can be kept in execution. This is basically used for better utilization of resources. Time-Sharing Operating Systems: It is a type of Multiprogramming system with every process running in round robin manner. Each task is given some time to execute so that all the tasks work smoothly. Each user gets the time of the CPU as they use a single system. These systems are also known as Multitasking Systems. The task can be from a single user or different users also. The time that each task gets to execute is called quantum. After this time interval is over OS switches over to the next task. Multitasking: Time Sharing and Multiprogramming systems are also called multitasking sometimes as multiple tasks run in interleaving manner. 3. Multi-Processing Operating System: Multi-Processing Operating System is a type of Operating System in which more than one CPU is used for the execution of resources. It betters the throughput of the System. 4. Multi User Operating Systems: These systems allow multiple users to be active at the same time. These system can be either multiprocessor or single processor with interleaving. 5. Distributed Operating System: These types of operating system is a recent advancement in the world of computer technology and are being widely accepted all over the world and, that too, at a great pace. Various autonomous interconnected computers communicate with each other using a shared communication network. Independent systems possess their own memory unit and CPU. These are referred to as loosely coupled systems or distributed systems. These systems’ processors differ in size and function. The major benefit of working with these types of the operating system is that it is always possible that one user can access the files or software which are not actually present on his system but some other system connected within this network i.e., remote access is enabled within the devices connected in that network. 6. Network Operating System: These systems run on a server and provide the capability to manage data, users, groups, security, applications, and other networking functions. These types of operating systems allow shared access to files, printers, security, applications, and other networking functions over a small private network. One more important aspect of Network Operating Systems is that all the users are well aware of the underlying configuration, of all other users within the network, their individual connections, etc. and that’s why these computers are popularly known as tightly coupled systems. 7. Real-Time Operating System: These types of OSs serve real-time systems. The time interval required to process and respond to inputs is very small. This time interval is called response time.Real-time systems are used when there are time requirements that are very strict like missile systems, air traffic control systems, robots, etc. Types of Real-Time Operating Systems:  Hard Real-Time Systems: Hard Real-Time OSs are meant for applications where time constraints are very strict and even the shortest possible delay is not acceptable. These systems are built for  saving life like automatic parachutes or airbags which are required to be readily available in case of an accident. Virtual memory is rarely found in these systems.  Soft Real-Time Systems: These OSs are for applications where time-constraint is less strict. 8. Mobile Operating Systems: These operating systems are mainly for mobile devices. Examples of such operating systems are Android and iOS. Operating systems services Following are the five services provided by operating systems to the convenience of the users. 1. Program Execution: The purpose of computer systems is to allow the user to execute programs. So the operating system provides an environment where the user can conveniently run programs. Running a program involves the allocating and deallocating memory, CPU scheduling in case of multiprocessing. 2. I/O Operations : Each program requires an input and produces output. This involves the use of I/O. So the operating systems are providing I/O makes it convenient for the users to run programs. 3. File System Manipulation: The output of a program may need to be written into new files or input taken from some files. The operating system provides this service. 4. Communications: The processes need to communicate with each other to exchange information during execution. It may be between processes running on the same computer or running on the different computers. Communications can be occur in two ways: (a) shared memory or (b) message passing 5. Error Detection: An error is one part of the system may cause malfunctioning of the complete system. To avoid such a situation operating system constantly monitors the system for detecting the errors. This relieves the user of the worry of errors propagating to various part of the system and causing malfunctioning. Following are the three services provided by operating systems for ensuring the efficient operation of the system itself. i). Resource allocation: When multiple users are logged on the system or multiple jobs are running at the same time, resources must be allocated to each of them. Many different types of resources are managed by the operating system. ii). Accounting: The operating systems keep track of which users use how many and which kinds of computer resources. This record keeping may be used for accounting (so that users can be billed) or simply for accumulating usage statistics. iii). Protection: When several disjointed processes execute concurrently, it should not be possible for one process to interfere with the others, or with the operating system itself. Protection involves ensuring that all access to system resources is controlled. Security of the system from outsiders is also important. Such security starts with each user having to authenticate him to the system, usually by means of a password, to be allowed access to the resources. Introduction to System call and System call types The interface between a process and an operating system is provided by system calls. In general, system calls are available as assembly language instructions. They are also included in the manuals used by the assembly level programmers. System calls are usually made when a process in user mode requires access to a resource. Then it requests the kernel to provide the resource via a system call. A figure representing the execution of the system call is given as follows: As can be seen from this diagram, the processes execute normally in the user mode until a system call interrupts this. Then the system call is executed on a priority basis in the kernel mode. After the execution of the system call, the control returns to the user mode and execution of user processes can be resumed. In general, system calls are required in the following situations:  If a file system requires the creation or deletion of files. Reading and writing from files also require a system call.  Creation and management of new processes.  Network connections also require system calls. This includes sending and receiving packets.  Access to a hardware devices such as a printer, scanner etc. requires a system call. The following different types of system calls provided by an operating system: i) Process control:  end, abort  load, execute  create process, terminate process  get process attributes, set process attributes  wait for time  wait event, signal event  allocate and free memory ii) File management:  create file, delete file  open, close  read, write, reposition  get file attributes, set file attributes iii) Device management:  request device, release device  read, write, reposition  get device attributes, set device attributes  logically attach or detach devices iv) Information maintenance:  get time or date, set time or date  get system data, set system data  get process, file, or device attributes  set process, file, or device attributes v) Communications:  create, delete communication connection   send, receive messages  transfer status information  attach or detach remote devices Process Management Process Concept A process is basically a program in execution. The execution of a process must progress in a sequential fashion. A process is defined as an entity which represents the basic unit of work to be implemented in the system. To put it in simple terms, we write our computer programs in a text file and when we execute this program, it becomes a process which performs all the tasks mentioned in the program. When a program is loaded into the memory and it becomes a process, it can be divided into four sections: stack, heap, text and data. The following image shows a simplified layout of a process inside main memory: Stack section: The process Stack contains the temporary data such as method/function parameters, return address and local variables. Heap section: This is dynamically allocated memory to a process during its run time.  Text section: This includes the current activity represented by the value of Program Counter and the contents of the processor's registers. Data section: This section contains the global and static variables. Process State Diagram When a process executed, it changes the state, generally the state of process is determined by the current activity of the process. Each process may be in one of the following states:  New State: The process is being created.  Running State: A process is said to be running if it has the CPU, that is, process actually using the CPU at that particular instant.  Blocked (or waiting) State: A process is said to be blocked if it is waiting for some event to happen such that as an I/O completion before it can proceed. Note that a process is unable to run until some external event happens.  Ready State: A process is said to be ready if it needs a CPU to execute. A ready state process is runnable but temporarily stopped running to let another process run.  Terminated state: The process has finished execution. Process control block Each process is represented in the operating System by a Process Control Block. It is also called Task Control Block. It contains many pieces of information associated with a specific Process. It is very important for process management as the data structuring for processes is done in terms of the PCB. It also defines the current state of the operating system. The following are the data items:  Process state  Program counter  CPU registers  CPU scheduling information  Memory-management information  Accounting information  I/O status information Process state: The state may be new, ready, running, waiting, halted, and So on. Program counter: The counter indicates the address of the next instruction to be executed for this process. CPU registers: The registers vary in number and type, depending on the computer architecture. They include accumulators, index registers, stack pointers, and general-purpose registers, plus any condition- code information. Along with the program counter, this state information must be saved when an interrupt occurs, to allow the process to be continued correctly afterward. CPU-scheduling information: This information includes a process priority, pointers to scheduling queues, and any other scheduling parameters. Memory-management information: This information may include such information as the value of the base and limit registers, the page tables, or the segment tables, depending on the memory system used by the operating system. Accounting information: This information includes the amount of CPU and real time used, time limits, account numbers, job or process numbers, and so on. I/O status information: The information includes the list of I/O devices allocated to this process, a list of open files, and so on. The PCB simply serves as the repository for any information that may vary from process to process. Process Scheduling Scheduling Queues The processes that are entering into the system are stored in the Job Queue. Suppose if the processes are in the Ready state are generally placed in the Ready Queue. The processes waiting for a device are placed in Device Queues. There are unique device queues which are available for every I/O device. First place a new process in the Ready queue and then it waits in the ready queue till it is selected for execution. Once the process is assigned to the CPU and is executing, any one of the following events occur −  The process issue an I/O request, and then placed in the I/O queue.  The process may create a new sub process and wait for termination.  The process may be removed forcibly from the CPU, which is an interrupt, and it is put back in the ready queue. Representation of Process Scheduling: In the first two cases, the process switches from the waiting state to the ready state, and then puts it back in the ready queue. A process continues this cycle till it terminates, at which time it is removed from all queues and has its PCB and resources deallocated. Schedulers A scheduler is a decision maker that selects the processes from one scheduling queue to another or allocates CPU for execution. The Operating System has three types of schedulers: 1. Long-term scheduler or Job scheduler 2. Short-term scheduler or CPU scheduler 3. Medium-term scheduler 1. Long-term scheduler or Job scheduler: Long Term Scheduler loads a process from disk to main memory for execution. The new process to the ‘Ready State’.  It mainly moves processes from Job Queue to Ready Queue.  It controls the Degree of Multi-programming, i.e., the number of processes present in a ready state or in main memory at any point in time.   It is important that the long-term scheduler make a careful selection of both I/O and CPU-bound processes. I/O-bound tasks are which use much of their time in input and output operations while CPU-bound processes are which spend their time on the CPU. The job scheduler increases efficiency by maintaining a balance between the two.  In some systems, the long-term scheduler might not even exist. For example, in time-sharing systems like Microsoft Windows, there is usually no long-term scheduler. Instead, every new process is directly added to memory for the short-term scheduler to handle.  Slowest among the three (that is why called long term). 2. Short-Term or CPU Scheduler: CPU Scheduler is responsible for selecting one process from the ready state for running (or assigning CPU to it).  STS (Short Term Scheduler) must select a new process for the CPU frequently to avoid starvation.  The CPU scheduler uses different scheduling algorithms to balance the allocation of CPU time.  It picks a process from ready queue.  Its main objective is to make the best use of CPU.  It mainly calls dispatcher.  Fastest among the three (that is why called Short Term). The dispatcher is responsible for loading the process selected by the Short-term scheduler on the CPU (Ready to Running State). Context switching is done by the dispatcher only. A dispatcher does the following work:  Saving context (process control block) of previously running process if not finished.  Switching system mode to user mode.  Jumping to the proper location in the newly loaded program. Time taken by dispatcher is called dispatch latency or process context switch time. 3. Medium-term scheduler: Medium Term Scheduler (MTS) is responsible for moving a process from memory to disk (or swapping).  It reduces the degree of multiprogramming (Number of processes present in main memory).  A running process may become suspended if it makes an I/O request. A suspended processes cannot make any progress towards completion. In this condition, to remove the process from memory and make space for other processes, the suspended process is moved to the secondary storage. This process is called swapping, and the process is said to be swapped out or rolled out. Swapping may be necessary to improve the process mix (of CPU bound and IO bound)  When needed, it brings process back into memory and pick up right where it left off.  It is faster than long term and slower than short term. Context Switch In order for a process execution to be continued from the same point at a later time, context switching is a mechanism to store and restore the state or context of a CPU in the Process Control block. A context switcher makes it possible for multiple processes to share a single CPU using this method. A multitasking operating system must include context switching among its features. The state of the currently running process is saved into the process control block when the scheduler switches the CPU from executing one process to another. The state used to set the computer, registers, etc. for the process that will run next is then loaded from its own PCB. After that, the second can start processing. In order for a process execution to be continued from the same point at a later time, context switching is a mechanism to store and restore the state or context of a CPU in the Process Control block. A context switcher makes it possible for multiple processes to share a single CPU using this method.  Context-switch time is overhead; the system does no useful work while switching.  Time dependent on hardware support. Operations on Processes The operations on a process occur when the process is in a particular state or when the process makes a transition from one state to another. There are mainly five operations on a process:  Process Creation  Process Dispatch  Process Pre-emption  Process Blocking  Process Termination 1. Process Creation: The first operation that a process undergoes when it enters a system is process creation. It involves formation of a process and is associated with “New” state of the process. Process creation occurs due to any of the following events −  System initialization − When the computer is started, a number of system processes and background processes are created.  User request − A user may start executing a program leading to creation of a process.  Child process system call − A running process may create a child process by process creation system call.  Batch system − The batch system may initiate batch jobs A process may be created by another process using fork(). The creating process is called the parent process and the created process is the child process. A child process can have only one parent but a parent process may have many children. Both the parent and child processes have the same memory image, open files, and environment strings. However, they have distinct address spaces. A diagram that demonstrates process creation using fork() is as follows − 2. Process Dispatch: When a process in the ready state is selected for execution by the scheduler, process dispatch operation occurs. Process dispatch is initiated according to the scheduling algorithm used. It may happen when the CPU becomes idle and the ready queue has processes, time quantum allotted for an on-going process expires, a high priority process enters the system or a hardware interrupt occurs. When a new process is assigned to the CPU, its status is loaded from its Process Control Block (PCB). 3. Process Preemption: Process pre-emption is an operation by which the execution of an on-going process is suspended and some other process is selected by the CPU for execution. Process pre-emption may occur when time quantum of on-going process expires, a high priority process enters the ready queue or a hardware interrupt occurs. The preemption of executing processes in the CPU causes a phenomenon called context switch. Here, the context or state of the out-going process is stored in its PCB so that it can be reloaded when required and execution can be resumed from the same point as earlier. 4. Process Blocking: The on-going process is blocked and put in the “Waiting” state and swapped out of the CPU, if it needs some event to occur in order to proceed with execution. This event may be an input/output system call since the I/O events are executed in the main memory and don't require the processor. Here, the operating system blocks the process, when the process itself demands so. After the event is complete, the process again goes to the ready state. The following diagram demonstrates process dispatch, process pre-emption, and process blocking: 5. Process Termination: Process Termination is the operation of ending a process and releasing all the resources that have been held by the process. The process ceases to exist after its termination. Similar to process creation, there may be multiple reasons for process termination, as follows:  The process has completed the execution of its last instruction and so it is terminated by the operating system.  A child process can be terminated by its parent process if its task is no longer relevant. The child process sends its status information to the parent process before it terminates. Also, when a parent process is terminated, its child processes are terminated as well as the child processes cannot run if the parent processes are terminated.   The process can be terminated by the operating system if there are service errors.  A hardware malfunction may also cause process termination. Inter process Communication The concurrent processes executing in the operating system may be either independent processes or cooperating processes. A process is independent if it cannot affect or be affected by the other processes executing in the system. Clearly, any process that does not share any data (temporary or persistent) with any other process is independent. On the other hand, a process is cooperating if it can affect or be affected by the other processes executing in the system. Clearly, any process that shares data with other processes is a cooperating process. Inter process communication (IPC) allows different programs or processes running on a computer to share information with each other. IPC allows processes to communicate by using different techniques like sharing memory, sending messages, or using files. It ensures that processes can work together without interfering with each other. Cooperating processes require an Inter Process Communication (IPC) mechanism that will allow them to exchange data and information. The two fundamental models of Inter Process Communication are:  Shared Memory  Message Passing Following figure shows a basic structure of communication between processes via the shared memory method and via the message passing method: An operating system can implement both methods of communication. First, we will discuss the shared memory methods of communication and then message passing. Communication between processes using shared memory requires processes to share some variable, and it completely depends on how the programmer will implement it. One way of communication using shared memory can be imagined like this: Suppose process1 and process2 are executing simultaneously, and they share some resources or use some information from another process. Process1 generates information about certain computations or resources being used and keeps it as a record in shared memory. When process2 needs to use the shared information, it will check in the record stored in shared memory and take note of the information generated by process1 and act accordingly. Processes can use shared memory for extracting information as a record from another process as well as for delivering any specific information to other processes. Message passing provides a mechanism to allow processes to communicate and to synchronize their actions without sharing the same address space and is particularly useful in a distributed environment, where the communicating processes may reside on different computers connected by a network. A message-passing facility provides at least two operations: send(message) and receive(message). Role of Synchronization in IPC: In IPC, synchronization is essential for controlling access to shared resources and guaranteeing that processes do not conflict with one another. Data consistency is ensured and problems like race situations are avoided with proper synchronization. Advantages of IPC:  Enables processes to communicate with each other and share resources, leading to increased efficiency and flexibility.  Facilitates coordination between multiple processes, leading to better overall system performance.  Allows for the creation of distributed systems that can span multiple computers or networks.  Can be used to implement various synchronization and communication protocols, such as semaphores, pipes, and sockets. Scheduling Basic Concepts The process scheduling is the activity of the process manager that handles the removal of the running process from the CPU and the selection of another process on the basis of a particular strategy. Process scheduling is an essential part of a Multiprogramming operating systems. Such operating systems allow more than one process to be loaded into the executable memory at a time and the loaded process shares the CPU using time multiplexing. Categories of Scheduling: There are two categories of scheduling: 1. Non-preemptive: Here the resource can’t be taken from a process until the process completes execution. The switching of resources occurs when the running process terminates and moves to a waiting state. 2. Preemptive: Here the OS allocates the resources to a process for a fixed amount of time. During resource allocation, the process switches from running state to ready state or from waiting state to ready state. This switching occurs as the CPU may give priority to other processes and replace the process with higher priority with the running process. CPU scheduling CPU Scheduling is a process that allows one process to use the CPU while another process is delayed due to unavailability of any resources such as I / O etc, thus making full use of the CPU. In short, CPU scheduling decides the order and priority of the processes to run and allocates the CPU time based on various parameters such as CPU usage, throughput, turnaround, waiting time, and response time. The purpose of CPU Scheduling is to make the system more efficient, faster, and fairer. CPU Scheduler:  Selects from among the processes in memory that are ready to execute, and allocates the CPU to one of them.  CPU scheduling decisions may take place when a process: 1. Switches from running to waiting state. 2. Switches from running to ready state. 3. Switches from waiting to ready. 4. Terminates.  Scheduling under 1 and 4 is non preemptive.  All other scheduling is preemptive. Dispatcher: Dispatcher module gives control of the CPU to the process selected by the short-term scheduler; this involves: ✦Switching context ✦Switching to user mode ✦Jumping to the proper location in the user program to restart that program Dispatch latency – time it takes for the dispatcher to stop one process and start another running. Scheduling Criteria CPU scheduling criteria, such as turnaround time, waiting time, and throughput, are essential metrics used to evaluate the efficiency of scheduling algorithms. Now let’s discuss CPU Scheduling has several criteria. Some of them are mentioned below: 1. CPU utilization The main objective of any CPU scheduling algorithm is to keep the CPU as busy as possible. Theoretically, CPU utilization can range from 0 to 100 but in a real-time system, it varies from 40 to 90 percent depending on the load upon the system. 2. Throughput A measure of the work done by the CPU is the number of processes being executed and completed per unit of time. This is called throughput. The throughput may vary depending on the length or duration of the processes. 3. Turnaround Time For a particular process, an important criterion is how long it takes to execute that process. The time elapsed from the time of submission of a process to the time of completion is known as the turnaround time. Turn-around time is the sum of times spent waiting to get into memory, waiting in the ready queue, executing in CPU, and waiting for I/O. Turn Around Time = Completion Time – Arrival Time. 4. Waiting Time A scheduling algorithm does not affect the time required to complete the process once it starts execution. It only affects the waiting time of a process i.e. time spent by a process waiting in the ready queue. Waiting Time = Turnaround Time – Burst Time. 5. Response Time In an interactive system, turn-around time is not the best criterion. A process may produce some output fairly early and continue computing new results while previous results are being output to the user. Thus another criterion is the time taken from submission of the process of the request until the first response is produced. This measure is called response time. Response Time = CPU Allocation Time(when the CPU was allocated for the first) – Arrival Time Scheduling Algorithms 1. First-Come, First-Served Scheduling By far the simplest CPU-scheduling algorithm is the first-come, first-served (FCFS) scheduling algorithm. With this scheme, the process that requests the CPU first is allocated the CPU first. The implementation of the FCFS policy is easily managed with a FIFO queue. When a process enters the ready queue, its PCB is linked onto the tail of the queue. When the CPU is free, it is allocated to the process at the head of the queue. The running process is then removed from the queue. The code for FCFS scheduling is simple to write and understand. The average waiting time under the FCFS policy, however, is often quite long. Consider the following set of processes that arrive at time 0, with the length of the CPU-burst time given in milliseconds: Process Burst Time P1 24 P2 3 P3 3 If the processes arrive in the order P1, P2, P3, and are served in FCFS order, we get the result shown in the following Gantt chart: The waiting time is 0 milliseconds for process P1, 24 milliseconds for process P2, and 27 milliseconds for process P3. Thus, the average waiting time is (0 + 24 + 27)/3 = 17 milliseconds. If the processes arrive in the order P2, P3, P1, however, the results will be as shown in the following Gantt chart: The average waiting time is now (6 + 0 + 3)/3 = 3 milliseconds. This reduction is substantial. Thus, the average waiting time under a FCFS policy is generally not minimal, and may vary substantially if the process CPU-burst times vary greatly. In addition, consider the performance of FCFS scheduling in a dynamic situation. Assume we have one CPU-bound process and many I/O-bound processes. As the processes flow around the system, the following scenario may result. The CPU-bound process will get the CPU and hold it. During this time, all the other processes will finish their I/O and move into the ready queue, waiting for the CPU. While the processes wait in the ready queue, the I/O devices are idle. Eventually, the CPU-bound process finishes its CPU burst and moves to an I/O device. All the I/O-bound processes, which have very short CPU bursts, execute quickly and move back to the I/O queues. At this point, the CPU sits idle. The CPU-bound process will then move back to the ready queue and be allocated the CPU. Again, all the I/O processes end up waiting in the ready queue until the CPU-bound process is done. There is a convoy effect, as all the other processes wait for the one big process to get off the CPU. This effect results in lower CPU and device utilization than might be possible if the shorter processes were allowed to go first. The FCFS scheduling algorithm is non-preemptive. Once the CPU has been allocated to a process, that process keeps the CPU until it releases the CPU, either by terminating or by requesting I/O. The FCFS algorithm is particularly troublesome for time-sharing systems, where each user needs to get a share of the CPU at regular intervals. It would be disastrous to allow one process to keep the CPU for an extended period. 2. Shortest-Job-First Scheduling A different approach to CPU scheduling is the shortest-job-first (SJF) scheduling algorithm. This algorithm associates with each process the length of the latter's next CPU burst. When the CPU is available, it is assigned to the process that has the smallest next CPU burst. If two processes have the same length next CPU burst, FCFS scheduling is used to break the tie. Note that a more appropriate term would be the shortest next CPU burst, because the scheduling is done by examining the length of the next CPU burst of a process, rather than its total length. We use the term SJF because most people and textbooks refer to this type of scheduling discipline as SJF. As an example, consider the following set of processes, with the length of the CPU-burst time given in milliseconds: Process Burst Time P1 6 P2 8 P3 7 P4 3 Using SJF scheduling, we would schedule these processes according to the following Gantt chart: The waiting time is 3 milliseconds for process P1, 16 milliseconds for process P2,9 milliseconds for process P3, and 0 milliseconds for process P4. Thus, the average waiting time is (3 + 16 + 9 + 0)/4 = 7 milliseconds. If we were using the FCFS scheduling scheme, then the average waiting time would be 10.25 milliseconds. The SJF scheduling algorithm is provably optimal, in that it gives the minimum average waiting time for a given set of processes. By moving a short process before a long one, the waiting time of the short process decreases more than it increases the waiting time of the long process. Consequently, the average waiting time decreases. The real difficulty with the SJF algorithm is knowing the length of the next CPU request. For long-term (or job) scheduling in a batch system, we can use as the length the process time limit that a user specifies when he submits the job. Thus, users are motivated to estimate the process time limit accurately, since a lower value may mean faster response. (Too low a value will cause a time-limit exceeded error and require resubmission.) SJF scheduling is used frequently in long-term scheduling. Although the SJF algorithm is optimal, it cannot be implemented at the level of short-term CPU scheduling. There is no way to know the length of the next CPU burst. One approach is to try to approximate SJF scheduling. We may not know the length of the next CPU burst, but we may be able to predict its value. We expect that the next CPU burst will be similar in length to the previous ones. Thus, by computing an approximation of the length of the next CPU burst, we can pick the process with the shortest predicted CPU burst. The SJF algorithm may be either preemptive or nonpreemptive. The choice arises when a new process arrives at the ready queue while a previous process is executing. The new process may have a shorter next CPU burst than what is left of the currently executing process. A preemptive SJF algorithm will preempt the currently executing process, whereas a nonpreemptive SJF algorithm will allow the currently running process to finish its CPU burst. Preemptive SJF scheduling is sometimes called shortest-remaining-time-first scheduling. As an example, consider the following four processes, with the length of the CPU-burst time given in milliseconds: Process Arrival Time Burst Time P1 0 8 P2 1 4 P3 2 9 p4 3 5 If the processes arrive at the ready queue at the times shown and need the indicated burst times, then the resulting preemptive SJF schedule is as depicted in the following Gantt chart: Process P1 is started at time 0, since it is the only process in the queue. Process P2 arrives at time 1. The remaining time for process P1 (7 milliseconds) is larger than the time required by process P2 (4 milliseconds), so process P1 is preempted, and process P2 is scheduled. The average waiting time for this example is ((10 - 1) + (1 - 1) + (17 - 2) + (5 - 3))/4 = 26/4 = 6.5 milliseconds. A nonpreemptive SJF scheduling would result in an average waiting time of 7.75 milliseconds. 3. Priority Scheduling The SJF algorithm is a special case of the general priority-scheduling algorithm. A priority is associated with each process, and the CPU is allocated to the process with the highest priority. Equal-priority processes are scheduled in FCFS order. An SJF algorithm is simply a priority algorithm where the priority (p) is the inverse of the (predicted) next CPU burst. The larger the CPU burst, the lower the priority, and vice versa. Note that we discuss scheduling in terms of high priority and low priority. Priorities are generally some fixed range of numbers, such as 0 to 7, or 0 to 4,095. However, there is no general agreement on whether 0 is the highest or lowest priority. Some systems use low numbers to represent low priority; others use low numbers for high priority. This difference can lead to confusion. In this text, we use low numbers to represent high priority. As an example, consider the following set of processes, assumed to have arrived at time 0, in the order PI, P2,..., P5, with the length of the CPU-burst time given in milliseconds: Process Burst Time Priority P1 10 3 P2 1 1 P3 2 4 P4 1 5 P5 5 2 Using priority scheduling, we would schedule these processes according to the following Gantt chart: The waiting time is 6 milliseconds for process P1, 0 milliseconds for process P2, 16 milliseconds for process P3, 18 milliseconds for process P4, and 1 milliseconds for process P5. Thus, the average waiting time is=(6+0+16+18+1)/5=8.2milliseconds The average waiting time is 8.2 milliseconds. Priorities can be defined either internally or externally. Internally defined priorities use some measurable quantity or quantities to compute the priority of a process. For example, time limits, memory requirements, the number of open files, and the ratio of average I/O burst to average CPU burst have been used in computing priorities. External priorities are set by criteria that are external to the operating system, such as the importance of the process, the type and amount of funds being paid for computer use, the department sponsoring the work, and other, often political, factors. Priority scheduling can be either preemptive or nonpreemptive. When a process arrives at the ready queue, its priority is compared with the priority of the currently running process. A preemptive priority-scheduling algorithm will preempt the CPU if the priority of the newly arrived process is higher than the priority of the currently running process. A nonpreemptive priority-scheduling algorithm will simply put the new process at the head of the ready queue. A major problem with priority-scheduling algorithms is indefinite blocking (or starvation). A process that is ready to run but lacking the CPU can be considered blocked-waiting for the CPU. A priority-scheduling algorithm can leave some low-priority processes waiting indefinitely for the CPU. A solution to the problem of indefinite blockage of low-priority processes is aging. Aging is a technique of gradually increasing the priority of processes that wait in the system for a long time. For example, if priorities range from 127 (low) to 0 (high), we could decrement the priority of a waiting process by 1 every 15 minutes. Eventually, even a process with an initial priority of 127 would have the highest priority in the system and would be executed. In fact, it would take no more than 32 hours for a priority 127 process to age to a priority 0 process. 4. Round-Robin Scheduling The round-robin (RR) scheduling algorithm is designed especially for timesharing systems. It is similar to FCFS scheduling, but preemption is added to switch between processes. A small unit of time, called a time quantum (or time slice), is defined. A time quantum is generally from 10 to 100 milliseconds. The ready queue is treated as a circular queue. The CPU scheduler goes around the ready queue, allocating the CPU to each process for a time interval of up to 1 time quantum. To implement RR scheduling, we keep the ready queue as a FIFO queue of processes. New processes are added to the tail of the ready queue. The CPU scheduler picks the first process from the ready queue, sets a timer to interrupt after 1 time quantum, and dispatches the process. One of two things will then happen. The process may have a CPU burst of less than 1 time quantum. In this case, the process itself will release the CPU voluntarily. The scheduler will then proceed to the next process in the ready queue. Otherwise, if the CPU burst of the currently running process is longer than 1 time quantum, the timer will go off and will cause an interrupt to the operating system. A context switch will be executed, and the process will be put at the tail of the ready queue. The CPU scheduler will then select the next process in the ready queue. The average waiting time under the RR policy, however, is often quite long. Consider the following set of processes that arrive at time 0, with the length of the CPU-burst time given in milliseconds: Process Burst Time P1 24 P2 3 P3 3 If we use a time quantum of 4 milliseconds, then process P1 gets the first 4 milliseconds. Since it requires another 20 milliseconds, it is preempted after the first time quantum, and the CPU is given to the next process in the queue, process P2. Since process P2 does not need 4 milliseconds, it quits before its time quantum expires. The CPU is then given to the next process, process P3. Once each process has received 1 time quantum, the CPU is returned to process P1 for an additional time quantum. The resulting RR schedule is The waiting time is (10-4) milliseconds for process P1, 4 milliseconds for process P2, and 7 milliseconds for process P3. Thus, the average waiting time is =(10-4)+4+7=17/3 = 5.66 milliseconds. In the RR scheduling algorithm, no process is allocated the CPU for more than 1 time quantum in a row. If a process' CPU burst exceeds 1 time quantum, that process is preempted and is put back in the ready queue. The RR scheduling algorithm is preemptive. If there are n processes in the ready queue and the time quantum is q, then each process gets l/n of the CPU time in chunks of at most q time units. Each process must wait no longer than (n - 1) x q time units until its next time quantum. For example, if there are five processes, with a time quantum of 20 milliseconds, then each process will get up to 20 milliseconds every 100 milliseconds. The performance of the RR algorithm depends heavily on the size of the time quantum. At one extreme, if the time quantum is very large (infinite), the RR policy is the same as the FCFS policy. If the time quantum is very small (say 1 microsecond), the RR approach is called processor sharing, and appears (in theory) to the users as though each of n processes has its own processor running at 1/n the speed of the real processor. This approach was used in Control Data Corporation (CDC) hardware to implement 10 peripheral processors with only one set of hardware and 10 sets of registers. The hardware executes one instruction for one set of registers, then goes on to the next. This cycle continues, resulting in 10 slow processors rather than one fast processor.