CH3 Process Management.pptx

Operating Systems 2505413 3. Process Management Summer 2024 1 Prepared by Dr. Yasir Eltigani Introduction to Process Management Process management is a fundamental aspect of operating systems, ensuring the efficient execution and resource allocation of m...

Operating Systems 2505413 3. Process Management Summer 2024 1 Prepared by Dr. Yasir Eltigani Introduction to Process Management Process management is a fundamental aspect of operating systems, ensuring the efficient execution and resource allocation of multiple processes. Definition: A process is a program in execution, consisting of the program code, its current activity represented by the value of the program counter, and the contents of the processor's registers. Summer 2024 2 Process States New: The process is being created. Ready: The process is waiting to be assigned to a processor. Running: Instructions are being executed. Waiting: The process is waiting for some event to occur (such as an I/O completion). Terminated: The process has finished execution. Summer 2024 3 Process Control Block (PCB) Process Control Block is a data structure that contains information of the process related to it. It is very important for process management as the data structuring for processes is done in terms of the PCB. It also defines the current state of the operating system. Process Id Process state Program counter CPU registers Memory management information Accounting information I/O status Summer 2024 information 4 Process Control Block (PCB) PCB Contains crucial information about the process, including: Process Id: A unique identifier assigned by the operating system. Process state: Can be ready, running, etc. Program counter: It stores the counter,: which contains the address of the next instruction that is to be executed for the process. CPU registers: Like the Program Counter (CPU registers must be saved and restored when a process is swapped in and out of the CPU) Memory management information: The memory management information includes the page tables or the segment tables depending on the memory system used. It also contains the value of the base registers, limit registers etc. Accounting information: The time limits, account numbers, amount of CPU used, process numbers etc. are all a part of the PCB accounting information. I/O status information: For example, devices allocated to the process, open files, etc List of Open Files: These are the different files that are associated with the process Summer 2024 5 Context Switching The process of saving the state of a currently running process and loading the state of the next process to run. It involves switching the CPU from one process to another, ensuring the smooth execution of multiple processes. When Does Context Switching Happen? 1. When a high-priority process comes to a ready state (i.e. with higher priority than the running process). 2. An Interrupt occurs. 3. User and kernel-mode switch (It is not necessary though) 4. Preemptive CPU scheduling is used. Summer 2024 6 CPU Switch From Process to Process Summer 2024 7 Threads in Operating Systems Definition: A thread is the smallest unit of a process that can be scheduled and executed by the CPU. Importance: Threads allow parallelism within a process, leading to more efficient and faster execution. Types of Threads 1. User-Level Threads (ULTs): Managed by user-level libraries. Pros: Fast context switch, no OS modification required. Cons: Entire process blocks if a thread blocks. 2. Kernel-Level Threads (KLTs): Managed by the operating system kernel. Pros: The OS can manage and schedule threads independently. Cons: Slower context switches compared to ULTs. Summer 2024 8 Threads in Operating Systems Advantages of Using Threads: Responsiveness: Allows a program to continue running even if part of it is blocked. Resource Sharing: Threads of the same process share memory and resources. Economy: Creating and managing threads is less costly than processes. Scalability: Threads can run on different processors in a multiprocessor system. Thread Lifecycle New: Thread is created. Runnable: Thread is ready to run. Running: CPU is executing the thread. Blocked: Thread is waiting for resources. Terminated: Thread has finished execution. Summer 2024 9 Process Scheduling in Operating Systems Definition: Process scheduling is the method by which the operating system decides which process runs at any given time. Importance: Ensures efficient execution of processes, optimal CPU utilization, and overall system performance. Categories of Scheduling Scheduling falls into one of two categories: 1. Non-preemptive: In this case, a process’s resource cannot be taken before the process has finished running. When a running process finishes and transitions to a waiting state, resources are switched. 2. Preemptive: In this case, the OS assigns resources to a process for a predetermined period. The process switches from running state to ready state or from waiting state to ready state during resource allocation. This switching happens because the CPU may give other processes priority and substitute the currently active process for the higher priority process. Summer 2024 10 Types of Schedulers Long-term Scheduler (Job Scheduler): Determines which processes are to be admitted into the system. It brings the new process to the ‘Ready State’. Short-term Scheduler (CPU Scheduler): Selects which process should be executed next. It brings process from the ready state for scheduling it on the running state. Medium-term Scheduler: Manages swapping of processes in and out of memory to balance load. Summer 2024 11 Scheduling Queues Job Queue: All processes in the system. Ready Queue: Processes that are ready to run. Device Queue: Processes waiting for devices (I/O). Summer 2024 12 Scheduling Algorithms Overview There are mainly two types of scheduling methods: 1. Preemptive Scheduling: Preemptive scheduling is used when a process switches from running state to ready state or from the waiting state to the ready state. 2. Non-Preemptive Scheduling: Non-Preemptive scheduling is used when a process terminates , or when a process switches from running state to waiting state. CPU scheduling algorithms in operating systems First-Come, First-Served (FCFS) Shortest Job Next (First) (SJN) Priority Scheduling Round Robin (RR) Multilevel Queue Scheduling Summer 2024 13 Key Concepts in CPU Scheduling 1. Arrival Time: It is the moment in time when a process enters the ready queue and is awaiting execution by the CPU. 2. Burst Time: It is the amount of CPU time the process requires to complete its execution. 3. Completion Time: Completion time is when a process finishes execution and is no longer being processed by the CPU. It is the summation of the arrival, waiting, and burst times. 4. Turnaround Time: The time elapsed between the arrival of a process and its completion. Turnaround Time = Completion Time – Arrival Time 5. Waiting Time: This is a process’s duration in the ready queue before it begins executing. Waiting Time = Turnaround Time – Burst Time 6. Response Time: It is the duration between the arrival of a process and the first time it runs. Response Time = Time it Started Executing – Arrival Time Summer 2024 14 1. First-Come, First-Served (FCFS) Description: Processes are executed in the order they arrive. Advantages: Simple and easy to implement. Disadvantages: Can lead to long wait times and poor response time for short processes. Example: Suppose that the processes arrive in the order: P1 , P2 , P3 Process Burst Time P1 24 P2 3 P3 3 The Gantt Chart for the schedule is: P 1 P 2 P3 0 24 27 30 Waiting time for P1 = 0; P2 = 24; P3 = 27 Average waiting time: (0 + 24 + 27)/3 = 17 Summer 2024 15 1. First-Come, First-Served (FCFS) Example cont.: Suppose that the processes arrive in the order: P2 , P3 , P1 The Gantt chart for the schedule is: P 2 P 3 P1 0 3 6 30 Waiting time for P1 = 6; P2 = 0; P3 = 3 Average waiting time: (6 + 0 + 3)/3 = 3 Much better than previous case Convoy effect - short process behind long process Consider one CPU-bound and many I/O-bound processes Summer 2024 16 1. First-Come, First-Served (FCFS) Example: Let's consider an example with three processes (P1, P2, P3) and their respective arrival and burst times. We will calculate the completion time, turnaround time, waiting time, and response time for each process using First- Come, First-Served (FCFS) scheduling. Process Arrival Burst P1 P2 P3 time Time P1 0 5 0 5 8 16 P2 1 3 Completion Time (CT): (CT = Arrival time + Burst time) P1: CT = Arrival Time + Burst Time = 0 + 5 = 5 P3 2 8 P2: CT = max(previous CT, Arrival Time) + Burst Time = max(5, 1) + 3 = 8 P3: CT = max(previous CT, Arrival Time) + Burst Time = max(8, 2) + 8 = 16 Turnaround Time (TAT): (TAT = Completion Time - Arrival Time) P1: TAT = 5 - 0 = 5 P2: TAT = 8 - 1 = 7 P3: TAT = 16 - 2 = 14 1. b Summer 2024 17 1. First-Come, First-Served (FCFS) Process Arrival Burst time Time P1 P2 P3 P1 0 5 0 5 8 16 P2 1 3 Waiting Time (WT): (WT = Turnaround Time - Burst Time) P3 2 8 P1: WT = 5 - 5 = 0 P2: WT = 7 - 3 = 4 P3: WT = 14 - 8 = 6 Response Time (RT): (RT = Time process starts executing - Arrival Time) P1: RT = 0 - 0 = 0 P2: RT = 5 - 1 = 4 P3: RT = 8 - 2 = 6 Summer 2024 18 1. First-Come, First-Served (FCFS) Example: Consider the following process table. Calculate the average waiting time using FCFS. Process Arrival time Burst Time P1 0 3 P2 2 6 P3 4 4 P4 6 5 P5 8 2 Summer 2024 19 1. First-Come, First-Served (FCFS) Process Arrival Burst Example: time Time The Gantt Chart for the schedule is: P1 0 3 P2 2 6 P1 P2 P3 P4 P5 P3 4 4 P4 6 5 0 3 9 13 1 2 Waiting time for P1 = 0 – 0 = 0 8 0 P5 8 2 Waiting time for P2 = 3 – 2 = 1 Waiting time for P3 = 9 – 4 = 5 Waiting time for P4 = 13 – 6 = 7 Waiting time for P5 = 18 – 8 = 10 Average waiting time = = Summer 2024 20 1. First-Come, First-Served (FCFS) Exercise: Consider the following process table. Calculate the average waiting time using FCFS. Process Arrival time Burst Time P1 0 10 P2 2 1 P3 4 2 P4 6 1 P5 8 5 Ans. 5.6 Summer 2024 21 2. Shortest Job Next (SJN) Description: Process with the shortest execution time is selected next. Advantages: Minimizes average waiting time. Disadvantages: Many times it becomes complicated to predict the length of the upcoming CPU request. Types: 1. Non-preemptive SJF: Once a process starts, it cannot be interrupted until it finishes. Process with the shortest burst time is selected from the ready queue. 2. Preemptive SJF: A running process can be interrupted if a new process with a shorter burst time arrives. More complex but often reduces average waiting time more effectively. Its called (Shortest- Remaining –Time-First(SRTF) Starvation: Occurs when short jobs keep arriving, causing longer jobs to wait indefinitely. Solution: By increasing the priority of processes that have been waiting for a significant period, the SJN algorithm ensures that even longer jobs eventually get executed.. Summer 2024 22 2. Shortest Job Next (SJN) Example: Consider the following table of arrival time and burst time for four processes P1, P2, P3 and P4: Process Arrival time Burst Time P1 0 7 P2 2 4 P3 4 1 P4 5 4 Calculate the average waiting time for each method: 1. Non-preemptive. 2. Preemptive Summer 2024 23 2. Shortest Job Next (SJN) First Non-preemptive: Process Arrival Burst The Gantt Chart for the schedule is: time Time P1 0 7 P1 P3 P2 P4 P2 2 4 0 7 8 1 16 P3 4 1 2 P4 5 4 Waiting time for P1 = 0 – 0 = 0 Waiting time for P2 = 8 – 2 = 6 Waiting time for P3 = 7 – 4 = 3 Waiting time for P4 = 12 – 5 = 7 Average waiting time = = Summer 2024 24 2. Shortest Job Next (SJN) Second Preemptive: Process Arrival Burst The Gantt Chart for the schedule is: time Time P1 0 7 (5 P P1 P2 P2 P4 P1 P2 2 4 ) 3 (2 P3 4 1) 0 2 4 5 7 11 16 P4 5 4 Waiting time for P1 = (0 – 0) + (11-2) = 9 Waiting time for P2 = (2 - 2) + (5 – 4) = 1 Waiting time for P3 = 4 – 4 = 0 Waiting time for P4 = 7 – 5 = 2 Average waiting time = = Summer 2024 25 2. Shortest Job Next (SJN) Exercise: Consider the following table of arrival time and burst time for four processes P1, P2, P3 and P4: Process Arrival time Burst Time P1 0 8 P2 1 4 P3 2 9 P4 3 5 Calculate the average waiting time for each method: 1. Non-preemptive. 1. Ans. 6 2. Preemptive 2. Ans. Summer 2024 4.75 26 3. Priority Scheduling Description: Processes are assigned priority numbers, and the highest priority process is selected next. Advantages: Minimizes average waiting time. Disadvantages: Can lead to starvation of lower priority processes. Types: 1. Non-preemptive SJF: Once a process starts, it cannot be interrupted until it finishes. Process with highest priority number is selected from the ready queue. 2. Preemptive SJF: A running process can be interrupted if a new process with a high priority number arrives. More complex but often reduces average waiting time more effectively. Its called (Shortest- Remaining –Time-First(SRTF) Starvation occurs when a process in the OS runs out of resources because other processes are using it. Solution to Starvation: Aging Aging is a technique of gradually increasing the priority of processes that wait in the system for a long time. Summer 2024 27 3. Priority Scheduling Description: Processes are assigned priority numbers, and the highest priority process is selected next. Advantages: Minimizes average waiting time. Disadvantages: Can lead to starvation of lower priority processes. Types: 1. Non-preemptive SJF: Once a process starts, it cannot be interrupted until it finishes. Process with highest priority number is selected from the ready queue. 2. Preemptive SJF: A running process can be interrupted if a new process with a high priority number arrives. More complex but often reduces average waiting time more effectively. Its called (Shortest- Remaining –Time-First(SRTF) Starvation occurs when a process in the OS runs out of resources because other processes are using it. Solution to Starvation: Aging Aging is a technique of gradually increasing the priority of processes that wait in the system for a long time. Summer 2024 28 4. Round Robin (RR) Description: (RR) is a preemptive scheduling algorithm. Each process is allocated a fixed time slot (time quantum). If a process does not finish execution within its time quantum, it is preempted and placed at the end of the ready queue.. Process Burst Advantages: Fair and predictable. Time P1 53 Disadvantages: Time slice size can impact performance. P2 17 Example of RR with Time Quantum = 20 P3 68 P4 24 The Gantt Chart for the schedule is: P1 P2 P3 P4 P1 P3 P4 P1 P3 P3 0 20 37 5 77 97 117 121 13 15 16 7 4 4 2 Summer 2024 29 5. Multilevel Queue Scheduling Description: Multilevel Queue (MLQ) scheduling divides the ready queue into several separate queues. Each queue has its own scheduling algorithm. Processes are permanently assigned to one queue based on specific attributes like process type, priority, or resource needs. Advantages: Can be tailored to specific types of processes. Disadvantages: Complex to implement and manage. Summer 2024 30