operating systems scheduling concepts for engineers

operating systems scheduling

1. Process And Process Scheduling Bhargavi Varala "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 1

2. MODULE OBJECTIVES "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 2 To introduce the notion of a process To describe the various features of processes To describe various scheduling algorithms To understand the concept of threads

3. Recipe (Program) Recipe being made (Program in execution) ( Process ) "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 3

4. What Is A Process? Process is a program in execution Process contains Program code Program counter and registers Stack Data section Heap Stack Heap Data Text Fig. Process in memory Program is a passive entity while process is an active entity. Main Memory Program Process Two or more processes of same program might run at the same time but each of them is a separate process. "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 4

5. Process States "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 5

6. Process Description: Process Control Block (PCB) "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 6 Each is represented by a Process Control Block ( PCB ) Also known as task control block PCB contains Process state Program counter CPU registers CPU Scheduling information Memory management information Accounting information I/O status information PCB is a repository for any information that vary from process to process Process State Process Number Program Counter Registers Memory Limits List of Open Files . . . . Fig. Process Control Block

7. Scheduling Queues Contains all processes Job Queue Ready to execute Waiting for CPU Ready Queue Waiting for a particular device I/O device Device Queue Fig. Different Scheduling Queues "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 7

8. How A Process Is Scheduled? "PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 8 ready queue CPU I/O I/O queue I/O request Time slice expired fork a child Wait for an interrupt Child executes Interrupt occurs Newly admitted process Dispatched Fig. Queueing diagram of process scheduling "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 8

9. Who Schedules The Process? "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 9 Scheduler Selects processes from different queues for scheduling purpose Types of schedulers Long- term Scheduler ( Job Scheduler ) Selects processes from job pool ( job queue ) and loads them into main memory for execution Less frequently executed Controls the degree of multiprogramming (no. of processes in main memory) Short- term Scheduler ( CPU Scheduler) Selects processes from ready queue and allocates CPU to one of them. Most frequently executed Medium-term Scheduler (Memory Scheduler) Medium-term schedulers are responsible for swapping of a process from the Main Memory to Secondary Memory and vice-versa. It is helpful in maintaining a perfect balance between the I/O bound and the CPU bound.

10. Context Switch "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 11 When interrupt occurs, the system saves the current context of a process running on the CPU The context is represented in the PCB We perform State save of the current state of the process State restore to resume operations Context switch Switching the CPU to another process requires performing a state save of the current process and a state restore of a different process Context- switch time is pure overhead Highly dependent on hardware support

11. Context Switch Fig. CPU Switching from Process to Process "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 12

12. Process Scheduling "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 13

13. Basic Concept of Scheduling "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 14 Multiprogramming concept Properties of a process/program CPU- bound program I/O-bound program CPU Scheduler selects process to execute Scheduling Non-preemptive or cooperative Preemptive Incurs a cost associated with access to shared data Affects the design of the operating- system kernel When CPU Scheduling is to be done? When a process moves from Running state  waiting state Running state  ready state Waiting state  ready state Terminates

14. 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. 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. "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 15

15. Basic Concept of Scheduling "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 17 Dispatcher Gives control of the CPU to the process selected by short- term scheduler Involves Switching context Switching to user mode Jumping to the proper location in the user program to restart that program Dispatch latency The time it takes for the dispatcher to stop one process and start another running

16. Scheduling Criteria CPU Utilization To keep the CPU as busy as possible Throughput The number of processes that are completed per unit time Turnaround time The interval from the time of submission of a process to the time of completion Waiting to get in memory Waiting to ready queue Executing on the CPU Doing I/O Turnaround Time "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 18

17. Scheduling Criteria Waiting time The sum of the periods spent waiting in the ready queue Response time The time from the submission of a request until the first response is produced "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 19

18. Scheduling Algorithms First- Come First- Served Scheduling (FCFS) Shortest Job First Scheduling (SJF) Priority Scheduling Round Robin Scheduling (RR) Multilevel Queue Scheduling Multilevel Feedback Queue Scheduling "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 20

19. Scenario 1 How movie tickets are issued? First- Come First- Served Scheduling (FCFS) "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 21

20. First- Come First- Served Scheduling (FCFS) Managed with FIFO queue Working of an algorithm When a process enters in ready queue, its PCB is linked to the tail of the queue When CPU is free, it is allocated to the process at the head of the queue Average waiting time is quite long 𝑷 𝒙 . . . . . . . . . . . . . . . 𝑷 𝒃 𝑷 𝒂 𝑷 𝒃 Busy Free Tail "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 22

