OPERATING SYSTEMS CSC 4103
Popular in Course
verified elite notetaker
Popular in ComputerScienence
This 8 page Class Notes was uploaded by Miss Emery VonRueden on Tuesday October 13, 2015. The Class Notes belongs to CSC 4103 at Louisiana State University taught by T. Kosar in Fall. Since its upload, it has received 18 views. For similar materials see /class/222854/csc-4103-louisiana-state-university in ComputerScienence at Louisiana State University.
Reviews for OPERATING SYSTEMS
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/13/15
CSC 4103 Operating Systems Spring 2007 LECTURE XI MIDTERM REVIEW Tevfi k Kosar Louisiana State University March 1st 2007 IO Structure o After O starts control returns to user program only upon O completion synchronous Wait instruction idles the CPU until the next interrupt Wait loop contention for memory access At most one IO request is outstanding at a time no simultaneous IO processing o After O starts control returns to user program without waiting for IO completion asynchronous System call request to the operating system to allow to wait for IO completion Devicestatus table contains entry for each IO device indicating its type address and state USGI Operating system indexes into O device table to determine device status and to modify table entry to include interrupt Two O Methods Synchronous Asynchronous user requesnng process requesting process user I waiting n I f A r quot1 l device driver I device driver I I l I I kernel i I interrupt handler I l interrupt handler gt kernel I I I I hardware ll hardware data transfer data transfer K J time gt time gt a b DualMode Operation Dualmode 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 privi eged only executable in kernel mode System call changes mode to kernel return from call resets it to user Transition from User to Kernel Mode o 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 time user process user mode user process executing H calls system call return from system can mode bit 1 l f 39l I 1 k I trap return Ema mode bit 0 mode bit i kernel mode execute system call mOde 13 0 OS Design Approaches application program F W resident system program Simple Structure Layered Approach Microkernels Modules ROM BIOS device drivers anguish device and bus drivers application environments and common services classes 539 lilesyslem9 980 X em ll il39 cor miscellaneous k modules quot laris 39 el ltoadablv system calls s quotquotquot h r f kernel BSD STREAMS qexeculable environment 39 modules lormais Mach Process State As a process executes it changes state new The process is being created running Instructions are being executed waiting The process is waiting for some event to occur ready The process is waiting to be assigned to a process terminated The process has finished execution admitted interrupt exit terminated scheduler dispatch IO or event completion IO or event wait waiting Information associated with each Process Control Block PCB process state process Process state Program counter CPU registers CPU scheduling information Memorymanagement process number program counter registers memory limits mformauon list of open files Accounting information IO statusinformation CPU Switch From Process to Process process PC operating system process P1 interrupt or system call executing save state into PCBD I reload state from PCB1 l39 idle interrupt or system call executing V 7 save state into PCB1 I reload state from PCBO executing idle idle Schedulers Cont Shortterm scheduler is invoked very frequently milliseconds 2 must be fast Longterm scheduler is invoked very infrequently seconds minutes 2 may be slow The longterm scheduler controls the degree of mul tiprogramming Processes can be described as either IlObound process spends more time doing lO than computations many short CPU bursts CPUbound process spends more time doing computations few very long CPU bursts longterm schedulers need to make careful decision Addition of Medium Term Scheduling In timesharing systems remove processes from memory temporarily to reduce degree of multiprogramming Later these processes are resumed Swaping SWaP in partially executed swap out swappedout processes ready queue r lO waiting queues CPU 7 eno Process Creation Cont Address space Child duplicate of parent Child has a program loaded into it UNIX examples fork system call creates new process exec system call used after a fork to replace the process memory space with a new program parent resumes C Program Forking Separate Process int main Pidt pid fork another process pid fork if pid lt O error occurred fprintfstderr quotFork Failedquot exit1 else if pid child process execlpquotbinlsquot quotlsquot NULL else parent process parent will wait for the child to complete wait NULL printf quotChild Completequot exitO 13 Synchronization Message passing may be either blocking or nonblocking Blocking is considered synchronous Blocking send has the sender block until the message is received Blocking receive has the receiver block until a message is available Nonblocking is considered asynchronous Nonblocking send has the sender send the message and con nue Nonblocking receive has the receiver receive a valid message or null 14 Threads vs Processes Heavyweight Process Process Lightweight Process Thread Advantages Thread vs Process Much quicker to create a thread than a process Much quicker to switch between threads than to switch between processes Threads share data easily Disadvantages Thread vs Process Processes are more flexible They don t have to run on the same processor No security between threads One thread can stomp on another thread39s data For threads which are supported by user thread package instead of the kernel If one thread blocks all threads in task block 15 Different Multithreading Models 3 s s g 3 3 34 user thread ManytoOne OnetoOne ManytoMany Two level Model lt kernel thread 3 3 3 E a s a a a 3 lt user thread G lt kernel thread 16 FirstCome PZaP3 FirstServed FCFS Scheduling Process Burst Time P 24 P2 3 P3 3 Suppose that the processes arrive in the order P The Gantt Chart for the schedule is P1 P2 P3 24 27 30 Waiting time for P1 0 P2 24 P3 27 Average waiting time 0 24 273 17 17 ShortestJobFirst SJF Scheduling Associate with each process the length of its next CPU burst Use these lengths to schedule the process with the shortest time Two schemes nonpreemptive once CPU given to the process it cannot be preempted until completes its CPU burst preemptive if a new process arrives with CPU burst length less than remaining time of current executing process preempt This scheme is know as the ShortestRemainingTimeFirst SRTF SJF is optimal gives minimum average waiting time for a given set of processes 18 Example of NonPreemptive SJF Process ArrivalTime BurstTime AAAV Average waiting time 0 6 3 74 4 Example of Preemptive SJF Process ArrivalTime BurstTime 7 P 20 4 P3 40 1 P 50 4 Average waiting time 9 1 0 Z4 3 Priority Scheduling A priority number integer is associated with each process The CPU is allocated to the process with the highest priority smallest integer 2 higwest priority reemptive nonpreemptive SJF is a priority scheduling where priority is the predicted next CPU burst time Problem 2 Stanation low priority processes may never execute Solution 2 Aging as time progresses increase the priority of the process Round Robin RR Each process gets a small unit of CPU time time quantum usually 10100 milliseconds After this time has elapsed the process is preempted and added to the end of the ready queue If there are n processes in the ready queue and the time quantum is q then each process gets 1n of the CPU time in chunks of at most q time units at once No process waits more than n1q time units 390 m 3 a n 3 n m q small q must be large with respect to context switch otherwise overhead is too hiyi 22 Example of RR with Time Quantum 20 Process Burst Time 53 P1 P2 1 7 P3 68 P4 The Gantt chart is 0 20 37 57 77 97 H7 i2l 34 54 62 ypically higher average turnaround than SJF but better response Multilevel Feedback Queue A process can move between the various queues aging can be implemented this way Multilevelfeedbackqueue scheduler defined by the following parameters ueues schedulingalgorithms foreach queue method used to determine which queue a process will enter when that process needs service Solution to CriticalSection Problem A solution to the criticalsection problem must satisfy the following requirem nts 1Mutual lusion f process P is executingin its critical section then no other processes can be xecuting in their critical sections Progress If no process is executing in its critical section and there exist some processes that wish to enter their critical section then the selection of the processes that will enter the critical section next cannot be postponed indefinitely quot Solution to CriticalSection Problem 3 Bounded Waiting A bound must exist on the n mber of times that other processes are allowed to enter their critical sections afte a process has made a request to enter its critical section and before that request is granted 0 Assume that each process executes at a nonzero speed 0 No assumption concerning relative speed of the N processes Semaphores as Synchronization Tool Counting semapho e integer value can range over an nrestricted domain Binary semaphore integer value can range only between 0 and 1can be simpler to implement Also known as mutex locks Provides mutualexclusion Semaphore 5 ll initialized to 1 wait 5 ritical Section signal 51 Classical Problems of Synchronization BoundedBuffer Problem Readers and Writers Problem DiningPhilosophers Problem Sleeping Barber Problem You should be able to solve them using semaphores as well as monitors Deadlock and Starvation Deadlock two or more processes are waitingindefinitely for an vent that can be caused by only one of the waiting processes Let and Qbe two semaphores initialized to 1 o 1 wait 1 wait Q1 wait Q Wall E igial 1 igial Q1 l wl Q lgnal 1 Starvation indefinite blocking A process may neverbe removed from the semaphore queue in which it is suspended Monitors A highrlevel abtractiuri that pruvide a convenient and effective mechanivn for pruce ynchrunizatiun Only one proce may be active Within the monitor at a time ensemble comm Procedure Pi l H Procedure Pnl H initialization codel H A monitor procedure Lake the luck before doing anything ele and hold it until it either finihe or Wait for a condition Deadlock Characterization Deadlock can arise if four conditions hold simultaneously 1 Mutual exclusion nonshared resources only one process at a time can use a specific resource 2 Hold and wait a process holding at least one resource is waiting to acquire additional resources held by other processes 3 No preemption a resource can be released only voluntarily by the process holding it after that process has completed its task 31 Deadlock Characterization cont Deadlock can arise if four conditions hold simultaneously 4 Circular wait there exists a set P0 P1 P0 of waiting processes such that Pois waiting for a resource that is held by P1 P1 is waiting for a resource that is held by P2 P1 is waiting for a resource that is held by Pn and Pn is waiting for a resource that is held by P0 32 ResourceAllocation Graph Used to describe deadlocks Consists of a set of vertices Vand a set of edges E V is partitioned into two types P P1 P2 Pn the set consisting of all the processes in the system R R1 R2 Rm the set consisting of all resource types in the system c P requests R directed edge P1 gt R o R is assigned to P directed edge R gt P 33 Example of a Resource Allocation Graph R4 34 Basic Facts If graph contains no cycles gt no deadlock If graph contains a cycle 3 there may be a deadlock if only one instance per resource type then deadlock if several instances per resource type possibility of deadlock 35 Deadlock Prevention Ensure one of the deadlock conditions cannot hold Restrain the ways request can be made Mutual Exclusion not required for sharable resources must hold for nonsharable resources Eg readonly files Hold and Wait must guarantee that whenever a process requests a resource it does not hold any other resources 1 Require process to request and be allocated all its resources before it begins execution 2 or allow process to request resources only when the process has none Example Write from DVD to disk then print 1 holds printer unnecessarily for the entire execution Low resource utilization 2 may never get the printer later starvation possible 36 Deadlock Prevention Cont No Preemption If a process that is holding some resources requests another resource that cannot be immediately allocated to it then all resources currently being held are released Preempted resources are added to the list of resources for which the process is waiting Process will be restarted only when it can regain its old resources as well as the new ones that it is requesting Circular Wait impose a total ordering of all resource types and require that each process requests resources in an increasing order of enumeration Deadlock Avoidance If a system is in safe state gt no deadlocks If a system is in unsafe state gt possibility of deadlock Avoidance 2 ensure that a system will never enter an unsafe state 37 38 ResourceAllocation Graph For Deadlock Avoidance 39 Banker s Algorithm Multiple instances Each process must a priori claim maximum use When a process requests a resource it may have to wait When a process gets all its resources it must return them in a finite amount of time 40 ResourceAllocation Graph and Waitfor Graph Pa b ResourceAllocation Graph Corresponding waitfor graph 41 Detection Algorithm 1 Let Work and Finish be vectors of length m and n respectively Initialize a Work Available b For i 12 n if Allocation i 0 then Finishi falseotherwise Finishi true 2 Find an index i such that both a Finishi false b Request S Work If no such i exists go to step 4 42 Recovew from Deadlock Process Termination Abort all deadlocked processes Abort one process at a time until the deadlock cycle is eliminated In which order should we choose to abort Priority of the process How long process has computed and how much longer to completion Resources the process has used Resources process needs to com lete How many processes will need to be terminated lsprocess interactive orbatch Recovely from Deadlock Resource Preemption Selecting a victim minimize cost Rollback return to some safe state restart process for that state Stanation same process may always be picked as victim include number of rollback in cost factor
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'