Tutorial3_Sol.pdf

COMPS267F (2024) Operating Systems Tutorial 3 Stage 1: Concepts and Keywords of Chapter 3 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Process is a program in ___________. (execution) The process is in a _____ state if it is waiting to be assigned to a processor. (ready) The process is in a _____ state if it is w...

COMPS267F (2024) Operating Systems Tutorial 3 Stage 1: Concepts and Keywords of Chapter 3 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Process is a program in ___________. (execution) The process is in a _____ state if it is waiting to be assigned to a processor. (ready) The process is in a _____ state if it is waiting for some event to occur. (waiting) The process is in a _____ state if it has finished execution. (terminated) Each process is represented in the OS by a ____________, including process state, program counter, CPU scheduling information, etc. (PCB/process control block) A __________ occurs when the CPU switches from one process to another. (context switch) Parent process create ______ processes, which, in turn create other processes, forming a _____ of processes. (children, tree) ________ process can affect or be affected by other processes, including sharing data. ________ cannot affect or be affected by other processes. (Cooperating, Independent) With indirect communication, the messages are sent to and received from ______, or ports. (mailboxes) Communication between processes takes place through calls to ______ and _____ primitives. (send(), receive()) Stage 2: CPU utilization and multi-programming (developed by Dr. Andrew LUI) First learn the materials and then solve the similar problems. Process turn-around time: The period of time between the creation and termination of a process. CPU utilization rate: The proportion of time that the CPU is doing the work of executing user programs. Example 1: CPU Utilization and Turn-Around Time A set of five processes is to be executed on a single processor computer system. Each process has the following characteristics: the turn-around time is 10 ms, and it spends 20% of the time in CPU bursts and 80% in IO bursts. Calculate the CPU Utilization and the overall turnaround time of the five processes if only the execution a single process is allowed (non multi-programming). The processes must be executed in the following pattern. The execution of one process first. Only after the process has completed execution, the execution of the second process will begin. Total turnaround time is 10 ms (each process) x 5 = 50 ms Each process spends 10 ms x 20% = 2 ms using the CPU and 10 ms x 80 % = 8 ms doing IO operations. Totally the time the CPU is being used is 2 ms (each process) x 5 = 10 ms. CPU Utilization = 10 ms / 50 ms = 20% This is a low utilization rate. Example 2: CPU Utilization and Turn-Around Time Consider the above example again. Calculate the CPU Utilization and the overall turnaround time of the five processes if multi-programming is supported. Assumption #1: Ignore the time taken by the OS to do work in executing the processes. Assumption #2: Many IO operations cannot happen in parallel. The OS will execute all five processes at the same time. The OS first loads the program of these five processes into the main memory. There is only one CPU and so the OS will select one of the processes in CPU bursts to use the CPU. When the process selected has finished one CPU burst and doing IO operations, the OS will select another process in CPU burst to use the CPU. The OS tries to arrange the five processes so that the CPU is not idling. Total CPU burst time of 5 processes = 2 ms (each process) x 5 = 10 ms Total IO burst time of 5 processes = 8 ms (each process) x 5 = 40 ms The CPU burst time can happen in parallel with the IO burst time, except for the first process. Turnaround time = 40 ms (IO burst time) + 2 ms (CPU burst time of first process = 42 ms CPU Utilization = 10 ms / 42 ms = 24% The turnaround time is shortened and the CPU utilization improved. Example 3: OS Process Management Overhead Consider Example 2. In a simplified model, the multi-programming OS spends on average 1 ms per process in overhead operations such as loading programs. Assume that these overhead operations of the processes cannot happen in parallel. Calculate the turn-around time and CPU utilization for the situation of Example 2. The total time for the OS to manage the five processes = 1 ms x 5 = 5 ms Turnaround time becomes = 40 ms (IO burst time) + 2 ms (CPU burst time of first process) + 5 ms (overhead) = 47 ms CPU Utilization = 10 ms / 47 ms = 21% The turnaround time is longer and the CPU utilization reduced. Please answer the following questions: A set of three processes A, B, C is to be executed on a single processor computer system. These processes have the following characteristics: the turn-around time is 4, 12 and 16 ms respectively for A, B, and C, each of these processes spends 25% of the time in CPU bursts and 75% in IO bursts. 1. Calculate the CPU utilization rate and the overall turnaround time of the three processes if only the execution one process is allowed for each time (i.e. uni-programming). The processes must be executed in this pattern. The execution of one process first. Only after the process has completed execution, the execution of the second process will begin. Assume that there is no management overhead. CPU utilization rate is the proportion of time CPU is doing useful work, which is 25% of the time. Overall turnaround time is the total time taken for all three processes to complete their execution. It is a uniprogramming system, so one process is allowed to run only when another process is completed execution. Therefore, the overall turnaround time is the sum of individual process’s turnaround time = (4 + 12 + 16) ms A C B CPU IO CPU IO CPU IO Overall turnaround time 2. Is the CPU utilization rate affected by the order of execution of the three processes? Justify your answer. No. It is again due to uni-programming, one process is executed at a time. The overall turnaround time is always the same, which is (4 + 12 + 16) ms. The total amount of time using the CPU is (4 + 12 + 16) * 25% ms So the CPU utilization rate is (4 + 12 + 16) * 25% / (4 + 12 + 16) = 25% 3. Estimate the CPU utilization rate and the overall turnaround time of these three processes if multiprogramming is supported. Assumption #1: Ignore the time taken by the OS to do work in executing the processes. Assumption #2: IO operations cannot happen in parallel. Assumption #3: For each process, CPU burst must happen first. The OS will execute all three processes at the same time. The OS first loads the program of these three processes into the main memory. There is only one CPU and so the OS will select one of the processes in CPU bursts to use the CPU. When the process selected has finished one CPU burst and doing IO operations, the OS will select another process in CPU burst to use the CPU. The OS tries to arrange the three processes so that the CPU is not idling. In a multi-programming scenario, the overall turnaround time becomes shorter. It is because while one process is doing CPU another one is doing the IO at the same time. The turnaround time is shortened by that overlapped period of time. FORMULATION 1 For example, process B’s CPU burst (3ms) is happening, process A’s IO can happen as well. So, 3ms is saved. In details, - Process A’s CPU burst (1ms) begins first. Processes B and C are waiting. After 1ms, process B’s CPU burst (3ms) begins. Process A IO can happen at the same time. Save 3ms - After 3ms, process C’s CPU burst (4ms) begins. Process A or B IO can happen at the same time. Save 4ms. Overall turnaround time = (4 + 12 + 16) – (3 + 4) = 25 ms The total amount of time using the CPU is the same = (4 + 12 + 16) * 25% ms = 8 ms CPU utilization rate is estimated to be 8 / 25 = 32 % FORMULATION 2 Overall turnaround time is estimated = total IO burst time + CPU burst of Process A = (4 + 12 + 16) * 75% + (4 * 25%) = 24 + 1 = 25 ms CPU utilization rate is estimated to be 8 / 25 = 32% A CPU B IO IO CPU C CPU IO Overall turnaround time