21. First- Come First- Served Scheduling (FCFS) Average Waiting time: 𝒔𝒖𝒎 𝒐𝒇 𝒘𝒂𝒊𝒕𝒊𝒏𝒈 𝒕𝒊𝒎𝒆 𝒐𝒇 𝒂𝒍𝒍 𝒑𝒓𝒐𝒄𝒆𝒔𝒔𝒆𝒔 𝒏𝒐. 𝒐𝒇 𝒑𝒓𝒐𝒄𝒆𝒔𝒔𝒆𝒔 Total Turnaround time: 𝒔𝒖𝒎 𝒐𝒇 𝒕𝒐𝒕𝒂𝒍 𝒆𝒙𝒆𝒄𝒖𝒕𝒊𝒐𝒏 𝒕𝒊𝒎𝒆 + 𝒘𝒂𝒊𝒕𝒊𝒏𝒈 𝒕𝒊𝒎𝒆 𝒓𝒆𝒒𝒖𝒊𝒓𝒆𝒅 𝒇𝒐𝒓 𝒑𝒓𝒐𝒄𝒆𝒔𝒔 Average Turnaround time: 𝒕𝒖𝒓𝒏𝒂𝒓𝒐𝒖𝒏𝒅 𝒕𝒊𝒎𝒆 𝒏𝒐. 𝒐𝒇 𝒑𝒓𝒐𝒄𝒆𝒔𝒔𝒆𝒔 Schedules in order of arrival of processes Algorithm is non-preemptive "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 23

22. Remember … Process Times Burst Time (BT) Arrival Time (AT) Completion Time (CT) Turnaround Time (TT) Avg. Turnaround Time (ATT) Waiting Time (WT) Avg. Waiting Time (AWT) 𝑻𝑻 = 𝑪𝑻 − 𝑨𝑻 𝑨𝑻𝑻 = 𝒊=𝟏 "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 24 σ 𝒏 𝑻𝑻 𝒊 𝒏𝒐. 𝒐𝒇 𝒑𝒓𝒐𝒄𝒆𝒔𝒔𝒆𝒔 𝑾𝑻 = 𝑻𝑻 − 𝑩𝑻 𝑨𝑾𝑻 = 𝒊= σ 𝒏 𝟏 𝑾𝑻 𝒊 𝒏𝒐. 𝒐𝒇 𝒑𝒓𝒐𝒄𝒆𝒔𝒔𝒆𝒔

23. Example 1 "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 25 P1 P2 P3 P4 7 17 40 44 Suppose following set of processes arrived in system at time in given order. Process BT WT TT P1 P2 P3 P4 Average Process BT WT TT P1 7 7 P2 10 7 17 P3 23 17 40 P4 4 40 44 Average 16 27 Process BT P1 7 P2 10 P3 23 P4 4 Gantt Chart

24. Example 2 Process BT AT CT TT WT P1 4 P2 5 1 P3 3 2 P4 5 3 P5 6 4 P1 P2 P3 P4 P5 "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 26 Suppose following set of five processes arriving at different times. Ready queue

25. Example 2 CT TT WT Process BT AT CT TT WT P1 4 4 4 P2 5 1 9 8 3 P3 3 2 12 10 7 P4 5 3 17 14 9 P5 6 4 23 19 13 P1 P2 P3 P4 P5 "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 27 Suppose following set of five processes arriving at different times. Ready queue ATT = 11 AWT = 6.4 P1 P2 P3 P4 P5 4 9 12 17 23

26. First- Come First- Served Scheduling (FCFS) "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 27 Suppose, we have one CPU- bound process and many I/O-bound processes. What will be the situation?? When all I/O-bound processes wait in ready queue, I/O devices are idle When all processes wait in I/O queue, CPU sits idle. Convoy Effect All the other processes wait for one big process to release the CPU

27. Scenario 2 I just want to book a flight ticket I want to place an order for grocery I want to play Counter Strike. My friends are waiting I want to see cartoon "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 28

28. Shortest Job First (SJF) "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 29 Each process is associated with the length of the process's next CPU burst Shortest-next- CPU- burst algorithm CPU is assigned to process that has the smallest next CPU burst . If two processes have same CPU burst, FCFS is used. Algorithm can be either preemptive or non- preemptive The choice arises when a new process arrives at the ready queue while a previous process is still running Preemptive algorithm : Shortest-Remaining- Time- First (SRTF)

29. Example 4 "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 30 Suppose process are arrived in system at different times, Find average turnaround time and average waiting time using SJF scheduling (Non-preemptive). Process AT BT A 8 B 2 5 C 1 9 D 3 2

30. Example 4 Suppose process are arrived in system at different times, Find average turnaround time and average waiting time using SJF scheduling (Non-preemptive). (SRTN) A D B C 8 10 15 24 CT TT WT Process AT BT CT TT WT A 8 8 8 B 2 5 15 13 8 C 1 9 24 23 14 D 3 2 10 7 5 𝟒 𝟓𝟏 𝑨𝒗𝒈. 𝑻𝑻 = = 𝟏𝟐. 𝟕𝟓 𝟐𝟕 𝑨𝒗𝒈. 𝑾𝑻 = = 𝟔. 𝟕𝟓 𝟒 "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 31

