CPU scheduling

CPU scheduling is the basis of multi-programming operating system. With the switch the CPU among processes. As a result, the operating system can make computers productive. In this chapter we will introduce the basic concepts of scheduling and some scheduling algorithm. And we also presented a problem in choosing an algorithm in a system.Basic ConceptsThe purpose of the multi-programming is to have processes running simultaneously, to maximize the performance of the CPU. For uniprosesor system, there never was a process running more than one. If there is a process that is more than one then the others have to wait until the cpu is free.The idea of ​​multi porgamming very simple. When an executable process that others must wait until the finish. In a simple computer system CPU will be much in the position very terbunag idle.Semua this time. With multiprogamming we try to use the time productively. Some processes are stored in memory at one time. When the process must menuggu. Mengmbil operating system cpu to process the process and leave the process of being executed.scheduling is the basic function of a system opersai. Almost all computer resources are scheduled before use. CPU is one of the sources of the essential computer that became central to central scheduling at the operating system.Burst Cycle CPU-I / OThe success of CPU scheduling depends on several properties processors. Contains a cycle of CPU execution process execution and I / o Wait. The process will only back and forth from these two states. Poses execution begins with the CPU Burst, after that dikikuti by I / O burst, and conducted in turns.The duration of this bust CPU ditelah measured extensively, although they are very different from the process into prose. They have frekeunsi same curve as shown below.
 CPU schedulingWhenever the CPU becomes idle, the system opersai must select one process to enter the ready queue (ready) to executed. The selection is done by short-term scheduler. Scheduling choose from all these processes in memory that are ready to be executed, den allocates the CPU to executeCPU scheduling may be executed when the process:1. Changed from running to waiting state2. Changed from running to ready state3. Changed from waiting to ready4. TerminatesScheduling from No. 1 to 4 while the other non-preemptive preemptive. In nonpreemptive scheduling once the cpu has been allocated to a process, it can not be disturbed, such as scheduling model is used by Windows 3.x; windows 95 have used preemptive scheduling.DispatcherOther components involved in the scheduling of the CPU adalan dispatcher. Dispatcher is the module that gives control of the CPU to process the function is:1. Switching context2. Switching to user mode3. Jumping from one section in porgam user to repeat the program.Dispatchers should be as fast as possible,Criteria SchedulingDifferent CPU scheduling algorithms have different properties. In selecting the algorithm used for certain situations, we must think about the different properties for different algorithms. Many of the recommended criteria separately comparing CPU scheduling algorithms. Kritria you select a commonly used in are:1. CPU utilization: we want to keep the CPU as busy as possible. CPU utilization will have a range from 0 to 100 percent. In the actual system he should have served until the range from 40 percent 90 percent2. Throughput: if the cpu is busy executing the process, if such work has been carried out. One measure of work is a lot of processes completed per unit time, called throughput. For a long process that may be one process per hour; for the moment processes may be 10 processes per second.3. Turnaround time: sudur view of a particular process, an important criterion is how long to execute that process. The interval of time allowed by the time needed to complete a prose called turn around time. Trun around time is the number of periods to wait to get into memory, waiting in the ready queue, execution on the CPU, and perform I / O4. Waiting time: cpu scheduling algorithm does not affect the time to carry out the process or I / O; it only affects the amount of time required in the process ready queue. Waiting time is the number of periods spent in the ready queue.5. Response time: in an interactive system, turnaround time may not be the best time to criterion. Often a process can produce output at the beginning, and could continue while the new results that have previously been granted to the user. Another measure is the time of pengiriamn request until the first response given. This is called response time, ie time to begin to respond, but not time spent untu output response.Usually done is to maximize CPU utilization and throughput, and minimize turnaround time, waiting time, and response time in certain cases we take the average.Scheduling AlgorithmCPU scheduling deals with problems of deciding which one to dillaksanakan process, therefore a lot of different scheduling algorithms, in this section we will describe some algorithms.First Come, First ServedThis is the simplest algorithm, with a scheme that asks cpu process priority. Implementation of FCFS easily dealt with FIFO queue.eg the arrival sequence is P1, p2, p3 Gantt Chart for this are:ie the process is reversed so that the order of arrival is p3, p2, p1Of the two examples above that the second case is better than the first case, because the effect of the arrival besides that FCFS has a drawback that is convoy effect if there is a process where a small, but he lined up with a process that requires a long lead time will be a long process executedFCFS scheduling algorithm is nonpremptive. When the CPU has been allocated to a process, the process on hold until selssai cpu. FCFS algorithm is clearly a problem for time-sharing system, which is very important for users to share cpu at regular intervals. That would be disastrous for megizinkan one process on cpu for an unlimited timeShortest Job First SchedulingOne of the other algorithms are Shortest Job First. This algorithm is related to the time of each process. When the CPU is free process that has the shortest time to complete a priority. If two or more processes have the same time then the FCFS algorithm is used to solve the problem.
 There are two schemes in this SJFS namely:1. nonpremptive - when the CPU gives the process can not be postponed until the completion2. preemptive - if a process comes with a lower procedural time compared to the time the process is being executed ooleh CPU time the process is a lower priority. This scheme is also called Short-Remaining Time First (SRTF)SJF algorithm is probably the most optimal, because it gives the average minimum set of processes waiting for the queue. With the shortest time to execute the new longest. As a result the average time mnenuggu decreased.It is difficult to SJF algorithm is mengethaui Waku of the next process. For long term scheduling (old) in a batch system, we can use the long time limit a user process mentioned when he sent the job. Therefore SJF scheduling is often used in long term.Although the optimal SJF but he can not be used for short term CPU scheduling. There is no way to know the length of next CPU burst. One way to implement it is to predict the next CPU burst.
 Scheduling priorityPendawalan SJF (Shorthest Job First) is a special case for priority scheduling algorithm. Priorities can be associated each of these processes and the CPU is allocated to the process with highest priority. For the same priorities done with FCFS.The algorithm penjadwalam priorities are as follows:• Each process will have a priority (integer). Some systems use a sequence of integers with small for low-priority process, and other systems could also use a small integer sequences for high-priority process. But in this text it is assumed that a small integer is a top priority.• CPU is allocated to the process with highest priority (integer small is the highest priority).• In this algorithm there are two schemes namely:1. Preemptive: the process can be interrupted if there is a higher priority that requires the CPU.2. Nonpreemptive: a high priority process will replace the current usage of time-slice runs out.• SJF is an example of priority scheduling where priority is determined by the next time the CPU usage.The problems that arise in penjadwlan priority is indefinite blocking or starvation• Sometimes the case with lace priority may never be executedSolutions for priority scheduling algorithm is aging• Priority will go up if the process of growing old waiting for CPU time allocation.Round Robin SchedulingAlgorithm Round Robin (RR) is designed for time-sharing system. This algorithm is similar to FCFS scheduling, but preemption is added to switch between processes. Ready queue is treated or regarded as a circular queue. Menglilingi CPU ready queue and allocates each process for specified time intervals up to one time slice / quantum.Here algritma to Round Robin scheduling:• Each process gets a small CPU time (time slice / quantum) Time particular slice / quantum ntara usually 10-100 milliseconds.1. After the time slice / quantum, the process is in-preempt and transferred to the ready queue.2. This process is fair and is very simple.• If there are n processes in the "ready queue" and the time quantum q (milliseconds), then:1. Then each process gets 1 / n of the CPU time.2. No process waits more than (n-1) q time units.• Performance of this algorithm depends on the size of time quantum1. Time Quantum with a large size it will be the same as the FCFS2. Time Quantum with the small size of the time quantum should be resized larger with respect to context switch would otherwise require large expenses.






