LM10,11,12 - CPU SCHEDULING algorithms and its processes

LM10,11,12 - CPU SCHEDULING algorithms and its processes

1. CS8493 – Operating Systems UNIT II – PROCESS MANAGEMENT KGiSL INSTITUTE OF TECHNOLOGY

2. Session Agenda Process Concepts Process Operations, Scheduling, IPC CPU Scheduling – Criteria & Algorithms (3 hours) Multiple Processor & Real-Time Scheduling Threads – Overview, Models & Issues Process Synchronization – CS problem, hardware, mutex locks, semaphores, CR, monitors Deadlock – Model, Characteristics, handling methods Deadlock, prevention & avoidance Deadlock detection & recovery

3. Recap Operations on Process – Creation & Termination Process Queue – Ready Queue, Waiting Queue, Job Queue Process Schedulers – Long Term, Short Term, Medium Term IPC – Inter Process Communication – Shared Memory & Message Passing

4. CPU Scheduling – Basic Concepts Almost all programs have some alternating cycle of CPU number crunching and waiting for I/O of some kind. In a simple system running a single process, the time spent waiting for I/O is wasted, and those CPU cycles are lost forever. A scheduling system allows one process to use the CPU while another is waiting for I/O, thereby making full use of otherwise lost CPU cycles. The challenge is to make the overall system as "efficient" and "fair" as possible, subject to varying and often dynamic conditions, and where "efficient" and "fair" are somewhat subjective terms, often subject to shifting priority policies.

5. CPU-I/O Burst Cycle Almost all processes alternate between two states in a continuing  cycle A CPU burst of performing calculations An I/O burst, waiting for data transfer in or out of the system.

6. CPU Scheduler Whenever the CPU becomes idle, it is the job of the CPU Scheduler to select another process from the ready queue to run next. Pre-emptive Scheduling Preemptive Scheduling is a CPU scheduling technique that works by dividing time slots of CPU to a given process. The time slot given might be able to complete the whole process or might not be able to it. Non-Pre-emptive Scheduling Non-preemptive Scheduling is a CPU scheduling technique the process takes the resource (CPU time) and holds it till the process gets terminated or is pushed to the waiting state.

7. Dispatcher The  dispatcher  is the module that gives control of the CPU to the process selected by the scheduler. The function involves: Switching context. Switching to user mode. Jumping to the proper location in the newly loaded program. The dispatcher needs to be as fast as possible, as it is run on every context switch. The time consumed by the dispatcher is known as dispatch latency.

8. CPU Scheduling Algorithms CPU Scheduling is a process of determining which process will own CPU for execution while another process is on hold. The main task of CPU scheduling is to make sure that whenever the CPU remains idle, the OS at least select one of the processes available in the ready queue for execution. The selection process will be carried out by the CPU scheduler. It selects one of the processes in memory that are ready for execution.

9. CPU Scheduling Algorithms - Circumstances CPU scheduling decisions may take place under the following four circumstances: When a process switches from the running state to the waiting state(for I/O request or invocation of wait for the termination of one of the child processes). When a process switches from the running state to the ready state (for example, when an interrupt occurs). When a process switches from the waiting state to the ready state(for example, completion of I/O). When a process terminates.

10. CPU Scheduling Algorithms - Criteria CPU Utilization Throughput Turnaround Time Waiting Time Load Average Response Time

11. CPU Scheduling Algorithms - Types FCFS SJF Priority Round Robin

12. FCFS It is like QUEUE Data structure which follows First In First Out process. It is non-preemptive type of scheduling algorithm ADVANTAGES Simple Easy Jobs are always executed on a first-come, first-serve basis DISADVANTAGES W ait time is quite high T he problem of starvation may occur.

13. FCFS Convoy Effect is a situation where many processes, who need to use a resource for short time are blocked by one process holding that resource for a long time. If the CPU gets the processes of the higher burst time at the front end of the ready queue then the processes of lower burst time may get blocked which means they may never get the CPU if the job in the execution has a very high burst time. This is called convoy effect or starvation.

14. SJF In SJF scheduling, the process with the lowest burst time, among the list of available processes in the ready queue, is going to be scheduled next. It is used in batch systems It is of 2 types: Preemptive Non-preemptive

15. SJF

16. Priority Priority scheduling is a method of scheduling processes based on priority. In this method, the scheduler selects the tasks to work as per the priority. Priority scheduling also helps OS to involve priority assignments. The processes with higher priority should be carried out first, whereas jobs with equal priorities are carried out on a round-robin or FCFS basis. Priority can be decided based on memory requirements, time requirements, etc.

17. Priority The priority of process, when internally defined, can be decided based on memory requirements, time limits ,number of open files, ratio of I/O burst to CPU burst etc. Whereas, external priorities are set based on criteria outside the operating system, like the importance of the process, funds paid for the computer resource use, makrte factor etc.

18. Priority Preemptive Priority Scheduling: If the new process arrived at the ready queue has a higher priority than the currently running process, the CPU is preempted, which means the processing of the current process is stopped and the incoming new process with higher priority gets the CPU for its execution.

19. Priority Non-Preemptive Priority Scheduling: In case of non-preemptive priority scheduling algorithm if a new process arrives with a higher priority than the current running process, the incoming process is put at the head of the ready queue, which means after the execution of the current process it will be processed.

20. Priority The priority number assigned to each of the process may or may not vary. If the priority number doesn't change itself throughout the process, it is called static priority , while if it keeps changing itself at the regular intervals, it is called dynamic priority. In priority scheduling algorithm, the chances of indefinite blocking or starvation.

21. Round Robin The name of this algorithm comes from the round-robin principle, where each person gets an equal share of something in turn. It is mostly used for scheduling algorithms in multitasking. This algorithm method helps for starvation free execution of processes. Round Robin(RR) scheduling algorithm is mainly designed for time-sharing systems. It is by default preemptive scheduling

22. Round Robin A fixed time is allotted to each process, called a quantum, for execution. Once a process is executed for the given time period that process is preempted and another process executes for the given time period. It is important to note here that the length of time quantum is generally from 10 to 100 milliseconds in length. This Algorithm is a real-time algorithm because it responds to the event within a specific time limit.

23. Round Robin This is a hybrid model and is clock-driven in nature. In this algorithm, the time slice should be the minimum that is assigned to a specific task that needs to be processed. Though it may vary for different operating systems.

24. Round Robin Advantages While performing this scheduling algorithm, a particular time quantum is allocated to different jobs. With the help of this algorithm, all the jobs get a fair allocation of CPU. This algorithm deals with all processes without any priority. This algorithm is cyclic in nature. In this scheduling algorithm, each process gets a chance to reschedule after a particular quantum time.

25. Round Robin Disadvantages This algorithm spends more time on context switches. For small quantum, it is time-consuming scheduling. This algorithm offers a larger waiting time and response time. In this, there is low throughput. If time quantum is less for scheduling then its Gantt chart seems to be too big.

26. Summary Introduction to CPU Scheduling I/O Burst Cycle Schedulers Dispatcher Scheduling Circumstances Scheduling Criteria Scheduling Types, Advantages, Disadvantages

27. THANK YOU