cpu sc

PowerPoint Presentation: 

CPU SCHEDULING

NEW DOOR: 

NEW DOOR

ONE WORD: 

ONE WORD

INTRODUCTION: 

INTRODUCTION CPU scheduling is the basis of multiprogrammed OS. By switching the CPU among processes, the OS can make the computer more productive. Almost all computer resources are scheduled before use.

BASIC CONCEPTS : 

BASIC CONCEPTS In single processor system, only one process can run at a time; any others must wait until the CPU is free and can be rescheduled. A process is executed until it must wait, typically for the completion of some I/O request. In a simple computer system, the CPU then just sits idle. All this waiting time is wasted; no useful work is accomplished. In multiprogramming when one process has to wait, the operating system takes the CPU away from that process and gives the CPU to another process. Scheduling is fundamental operating-system function.

CPU SCHEDULER: 

CPU SCHEDULER When ever the CPU becomes idle, the OS must select one of the processes in the ready queue to be executed. The selection process is carried out by the short-term scheduler. However, all the processes in the ready queue are lined up waiting for a chance to run on the CPU.

Preemptive Scheduling: 

Preemptive Scheduling CPU Scheduling decisions may take place under the following four circumstances: When a process switches from the running state to waiting state (as result of an I/O request or an invocation of wait ) When a process switches from the running state to ready state (when an interrupt occurs) When a process switches from the waiting state to ready state (at completion of I/O) When a process terminates 1 and 2 = nonpreemptive or cooperative; Else preemptive. Non preemptive: Once the CPU has been allocated to a process, the process keeps the CPU until it releases the CPU either by termination or by switching to the waiting state. Used in Microsoft windows 3.x;windows 95,Mac OS Preemptive: It incurs a cost associated with access to shared data. It also affects the design of the OS kernel.

OS: 

OS Microsoft windows Apple Macintosh Sown in discomfort Machines apt to help

DISPATCHER: 

DISPATCHER The dispatcher is the module that gives control of the CPU to the process selected by the short-term scheduler. This function involves the following: Switching context Switching to user mode Jumping to the proper location in the user program to restart that program The dispatcher should be as fast as possible, since it is invoked during every process switch.

Scheduling Criteria: 

Scheduling Criteria Different CPU scheduling algorithms have different properties which are used for choosing algorithm in particular situation. Criteria include the following: CPU utilization: We want to keep the CPU as busy as possible. It range from 0 to 100 percent. Throughput: One measure of work is the no. of processes that are completed per time unit, called throughput. Turnaround time: The interval from the time of submission of a process to the time of completion

PowerPoint Presentation: 

. . Waiting time: It is the sum of the periods spent waiting in the ready queue. Response time: It is the time takes to start responding, not the time it takes to output the response It is desirable to maximize CPU utilization and throughput Minimize turnaround time, waiting time and response time. Optimize the average measure

SCHEDULING ALGORITHMS: 

SCHEDULING ALGORITHMS CPU scheduling deals with the problem of deciding which of the processes in the ready queue is to be allocated the CPU Different CPU scheduling algorithms are: First-come,First-Served Scheduling Shortest-Job-First Scheduling Priority Scheduling Round-Robin Scheduling Multilevel Queue Scheduling Multilevel Feedback-Queue Scheduling

FCFS With this scheme, the process that requests the CPU first is allocated the CPU first: 

FCFS With this scheme, the process that requests the CPU first is allocated the CPU first Process Burst Time P1 24 P2 3 P3 3 If the processes arrive in the order P1,P2,P3 and are served in FCFS order GANTT CHART 0 24 27 30 The average waiting time is (0+24+27)/3=17 milliseconds If the processes arrive in p2,p3,p1 order GANTT CHART 0 3 6 30 P1 P2 P3 P2 P3 P1

SJFC : 

SJFC Process Burst Time P1 6 P2 8 P3 7 P4 3 Using SJF GANTT CHART 0 3 9 16 24 The average time (0+3+16+9)/4=7 milliseconds SFJS is used frequently in long term scheduling. Exponential average Ŧn+1= α tn+(1- α )Ŧ n This algorithm associates with each process the length of the process’s next CPU burst. When the CPU is available, it is assigned to the process that has the smallest next CPU burst. If the next CPU bursts of two processes are the same, FCFS scheduling is used to break the tie P4 P1 P3 P2

PRIORITY SCHEDULING: 

PRIORITY SCHEDULING When a process arrives at the ready queue, its priority is compared with the priority of the currently running process. A preemptive priority scheduling algorithm will preempt the CPU if the priority of the newly arrived process is higher than the priority of the currently running process. A non-preemptive priority scheduling algorithm will simply put the new process at the head of the ready queue. A major problem with PSA is indefinite blocking or starvation. A solution to problem is aging AGING is technique of gradually increasing the priority of processes that wait in the system for a long time.

GANTT CHART 1 6 16 18 19 : 

GANTT CHART 1 6 16 18 19 Process Burst Time Priority P1 10 3 P2 1 1 P3 2 4 P4 1 5 P5 5 2 P2 P5 P1 P3 P4

Round Robin Scheduling: 

Round Robin Scheduling RRS is designed especially for time-sharing systems. Preemption is added to switch between processes. Time quantum -a small unit of time,10 to 100 milliseconds. Ready queue is treated as circular queue The CPU scheduler goes around the ready queue, allocating the CPU to each process for a time interval of up to 1 time quantum.

The way in which a smaller time quantum increases context switches: 

The way in which a smaller time quantum increases context switches Process Burst Time P1 24 P2 3 P3 3 0 4 7 10 14 18 22 26 30 Each process must wait no longer than (n-1)*q time units until its next time quantum. 0 10 0 6 10 0 1 2 3 4 5 6 7 8 9 10 P1 P2 P3 P1 P1 P1 P1 P1

Multilevel queue scheduling: 

Multilevel queue scheduling A multilevel queue scheduling algorithm partitions the ready queue into several separate queues. The processes are permanently assigned to one queue. The foreground queue might be scheduled by an RR algorithm, while the backgroun queue is scheduled by an FCFS algorithm. System processes Interactive processes Student processes Batch processes Interactive editing processes

Multilevel Feedback-Queue Scheduling In contrast,allows a process to move between queues. The scheduler first executes all processes in queue 0. A process in queue 1 will in turn be preempted by a process arriving for queue 0. : 

Multilevel Feedback-Queue Scheduling In contrast,allows a process to move between queues. The scheduler first executes all processes in queue 0. A process in queue 1 will in turn be preempted by a process arriving for queue 0. In general, it is defined by following parameters: The number of queues The method used to determine when to upgrade a process to a higher priority queue The method used to determine when to demote a process to lower priority queue The method used to determine which queue a process will enter when that process needs service Quantum=8 Quantum=16 FCFS

Approaches to Multiple-Processor Scheduling Asymmetric multiprocessing is simple only one processor accesses the system data structures, reducing the need for data sharing. Symmetric multiprocessing(SMP) where each processor is self-scheduling. : 

Approaches to Multiple-Processor Scheduling Asymmetric multiprocessing is simple only one processor accesses the system data structures, reducing the need for data sharing. Symmetric multiprocessing(SMP) where each processor is self-scheduling. CPU scheduling is the task of selecting a waiting process from the ready queue and allocating the CPU to it.

PowerPoint Presentation: 

SHAIK RIZWANA is here to Welcome questions