51
 CPU scheduling
Highlights:􀀹 Basic Concepts􀀹 Criteria Scheduling􀀹 Scheduling Algorithm
LEARNING OBJECTIVES:After studying the material in this chapter, students should be able to:􀀹 Understand the basic concepts of CPU scheduling􀀹 Understand the criteria necessary for the CPU scheduling􀀹 Understanding some CPU scheduling algorithm that consists of algorithmsFirst Come First Serve, Shortest Job First, Priority and Round Robin
4.1 BASIC CONCEPTSIn multiprogramming systems, always will be some process runningat a time. While on uniprogramming this will not happen, becausethere is only one process running at any given moment. Multiprogramming systemrequired to maximize the utility of the CPU.At the time the process is run and the CPU execution cycles waiting for I / Ocalled a cycle of CPU-I / O burst. The execution process begins with CPU burst andfollowed by I / O burst, followed by another CPU burst, then I / O burst another andso as in Figure 4-1.
53 CHAPTER 4 CPU SCHEDULINGWhen a process is executed, there are many short CPU burst andthere are few long CPU burst. Programs that are I / O bound is usually veryits short CPU burst, while the program is CPU bound CPU burst possibilityhis old partner. This can be illustrated with graphs of exponential orhyper exponential as in Figure 4-2. It is therefore very important electionCPU scheduling algorithms.
4.1.1 CPU SchedulerThe CPU time idle, the operating system must select prosesprosesin main memory (ready queue) for execution and allocatingCPU for one of the process. Such selection is called the shorttermscheduler (CPU scheduler). The decision to schedule the CPU follow the Empathe following circumstances:1. If the process of switching from running to waiting state;2. If the process of switching from running to ready state;3. If the process of moving from waiting to ready state;4. If the process stops.If the scheduling of the selected model using the state 1 and 4, thenpenjadwakan are called non-peemptive. Conversely, if usedis a state of 2 and 3, it is called with preemption.In non-preemptive, if a process is using the CPU, then the processwill still bring the CPU to process the release (stoppingor in a state of waiting). Preemptive scheduling has the disadvantage, namely the costrequired is very high. Among other things, the data should always be improvements. caseThis occurs if a process was abandoned and will soon do another process.
4.1.2 DispatcherDispatcher is a module that will give control of the CPUof the selection process undertaken during the short-term scheduling. Functions ofcontained in it include:1. Context switching;2. Switching to user-mode;

 SCHEDULING CPU 543. Jump to a specific location on the user program to start the program.The time required by the dispatcher to stop one process andbegin to run another process called the dispatch latency.
