OS2.pdf

Operating System Unit-2 Process & CPU Scheduling By Mr. Nitin Y. Suryawanshi Process & CPU Scheduling Process Concept Process Scheduling Operations on Processes Inter process Communication Threads Scheduling criteria Scheduling...

Operating System Unit-2 Process & CPU Scheduling By Mr. Nitin Y. Suryawanshi Process & CPU Scheduling Process Concept Process Scheduling Operations on Processes Inter process Communication Threads Scheduling criteria Scheduling algorithms Performance evaluation Mr. Nitin Y. Suryawanshi  What is Process in OS ? In an operating system (OS), a process is a fundamental concept that represents a running program. It encompasses the program's code, its current activity, and the resources allocated to it by the OS. A process is a program in execution. An instance of running program The entity, that can be assigned to & execute on, a processor. The execution of a process progresses in a sequential fashion. A program is a passive entity while a process is an active entity. A process includes much more than just the program code. Mr. Nitin Y. Suryawanshi Process in memory. function call in the program memory that is dynamically allocated during process run time values of initialized and uninitialized global variables set of instructions to be executed for the process Mr. Nitin Y. Suryawanshi  Process in memory. A process includes the text section, stack, data section, program counter, register contents and so on. The text section consists of the set of instructions to be executed for the process. The data section contains the values of initialized and uninitialized global variables in the program. The stack is used whenever there is a function call in the program. A layer is pushed into the stack when a function is called. The arguments to the function and the local variables used in the function are put into the layer of the stack. Once the function call returns to the calling program, the layer of the stack is popped. A process may also include a heap, which is memory that is dynamically allocated during process run time. The text, data and stack sections comprise the address space of the process. The program counter has the address of the next instruction to be executed in the process. Mr. Nitin Y. Suryawanshi  Process States As a process executes, it changes state. The state of a process refers to what the process currently does. A process can be in one of the following states during its lifetime: new: The process is being created. running: Instructions are being executed. waiting: The process is waiting for some event to occur. ready: The process is waiting to be assigned to a processor. terminated: The process has finished execution. Mr. Nitin Y. Suryawanshi Process state transition diagram Mr. Nitin Y. Suryawanshi Process state transition diagram Suspend ready : A process in the ready state, which is moved to secondary memory from the main memory due to lack of the resources (mainly primary memory) is called in the suspend ready state. Suspend wait : Instead of removing the process from the ready queue, it's better to remove the blocked process which is waiting for some resources in the main memory. Since it is already waiting for some resource to get available hence it is better if it waits in the secondary memory and make room for the higher priority process. These processes complete their execution once the main memory gets available and their wait is finished. Mr. Nitin Y. Suryawanshi  The process is in the new state when it is being created. Then the process is moved to the ready state, where it waits till it is taken for execution. There can be many such processes in the ready state. One of these processes will be selected and will be given the processor, and the selected process moves to the running state. A process, while running, may have to wait for I/O or wait for any other event to take place. That process is now moved to the waiting state. After the event for which the process was waiting gets completed, the process is moved back to the ready state. Similarly, if the time-slice of a process ends while still running, the process is moved back to the ready state. Once the process completes execution, it moves to the terminated state. Mr. Nitin Y. Suryawanshi  Process Control Block Each process is Process state. The state may be new, ready, running, waiting, halted, and so on. represented in the Program counter. The counter indicates the address of the next instruction to be operating system by a executed for this process. process control block CPU registers. The registers vary in number and type, depending on the computer (PCB)—also called a architecture. They include accumulators, index registers, stack pointers, and general- task control block. 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 items as the value of the base and limit registers and 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. This information includes the list of I/O devices allocated to the process, a list of open files, and so on. Mr. Nitin Y. Suryawanshi  CPU Switch From Process to Process Figure shows how the contents of the PCB of a process are used when the CPU switches from one process to another process. Process P0 is executing first, and there is an interrupt. Process P0 should now release the CPU and the CPU should be assigned to the next process P1. Before the CPU is assigned to the next process P1, the state of the process currently using the CPU, P0, is saved in its PCB. The state of the next process P1 is then loaded from the PCB of P1. When there needs to be a switch from P1 to P0, the state of P1 is saved and the state of P0 is loaded. Mr. Nitin Y. Suryawanshi  *Process Scheduling* In multi-programmed systems, some process must run at all times, to increase CPU utilization. In time-sharing systems, processes must be switched to increase interaction between the user and the system. If there are many processes, only one can use the CPU at a particular time and the remaining must wait during that time. When the CPU becomes free, the next process can be scheduled. Mr. Nitin Y. Suryawanshi  Scheduling Queues When processes enter the system, they are put into a job queue. This job queue is the set of all processes in the system. The set of all processes residing in main memory, ready and waiting to execute is kept in a ready queue. The ready queue is maintained as a linked list. A ready-queue header contains pointers to the first and final PCBs in the list. In addition to the ready queue, there are other queues in the system in which a process may be kept during its lifetime. When a process has to wait for I/O, the PCB of the process is removed from the ready queue and is placed in a device queue. The device queue corresponds to the I/O device from/to which the process is waiting for I/O. Hence, there are a number of device queues in the system corresponding to the devices present in the system. Mr. Nitin Y. Suryawanshi  Figure shows the ready queue and the various device queues in the system. Any process during its lifetime will migrate between the various queues. Mr. Nitin Y. Suryawanshi  Figure shows a common representation of process scheduling using a queuing diagram. The rectangular boxes represent the various queues. The circles denote the resources that serve the queues and the arrows show the flow of processes in the system. Queuing diagram representation of process scheduling Mr. Nitin Y. Suryawanshi A new process is initially placed in the ready queue. When the process is given the CPU and is running one of the following may occur: The process may request for I/O and may be placed in an I/O queue. After I/O gets completed, the process is moved back to the ready queue. The time slice allotted to the process may get over. The process is now forcibly removed from the CPU and is placed back in the ready queue. The process may create (fork) a new process and may wait for the created child process to finish completion. Once the child completes execution, the process moves back to the ready queue. While the process executes, an interrupt may occur. The process is now removed from the CPU, the process waits till the interrupt is serviced and is then moved to the ready state. Mr. Nitin Y. Suryawanshi  Schedulers A process moves between different queues during its lifetime. The OS should select the process that should move to the next queue and the queue to which the selected process should move, in some fashion. This selection is done by schedulers. The different schedulers available are long-term scheduler, short-term scheduler and medium-term scheduler. Mr. Nitin Y. Suryawanshi  Schedulers The long-term scheduler, or job scheduler, selects processes from this pool and loads them into memory for execution. The short-term scheduler, or CPU scheduler, selects from among the processes that are ready to execute and allocates the CPU to one of them. Some operating systems, such as time-sharing systems, may introduce an additional, intermediate level of scheduling. This medium-term scheduler. Mr. Nitin Y. Suryawanshi  Schedulers The main difference between the job scheduler and the CPU scheduler is the frequency of execution. The long-term scheduler controls the degree of multiprogramming (number of processes in memory). It is invoked only when a process leaves the system. The short-term scheduler is invoked whenever the CPU switches from one process to another. Hence, the short-term scheduler is run more frequently than the long-term scheduler. Mr. Nitin Y. Suryawanshi  Medium-term scheduling Some operating systems, like the time-sharing systems introduce an additional, intermediate level of scheduling, called medium-term scheduling. Any process that is in the running state has to be kept in the main memory. Such a process may not be in the run ning state throughout its life time till its termination. It may be moving to the waiting state or to the ready queue and then may move back to the running state and so on. Mr. Nitin Y. Suryawanshi  Context of a process The context of a process is represented in the PCB of the process. It includes the values in CPU registers, process state, memory management information, open files for the process and so on. When the CPU switches from one process to another process, it is said that a context switch occurs. During a context switch, the system must save the context of the old process and load the saved context for the new process. Context-switch time is overhead, because the system does no useful work while switching. Mr. Nitin Y. Suryawanshi  Operations on Processes The operating system must provide support for creation and termination of processes. Creation of Processes 1. Process Creation Request: A process can request the creation of another process. This can be done via system calls such as fork() in Unix/Linux, or CreateProcess() in Windows. 2. Resource Allocation: The operating system allocates necessary resources for the new process, such as memory, CPU time, file handles, etc. 3. Initialization: The new process is initialized with essential attributes such as a process control block (PCB), which contains information about the process state, program counter, CPU registers, memory management information, etc. 4. Parent-Child Relationship: The newly created process often has a parent-child relationship with the process that created it. The parent process can control or monitor the child process. 5. Process State: The new process is placed into a ready state or a suspended state until the scheduler allows it to execute. Mr. Nitin Y. Suryawanshi Creating a separate process using the UNIX fork() system call Mr. Nitin Y. Suryawanshi  Operations on Processes Process Termination 1. Request: A process requests termination (e.g., exit() in Unix/Linux, ExitProcess() in Windows). 2. Resource Deallocation: The OS deallocates resources assigned to the process. 3. Update State: The PCB is updated, and the process state changes to terminated or zombie. 4. Parent Notification: The parent process is notified of the child process's termination. 5. Cleanup: The OS cleans up remaining data structures and releases the process ID. Mr. Nitin Y. Suryawanshi  Inter process Communication Processes executing concurrently 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. Any process that does not share data with any other process is independent. 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. Mr. Nitin Y. Suryawanshi Reasons for providing an environment that allows process cooperation: Information sharing. Since several users may be interested in the same piece of information (for instance, a shared file), we must provide an environment to allow concurrent access to such information. Computation speedup. If we want a particular task to run faster, we must break it into subtasks, each of which will be executing in parallel with the others. Notice that such a speedup can be achieved only if the computer has multiple processing cores. Modularity. We may want to construct the system in a modular fashion, dividing the system functions into separate processes or threads, Convenience. Even an individual user may work on many tasks at the same time. For instance Mr. Nitin Y. Suryawanshi Cooperating processes require an inter process communication (IPC) mechanism that will allow them to exchange data and information. There are two fundamental models of inter process communication: shared memory and message passing. In the shared-memory model, a region of memory that is shared by cooperating processes is established. Processes can then exchange information by reading and writing data to the shared region. In the message-passing model, communication takes place by means of messages exchanged between the cooperating processes. The two communications models are contrasted in Figure Mr. Nitin Y. Suryawanshi Message passing is useful for exchanging smaller amounts of data, because no conflicts need be avoided. Message passing is also easier to implement in a distributed system than shared memory. (Although there are systems that provide distributed shared memory, we do not consider them in this text.) Shared memory can be faster than message passing, since message-passing systems are typically implemented using system calls and thus require the more time-consuming task of kernel intervention. Inshared-memory systems, system calls are required only to establish shared memory regions. Once shared memory is established, all accesses are treated as routine memory accesses, and no assistance from the kernel is required. Mr. Nitin Y. Suryawanshi  i) Shared Memory Method Ex: Producer-Consumer problem There are two processes: Producer and Consumer. The producer produces some items and the Consumer consumes that item. The two processes share a common space or memory location known as a buffer where the item produced by the Producer is stored and from which the Consumer consumes the item if needed. There are two versions of this problem: the first one is known as the unbounded buffer problem in which the Producer can keep on producing items and there is no limit on the size of the buffer, the second one is known as the bounded buffer problem in which the Producer can produce up to a certain number of items before it starts waiting for Consumer to consume it. We will discuss the bounded buffer problem. First, the Producer and the Consumer will share some common memory, then the producer will start producing items. If the total produced item is equal to the size of the buffer, the producer will wait to get it consumed by the Consumer. Similarly, the consumer will first check for the availability of the item. If no item is available, the Consumer will wait for the Producer to produce it. If there are items available, Consumer will consume them. Mr. Nitin Y. Suryawanshi  Message-Passing Systems Message passing provides a mechanism to allow processes to communicate and to synchronize their actions without sharing the same address space. It is particularly useful in a distributed environment, where the communicating processes may reside on different computers connected by a network. For example, an Internet chat program could be designed so that chat participants communicate with one another by exchanging messages. A message-passing facility provides at least two operations: send(message) receive(message) Messages sent by a process can be either fixed or variable in size. If only fixed-sized messages can be sent, the system-level implementation is straightforward. Mr. Nitin Y. Suryawanshi Several methods for logically implementing a link and the send()/receive() operations: 1. Direct or indirect communication 2. Synchronous or asynchronous communication 3. Automatic or explicit buffering Mr. Nitin Y. Suryawanshi  Direct or indirect communication Direct Communication links are implemented when the processes use a specific process identifier for the communication, but it is hard to identify the sender ahead of time. For example the print server. In-direct Communication is done via a shared mailbox (port), which consists of a queue of messages. The sender keeps the message in mailbox and the receiver picks them up. Mr. Nitin Y. Suryawanshi  Synchronous or asynchronous communication A process that is blocked is one that is waiting for some event, such as a resource becoming available or the completion of an I/O operation. IPC is possible between the processes on same computer as well as on the processes running on different computer i.e. in networked/distributed system. In both cases, the process may or may not be blocked while sending a message or attempting to receive a message so message passing may be blocking or non-blocking. Blocking is considered synchronous and blocking send means the sender will be blocked until the message is received by receiver. Similarly, blocking receive has the receiver block until a message is available. Non-blocking is considered asynchronous and Non-blocking send has the sender sends the message and continue. Similarly, Non-blocking receive has the receiver receive a valid message or null. Mr. Nitin Y. Suryawanshi  Automatic or explicit buffering Whether communication is direct or indirect, messages exchanged by communicating processes reside in a temporary queue. Basically, such queues can be implemented in three ways: Zero capacity. The queue has a maximum length of zero; thus, the link cannot have any messages waiting in it. In this case, the sender must block until the recipient receives the message. Bounded capacity. The queue has finite length n; thus, at most n messages can reside in it. If the queue is not full when a new message is sent, the message is placed in the queue (either the message is copied or a pointer to the message is kept), and the sender can continue execution without waiting. The link’s capacity is finite, however. If the link is full, the sender must block until space is available in the queue. Unbounded capacity. The queue’s length is potentially infinite; thus, any number of messages can wait in it. The sender never blocks. Mr. Nitin Y. Suryawanshi  Threads A thread is a basic unit of CPU utilization; it comprises a thread ID, a program counter, a register set, and a stack. It shares with other threads belonging to the same process its code section, data section, and other operating-system resources, such as open files and signals. A traditional (or heavyweight) process has a single thread of control. If a process has multiple threads of control, it can perform more than one task at a time. Figure illustrates the difference between a traditional single-threaded process and a multithreaded process. Mr. Nitin Y. Suryawanshi  Threads  A thread may be defined as a flow of execution through some process code.  A thread is also known as a lightweight process.  Threads improve application’s performance by providing parallelism.  Threads improve the performance of operating systems by reducing the process overhead. Thread is equivalent to a classical process and it is a software approach for software improvement.  Every thread belongs to only one process and not a single thread can exist outside a process.  Two Types of Threads1. User Level Threads 2. Kernel Level Threads Mr. Nitin Y. Suryawanshi Difference between ULT and KLT Mr. Nitin Y. Suryawanshi  Why do we need Threads over Process? Creating a process and switching between processes is costly. Processes have separate address space Sharing memory areas among processes is non-trivial. A process is divide into number of light weight process, each light weight process is said to be a Thread. The Thread has a program counter (Keeps track of which instruction to execute next), registers (holds its current working variables), stack (execution History). Mr. Nitin Y. Suryawanshi Differences between Process and Thread Mr. Nitin Y. Suryawanshi  Thread States: 1. Born State : A thread is just created. 2. Ready state : The thread is waiting for CPU. 3. running : System assigns the processor to the thread. 4. sleep : A sleeping thread becomes ready after the designated sleep time expires. 5. dead : The Execution of the thread finished. Mr. Nitin Y. Suryawanshi  Multithreading A process is divided into number of smaller tasks each task is called a Thread. Number of Threads with in a Process execute at a time is called Multithreading. If a program, is multithreaded, even when some portion of it is blocked, the whole program is not blocked. The rest of the program continues working If multiple CPU’s are available. Multithreading gives best performance. If we have only a single thread, number of CPU’s available, No performance benefits achieved. Process creation is heavy-weight while thread creation is light-weight can simplify code, increase efficiency Mr. Nitin Y. Suryawanshi  Kernels are generally multithreaded CODE- Contains instruction DATA- holds global variable FILES- opening and closing files REGISTER- contain information about CPU state STACK-parameters, local variables, functions Mr. Nitin Y. Suryawanshi  The Benefits of Multithreaded Programming 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. 2. Resource sharing. Processes can only share resources through techniques such as shared memory and message passing. Such techniques must be explicitly arranged by the programmer 3. Economy. Allocating memory and resources for process creation is costly. Because threads share the resources of the process to which they belong, it is more economical to create and context-switch threads. 4. Scalability. The benefits of multithreading can be even greater in a multiprocessor architecture, where threads may be running in parallel on different processing cores. Mr. Nitin Y. Suryawanshi  Multithreading Models  Support for threads may be provided either at the user level, for user threads, or by the kernel, for kernel threads. User threads are supported above the kernel and are managed without kernel support, whereas kernel threads are supported and managed directly by the operating system.  A relationship must exist between user threads and kernel threads.  At three common ways of establishing such a relationship: 1. The many-to-one model 2. The one-to-one model 3. The many-to-many model Mr. Nitin Y. Suryawanshi The many-to-one model In the many-to-one model, multiple user threads are mapped to a single kernel thread. Advantages: It is simple to implement. User-level thread management does not require any kernel intervention, making it fast. Disadvantages :If one user thread makes a blocking system call, the entire process is blocked. It cannot take advantage of multiprocessor systems since only one kernel thread can run at a time. Mr. Nitin Y. Suryawanshi One-to-one model. In the one-to-one model, each user thread is mapped to a kernel thread. Advantages: Provides more concurrency because each user thread can run on a different processor. Blocking system calls are handled individually, so one blocking call does not block other threads. Disadvantages: Creating a kernel thread for each user thread results in a significant overhead. The limit on the number of threads is lower due to the higher resource usage. Mr. Nitin Y. Suryawanshi Many-to-many model In the many-to-many model, many user threads are mapped to many kernel threads. Advantages: Combines the best aspects of the many-to-one and one-to-one models. User threads can be scheduled independently by the thread library. Kernel threads can run in parallel on multiprocessors. Disadvantages: More complex to implement compared to the other two models. Mr. Nitin Y. Suryawanshi  Scheduling criteria CPU scheduling is a fundamental concept in operating systems that involves determining which processes in the system should be assigned to the CPU for execution at any given time. Effective CPU scheduling can greatly enhance the performance and responsiveness of a system. Key Concepts Process: A program in execution, which requires CPU time for its completion. CPU Burst: The time period during which a process is using the CPU for execution. I/O Burst: The time period during which a process is performing I/O operations and not using the CPU. Scheduler: The part of the operating system that decides which process runs at a given time. Mr. Nitin Y. Suryawanshi Alternating sequence of CPU and I/O bursts. Mr. Nitin Y. Suryawanshi  Goals of CPU Scheduling Maximize CPU Utilization: Keep the CPU as busy as possible. Maximize Throughput: Increase the number of processes completed per unit time. Minimize Turnaround Time: Reduce the total time taken for a process to complete, from submission to completion. Minimize Waiting Time: Reduce the time a process spends waiting in the ready queue. Minimize Response Time: Reduce the time from when a request was submitted until the first response is produced. Mr. Nitin Y. Suryawanshi CPU-scheduling decisions may take place under the following four circumstances: 1. When a process switches from the running state to the waiting state (for example, as the result of an I/O request or an invocation of wait() for the termination of a child process) 2. When a process switches from the running state to the ready state (for example, when an interrupt occurs) 3. When a process switches from the waiting state to the ready state (for example, at completion of I/O) 4. When a process terminates For situations 1 and 4, there is no choice in terms of scheduling. A new process (if one exists in the ready queue) must be selected for execution. There is a choice, however, for situations 2 and 3. When scheduling takes place only under circumstances 1 and 4, we say that the scheduling scheme is nonpreemptive or cooperative. Otherwise, it is preemptive. Mr. Nitin Y. Suryawanshi  Non-preemptive Scheduling In non-preemptive scheduling, once a process starts executing on the CPU, it continues to run until it finishes its CPU burst or voluntarily releases the CPU (e.g., it waits for I/O operations). Characteristics: No Interruption: The running process cannot be interrupted by another process. Simplicity: Easier to implement since context switches occur only when a process completes its CPU burst or performs I/O operations. Less Overhead: Fewer context switches, resulting in lower overhead. Common Algorithms: First-Come, First-Served (FCFS): Processes are executed in the order they arrive. Shortest Job Next (SJN) or Shortest Job First (SJF): The process with the shortest CPU burst time is selected next. Priority Scheduling:The process with the highest priority is selected next. Mr. Nitin Y. Suryawanshi  Preemptive Scheduling In preemptive scheduling, a running process can be interrupted and moved back to the ready queue if a more critical process arrives or the time quantum expires (in the case of time-sharing systems). Characteristics: Interruption Allowed: The scheduler can interrupt the running process. Better Responsiveness: More responsive to interactive processes and changes in process priority. Higher Overhead: More context switches, leading to higher overhead. Common Algorithms: Round Robin (RR):Each process is assigned a fixed time slice (quantum) and is executed in a cyclic order. Preemptive Shortest Job Next (PSJN) or Shortest Remaining Time First (SRTF):The process with the shortest remaining CPU burst time is selected next. Preemptive Priority Scheduling: The process with the highest priority is selected next, and higher priority processes can preempt lower priority ones. Multilevel Queue Scheduling: Processes are divided into different queues based on priority or type, with each queue having its own scheduling algorithm. Mr. Nitin Y. Suryawanshi  Scheduling Criteria CPU scheduling criteria are metrics used to evaluate the performance and efficiency of different scheduling algorithms. These criteria help determine how well an algorithm manages process execution and resource allocation. Here are the main scheduling criteria: CPU Utilization: The percentage of time the CPU is actively executing processes. Goal: Maximize CPU utilization to ensure the CPU is not idle. Throughput: The number of processes completed per unit of time. Goal: Maximize throughput to improve the overall performance of the system. Turnaround Time: The total time taken for a process to complete, from the time of submission to the time of completion. Goal: Minimize turnaround time to ensure processes complete quickly. Waiting Time: The total time a process spends in the ready queue waiting to be executed. Goal: Minimize waiting time to reduce delays in process execution. Response Time: The time from the submission of a request until the first response is produced (not the completion time). Goal: Minimize response time to ensure the system is responsive to user interactions. Fairness: Ensuring all processes get a fair share of CPU time without starvation. Goal: Achieve fairness so that no process is unduly delayed or starved. Mr. Nitin Y. Suryawanshi CPU SCHEDULINGALGORITHMS Mr. Nitin Y. Suryawanshi First come First served scheduling: (FCFS): The process that request the CPU first is holds the CPU first. If a process request the cpu then it is loaded into the ready queue, connect CPU to that process. Consider the following set of processes that arrive at time 0, the length of the cpu burst time given in milli seconds. burst time is the time, required the cpu to execute that job, it is in milli seconds. Mr. Nitin Y. Suryawanshi Mr. Nitin Y. Suryawanshi Mr. Nitin Y. Suryawanshi Mr. Nitin Y. Suryawanshi Mr. Nitin Y. Suryawanshi First Come First Serve: Mr. Nitin Y. Suryawanshi Mr. Nitin Y. Suryawanshi Mr. Nitin Y. Suryawanshi