Operating System IBPS PDF

# Operating System ## 1. Introduction Operating System is software that works as an interface between a user and the computer hardware. The primary objective of an operating system is to make computer system convenient to use and to utilize computer hardware in an efficient manner. The operating s...

# Operating System ## 1. Introduction Operating System is software that works as an interface between a user and the computer hardware. The primary objective of an operating system is to make computer system convenient to use and to utilize computer hardware in an efficient manner. The operating system performs the basic tasks such as receiving input from the keyboard, processing instructions and sending output to the screen. - User 1 - User 2 - User N - Software - System Softwares - Application Softwares - Operating system - Hardware - CPU - RAM - I/O ## 1.1. Functions of Operating System: - Memory Management - Processor Management - Device Management - File Management - Security - Control over system performance - Job accounting - Error detecting aids - Coordination between other software and users ## 1.2. Types of Operating System: ### (a) Batch operating system The users of a batch operating system do not interact with the computer directly. Each user prepares his job on an off-line device like punch cards and submits it to the computer operator. To speed up processing, jobs with similar needs are batched together and run as a group. The programmers leave their programs with the operator and the operator then sorts the programs with similar requirements into batches. The problems with Batch Systems are as follows: - Lack of interaction between the user and the job. - CPU is often idle, because the speed of the mechanical I/O devices is slower than the CPU. - Difficult to provide the desired priority. ### (b) Time-sharing operating systems Time-sharing is a technique which enables many people, located at various terminals, to use a particular computer system at the same time. Time-sharing or multitasking is a logical extension of multiprogramming. Processor's time which is shared among multiple users simultaneously is termed as time-sharing. The main difference between Multiprogrammed Batch Systems and Time-Sharing Systems is that in case of Multiprogrammed batch systems, the objective is to maximize processor use, whereas in Time-Sharing Systems, the objective is to minimize response time. Multiple jobs are executed by the CPU by switching between them, but the switches occur so frequently. Thus, the user can receive an immediate response. For example, in a transaction processing, the processor executes each user program in a short burst or quantum of computation. That is, if n users are present, then each user can get a time quantum. When the user submits the command, the response time is in few seconds at most. Computer systems that were designed primarily as batch systems have been modified to time-sharing systems. Advantages of Timesharing operating systems are as follows: - Provides the advantage of quick response. - Avoids duplication of software. - Reduces CPU idle time. Disadvantages of Time-sharing operating systems are as follows: - Problem of reliability. - Question of security and integrity of user programs and data. - Problem of data communication. ### (c) Multiprocessor system A multiprocessor system consists of several processors that share a common physical memory. Multiprocessor system provides higher computing power and speed. In multiprocessor system all processors operate under single operating system. Multiplicity of the processors and how they do act together are transparent to the others. Following are some advantages of this type of system: - Enhanced performance - Execution of several tasks by different processors concurrently, increases the system's throughput without speeding up the execution of a single task. - If possible, system divides task into many subtasks and then these subtasks can be executed in parallel in different processors. Thereby speeding up the execution of single tasks. ### (d) Distributed operating System Distributed systems use multiple central processors to serve multiple real-time applications and multiple users. Data processing jobs are distributed among the processors accordingly. Processors in a distributed system may vary in size and function. These processors are referred as sites, nodes, computers, and so on. The motivation behind developing distributed operating system is the availability of power and inexpensive microprocessor and advances in communication technology. The advantages of distributed systems are as follows: - With resource sharing facility, a user at one site may be able to use the resources available at another. - Speedup the exchange of data with one another via electronic mail. - If one site fails in a distributed system, the remaining sites can potentially continue operating. - Better service to the customers. - Reduction of the load on the host computer. - Reduction of delays in data processing. ### (e) Real Time operating System A real-time system is defined as a data processing system in which the time interval required to process and respond to inputs is so small that it controls the environment. The time taken by the system to respond to an input and display of required updated information is termed as the response time. So, in this method, the response time is very less as compared to online processing. Real-time systems are used when there are rigid time requirements on the operation of a processor or the flow of data and real-time systems can be used as a control device in a dedicated application. A real-time operating system must have well-defined, fixed time constraints, otherwise the system will fail. For example, Scientific experiments, medical imaging systems, industrial control systems, weapon systems, robots, air traffic control systems, etc. There are two types of real-time operating systems. - Hard real-time systems - Hard real-time systems guarantee that critical tasks complete on time. In hard real-time systems, secondary storage is limited or missing, and the data is stored in ROM. In these systems, virtual memory is almost never found. - Soft real-time systems - Soft real-time systems are less restrictive. A critical real-time task gets priority over other tasks and retains the priority until it completes. Soft real-time systems have limited utility than hard real-time systems. For example, multimedia, virtual reality, Advanced Scientific Projects like undersea exploration and planetary rovers, etc. ### (f) Embedded Operating System: These are embedded in a device, which is located in ROM. These are applicable and developed only for the needed resources and accordingly developed. These OS are less resource intensive. Mainly, applicable in appliances like microwaves, washing machines, traffic control systems etc. ## 1.3. Tasks of OS: ### 1. Process Management: The operating system manages many kinds of activities ranging from user programs to system programs. Each of these activities is encapsulated in a process. There are many processes can be running the same program. The five major activities of an operating system in regard to process management are: - Creation and deletion of user and system processes. - Suspension and resumption of processes. - A mechanism for process synchronization. - A mechanism for process communication. - A mechanism for deadlock handling. ### 2. Memory Management: - Keeping track of which parts of memory are currently being used and by whom. - Deciding which processes (or parts thereof) and data to move into and out of memory. - Allocating and reallocating memory space as needed. ### 3. Device Management: The assembling-disassembling of I/O peripherals devices are managed by the OS. ### 4. Storage Management: The three major activities of an operating system in regard . to secondary storage management are: - Managing the free space available on the secondary-storage device. - Allocation of storage space when new files have to be written. - Scheduling the requests for memory access. ## 1.4. Operating System - Services An Operating System provides services to both the users and to the programs. - It provides programs an environment to execute. - It provides users the services to execute the programs in a convenient manner. Following are a few common services provided by an operating system: - Program execution - I/O operations - File System manipulation - Communication - Error Detection - Resource Allocation - Protection ### Program execution Operating systems handle many kinds of activities from user programs to system programs like printer spooler, name servers, file server, etc. Each of these activities is encapsulated as a process. A process includes the complete execution context (code to execute, data to manipulate, registers, OS resources in use). Following are the major activities of an operating system with respect to program management: - Loads a program into memory. - Executes the program. - Handles program's execution. - Provides a mechanism for process synchronization. - Provides a mechanism for process communication. - Provides a mechanism for deadlock handling. ### I/O Operation An I/O subsystem comprises of I/O devices and their corresponding driver software. Drivers hide the peculiarities of specific hardware devices from the users. An Operating System manages the communication between user and device drivers. - I/O operation means read or write operation with any file or any specific I/O device. - Operating system provides the access to the required I/O device when required. ### File system manipulation A file represents a collection of related information. Computers can store files on the disk (secondary storage), for long-term storage purpose. Examples of storage media include magnetic tape, magnetic disk and optical disk drives like CD, DVD. Each of these media has its own properties like speed, capacity, data transfer rate and data access methods. A file system is normally organized into directories for easy navigation and usage. These directories may contain files and other directions. Following are the major activities of an operating system with respect to file management: - Program needs to read a file or write a file. - The operating system gives the permission to the program for operation on file. - Permission varies from read-only, read-write, denied and so on. - Operating System provides an interface to the user to create/delete files. - Operating System provides an interface to the user to create/delete directories. - Operating System provides an interface to create the backup of file system. ### Communication In case of distributed systems which are a collection of processors that do not share memory, peripheral devices, or a clock, the operating system manages communications between all the processes. Multiple processes communicate with one another through communication lines in the network. The OS handles routing and connection strategies, and the problems of contention and security. Following are the major activities of an operating system with respect to communication: - Two processes often require data to be transferred between them - Both the processes can be on one computer or on different computers, but are connected through a computer network. - Communication may be implemented by two methods, either by Shared Memory or by Message Passing. ### Error handling Errors can occur anytime and anywhere. An error may occur in CPU, in I/O devices or in the memory hardware. Following are the major activities of an operating system with respect to error handling: - The OS constantly checks for possible errors. - The OS takes an appropriate action to ensure correct and consistent computing. ### Resource Management In case of multi-user or multi-tasking environment, resources such as main memory, CPU cycles and files storage are to be allocated to each user or job. Following are the major activities of an operating system with respect to resource management: - The OS manages all kinds of resources using schedulers. - CPU scheduling algorithms are used for better utilization of CPU. ### Protection Considering a computer system having multiple users and concurrent execution of multiple processes, the various processes must be protected from each other's activities. Protection refers to a mechanism or a way to control the access of programs, processes, or users to the resources defined by a computer system. Following are the major activities of an operating system with respect to protection: - The OS ensures that all access to system resources is controlled. - The OS ensures that external I/O devices are protected from invalid access attempts. - The OS provides authentication features for each user by means of passwords. ## 2. Process Management A program in execution is a process. A process is executed sequentially, one instruction at a time. A program is a passive entity. For example, a file on the disk. A process on the other hand is an active entity. In addition to program code, it includes the values of the program counter, the contents of the CPU registers, the global variables in the data section and the contents of the stack that is used for subroutine calls. A program becomes a process when the executable file of a program is loaded in memory. There can be a possibility in large programs that more than one process is needed to completely run the program, but there are nevertheless considered two separate execution sequences. Process after being loaded in memory, the above diagram shows the process memory state when it is in execution. The stack region is used to store temporary data being used by the process. The Heap is the dynamic memory region i.e. i.e. on run-time allocated to the process. It consumes the free space in memory (Random access memory). Data region holds the computed results and values, and the global variables being used by the process. The text region holds the code or the executable instructions for the process. ## 2.1. PROCESS STATE A process being an active entity changes state as execution proceeds. A process can be any one of the following states: - New: Process being created. - Running: Instructions being executed. - Waiting: Process waiting for an event to occur. - Ready: Process waiting for CPU. - Terminated: Process has finished execution. A state diagram is used to diagrammatically represent the states and also the events that trigger the change of state of a process in execution. | new | admitted | interrupt | Exit | terminated | |---|---|---|---|---| | ready | running | scheduler dispatch | I/O or event completion | I/O of event waid | | waiting | | | | | ## 2.2 PROCESS CONTROL BLOCK Every process has a number and a process control block (PCB) represents a process in an operating system. The PCB contains information that makes the process an active entity. The PCB consists of the number of the process, its state, value of the program counter, contents of the CPU registers and much more as given below. The PCB serves as a repository of information about a process and varies from process to process. Information associated with each process: 1. Process State – The state, may be any of the 5 states shown in process state diagram such as New, ready, running, waiting and terminated. 2. Program Counter – It indicates the address of the next instruction to be executed for this process. 3. CPU registers - the registers highly vary based on number and type and also depending on the computer architecture. They include accumulators, index registers, stack pointers and general-purpose registers. Along with the program counter, this state information must be saved when an interrupt occurs to allow the process to be continued correctly after it recovers from the interrupt. 4. CPU scheduling information – it includes information such as process priority, pointers to scheduling queues and other scheduling parameters. 5. Memory-management information - this information contains value of base register and limit register, page tables, segment tables. These tables are used for referring the right locations of memory to be used by the process. 6. Accounting information - this includes amount of processor time and real time used, time limits, account numbers etc. 7. I/O status information – This includes list of I/O devices allocated to the process, list of open files, etc. ## 2.3. Inter-process Communication Processes executing concurrently in the operating system may be either independent process or cooperating process. A process is called cooperating if it is affected by the other processes executing in the system, whereas it is called Independent when its execution is not dependent on execution of other processes. Cooperating processes require Inter-process communication (IPC) mechanisms that enable them to send and receive data. Since processes frequently need to communicate with other processes therefore, there is a need for a well-structured communication, without using interrupts, among processes. Inter-process communication has two models: - (a)Message passing system model - (b)Shared memory system model Message passing is useful for exchanging smaller amounts of data, because no conflicts need be avoided. Message passing is also easier to implement than is shared memory for intercomputer communication. Shared memory allows maximum speed and convenience of communication. Shared memory is faster than message passing, as message-passing systems are typically implemented using system calls and thus require the more time-consuming task of kernel intervention. **NOTE:** If two processes want to communicate, a communication link must exist between them. This link can be implements in a various ways. But we are concerned here not with the link's physical implementation, rather with its logical implementation. Here are several methods for logically implementing a link and the send/ receive operation. ### 1. Direct or Indirect Communication Under Direct communication, Process A should explicitly name the recipient of the message i.e. Process B. In this case, the send() and receive( ) are defined as: - SEND (A, MESSAGE) – Sends a message to process A. - RECEIVE( B, MESSAGE) – Receive a message from process B. Three characteristics of Direct communication: - a) A link is automatically established between every pair of processes that want to communicate. The process only needs to know about other process identity. - b) A link is established with exactly two of the processes. - c) Between each pair of process, there exists only a single link. Under Indirect communication, messages are sent and received via mailboxes also known as ports. Mailboxes can be simply understood as an object in which messages are temporarily stored by first process and removed by the other process In Indirect communication, the send() and receive() are defined as: - SEND (X, MESSAGE) – Send/store message to mailbox X - RECEIVE(X, MESSAGE) - Receive/remove message from mailbox X Three characteristics of Indirect communication: - a) A link is established between every pair of processes only if both processes share a common mailbox. - b) A link can be established between two or more processes. - c) Between each pair of process, there may exists more than a single link ### 2. Synchronous or Asynchronous Communication Communication between processes takes places through calls to send() and receive() calls. There are different design options for implementing each function. Message passing may be either synchronous and asynchronous or blocking and nonblocking. - Blocking Send – sending is blocking until the message. Is received by receiving process - Non-Blocking Send - sending process sends message and resumes operation - Blocking Receive – receiver blocks until a message is available - Non-Blocking Receive – receiver retrieves either a valid message or a NULL. ### 3. Automatic or Explicit Buffering Whether communication is direct or indirect, messages exchanged by communicating processes reside in a temporary queue. Depending on how the queue is implemented, the method of execution of message-passing model varies: - (a). Zero Capacity - Queue has a maximum length zero, hence link can't have any messages waiting in it. So sender must wait until recipient retrieves the message. - (b). Bounded Capacity – Finite size queue. Till queue is not full, sender can send messages. Receiver can retrieve messages until queue is empty. - (c). Unbounded Capacity - Queue length is assumed to be infinite. Thus any number of messages can wait in it. The sender is never delayed. ## 2.4. Client-Server Communication In section above, we explained how communication was done between 2 processes via shared memory or message passing model. This can be used for client server communications as well, but we have special techniques available, that is especially suited for client server communication viz Sockets and Remote procedure calls. ### 2.4.1 Sockets - A socket is defined as an endpoint for communication - It is a concatenation of IP address and port - The socket 192.168.10.1:808 refers to port 808 on host 192.168.10.1 - Communication takes place between a pair of sockets When a client process initiates a request for communication, it is assigned a port by the host computer. This port is a random number and is greater than 1024. The scenario can be something as shown in diagram above. The packets travelling between the hosts are delivered to the appropriate process based on the destination port number. All connection must be unique. Therefore, if another process also on host X wishes to establish another communication with the same web server, it would be assigned a port number greater than 1024, but not equal to 1625. This thus ensures all connections consist of a unique pair of sockets. ### 2.4.2 Remote Procedure Calls Remote procedure calls (RPC) is a powerful technique for constructing client-server based applications. It is based on extending the notion of conventional, or local procedure calling, so that the called procedure need not exist in the same address space as the calling procedure. The two processes may be on the same system, or they may be on different systems with a network connecting them. By using RPC, programmers of distributed applications avoid the details of the interface with the network. The transport independence of RPC isolates the application from the physical and logical elements of the data communications mechanism and allows the application to use a variety of transports. RPC is similar in many respects to IPC mechanism, and is often built on top of them. But usually RPC is used when the processes are executing on two different systems, client and server. The RPC allows a user to do the communication as if the processes are in same address space, and the complexity of the network, the packing-unpacking of data packets from client-server-client is handled in background by the background stubs. #### How RPC Works An RPC is analogous to a function call. Like a function call, when an RPC is made, the calling arguments are passed to the remote procedure and the caller waits for a response to be returned from the remote procedure. The client makes a procedure call that sends a request to the server and waits. When the request arrives, the server calls a dispatch route that performs the requested service, and sends the reply to the client. After the RPC call is completed, the client program continues. RPC specifically supports network applications. The diagram clearly explains how the remote procedure call works. - Client - Application - Client stup - Client Runtime Library - Transport - Server - Application - Server stup - Server Runtime Library - Transport ## 2.5. THREAD A thread is a flow of execution through the process code, with its own program counter that keeps track of which instruction to execute next, system registers which hold its current working variables, and a stack which contains the execution history. A thread shares with its peer threads few information like code segment, data segment and open files. When one thread alters a code segment memory item, all other threads see that. A thread is also called a lightweight process. Threads provide a way to improve application performance through parallelism. Threads represent a software approach to improving performance of operating system by reducing the overhead thread is equivalent to a classical process. Each thread belongs to exactly one process and no thread can exist outside a process. Each thread represents a separate flow of control. Threads have been successfully used in implementing network servers and web server. They also provide a suitable foundation for parallel execution of applications on shared memory multiprocessors. - Register - Counter - Stack - Data - Files - Code - Single Thread - Single Process P with single thread - First Thread - Register - Counter - Stack - Second Thread - Register - Counter - Stack - Third Thread - Register - Counter - Stack - Data - Files - Code - Single Process P with three threads ### 2.5.1. Benefits 1. Responsiveness. Multithreading an interactive application may allow a program to continue running even if part of it is blocked or is performing a lengthy operation, thereby increasing responsiveness to the user. For instance, a multithreaded web browser could still allow user interaction in one thread while an image was being loaded in another thread. 2. Resource sharing. By default, threads share the memory and the resources of the process to which they belong. The benefit of sharing code and data is that it allows an application to have several different threads of activity within the same address space. 3. Economy. Allocating memory and resources for process creation is costly. Because threads share resources of the process to which they belong, it is more economical to create and context-switch threads. Empirically gauging the difference in overhead can be difficult, but in general it is much more time consuming to create and manage processes than threads. In Solaris, for example, creating a process is about thirty times slower than is creating a thread, and context switching is about five times slower. 4. Utilization of multiprocessor architectures. The benefits of multithreading can be greatly increased in a multiprocessor architecture, where threads may be running in parallel on different processors. A single threaded process can only run on one CPU, no matter how many are available. Multithreading on a multi-CPU machine increases concurrency. ### 2.5.2. Types of Thread ### 1. User-Level Threads User-level threads implement in user-level libraries, rather than via systems calls, so thread switching does not need to call operating system and to cause interrupt to the kernel. In fact, the kernel knows nothing about user-level threads and manages them as if they were single-threaded processes. Three primary thread libraries: POSIX Pthreads, Win32 threads, Java threads. Advantages: - Thread switching does not require Kernel mode privileges. - User level thread can run on any operating system. - Scheduling can be application specific in the user level thread. - User level threads are fast to create and manage. Disadvantages: - In a typical operating system, most system calls are blocking. - Multithreaded application cannot take advantage of multiprocessing. ### 2. Kernel-Level Threads In this method, the kernel knows about and manages the threads. No runtime system is needed in this case. Instead of thread table in each process, the kernel has a thread table that keeps track of all threads in the system. In addition, the kernel also maintains the traditional process table to keep track of processes. Operating Systems kernel provides system call to create and manage threads. Examples: Windows XP/2000, Solaris, Linux, Tru64 UNIX, Mac OS X Advantages: - Because kernel has full knowledge of all threads, Scheduler may decide to give more time to a process having large number of threads than process having small number of threads. - Kernel-level threads are especially good for applications that frequently block. Disadvantages: - The kernel-level threads are slow and inefficient. For instance, threads operations are hundreds of times slower than that of user-level threads. - Since kernel must manage and schedule threads as well as processes. It requires a full thread control block (TCB) for each thread to maintain information about threads. As a result, there is significant overhead and increased in kernel complexity. ### 2.5.3. Multithread Model As seen above, there may be user threads, and kernel level threads. The way they can relate to each other in multi-thread process are as follows, 1. Many-to-One Model: - In the many-to-one model, many user-level threads are all mapped onto a single kernel thread. - Thread management is handled by the thread library in user space, which is efficient in nature. | T | T | T | T | |---|---|---|---| | User thread | | K | | kernel thread | 2. One to One Model: - The one-to-one model creates a separate kernel thread to handle each and every user thread. - Most implementations of this model place a limit on how many threads can be created. - Linux and Windows from 95 to XP implement the one-to-one model for threads. | T | T | T | |---|---|---| | User thread | | K | K | L | | kernel thread | 3. Many to Many Model : - The many-to-many model multiplexes any number of user threads onto an equal or smaller number of kernel threads, combining the best features of the one-to-one and many-to-one models. - Users can create any number of the threads. - Blocking the kernel system calls does not block the entire process. - Processes can be split across multiple processors. | T | T | T | T | |---|---|---|---| | User Thread | | K | K | K | | kernel thread | | User- Level Thread | Kernel -level Thread | |---|---| | User thread are implemented by user | Kernel thread implemented by operating system | | User-level thread are faster to create and manage | Kernel-level threads are slower to create and manage | | User-level thread is generic and can run on any operating system | Kernel-level thread is specific to the operating system | | Multi-threaded application cannot take advantage of multiprocessing | Kernel routines themselves can be multithreaded | | Context switch required no hardware support | Hardware support is needed | ## 2.5.4. Difference between Process and Thread: | Process | Thread | |---|---| | Process is heavy weight or resource intensive. | Thread is light weight, taking lesser resources than a process. | | Process switching needs interaction with operating system. | Thread switching does not need to interact with operating system. | | In multiple processing environments, each process executes the same code but has its own memory and file resources. | All threads can share same set of open files, child processes. | | Multiple processes without using threads use more resources. | Multiple threaded processes use fewer resources. | | If one process is blocked, then no other process can execute until the first process is unblocked. | While one thread is blocked and waiting, a second thread in the same task can run. | | In multiple processes each process operates independently of the others. | One thread can read, write or change another thread's data. | ## 2.6. Schedulers Schedulers are special system software which handles process scheduling in various ways. Their main task is to select the jobs to be submitted into the system and to decide which process to run. Schedulers are of three types: - **Long-Term Scheduler:** It is also called a job scheduler. A long-term scheduler determines which programs are admitted to the system for processing. It selects processes from the queue and loads them into memory for execution. Process loads into the memory for CPU scheduling. The primary objective of the job scheduler is to provide a balanced mix of jobs, such as I/O bound and processor bound. It also controls the degree of multiprogramming. If the degree of multiprogramming is stable, then the average rate of process creation must be equal to the average departure rate of processes leaving the system. - **Short-Term Scheduler:** It is also called as CPU scheduler. Its main objective is to increase system performance in accordance with the chosen set of criteria. It is the change of ready state to running state of the process. CPU scheduler selects a process among the processes that are ready to execute and allocates CPU to one of them. Short-term schedulers, also known as dispatchers, make the decision of which process to execute next. Short-term schedulers are faster than long-term schedulers. - **Medium-Term Scheduler:** This scheduler removes the processes from memory (and from active contention for the CPU), and thus reduces the degree of multiprogramming. At some later time, the process can be reintroduced into memory and its execution van be continued where it left off. This scheme is called swapping. The process is swapped out, and is later swapped in, by the medium-term scheduler. Swapping may be necessary to improve the process mix, or because a change in memory requirements has overcommitted available memory, requiring memory to be freed up. This complete process is descripted in the below diagram: ## 2.7. Dispatcher: Another component involved in the CPU-scheduling function is the dispatcher. The dispatcher is the module that gives control of the CPU to the process selected by the short-term scheduler. This function involves the following: - Switching context - Switching to user mode - Jumping to the proper location in the user program to restart that program The dispatcher should be as fast as possible, since it is invoked during every process switch. The time it takes for the dispatcher to stop one process and start another running is known as the dispatch latency. ## 2.8. Scheduling Criteria Many criteria exist for comparing and deciding on CPU scheduling algorithms. Which characteristics are used for comparison can make a substantial difference in which algorithm is judged to be best. The criteria include the following: 1. **CPU utilization:** We want to keep the CPU as busy as possible. Conceptually, CPU utilization can range from 0 to 100 percent. In a real system, it should range from 40 percent (for a lightly loaded system) to 90 percent (for a heavily used system). 2. **Throughput:** If the CPU is busy executing processes, then work is being done. One measure of work is the number of processes that are completed per time unit, called throughput. For long processes, this rate may be one process per hour; for short transactions, it may be 10 processes per second. 3. **Turnaround time:** From the point of view of a particular process, the important criterion is how long it takes to execute that process. The interval from the time of submission of a process to the time of completion is the turnaround time. Turnaround time is the sum of the periods spent waiting to get into memory, waiting in the ready queue, executing on the CPU, and doing I/O. 5. **Waiting time:** The CPU scheduling algorithm does not affect the amount of time during which a process executes or does I/O; it affects only the amount of time that a process spends waiting in the ready queue. Waiting time is the sum of the periods spent waiting in the ready queue. 6. **Response time:** In an interactive system, turnaround time may not be the best criterion. Often, a process can produce some output fairly early and can continue computing new results while previous results are being output to the user. Thus, another measure is the time from the submission of a request until the first response is produced. This measure, called response time, is the time it takes to start responding, not the time it takes to output the response. The turnaround time is generally limited by the speed of the output device. It is needed to maximize the CPU utilization and the throughput and also to minimize turnaround time, waiting time, and response time. In most cases, we optimize the average measure. ## 2.9. Scheduling Algorithms: ### 1. First Come First Serve Scheduling The simplest of all scheduling algorithm is the first come first serve algorithm also known as FCFS. It implies that, the process that request for CPU firsts, gets the CPU allocated to it firsts. It can be easily implemented using a Queue (FIFO). Average waiting time is usually high in case of FCFS. **Example 1:** Let processes come in order P1, P2, P3 and request for CPU | process | Burst time | |---|---| | P1 | 24 | | P2 | 3 | | P3 | 3 | If process arrive in the order P1, P2, P3 and are server in FCFS order, the result is: | P1 | P2 | P3 | |---|---|---| | 0 | 24 | 27 | 30 | 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 result will be shown: | P2 | P3 | P1 | |---|---|---| | 0 | 3 | 6 | 30 | The average waiting time is now (6+0+3)/3=3 milliseconds This reduction is substantial. Thus, the average waiting times under FCFS policy is generally not minimal and varies substantially if the process's CPU burst times vary greatly. The FCFS scheduling algorithm is nonpreemptive. Once the CPU has been allocated for a process that process keeps the CPU until it releases the CPU either by terminating or by requesting I/O. The FCFS algorithm is thus particularly troublesome for time-sharing systems, where it is important that each user 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 This algorithm associates with each process the length of the process's next CPU burst. When the CPU is available, it is assigned to the process that has the smallest next CPU burst. If the next CPU bursts of two processes are the same, FCFS scheduling is used to break the tie. Note that a more appropriate term for this scheduling method would be the shortest-next-CPU-burst algorithm, because scheduling depends on the length of the next CPU burst of a process, rather than its total length. Shortest Job First Scheduling algorithm is the best approach to minimize waiting time. But, the real difficulty with the SJF algorithm knows the length of the next CPU request. 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, but we can predict it; i.e. 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 preemptive or non-preemptive depending on the kernel, or CPU requirement. **Example:** consider the following set of processes, with the length of the CPU burst given in milliseconds: | Process | Burst time |