1CSC 4103 - Operating SystemsFall 2009Tevfik Ko!arLouisiana State UniversitySeptember 14th, 2009Lecture - VIICPU Scheduling - II2Roadmap• Multilevel Feedback Queues• Estimating CPU bursts• Project Discussion• System Calls• Virtual Machines3Multilevel Queue• Ready queue is partitioned into separate queues:foreground (interactive)background (batch)• Each queue has its own scheduling algorithm– foreground – RR– background – FCFS• Scheduling must be done between the queues– Fixed priority scheduling; (i.e., serve all from foreground then from background). Possibility of starvation.– Time slice – each queue gets a certain amount of CPU time which it can schedule amongst its processes; i.e., 80% to foreground in RR, 20% to background in FCFS 4Multilevel Queue Scheduling5Multilevel Feedback Queue• A process can move between the various queues; aging can be implemented this way• Multilevel-feedback-queue scheduler defined by the following parameters:– number of queues– scheduling algorithms for each queue– method used to determine when to upgrade a process– method used to determine when to demote a process– method used to determine which queue a process will enter when that process needs service6Example of Multilevel Feedback Queue• Three queues: –Q0 – RR with time quantum 8 milliseconds–Q1 – RR time quantum 16 milliseconds–Q2 – FCFS• Scheduling–A new job enters queue Q0 which is served FCFS. When it gains CPU, job receives 8 milliseconds. If it does not finish in 8 milliseconds, job is moved to queue Q1.–At Q1 job is again served FCFS and receives 16 additional milliseconds. If it still does not complete, it is preempted and moved to queue Q2.7Multilevel Feedback Queues8Determining Length of Next CPU Burst• Can only estimate the length• Can be done by using the length of previous CPU bursts, using exponential averaging+9Examples of Exponential Averaging•! =0–"n+1 = "n– Recent history does not count•! =1– "n+1 = ! tn– Only the actual last CPU burst counts• If we expand the formula, we get:"n+1 = ! tn+(1 - !)! tn -1 + … +(1 - ! )j ! tn -j + … +(1 - ! )n +1 "0•Since both ! and (1 - !) are less than or equal to 1, each successive term has less weight than its predecessorExercise1011Prediction of the Length of the Next CPU BurstAlpha = 1/2, T0 = 1012Project Discussion13OS API: System Calls14System CallsTanenbaum, A. S. (2001)Modern Operating Systems (2nd Edition). user spacekernel spaceThe system calls are the mandatory interface between the user programs and the O/S!Location of the system calls in the Computing SystemSystem calls15System Calls• Programming interface to the services provided by the OS• Typically written in a high-level language (C or C++)• Mostly accessed by programs via a high-level Application Program Interface (API) rather than direct system call use– Ease of programming– portability• Three most common APIs are Win32 API for Windows, POSIX API for POSIX-based systems (including virtually all versions of UNIX, Linux, and Mac OS X), and Java API for the Java virtual machine (JVM)16System Calls!All programs needing resources must use system callsOperating systemUser programsLibrary functions & programs. . . fputs, getchar, ls, pwd, more . . .. . . fork, open, read System calls rm, chmod, kill . . . user spacekernel spacethe “middleman’scounter”"system calls are the only entry points into the kernel and system"most UNIX commands are actually library functions and utility programs (e.g., shell interpreter) built on top of the system calls"however, the distinction between library functions and system calls is not critical to the programmer, only to the O/S designer17Example of System Calls• System call sequence to copy the contents of one file to another file18System Call Implementation• Typically, a number associated with each system call– System-call interface maintains a table indexed according to these numbers• The system call interface invokes intended system call in OS kernel and returns status of the system call and any return values• The caller need know nothing about how the system call is implemented– Just needs to obey API and understand what OS will do as a result call– Most details of OS interface hidden from programmer by API • Managed by run-time support library (set of functions built into libraries included with compiler)19Dual-Mode Operation• Dual-mode operation allows OS to protect itself and other system components– User mode and kernel mode – Mode bit provided by hardware• Provides ability to distinguish when system is running user code or kernel code• Protects OS from errant users, and errant users from each other• Some instructions designated as privileged, only executable in kernel mode• System call changes mode to kernel, return from call resets it to user20Transition from User to Kernel Mode• How to prevent user program getting stuck in an infinite loop / process hogging resources# Timer: Set interrupt after specific period (1ms to 1sec)– Operating system decrements counter– When counter zero generate an interrupt– Set up before scheduling process to regain control or terminate program that exceeds allotted time21Standard C Library Example• C program invoking printf() library call, which calls write() system call22Solaris System Call Tracing23Virtual Machines24Virtual Machines• A virtual machine takes the layered approach to its logical conclusion. It treats hardware and the operating system kernel as though they were all hardware• A virtual machine provides an interface identical to the underlying bare hardware• The virtual machine creates the illusion of multiple processes, each executing on its own processor with its own (virtual) memory25Virtual Machines (Cont.)• The resources of the physical computer are shared to create the virtual machines– CPU scheduling can create the appearance that users have their own processor– Spooling and a file system can provide virtual card readers and virtual line printers– A normal user time-sharing terminal serves as the virtual machine operator’s console26Virtual Machines (Cont.) (a) Nonvirtual machine (b) Virtual machine Non-virtual MachineVirtual Machine27Virtual Machines (Cont.)• The virtual-machine concept provides complete protection of system resources since each virtual machine is isolated from all other