31. Example 4 Suppose process are arrived in system at different times, Find average turnaround time and average waiting time using SJF scheduling (preemptive). (SRTF) 9 15 24 CT TT WT Process AT BT CT TT WT A 8 15 15 7 B 2 5 9 7 2 C 1 9 24 23 14 D 3 2 5 2 𝟒 𝟓𝟏 𝑨𝒗𝒈. 𝑻𝑻 = = 𝟏𝟏. 𝟕𝟓 𝟐𝟕 𝑨𝒗𝒈. 𝑾𝑻 = = 𝟓. 𝟕𝟓 𝟒 "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 32 A B D B A C 2 3 5

32. Example 5 "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 33 An operating system uses shortest remaining time first scheduling algorithm for pre- emptive scheduling of processes. Consider the following set of processes with their arrival times and CPU burst times (in milliseconds): Find the average waiting time of processes. Process AT BT P1 12 P2 2 4 P3 3 8 P4 8 4

33. Example 5 An operating system uses shortest remaining time first scheduling algorithm for pre- emptive scheduling of processes. Consider the following set of processes with their arrival times and CPU burst times (in milliseconds): Find the average waiting time of processes. P1 P2 P3 P4 P3 P1 "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 34 2 6 8 12 18 28 CT TT WT Process AT BT CT TT WT P1 12 28 28 16 P2 2 4 6 4 P3 3 8 18 15 7 P4 8 4 12 4 𝑨𝒗𝒈. 𝑾𝑻 = 𝟓. 𝟕𝟓

34. Scenario 3 How to share the bicycle among all four friends? "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 35

35. Round Robin Scheduling Designed especially for time sharing systems. FCFS + Preemption Time quantum or time slice The ready queue is treated as a circular queue The ready queue is treated as a FIFO queue of processes P1 P2 Pn . . . P3 Circular Ready Queue P1 P2 … Pn "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 36 Ready Queue

36. Round Robin Scheduling Working of the Algorithm The scheduler picks the first process from the ready queue Sets a timer to interrupt after 1 time quantum Dispatches the process If 𝑏𝑢𝑟𝑠𝑡 _ 𝑡𝑖𝑚𝑒 < 1 𝑡𝑖𝑚𝑒 𝑞𝑢𝑎𝑛𝑡𝑢𝑚 Currently running process releases the CPU voluntarily Scheduler selects the next process in the ready queue. If 𝑏𝑢𝑟𝑠𝑡 _ 𝑡𝑖𝑚𝑒 > 1 𝑡𝑖𝑚𝑒 𝑞𝑢𝑎𝑛𝑡𝑢𝑚 Timer goes off and causes interrupt to OS and preempts the currently running process On interrupt, context switch will be executed The process will be put at the tail of the ready queue Selects the next process in the ready queue. "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 37

37. Round Robin Scheduling P3=4 P2=1 P1=8 P4=10 CPU P2 6 P3 4 P4 10 Process Burst Time P1 13 Time quantum = 5 ms P4=10 P2=1 P1=8 CPU P4=5 P1=3 CPU P2=1 P1=3 P4=5 CPU P2=6 P1=8 P4=10 P3=4 CPU P1=8 P4=5 P2=1 CPU P1=13 P4=10 P3=4 P2=6 CPU P1=3 CPU "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 38

38. Example Process Burst Time P1 18 P2 3 P3 5 Time quantum = 3 ms P1 P2 P3 P1 P3 P1 P1 P1 P1 3 6 9 12 14 17 20 23 26 Avg. waiting time: (0+6+2)+(3)+(6+3) = 20/3 = 6.67 Total turnaround time: (8+18)+(3+3)+(9+5)= 46 Avg. turnaround time: 46 / 3 = 15.33 "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 39

39. Round Robin Scheduling Average waiting time under the RR policy is often long Algorithm is preemptive The performance depends heavily on the size of the time quantum Approach is called processor sharing The effect of context switching on the performance of RR scheduling The time quantum has to be large with respect to the context switch time, but it should not be too large If the time quantum is too large, RR scheduling degenerates to FCFS policy. Turnaround time also depends on the size of the time quantum. "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 40

40. Example "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 41 Suppose 6 processes are sharing the CPU in FCFS fashion. If the context switch requires 1 unit time, calculate the average turn waiting time. (All times are in milliseconds) Process Name Arrival Time Burst Time A 3 B 1 2 C 2 1 D 3 4 E 4 5 F 5 2

