Homework answers / question archive / 1) Read about processor scheduling on pages 117-130

1) Read about processor scheduling on pages 117-130

Computer Science

Share With

1) Read about processor scheduling on pages 117-130. Select two scheduling algorithms and identify two real-world scheduling tasks, not currently involving computers, which the algorithms could be applied to. Discuss why the algorithms are appropriate for these scheduling tasks.

2. Regarding the role played by the victim in deadlock resolution, give an example of such a deadlock in real life and explain your answers to the following:

1. Describe how you might choose the victim to be removed, and the consequences, both positive and negative, of that removal.
2. Describe the fate of the victim and the chances of eventually completing its processing

controller and is discussed lacer), this extensive use of rhe CPU will build up the READY queue while emptying out the 1/0 queues, creating an imbalance in the system, which is often perceived as unacceptable. To solve this problem, the Process Scheduler uses a timing mechanism and periodically incerrupts running processes when a predetermined slice of time has expired. When this happens, the scheduler suspends all activity on the job currently running and reschedules it into the READY queue; it will be continued later. 'T'he CPU is now allocated to another job that runs until one of three chings happen: The timer goes off, the job issues an UO command, or the job is finished. Then the job moves 10 che READY queue, the WAIT queue, or the 1-lNISHED queue, respccrivdy. An UO requesr is called a natural wait in multiprogramming environments. It allows the processor co be allocated to another job until che UO request is complered. for example, if the 1/0 request is to print out the fourth chapter of a book, it could take several minutes for this request to be satisfied-rime that allows other waiting processes access to the CPU A scheduling strategy chat interrupts the processing of a job and transfers the CPU co anurhei· job U callc.:d a pceemptivc scheduling policy. The alreroacivc, uf cuun,-e, i~ a non• preemptive scheduling policy, which fum.-tions without external interrupts (intenupts exremal to the job). Therefore, once a job captures the processor and begins execution, it remains in the RUNNING state uninterrupted until ir issues an 1/0 request (natural wait) or until it is finished. In the ca.se of an infin ite loop, the proccs.s can he stopped and moved to the FINISH ED queue whether the policy is preemptive or nonpreemptive. ScheduUng Algorithms The Process Scheduler relies on a scheduling algorithm, based on a specific scheduling policy, in order to allocate the CPU in the best way for moving jobs through the sy~1:em efficiently. Most systems place an emphasis on fast user-response time. w., refer to these algorithms as process scheduling algorithms, though they an, also used t0 schedule threads. Here are several algorithms that have been used extensively for scheduling both processes and threads. First-Come, First-Served First-come, firsr.served (FCFS) is a nonpreemptive scheduling algorithm char handles all incoming objeas according co their arrival time: The earlier they arrive, the sooner they're served. Ir's a very simple algorithm co implement because ir uses a First In, First Our (FIFO) queue. Th.is algorithm is commonly used for batch syStcms, but it is unacceptable for many interactive systems because interactive users expea qujck response times. Copyrighl 2011 Cf.rig~ LH ng •""" ft N ft"" be co ru an, o ph WM o pa,t N 2·2\ .z,. 4- 117 With FCFS, as a new job enters the system, its PCB is linked to the end of the READY queue, and it is removed from the front of the READY queue after the job no longer needs the processor. The small amount In a strictly FCFS system, there are no W Arr queues because each job is run to its completion, although there may be systems in which conrrol (context) is switched on a natural wait (1/0 request), with the job resuming upon 1/0 completion. Assuming there's no multiprogramming, turnaround time-the time required to execute a job and return the output to the user- is unpredictable with the strict FCFS policy. For e,c•mple, cnnroccss Scheduler manages multiple READY queues instead of just one. Details about multiple queues arc presen ted later in this c hapter. Priorities can also be determined by the Processor Manager based on characteristics intrinsic ro rhc jobs \uch as: • i\1cmory requirements. Jobs req uiring large amounts of memory could be alloc.11ed lower priorities than those requesting small amounts of memory, or vice versa. • N 11111ber and type of peripheral devices. Jobs requiring many peripheral devices could be allocated lower p rionties than those rcquesung fewer devices. • Total CPU 111110. Jobs havi ng a long CPU cycle, or estimated run time, could be given lower priorities than those having a brief estimated run time. • Amount of time already spent in the sys/J!m. This is the rotal amount of elapsed time since the job was accepted for processing. Some systems increase the priority of jobs that have been in the system for an unusually long time to expedite their exit. This is known as aging. In a batch environment, these criteria are used to determine default prionties for many systems, although the default priorities can be overruled by users. Shortest Remaining n me Shortest remaining time (SRT) is a preemptive version of the SJN a lgorithm. The processor is allocated to the job closest to completion-bur even this job can be interrupted if a newer job in the READY queue has a remaining time to completion that's shorter. When using SRT, if several jobs have the same amount of t ime remaining, the job that has been waiting the longest goes next. In other words, it can use the FCFS algorithm to b reak the tie. This algorithm cannot be implemented in an interactive system because it requires advance k nowledge of the CPU cime required co finish each job, bur it can work well in b atch environments, because it can give preference to short jobs. One disadvantage Cc,pfdght 201 .. ... " •• W 2- 121 is that SRT involves more overhead tha n SJN-it requires the operating system to frequently monitor the CPU time for every job in the READY queue; and it must perform context switching for the jobs being swapped at preemption time (not necessarily swapped O lli 10 the disk, although this might occur as well). The example shown in Figu re 4.10 illustrates how the SRT algorirhm works with four jobs arriving Ill quick succession (only one CPU cycle apart). Arrival time: 0 1 2 Job: A B C CPU cycle: 6 3 3 D 4 For each job, the rumaround time is its completion time mi.n us its arrival time. Job: Completion Time: A 14 5 3 9 Minus Arrival Time: ~ -1 T urnarou nd: 14 4 -2 1 -3 6 C 8 D Therefore, the average turnaround time (6.25) is calculated as follows: (14 - 0)+(5 - I )+(3 - 2)+(9- 3) 4 6.25 ~"' Job A Is p,ttmpted by Job 8 beuuse Job 8 has !Ms CPU time n,m•lning. (fisure 4.10) ~"' Job 8 Is prMtnpted by Job C beaus, Job C has IMs CPU time remaining. Ti-lint for job uquence A. 8, C. and O using lht Now Job 8 an resume btuuse Job C~ finished. prHmplivt SRT olgorlrhm. Job Druns nect because it nttds IMs C.PU time to finish th•n does Job A. / ___ Hire Job A Is finolly •llo~ to finish. ,~ ~ ~ 0 1 2 ,~J:b ,~b ,~ 3 s 9 anotherJob Is walling wfth 7 / l~~b Eoch job Is interrupted a{ttr one CPU cych if less CPU ti- remaining. 14 Ho w docs this compare to the same problems encountered when using the nonpreemptive SJN policy? Figure 4.11 shows the same siruation with the same a rrival times using SJN. 122 ,, IC L .,,g, R 4-r M-- C' O ,pl 01 :N 02400-202 l(' =r Job: Completion Time: Minus Arrival Time: Turnaround: a. .. 5. ;;- D A B 6 --0 6 10 7 14 -1 -2 -3 > ~ :,. 9 5 11 :T C 3 "' In this case, the average turnaround cime is 7.75, calculated as follows: 6+9:5+1 I = 7.75 r;-un, for the same jab ~quence ~ B, C. and D using the nonprttmptlvt SJN algorithm, 0 6 7 10 14 Notice in Figure 4.11 that, initially, A is the only job in the READY queue, therefore, it runs first and continues until ir finishes because SJN is a nonprecmprivc algorithm. The next job co be run is C, because when Job A is finished (ar Time 6), all of the other jobs (8, C, and D) have arrived, and of those three, C has the shortest CPU cycle, so 1t is run next, followed by 8, and finally D. Therefore, in this example, SRT at 6.25 is faster than SJN at 7.75. However, in our calculations we ncglcacd to include the time required by the SRT algorithm to do the conceXt switching. Context switching cs the aa of saving a job's proccsslflg information lfl its PCB so tlur the job can be swapped out of memory; then the next job's processing inform:uion from its PCB is loaded into the appropriate registers so that the CPU can process it. Context switching is required by all preemptive algorithms in order for jobs to be able to pick up where they left off after being inrcrrupted. When Job A is preempted, all of ics processing information must be saved in ia PCB for later; when Job A's executton is t0 be continued, and the contencs of Job B's PCB arc loaded into the appropriate registers so that it can start running again, this is a context switch. Later, when Job A is once again assigned to the processor, another context switch is performed. This time the infonna• tion from the preempted job is stored in its PCB, and che contents of Job A's l>CB ore loaded into the appropriate registers. Coppghl 20 How che context switchi ng is aaually done depends on the architeaure of the CPU; in many systems, there arc special instruaions that provide quick saving and restoring of information. The switch ing is designed 10 be performed efficiently but, no matter how fas1 or efficient it is, i1 still takes valuable CPU t ime and contribuces 10 overhead. So although SRT a ppears co be faster, in a real operating environment, its advanrages arc diminished by che time spent while context switching. A precise comparison of SRT and SJN would ha"' It) indu~ the time required ro do the