CRITERIA SCHEDULINGDifferent CPU scheduling algorithms will have different properties.So to choose this algorithm should be considered first propertiesthe algorithm. There are several criteria used to performcomparing CPU scheduling algorithms, among others:1. CPU utilization. It is hoped that the CPU is always in a state of busy. Utility CPUexpressed in terms of 0-100% per cent. But in reality onlyranged between 40-90%.2. Throughput. Is the number of processes completed in a single unittime.3. Turnaround time. The amount of time needed to execute the process,from the start waiting to ask a place in main memory, waiting in the readyqueue, execution by the CPU, and do I / O.4. Waiting time. The time required by a process to wait in the readythe queue. Waiting time does not affect the execution process and the use of I / O.5. Response time. The time needed by a process of asking to be servedThe first response is to respond to these requests.6. Fairness. Ensure that each process will get a time divisionopenly CPU usage (fair).

 SCHEDULING ALGORITHMCPU scheduling involves determining the processes that exist in the readyqueue to be allocated on the CPU. There are several scheduling algorithmsCPU as described in the section below.
SCHEDULING CPU

First-Come First-Served Scheduling (FCFS)The process was first asked to use the allotted time the CPU willserved first. In this scheme, the process of asking the CPU will firstallocated to the CPU first.For example there are three processes that can be in the order P1, P2, and P3 withCPU-burst time in milliseconds is given as follows:Process Burst TimeP1 24P2 3P3 3Gant Chart with FCFS scheduling is as follows:The waiting time is 0 for P1, P2 and P3 is 24 is 27 so that the averagewaiting time is (0 + 24 + 27) / 3 = 17 milliseconds. Whereas if the process comesin the order P2, P3, and P1, the CPU scheduling can be seen on the Gantt chartthe following:The waiting time is 6 now to P1, P2 and P3 is 0 is 3 so that the averagewaiting time is (6 + 0 + 3) / 3 = 3 milliseconds. Average waiting time of this casemuch better than the previous case. In the CPU schedulingmade possible when the Convoy effect short process that is in the processthat long.The algorithm includes a non-preemptive FCFS. because, once the CPU is allocatedon a process, then the process will still be using the CPU to processThe release, ie if the process is stopped or asked for I / O.P1 P2 P30 24 27 30P1 P2 P30 3 6 30


 SCHEDULING CPU
  Scheduler Shortest Job First (SJF)At SJF scheduling, a process that has served the smallest CPU burstfirst. There are two schemes:1. Non-preemptive, when the CPU is given to the process, it can not be postponeduntil the CPU burst is complete.2. Preemptive, if the new process comes with CPU burst length shorterof the remaining processing time while it is being executed, the process is delayed andreplaced with a new process. This scheme is called the Shortest-Remaining-Time-First (SRTF).SJF is optimal scheduling algorithm with the average waiting timeare minimal. For example there are four processes by CPU burst length inmilliseconds.Process Arrival Time Burst TimeP1 0.0 7P2 2.0 4P3 4.0 1P4 5.0 4Processes with the SJF scheduling algorithm (non-preemptive) can be seen on the Gantthe following chart:The waiting time for P1 is 0, P2 is 26, P3 and P4 is 3 is 7, soAverage waiting time is (0 + 6 + 3 + 7) / 4 = 4 milliseconds. While Schedulingprocess with SRTF algorithm (preemptive) can be seen on the Gantt chart below:The waiting time is 9 to P1, P2 is 1, P3 and P4 is 0 is 4, soAverage waiting time is (9 + 1 + 0 + 4) / 4 = 3 milliseconds.P1 P2 P30 3 7 16P48 12P1 P2 P30 2 4 11P45 7P1 P216
  SCHEDULING CPUAlthough this algorithm is optimal, but in reality it is difficult toimplemented because it is difficult to know the length of next CPU burst.However, this value can be predicted. The next CPU burst is usually predictable asan exponential rate determined from previous CPU burst or"Exponential Average".τ α α τ n n t (1) 1 0 = + - + (4.1)with:τ n +1 = length of the expected CPU burstτ 0 = length of previous CPU burstτ n = length of CPU burst of the n (in progress)α = the size of the comparison between τ n +1 with τ n (0 to 1)Graph the results predicted CPU burst can be seen in Figure 4-3.For example, if α = 0.5, and:




 SCHEDULING CPUCPU burst (τ n) = 6 4 6 4 13 13 13. . .τ n = 10 8 6 6 5 9 11 12. . .At first τ 0 = 6 and τ n = 10, so that:τ 2 = 0.5 * 6 + (1 - 0.5) * 10 = 8Values ​​that can be used to find τ 3τ 3 = 0.5 * 4 + (1 - 0.5) * 8 = 6

 Priority SchedulingSJF algorithm is a special case of priority scheduling. Tiaptiapprocess is equipped with a priority number (integer). CPU is allocated to processwhich has the highest priority (smallest integer value is usually the prioritythe largest). If multiple processes have the same priority, it will be usedFCFS algorithm. Priority scheduling scheme that consists of two non-preemptiveand preemptive. If there is a process that comes at P1 P0 is running, thenP1 will be the priority. If priority P1 is greater than the priorityP0, then the non-preemptive, fixed algorithm will solve P0 until they run outIts CPU burst, and put the head position P1 in the queue. While inpreemptive, P0 will be stopped first, and replace the CPU allocated to P1.For example there are five processes P1, P2, P3, P4 and P5 that comes forsequentially with CPU burst in milliseconds.Process Burst Time PriorityP1 10 3P2 1 1P3 2 3P4 1 4P5 5 2Process with priority scheduling algorithm can be seen on the Gantt chart below:
  SCHEDULING CPUThe waiting time is 6 to P1, P2 is 0, P3 is 16, P4 and P5 is 18 is1 so that the average waiting time is (6 + 0 +16 + 18 + 1) / 5 = 8.2 milliseconds.

 Round-Robin SchedulingThe basic concept of this algorithm is to use time-sharing. OnThis algorithm is essentially the same as FCFS, only to be preemptive. EachCPU time the process of getting called with a time quantum (quantum time)to limit the processing time, typically 100-100 milliseconds. After a timeout, the processdelayed and added to the ready queue.If a process's CPU burst is smaller than the timequantum, then the process will release the CPU if it has finished its work,so the CPU can be immediately used by the next process. Conversely, if aprocess has the CPU burst greater than the time quantum,then the process will be suspended if it reaches the time quantum,and then queue up again at the position of the tail of the ready queue, the CPU thenrun the next process.If there are n processes in ready queue and the time quantum is q, then everyprocess gets 1 / n of the CPU time at most q time units at onceCPU scheduling. No process waits more than (n-1) q time units.Round robin algorithm performance can be explained as follows, if q is large, thenalgorithm used is FIFO, but if q is small, the frequent contextthe switch.Suppose there are three processes: P1, P2, and P3 which require the CPU to service-time quantum of 4 milliseconds.Process Burst TimeP1 24P2 3P3 3Scheduling processes with round robin algorithm can be seen on the Gantt chart below:P1 P2 P50 1 6 16P318 19P4
  SCHEDULING CPUP1 P2 P3 P1 P1 P1 P1 P10 4 7 10 14 18 22 26 30The waiting time is 6 to P1, P2 is 4, and P3 is 7 so that the average timewait is (6 + 4 + 7) / 3 = 5.66 milliseconds.Round-Robin algorithm is on one hand has the advantage, namely the existenceuniformity of time. But on the other hand, this algorithm will too often doswitching as shown in Figure 4-4. The greater the quantum-timenyaswitching that occurs will be less.Turnaround time also depends on the size of time quantum. As inFigure 4-5, the average turnaround time was not increased when the time quantum is increased.In general, the average turnaround time can be increased if multiple processescompleting the next CPU burst as a time quantum. As an example,There are three processes each 10 units of time and the time quantum of 1 unit of time,Average turnaround time is 29. If the time quantum 10, on the contrary, the averageturnaround time dropped to 20.Figure 4-4: Shows the smaller time quantum increasescontext switch