41. Scenario 4 What will Andy do first?? "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 42

42. Priority Scheduling "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 43 A priority is associated with each process Priority is a number assigned to the process CPU is allocated to the process with the highest priority Equal- priority processes are scheduled in FCFS manner What number is to consider as higher priority? Convention: Low numbers represent high priority order Can be either preemptive or non-preemptive

43. Priority Scheduling "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 44 When a newly arrived process has higher priority than the priority of the currently running process then Put the newly arrived process at the head of the ready queue and let the current process continue. (Non- Preemptive) OR Preempt the CPU from currently process, allocate it to the newly arrived process. (Preemptive)

44. Example 6 P2 P5 P1 P3 P4 3 4 12 17 19 Process BT Priority CT WT P1 8 3 12 4 P2 3 1 3 P3 5 4 17 12 P4 2 5 19 17 P5 1 2 4 3 Assume following set of processes are arrived in system. What will be the average waiting time when priority scheduling is applied? 4 + + 12 + 17 + 3 36 Avg. Waiting Time = 5 = 5 = 7.2 "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 45

45. Example 6 Process BT AT Priority CT WT P1 8 3 12 4 P2 3 1 1 4 P3 5 2 4 17 10 P4 2 3 5 19 14 P5 1 4 2 5 Assume following set of processes are arrived in system. What will be the average waiting time when priority scheduling (preemptive approach) is applied? 4 + + 10 + 14 + 28 Avg. Waiting Time = 5 = 5 = 5.6 "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 46 P1 P2 P5 P1 P3 P4 1 4 5 12 17 19

46. Priority Scheduling "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 47 Indefinite blocking or starvation Keeps a low priority processes waiting indefinitely Solution : aging Gradually increasing the priority of processes that wait in the system for a long time

47. Threads "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 48

48. Threads What is thread? A thread is a basic unit of CPU utilization, consisting of a program counter, a stack, and a set of registers, ( and a thread ID.) Processes (heavyweight) have a single thread of control. Also called as lightweight process. Process Threads "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 49

49. Threads Multithreading is an ability of an OS to support multiple, concurrent paths of execution within a single process. One Process One Thread Multiple Processes One Thread per process One Process Multiple Threads Multiple Processes Multiple Thread per process Fig. Single Threaded Approach Fig. Multithreaded Approaches "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 50

50. Threads In single threaded process model, a process includes Its PCB, User address space, User and kernel stack To manage call/return behavior of the execution of the process While the process is running, it controls the processor registers. The contents of these registers are saved when the process is not running Fig. Single Threaded Process Model "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 51

51. Threads In multithreaded process model, there is A single PCB User Address space Separate stack for each thread Separate control block of each thread All threads share the state and resources of that process All threads reside in same address space and have access to all data Fig. Multithreaded Process Model Process "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 52

52. Threads "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 53 Benefits of threads: Takes less time to create a new thread in an existing process than to create a brand new process. Takes less time to terminate than the process. Takes less time to switch between two threads within the same process than to switch between two processes. Enhance efficient in communication between different executing programs.

53. Types of Threads User Level Threads All of the work of thread management is carried out by the application and the kernel is not aware about the existence of the threads. Any application can be programmed to be multithreaded by using thread libraries. By default an application starts with single thread. While application is running, at any time, the application may spawn a new thread to run within the same process. Threads User Level Threads Kernel Level Threads Types of Threads Fig. Pure User Level Thread "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 54

54. Types of Threads "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 55 User Level Threads Advantages Thread switching does not require kernel mode privileges. Scheduling can be application specific. User level threads can run on any operating system. Disadvantages When a user level thread executes a system call, not only is that thread blocked, but also all of the threads within the process are blocked. In pure user level thread strategy, a multithreaded application cannot take advantage of multiprocessing OS.

55. Types of Threads Kernel Level Threads All of the work of thread management is done by the kernel. There is no thread management code in the application level. Kernel saves context information for process as a whole and for individual threads within the process. Scheduling is done by kernel on thread basis. Kernel can schedule multiple threads on multiple processors If one thread is blocked, kernel schedules another thread within the same process. Transferring control from one thread to another thread in same process requires a mode switch to the kernel. Fig. Pure Kernel Level Thread "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 56

56. Types of Threads Combined Approach Thread creation is done completely in user space. Multiple user level threads are mapped onto some (smaller or equal) number of kernel level threads Multiple threads within the same application can run in parallel on multiple processors Blocking system calls need not block the entire process. Fig. Combined Approach "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 57

57. Multi- Threading Models One-to- One Model "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 58 Many- to- One Model Many- to- Many Model

58. T h a nk Y ou… "PROCESS AND PROCESS SCHEDULING" BY Bhargavi Varala 59