USCS301- OS 31072024.pdf

USCS301 Principles of Operating Systems By- Prof. Hemangi Rane. M.Sc. (CS,Math),NET,Ph.D(Pusuing) B. K. Birla College of Arts, Science & Commerce, Kalyan  Software A program is a sequen...

USCS301 Principles of Operating Systems By- Prof. Hemangi Rane. M.Sc. (CS,Math),NET,Ph.D(Pusuing) B. K. Birla College of Arts, Science & Commerce, Kalyan  Software A program is a sequence of instructions that enables the computer to carry out some specific task.  Software Components The software components are the collection of programs that execute in the computer. These programs perform computations, control, manage, and carry out other important tasks. Two general types of software components are: System software Application software  System Software The system software is the set of programs that control the activities and functions of the various hardware components, programming tools and abstractions, and other utilities to monitor the state of the computer system. The system software forms an environment for the programmers to develop and execute their programs (collectively known as application software). Three types of users can be identified: system programmers, application programmers and end-users System software - Operating System, Assemblers, Loaders, Linkers, Compilers, Editors, …  Application Software Application software are the user programs and consist of those programs that solve specific problems for the users and execute under the control of the operating system. Application programs are developed by individuals and organizations for solving specific problems. Application software - All User-Oriented Programs. APPLICATION PROGRAMS Users SYSTEM PROGRAMS HARDWARE  What is an Operating System? Operating System lies in the category of system software. An Operating System (OS) is an interface between a computer user and computer hardware. An operating system (OS) is the core software that manages computer hardware resources and provides services for computer programs. It acts as an intermediary between the hardware and the various software applications, ensuring efficient and orderly utilization of the computer system. The primary roles of an operating system include Resource Management: The OS allocates system resources such as CPU time, memory space, and peripheral devices to running programs. It ensures fair and efficient utilization of these resources among competing processes. Process Management: It oversees the execution of processes or tasks within the system, scheduling them for execution, and managing their communication and synchronization.  Memory Management: The OS controls the allocation and deallocation of memory space for processes, ensuring efficient memory utilization and preventing conflicts between processes. File System Management: It provides an interface for organizing and accessing files stored on secondary storage devices such as hard drives, SSDs, and network storage. Device Management: The OS handles interactions with peripheral devices such as printers, disk drives, and network interfaces, managing device drivers and providing a unified interface for application programs to access these devices. Operating systems perform various operations to facilitate these roles, including: Bootstrapping: The process of starting the computer by loading the OS into memory from secondary storage. Interrupt Handling: Responding to hardware interrupts generated by devices or software exceptions. Process Scheduling: Deciding which processes should run, when, and for how long on the CPU.  Memory Protection: Ensuring that processes do not interfere with each other's memory space. File System Operations: Reading, writing, and organizing files on storage devices. Security: Enforcing access control policies and protecting the system from unauthorized access and malicious software.  Objectives of Operating Systems Convenient to use: One of the objectives is to make the computer system more convenient to use in an efficient manner. User Friendly: To make the computer system more interactive with a more convenient interface for the users. Easy Access: To provide easy access to users for using resources by acting as an intermediary between the hardware and its users. Management of Resources: For managing the resources of a computer in a better and faster way. Controls and Monitoring: By keeping track of who is using which resource, granting resource requests, and mediating conflicting requests from different programs and users. Fair Sharing of Resources: Providing efficient and fair sharing of resources between the users and programs.  Computing Environments Computing is nothing but process of completing a task by using this computer technology and it may involve computer hardware and/or software. When a problem is solved by the computer, during that computer uses many devices, arranged in different ways and which work together to solve problems. Based on the organization of different computer devices and communication processes there exists multiple types of computing environments  1) Personal Computing Environment : In individualized computing climate there is an independent machine. Complete program lives on PC and executed there. Diverse independent machines that establish an individualized computing climate are PCs, mobiles, printers, PC frameworks, scanners and so forth that we use at our homes and workplaces. 2) Time-Sharing Computing Environment : In Time Sharing Computing Environment multiple users share system simultaneously. Different users (different processes) are allotted different time slice and processor switches rapidly among users according to it, for example, student listening to music while coding something in an IDE. Windows 95 and later versions, UNIX, IOS, Linux operating systems ((OS) are the examples of this time sharing computing environment.  3) Client Server Computing Environment : In client server computing environment two machines are involved i.e., client machine and server machine, sometime same machine also serve as client and server. In this computing environment client requests resource/service and server provides that respective resource/service. A server can provide service to multiple clients at a time and here mainly communication happens through computer network.  4) Distributed Computing Environment : In a distributed computing environment multiple nodes are connected together using network but physically they are separated. A single task is performed by different functional units of different nodes of distributed unit. Here different programs of an application run simultaneously on different nodes, and communication happens in between different nodes of this system over network to solve task.  5) Grid Computing Environment : In grid computing environment, multiple computers from different locations work on single problem. In this system set of computer nodes running in cluster jointly perform a given task by applying resources of multiple computers/nodes. It is network of computing environment where several scattered resources provide running environment for single task.  6) Cloud Computing Environment : In cloud computing environment on demand availability of computer system resources like processing and storage are availed. Here computing is not done in individual technology or computer rather it is computed in cloud of computers where all required resources are provided by cloud vendor. This environment primarily comprised of three services i.e software-as-a-service (SaaS), infrastructure-as-a-service (IaaS), and platform-as-aservice (PaaS).  7) Cluster Computing Environment : In cluster computing environment cluster performs task where cluster is a set of loosely or tightly connected computers that work together. It is viewed as single system and performs task parallelly that’s why also it is similar to parallel computing environment. Cluster aware applications are especially used in cluster computing environment. 1) Batch processing system: The batch operating system will work to submit similar kinds of job tighter.  2) Time sharing operating system: The time sharing sharing operating system works with time sharing concept. Here CPU will provide a same time period to each and every process to complete its task as soon as possible weather it is a long process or short process.  3) Distributed operating system When many computers are interconnected each other through a network for the purpose of sharing their task then it is called distributed operating system  4) Network operating system: Network operating system has a server that connects many client computers. So we can easily share own files, resources and many more from the server machine to all machine which are connected through a server.  5) Real time operating system: Real time operating system is very useful where we required a quick response. Example is missile system. In this operating system CPU provides maximum offers to its tasks with quick response. Advantage: The real time operating system provide a quick response hence, generally used in scientific engineering, NASA and many more organizations. Disadvantage: This operating system is very costly. Multi-user vs. Single user ▪ A multi-user operating system allows multiple users to access a computer system concurrently. ▪ Time-sharing system can be classified as multi-user systems as they enable a multiple user access to a computer through the sharing of time. ▪ Single-user operating systems, as opposed to a multi-user operating system, are usable by a single user at a time. Multi-tasking vs. Single-tasking ▪ When a single program is allowed to run at a time, the system is grouped under a single-tasking system ▪ While in case the operating system allows the execution of multiple tasks at one time, it is classified as a multi-tasking operating system.  System Calls System Calls: - Programming interface to the services provided by the operating system (OS). system calls is an interface between the user programs and the operating system For performing any operation a user must have to request for a service call which is also known as the SYSTEM CALL or we can say Three most normal APIs are Win32 API for Windows, POSIX API for POSIX- based frameworks (counting for all intents and purposes all adaptations of UNIX, Linux, and Mac OS X), and Java API for the Java virtual machine (JVM)  There are two modes in the operation of system which user more or system mode. 1) In user mode: All user processes are executed. 2) In system mode: All privileged operations are executed.  Types of system calls 1) Process control system calls A process is a basic entity in the system. The processes in the system need to be created, deleted and aborted. Beside these many operations are required on the processes for their management. These are some example: FORK ( ): Create a process EXIT ( ): Terminate a process KILL ( ): Terminate a process abnormally NICE ( ):Increase a priority of a process  2) File management system calls: Creation, deletion, opening, closing, reading and writing are some general operation of files. Similarly for organizing files, there is a directory system and there by system calls managing them. CREATE ( ): To create a new file OPEN ( ): To open a file CLOSE ( ): To close a file READ ( ): To read a file WRITE ( ) : To write a file LINK( ):Give another name to a file UNLINK( ): Delete a file in a directory MKdir( ):Create a new directory  3) Device management system calls: The general commands are: Request of device Release of device Read and Write operation and so on  4) Information maintenance system calls: Many system calls exits simply for the purpose of transferring information between the user program and the operating system. Return current date and time Number of current users Version number of operating system Amount of free memory Get Time ( ) Set Date ( ) Get process ( ) Get Date ( ) Get system data ( ) Set process ( ) Set Time ( ) Set system data ( ) Get file ( ) and so on.  5) Commination’s system calls There is a need for commination among the processes in the system. General operations are: Opening and closing the connection Sending and receiving messages Reading and writing messages and so on. Msgsnd( ): Sanding a message Msgrec( ): Receiving a message These system calls may be related to communication between processes either on the same machine or between processes on different nodes of a network. Thus inter process communication is provided by the operating system through these communication related system calls.  Process Process can be defined as: · A program in execution. · An instance of a program running on a computer. · The entity that can be assigned to and executed on a processor. · A unit of activity characterized by the execution of a sequence of instructions, a current state, and an associated set of system resources  A process is an entity that consists of a number of elements. Two essential elements of a process are program code, and a set of data associated with that code.  Process memory is mainly divided into four different categories as shown in figure. A process is more than the program code, which is sometimes known as the text section. It also includes the current activity, as represented by the value of the program counter and the contents of the processor's registers. A process generally also includes the process stack, which contains temporary data (such as function parameters, return addresses, and local variables), and a data section, which contains global variables. A process may also include a heap, which is memory that is dynamically allocated during process run time.  PROCESS STATES As a process executes, it changes state 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  New: The process is in the stage of being created. Ready State: In first stage, a process moves from new state to ready state after it is loaded into the main memory and this process is ready for execution. Running state: A process moves from ready state to run state after it is assigned the CPU for each process for execution. Waiting or Block State: The process cannot run at the time because process is waiting for some I/O resources or some event to occur. Suspended Ready State: A process moves from ready state to suspend ready state if a process with higher priority has to be executed but the main memory is full. Terminated: the process has completed. Long Term Scheduler Multiple Process Short Term Scheduler Only One Process Medium Term Scheduler Block diagram of Process States  PROCESS CONTROL BLOCK Process Control Block (PCB) is a data structure that stores all information about a particular each process. The Process Control Block diagram of a process looks like-  Process Id is a unique Id for each process that identifies process of the system uniquely. Program Counter is initialized with the address of the first instruction of the program. After executing a first instruction, value of program counter is automatically incremented to point to the next instruction of process. Process state specifies the current state of the process Process with the very highest priority is allocated the CPU first among all the other processes. General purpose registers are mainly used to hold the data of process generated during its execution time. List of Open Files-Each process requires some important files which must be present in the main memory during its execution time. Process control block (PCB) maintains a list of open devices used by the each process during its execution time.  Process Scheduling Process Scheduling responsible for selecting the jobs to be submitted into the system and deciding which process to run. There are 3 kinds of schedulers- 1) Long-term scheduler 2) Short-term scheduler 3) Medium-term scheduler  1. Long-term Scheduler- Long-term scheduler is also called as Job Scheduler. In long term scheduler, it selects a balanced mix of I/O bound and CPU bound processes from the secondary memory such as new state. Then, it loads the selected processes into the main memory (ready state) for time of execution.  2. Short-term Scheduler- Short-term scheduler is also called as CPU Scheduler. It decides which individual process to execute next from the ready queue. After short-term scheduler decides the each process, Dispatcher assigns the each decided process to the CPU for execution purpose.  3. Medium-term Scheduler- Medium-term scheduler processes swaps-out from main memory to secondary memory to free up the main memory when it required. Thus, medium-term scheduler mainly reduces the degree of multiprogramming. After some time when main memory becomes available to use, medium- term scheduler swaps-in and swapped-out process to the main memory and its execution is continued from where it left off.  Operations on processes There are many types of operations that can be performed on processes. such as: 1) Creation 2) Process pre-emption 3) Process blocking 4) Process termination  Unit 2 Process Synchronization: General structure of a typical process, race condition, The Critical-Section Problem, Peterson’s Solution, Synchronization Hardware, Mutex Locks, Semaphores, Classic Problems of Synchronization, Monitors CPU Scheduling: Basic Concepts, Scheduling Criteria, Scheduling Algorithms (FCFS, SJF, SRTF, Priority, RR, Multilevel Queue Scheduling, Multilevel Feedback Queue Scheduling), Thread Scheduling Deadlocks: System Model, Deadlock Characterization, Methods for Handling Deadlocks, Deadlock Prevention, Deadlock Avoidance, Deadlock Detection, Recovery from Deadlock  UNIT – 2- (2) CPU Scheduling CPU scheduling is a key part of how an operating system works. It decides which task (or process) the CPU should work on at any given time. This is important because a CPU can only handle one task at a time, but there are usually many tasks that need to be processed.  Types of CPU Scheduling Here are two kinds of Scheduling methods:  Preemptive Scheduling In Preemptive Scheduling, the tasks are mostly assigned with their priorities. Sometimes it is important to run a task with a higher priority before another lower priority task, even if the lower priority task is still running. The lower priority task holds for some time and resumes when the higher priority task finishes its execution.  Non-Preemptive Scheduling In this type of scheduling method, the CPU has been allocated to a specific process. The process that keeps the CPU busy will release the CPU either by switching context or terminating. It is the only method that can be used for various hardware platforms. That’s because it doesn’t need special hardware (for example, a timer) like preemptive scheduling.  When scheduling is Preemptive or Non-Preemptive? To determine if scheduling is preemptive or non-preemptive, consider these four parameters: A process switches from the running to the waiting state. Specific process switches from the running state to the ready state. Specific process switches from the waiting state to the ready state. Process finished its execution and terminated. Only conditions 1 and 4 apply, the scheduling is called non- preemptive. All other scheduling are preemptive.  CPU scheduling Terminologies Burst Time/Execution Time: It is a time required by the process to complete execution. It is also called running time. Arrival Time: when a process enters in a ready state Finish Time: when process complete and exit from a system Multiprogramming: A number of programs which can be present in memory at the same time. Jobs: It is a type of program without any kind of user interaction. User: It is a kind of program having user interaction. Process: It is the reference that is used for both job and user. CPU/IO burst cycle: Characterizes process execution, which alternates between CPU and I/O activity. CPU times are usually shorter than the time of I/O.  CPU Scheduling Criteria A CPU scheduling algorithm tries to maximize and minimize the following:  Maximize CPU utilization:CPU utilization is the main task in which the operating system needs to make sure that CPU remains as busy as possible. It can range from 0 to 100 percent. Throughput: The number of processes that finish their execution per unit time is known Throughput. The work completed per unit time is called Throughput.  Minimize Waiting time: Waiting time is an amount that specific process needs to wait in the ready queue. Response time: It is an amount to time in which the request was submitted until the first response is produced. Turnaround Time: Turnaround time is an amount of time to execute a specific process. It is the calculation of the total time spent waiting to get into the memory, waiting in the queue and, executing on the CPU. The period between the time of process submission to the completion time is the turnaround time.  What is Dispatcher? It is a module that provides control of the CPU to the process. The Dispatcher should be fast so that it can run on every context switch. Dispatch latency is the amount of time needed by the CPU scheduler to stop one process and start another. Functions performed by Dispatcher: Context Switching Switching to user mode Moving to the correct location in the newly loaded program.  Types of CPU scheduling Algorithm There are mainly six types of process scheduling algorithms First Come First Serve (FCFS) Shortest-Job-First (SJF) Scheduling Shortest Remaining Time Priority Scheduling Round Robin Scheduling Multilevel Queue Scheduling  First-Come, First-Served (FCFS) Scheduling First Come First Serve CPU Scheduling Algorithm shortly known as FCFS. In First Come First Serve Algorithm what we do is to allow the process to execute in linear manner. This means that whichever process enters process enters the ready queue first is executed first. This shows that First Come First Serve Algorithm follows First In First Out (FIFO) principle.  In this, the process that comes first will be executed first and next process starts only after the previous gets fully executed. Here we are considering that arrival time for all processes is 0. How to compute - Completion Time: Time at which process completes its execution. Turn Around Time: Time Difference between completion time and arrival time. Turn Around Time = Completion Time – Arrival Time Waiting Time(W.T): Time Difference between turn around time and burst time. Waiting Time = Turn Around Time – Burst Time Example- given the following demand: Arrival Time 0 1 2  PN BT WT TAT 1 24 0 24 2 3 24 27 3 3 27 30 Average waiting time = 17.00 Average turn around time = 27.00  Problems in the First Come First Serve CPU Scheduling Algorithm Example- Find wating time and  Solution- S. Proces Arrival Burst Comple Turn Waiting No s ID Time Time tion Around Time Time Time 1 P1 A 0 9 9 9 2 P2 B 1 3 12 11 3 P3 C 1 2 14 13 4 P4 D 1 4 18 17 5 P5 E 2 3 21 19 6 P6 F 3 2 23 20 Turn Around Time = CT - AT Waiting Time = TAT - BT  Consider the set of 5 processes whose arrival time and burst time are given below- If the CPU scheduling policy is FCFS, calculate the average waiting time and average turn around time.  Solution- Gantt Chart-  Turn Around time = Exit time – Arrival time Waiting time = Turn Around time – Burst time Average Turn Around time = (4 + 8 + 2 + 9 + 6) / 5 = 29 / 5 = 5.8 unit Average waiting time = (0 + 5 + 0 + 8 + 3) / 5 = 16 / 5 = 3.2 unit  Example-1: Consider the following table of arrival time and burst time for five processes P1, P2, P3, P4 and P5. Find Average Waiting Time. Processes Arrival Time Burst Time P1 0 4 P2 1 3 P3 2 1 P4 3 2 P5 4 5  Shortest Job First (SJF) Scheduling Shortest Job First (SJF) is an algorithm in which the process having the smallest execution time is chosen for the next execution. This scheduling method can be preemptive or non-preemptive. It significantly reduces the average waiting time for other processes awaiting execution. According to the algorithm, the OS schedules the process which is having the lowest burst time among the available processes in the ready queue.  Characteristics of SJF Scheduling: Shortest Job first has the advantage of having a minimum average waiting time among all scheduling algorithms. It is a Greedy Algorithm. It may cause starvation if shorter processes keep coming. This problem can be solved using the concept of ageing. It is practically infeasible as Operating System may not know burst times and therefore may not sort them. While it is not possible to predict execution time, several methods can be used to estimate the execution time for a job, such as a weighted average of previous execution times. SJF can be used in specialized environments where accurate estimates of running time are available. Non-Preemptive SJF In non-preemptive scheduling, once the CPU cycle is allocated to process, the process holds it till it reaches a waiting state or terminated. Consider the following five processes each having its own unique burst time and arrival time. Process Queue Burst time Arrival time P1 6 2 P2 2 5 P3 8 1 P4 3 0 P5 4 4  In the following example, there are five jobs named as P1, P2, P3, P4 and P5. Their arrival time and burst time are given in the table below. PID Arrival Burst Time Completion Turn Waiting Time Time Around Time Time 1 1 7 8 7 0 2 3 3 13 10 7 3 6 2 10 4 2 4 7 10 31 24 14 5 9 8 21 12 4  Consider the set of 5 processes whose arrival time and burst time are given below- Process Id Arrival time Burst time P1 3 1 P2 1 4 P3 4 2 P4 0 6 P5 2 3 If the CPU scheduling policy is SJF non-preemptive, calculate the average waiting time and average turn around time.  Gantt Chart- Process Id Exit time Turn Around time Waiting time Turn Around time = Exit time – Arrival time P1 7 7–3=4 4–1=3 Waiting time = Turn Around time – Burst time P2 16 16 – 1 = 15 15 – 4 = 11 P3 9 9–4=5 5–2=3 P4 6 6–0=6 6–6=0 P5 12 12 – 2 = 10 10 – 3 = 7 Average Turn Around time = (4 + 15 + 5 + 6 + 10) / 5 = 40 / 5 = 8 unit Average waiting time = (3 + 11 + 3 + 0 + 7) / 5 = 24 / 5 = 4.8 unit  Consider the set of 5 processes whose arrival time and burst time are given below- Process Id Arrival time Burst time P1 3 1 P2 1 4 P3 4 2 P4 0 6 P5 2 3 If the CPU scheduling policy is SJF preemptive, calculate the average waiting time and average turn around time.  Gantt Chart- Turn Around time = Exit time – Arrival time Waiting time = Turn Around time – Burst time Process Id Exit time Turn Around time Waiting time Average Turn Around time = (1 + 5 + 4 + 16 + 9) / 5 P1 4 4–3=1 1–1=0 = 35 / 5 P2 6 6–1=5 5–4=1 = 7 unit Average waiting time P3 8 8–4=4 4–2=2 = (0 + 1 + 2 + 10 + 6) / 5 = 19 / 5 P4 16 16 – 0 = 16 16 – 6 = 10 = 3.8 unit P5 11 11 – 2 = 9 9–3=6  Round Robin Round Robin CPU Scheduling uses Time Quantum (TQ). The Time Quantum is something which is removed from the Burst Time and lets the chunk of process to be completed. Time Sharing is the main emphasis of the algorithm. Each step of this algorithm is carried out cyclically. Round-robin scheduling allocates each task an equal share of the CPU time. In its simplest form, tasks are in a circular queue and when a task's allocated CPU time expires, the task is put to the end of the queue and the new task is taken from the front of the queue.  Find Avg. TAT and AWT using RR CPU Scheduling algorithm.  Priority CPU Scheduling Priority scheduling is a non-preemptive algorithm and one of the most common scheduling algorithms in batch systems. Each process is assigned first arrival time (less arrival time process first) if two processes have same arrival time, then compare to priorities (highest process first). Also, if two processes have same priority then compare to process number (less process number first). This process is repeated while all process get executed.  AWT= 5.6 Find Average Waiting Time ? Using Priority CPU Scheduling algorithm (highest number having higher priority) Consider the set of 5 processes whose arrival time and burst time are given below- Process Id Arrival time Burst time Priority P1 0 4 2 P2 1 3 3 P3 2 1 4 P4 3 5 5 P5 4 2 5 If the CPU scheduling policy is priority non-preemptive, calculate the average waiting time and average turn around time. (Higher number represents higher priority)  Average Turn Around time = (4 + 14 + 10 + 6 + 7) / 5 = 41 / 5 = 8.2 unit Average waiting time = (0 + 11 + 9 + 1 + 5) / 5 = 26 / 5 = 5.2 unit  Process Id Arrival time Burst time Priority P1 0 4 2 P2 1 3 3 P3 2 1 4 P4 3 5 5 P5 4 2 5 Consider the set of 5 processes whose arrival time and burst time are given above- If the CPU scheduling policy is priority preemptive, calculate the average waiting time and average turn around time. (Higher number represents higher priority) Process Id Arrival time Burst time Priority P1 0 4 2 P2 1 3 3 P3 2 1 4 P4 3 5 5 P5 4 2 5  Multilevel queue scheduling Multilevel Queue Scheduling is a CPU scheduling algorithm that is used in operating systems to manage the allocation of CPU resources to different processes. In this algorithm, the ready queue is divided into multiple queues based on the process characteristics such as priority, CPU burst time, memory requirement, etc. Each queue is assigned a different priority level, and each queue has its own scheduling algorithm. The highest priority queue gets the highest priority for CPU allocation, and the lowest priority queue gets the lowest priority.  In general, there are three types of queues: foreground (interactive) queue, background (batch) queue, and system queue. The foreground queue contains interactive processes that need quick response time, and the background queue contains processes that can run in the background with lower priority. The system queue contains processes that need to access system resources, such as device drivers.  The processes are initially assigned to the foreground queue, and after a certain amount of time, they are moved to the background queue. The processes in the foreground queue are scheduled using a round-robin algorithm to ensure that each process gets a fair share of the CPU time. The processes in the background queue are scheduled using a first-come, first- served algorithm. This results in a more efficient use of CPU resources and ensures that the system is responsive to the user’s needs. Multilevel Feedback Queue Scheduling (MLFQ) CPU Scheduling Multilevel Feedback Queue Scheduling (MLFQ) CPU Scheduling is like Multilevel Queue(MLQ) Scheduling but in this process can move between the queues. And thus, much more efficient than multilevel queue scheduling. In a multilevel queue-scheduling algorithm, processes are permanently assigned to a queue on entry to the system. Processes do not move between queues. This setup has the advantage of low scheduling overhead, but the disadvantage of being inflexible.  Multilevel feedback queue scheduling, however, allows a process to move between queues. The idea is to separate processes with different CPU-burst characteristics. If a process uses too much CPU time, it will be moved to a lower-priority queue. Similarly, a process that waits too long in a lower- priority queue may be moved to a higher-priority queue. This form of aging prevents starvation.  Process Synchronization: General structure of a typical process, race condition, The Critical-Section Problem, Peterson’s Solution, Synchronization Hardware, Mutex Locks, Semaphores, Classic Problems of Synchronization, Monitors  UNIT – 2- (1)PROCESS SYNCHRONIZATION Process Synchronization: General structure of a typical process, race condition, The Critical-Section Problem, Peterson’s Solution, Synchronization Hardware, Mutex Locks, Semaphores, Classic Problems of Synchronization, Monitors GENERAL STRUCTURE OF A TYPICAL PROCESS Process is program in execution. When a program is loaded into the memory and it consider as a process, it can be divided into four sections ─ stack, heap, text and data. Stack- which contains temporary data Heap-which is memory that is dynamically allocated during Data section-which contains global variables. Text contain-program code  On the basis of synchronization, processes are categorized as one of the following two types: Independent Process: The execution of one process does not affect the execution of other processes. Cooperative Process: A process that can affect or be affected by other processes executing in the system. Process synchronization problem arises in the case of Cooperative process because resources are shared in Cooperative processes.  Need of Process Synchronization? It is the task phenomenon of coordinating the execution of processes in such a way that no two processes can have access to the same shared data and resources. It is a procedure that is involved in order to preserve the appropriate order of execution of cooperative processes. In order to synchronize the processes, there are various synchronization mechanisms. Process Synchronization is mainly needed in a multi-process system when multiple processes are running together, and more than one processes try to gain access to the same shared resource or any data at the same time.  Race Condition When more than one processes are executing the same code or accessing the same memory or any shared variable in that condition there is a possibility that the output or the value of the shared variable is wrong so for that all the processes doing the race to say that my output is correct this condition known as a race condition. A race condition is an undesirable situation that occurs when a device or system attempts to perform two or more operations at the same time.  Race condition problem shared=5 P1 P2 ___________ ____________ int X=shared int Y=shared X++ Y-- Sleep(1) Sleep(1) Shared=x Shared=y In that condition, there is a possibility that the output or the value of the shared variable is wrong so for that purpose all the processes are doing the race to say that my output is correct. This condition is commonly known as a race condition. To avoid race conditions in system use Synchronisation technique.  Critical Section Problem A critical section is a code segment that can be accessed by only one process at a time. The critical section contains shared variables that need to be synchronized to maintain the consistency of data variables. The Critical section problem means designing a way for cooperative processes to access shared resources without creating data inconsistencies.  In the entry section, the process requests for entry in the Critical Section. Any solution to the critical section problem must satisfy three requirements: 1. Mutual Exclusion: If a process is executing in its critical section, then no other process is allowed to execute in the critical section. 2. Progress: If no process is executing in the critical section and other processes are waiting outside the critical section, then only those processes that are not executing in their remainder section can participate in deciding which will enter the critical section next, and the selection can not be postponed indefinitely. 3. Bounded Waiting: A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted. Semaphores The condition is that only one process can only enter the critical section. Remaining Processes which are interested to enter the critical section have to wait for the process to complete its work and then enter the critical section. There may be a state where one or more processes try to enter the critical state. After multiple processes enter the Critical Section, the second process try to access variable which already accessed by the first process. If both the processes occur at the same time, then the compiler would be in a confusion to choose which variable value. This state faced by the variable x is Data Inconsistency. These problems can also be solved by Hardware Locks. To, prevent such kind of problems can also be solved by Hardware solutions named Semaphores Semaphores Semaphores are integer variables that are used to solve the critical section problem by using two atomic operations, wait and signal that are used for process synchronization. The definitions of wait are as follows − The Wait Operation works on the basis of Semaphore or Mutex Value. Here, if the Semaphore value is greater than zero or positive then the Process can enter the Critical Section Area. If the Semaphore value is equal to zero then the Process has to wait for the Process to exit the Critical Section Area. WaitThe wait operation decrements the value of its argument S, if it is positive. If S is negative or zero, then no operation is performed. Algorithm of wait operation:  The definitions of Signal are as follows − The Signal Semaphore Operation is used to update the value of Semaphore. The Semaphore value is updated when the new processes are ready to enter the Critical Section. The Signal Operation is also known as: Wake up Operation Up Operation Increase Operation V Function (most important alias name for signal operation) The most important part is that this Signal Operation or V Function is executed only when the process comes out of the critical section. The value of semaphore cannot be incremented before the exit of process from the critical section  Types of Semaphores There are two types of Semaphores. They are: 1. Binary Semaphore 2. Counting Semaphore  1. Binary Semaphore: The two values are 1 and 0. If the Value of Binary Semaphore is 1, then the process has the capability to enter the critical section area. If the value of Binary Semaphore is 0 then the process does not have the capability to enter the critical section area. 2. Counting Semaphore: If the Value of Binary Semaphore is greater than or equal to 1, then the process has the capability to enter the critical section area. If the value of Binary Semaphore is 0 then the process does not have the capability to enter the critical section area.  Solving Classical Synchronization Problems using Semaphore Concept 1. Solving Readers - Writers Problem using Semaphore 2. Solving Bound Buffer Problem using the concept of Semaphores 3. Solving Dining Philosopher's Problem using the concept of Semaphores Solving Readers - Writers Problem using Semaphore Consider a situation where we have a file shared between many people. If one of the person tries editing the file, no other person should be reading or writing at the same time, otherwise changes will not be visible to him/her. There are four types of cases that could happen here. However, if some person is reading the file, then others may read it at the same time. There are four types of cases that could happen here.- Case Process 1 Process 2 Allowed/Not Allowed Case 1 Writing Writing Not Allowed Case 2 Writing Reading Not Allowed Case 3 Reading Writing Not Allowed Case 4 Reading Reading Allowed  This is an important problem of synchronization which has several variations like The simplest one is referred as first reader writer problem which requires that no reader will be kept waiting unless a writer has obtained permission to use the shared object. In other words no reader should wait for other reader to finish because a writer is waiting. The second reader writer problem requires that once a writer is ready then the writer performs its write operation as soon as possible. Three variables are used: mutex, wrt, readcnt to implement solution semaphore mutex, wrt; // semaphore mutex is used to ensure mutual exclusion when readcnt is updated i.e. when any reader enters or exit from the critical section and semaphore wrt is used by both readers and writers int readcnt; // readcnt tells the number of processes performing read in the critical section, initially 0 The structure of a reader process is as follows: Read count --; Wait (mutex); if (read count == 0) Read count++; Signal (wrt); if (read count == 1) Signal (mutex); Wait (wrt); Signal (mutex); The structure of the writer process........... is as follows: Reading is performed Wait (wrt);........... Writing is performed; Wait (mutex); Signal (wrt);  The bounded-buffer problems (aka the producer-consumer problem) is a classic example of concurrent access to a shared resource. A bounded buffer lets multiple producers and multiple consumers share a single buffer. Producers write data to the buffer and consumers read data from the buffer. Dining Philosopher Problem: Consider 5 philosophers to spend their lives in thinking & eating. A philosopher shares common circular table surrounded by 5 chairs each occupies by one philosopher. In the center of the table there is a bowl of rice and the table is laid with 6 chopsticks as shown in below figure. When a philosopher thinks she does not interact with her colleagues. From time to time a philosopher gets hungry and tries to pickup two chopsticks that are closest to her. A philosopher may pickup one chopstick or two chopsticks at a time but she cannot pickup a chopstick that is already in hand of the neighbor. When a hungry philosopher has both her chopsticks at the same time, she eats without releasing her chopsticks  When she finished eating, she puts down both of her chopsticks and starts thinking again. This problem is considered as classic synchronization problem. According to this problem each chopstick is represented by a semaphore. A philosopher grabs the chopsticks by executing the wait operation on that semaphore. She releases the chopsticks by executing the signal operation on the appropriate semaphore. The structure of dining philosopher is as follows: do{ Wait ( chopstick [i]); Wait (chopstick [(i+1)%5]);............. Eat............. Signal (chopstick [i]); Signal (chopstick [(i+1)%5]);............. Think............. } While (1);  Chapter 3. Deadlock A deadlock is a situation where a set of processes is blocked because each process is holding a resource and waiting for another resource acquired by some other process. Definition: Deadlock is a situation in computing where two or more processes are unable to proceed because each is waiting for the other to release resources. Consider an example when two trains are coming toward each other on the same track and there is only one track, none of the trains can move once they are in front of each other. This is a practical example of deadlock.  How Does Deadlock occur in the Operating System? A process in an operating system uses resources in the following way- Requests a resource Use the resource Releases the resource A situation occurs in operating systems when there are two or more processes that hold some resources and wait for resources held by other(s). For example, in the below diagram, Process 1 is holding Resource 1 and waiting for resource 2 which is acquired by process 2, and process 2 is waiting for resource 1. Necessary Conditions for Deadlock in OS Deadlock can arise if the following four conditions hold simultaneously (Necessary Conditions) Mutual Exclusion: Two or more resources are non-shareable (Only one process can use at a time). Hold and Wait: A process is holding at least one resource and waiting for resources. No Preemption: A resource cannot be taken from a process unless the process releases the resource. Circular Wait: A set of processes waiting for each other in circular form.  Resource Allocation Graph A Resource Allocation Graph (RAG) is a fundamental concept in operating systems, particularly in the context of process management and deadlock prevention. It is used to represent the allocation of resources to processes and to help detect potential deadlocks. The resource allocation graph is the pictorial representation of the state of a system. It also contains the information about all the instances of all the resources whether they are available or being used by the processes.  Vertices are mainly of two types, Resource and process. Each of them will be represented by a different shape. Circle represents process while rectangle represents resource. A resource can have more than one instance. Each instance will be represented by a dot inside the rectangle.  In Resource allocation graph, the process is represented by a Circle while the Resource is represented by a rectangle. Let's see the types of vertices and edges in detail.  Edges in RAG are also of two types, one represents assignment and other represents the wait of a process for a resource.  A resource is shown as assigned to a process if the tail of the arrow is attached to an instance to the resource and the head is attached to a process. A process is shown as waiting for a resource if the tail of an arrow is attached to the process while the head is pointing towards the resource.  Let's consider 2 processes P1, P2, and two types of resources R1 and R2. The resources are having 1 instance each. According to the graph, R1 is being used by P1 and waiting for R2, R2 is being used by P2, and waiting for R1  consider 3 processes P1, P2 and P3, and two types of resources R1 and R2. The resources are having 1 instance each. According to the graph, R1 is being used by P1, P2 is holding R2 and waiting for R1, P3 is waiting for R1 as well as R2.  Allocation Matrix Allocation matrix can be formed by using the Resource allocation graph of a system. In Allocation matrix, an entry will be made for each of the resource assigned. Request Matrix In request matrix, an entry will be made for each of the resource requested. Availability of resources  Single instance case R1 Proces Allocation Matrix Request P1 P2 s Matrix R1 R2 R1 R2 R2 P1 1 0 0 1 P2 0 1 1 0 If RAG has circular wait cycle then--→ always Deadlock occur Availability of resource= (0,0) Not full fill the request of P1 neither P2 So it’s a Deadlock situation  Pro Allocation Request ces Matrix Matrix s R1 R2 R1 R2 P1 1 0 0 0 P2 0 1 0 0 P3 0 0 1 1 Availability of resource= (0,0) First full fill request of P1, and release resources. Availability of resource= (1,0) Second full fill request of P2, and release resources. If RAG has circular wait no cycle Availability of resource= (1,1) then--→ No Deadlock occur Finally full fill request of P3 Successfully full fill request of resource So it is No Deadlock situation Strategies for handling Deadlock  Deadlock Ignorance 1. Deadlock Ignorance is the most widely used approach among all the mechanism. This is being used by many operating systems mainly for end user uses. In this approach, the Operating system assumes that deadlock never occurs. It simply ignores deadlock. This approach is best suitable for a single end user system where User uses the system only for browsing and all other normal stuff. The operating systems like Windows and Linux mainly focus upon performance. However, the performance of the system decreases if it uses deadlock handling mechanism all the time if deadlock happens 1 out of 100 times then it is completely unnecessary to use the deadlock handling mechanism all the time. In these types of systems, the user has to simply restart the computer in the case of deadlock. Windows and Linux are mainly using this approach.  2. Deadlock prevention Deadlock happens only when Mutual Exclusion, hold and wait, No preemption and circular wait holds simultaneously. If it is possible to violate one of the four conditions at any time then the deadlock can never occur in the system. The idea behind the approach is very simple that we have to fail one of the four conditions but there can be a big argument on its physical implementation in the system.  Deadlock avoidance In deadlock avoidance, the operating system checks whether the system is in safe state or in unsafe state at every step which the operating system performs. The process continues until the system is in safe state. Once the system moves to unsafe state, the OS has to backtrack one step. The OS reviews each allocation so that the allocation doesn't cause the deadlock in the system.  4. Deadlock detection and recovery This approach let the processes fall in deadlock and then periodically check whether deadlock occur in the system or not. If it occurs then it applies some of the recovery methods to the system to get rid of deadlock.  Banker’s Algorithm It is a banker algorithm used to avoid deadlock and allocate resources safely to each process in the computer system. it is also known as deadlock avoidance algorithm or deadlock detection in the operating system. The banker's algorithm is named because it checks whether a person should be sanctioned a loan amount or not to help the bank system safely simulate allocation resources.  Advantages It contains various resources that meet the requirements of each process. Each process should provide information to the operating system for upcoming resource requests, the number of resources, and how long the resources will be held. It helps the operating system manage and control process requests for each type of resource in the computer system. The algorithm has a Max resource attribute that represents indicates each process can hold the maximum number of resources in a system.  When working with a banker's algorithm, it requests to know about three things: How much each process can request for each resource in the system. It is denoted by the [MAX] request. How much each process is currently holding each resource in a system. It is denoted by the [ALLOCATED] resource. It represents the number of each resource currently available in the system. It is denoted by the [AVAILABLE] resource.  Suppose n is the number of processes, and m is the number of each type of resource used in a computer system. Available: It is an array of length 'm' that defines each type of resource available in the system. When Available[j] = K, means that 'K' instances of Resources type R[j] are available in the system. Max: It is a [n x m] matrix that indicates each process P[i] can store the maximum number of resources R[j] (each type) in a system. Allocation: It is a matrix of m x n orders that indicates the type of resources currently allocated to each process in the system. When Allocation [i, j] = K, it means that process P[i] is currently allocated K instances of Resources type R[j] in the system. Need: It is an M x N matrix sequence representing the number of remaining resources for each process. When the Need[i] [j] = k, then process P[i] may require K more instances of resources type Rj to complete the assigned work. Nedd[i][j] = Max[i][j] - Allocation[i][j]. Finish: It is the vector of the order m. It includes a Boolean value (true/false) indicating whether the process has been allocated to the requested resources, and all resources have been released after finishing its task. The Banker's Algorithm is the combination of the safety algorithm and the resource request algorithm to control the processes and avoid deadlock in a system: Safety Algorithm It is a safety algorithm used to check whether or not a system is in a safe state or follows the safe sequence in a banker's algorithm: 1. There are two vectors Wok and Finish of length m and n in a safety algorithm. Initialize: Work = Available Finish[i] = false; for I = 0, 1, 2, 3, 4… n - 1. 2. Check the availability status for each type of resources [i], such as: Need[i]