Operating Systems CS 35400
Popular in Course
Popular in ComputerScienence
This 86 page Class Notes was uploaded by Nick Rowe on Saturday September 19, 2015. The Class Notes belongs to CS 35400 at Purdue University taught by Staff in Fall. Since its upload, it has received 51 views. For similar materials see /class/208085/cs-35400-purdue-university in ComputerScienence at Purdue 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: 09/19/15
Part 4 Processes and Process Schedulling Optional Reading I Chapter 3 in Silbersehatz et a1 stop before 3 4 threads Chapter 5 in Silbersehatz et a1 skip 54 thread scheduling Processes A process is a program in execution I A program may have multiple processes running the same program Eg csh running for multiple users or multiple times for the same user I Each process will be a different instance of the same program I To list processes use 39 ps List processes of the current shell session 39 ps u ltyour logingt List processes you own 39 ps e List all processes of the system Example of ps command brastius 636 TTY PID O 1 2 3 317 218 248 57 72 140 153 158 390 390 390 390 390 390 390 390 390 390 390 390 ps e TIME 0 O O 17 08 OO CMD sched init pageout 11248 fsflush O 01 OO 00 OO 20 17 43 ONOOOOO OO de cron sendmail sysevent picld inroute sshd rpcbind State Diagram States of a Process I New 39Process is being initialized I Ready 39The process is waiting for its turn to run on the CPU 1 Running 39The process is currently using the CPU Waiting 39Process is waiting for an event I Terminated 39Process is exiting IOBound Processes I Processes that are most of the time waiting for an event mouse event keyboard Ethernet packet arrives etc i This type of processes spends most of its time in the waiting state I These processes are in readyrunning state only for a short period of time 39update mouse cursor after mouse movement 39show a character on the screen 39etc CPUBound Processes I These processes need the CPU for long periods of time 39Scienti cNumerical Applications 39CompilerOptimizer 39Renderer 39Image processing I These processes are often in the ready or running state IMost applications are 0 bound Process Table Each process Will be represented with an entry in the process table i The Process Table is one of the most important data structures in the kernel I The maximum number of entries in the process table determines the maximum number of processes in the system and it is set at boot time Process Table Each Entry Includes PID Index in process table Command and args List of memory mappings used by process Owner PC Program Counter Registers Stack pointer List of Open Files State Wait Ready K Running etc rocess ID PID 0 1 UIBMN MAX PIDl Process Table I Each process table entry contains enough information to restart put in running state a process that is in the waiting or ready state i A process may have more than one thread I There is a stack pc and a set of registers in the process table entry for each thread that the process has Zombie Processes I aka Defunct process i A process that is done running but still has an entry in the process table I The entry is needed to read the eXit status of the process I Notion processes have parents and children 39 Parent can read the eXit status of its children Example I ps eaf 39 UID PID PPID CMD root 1 O sbininit ntp 4859 1 usrsbinntpd I Note if a parent process dies the Child becomes an orphan 39 Orphan processes are adopted by init Process Scheduling I From the user s point of View an OS allows running multiple processes simultaneously I In reality the OS runs one process after another to give the illusion that multiple processes run simultaneously I The Process Scheduler is the OS subsystem that runs one process after the other and decides What process to run next I A Context Switch is the procedure used by the OS to switch from one process to another Process Scheduling I Steps of a Context Switch 39 Save current running process in process table 39 Load next ready process from process table and put registers and PC in the CPU I Context Switches may happen as a result of 39 A process needs to go to wait state and therefore another process can be scheduled 39 A process yields gives up the CPU so another process can run 39 Timer interrupt Only for Preemptive Scheduling Types of Scheduling I There are two types of scheduling 39 Non Preemptive Scheduling 39 Preemptive Scheduling Non Preemptive Scheduling In Non Preemptive Scheduling a context switch switch from one process to another happens only when the running process goes to a waiting state or when the process gives up the CPU voluntarily This is a very primitive type of scheduling It is also called cooperative scheduling I It was used in Windows 31 and initial versions of MacOS I The main problem of Non Preemptive Scheduling is that a misbehaved process that loops forever may hold the CPU and prevent other processes from running Preemptive Scheduling In Preemptive Scheduling a context switch happens periodically every 11005ec or quantum time as a result of a timer interrupt A timer interrupt will cause a context switch that is the running process to go to ready state and the process that has been the longest in ready state will go to running state i Preemptive scheduling is implemented in UNIX and Windows 95 and above AdvantagesDisadvantages of Non Preemptive Scheduling Advantages of Non Preemptive Scheduling 39 More control on how the CPU is used 39 Simple to implement I Advantages of Preemptive scheduling 39 More robust one process cannot monopolize the CPU 39 Fairness The OS makes sure that CPU usage is the same by all running process CPU Burst I Most processes require periodic CPU time only for a short While 39 CPU Burst 39 e g process an event then return to waiting state 39Needs vary process by process i The faster the needed CPU bursts are satis ed the better the responsiveness of the OS I Average Completion Time I Average time a process waits for a CPU burst to be satis ed until the task is completed Scheduling Policy I The Scheduling Policy tells the Scheduler which process to run next I The goal of the Scheduler is to satisfy as many CPU bursts as possible in the shortest amount of time I This minimizes the Average Completion Time Scheduling Policy for Non Preemptive Scheduling irst Come First Served FCFS 39 Assume p1 p2 p3 arrive more or less at the same time Process Burst Time p1 24ms p2 3ms p3 3ms P1 P2 P3 24 3 3 Average completion time 242 73032 7ms Scheduling Policy for Non Preemptive Scheduling I Shortest Job First SJF Process Burst Time p1 24ms p2 3ms p3 3ms I P3 P1 3 3 24 Average completion time 3630313ms Problems Implementing SJF SJF assumes that we know in advance how long each CPU burst will take for each process I In general it is very dif cult to know in advance how long a burst is going to take I The OS does an estimate based on past performance I The estimate is done in such a way that the most recent samples are more important than the old samples Moving Average 9 I The estimates are usually done using a moving average CpuBurstEstimate 8 OldeuBurstEstimate 2 NepruBurst I The weights can be changed as long as they add to 1 Depending on the coef cients the moving average gives more or less weight to the most recent samples 39 It is a lowpass lter I The intent is that it dampens out an abnormal CPU burst or abrupt change but adapts to slow changes I Think of shock absorbers on a car i Moving Average is also used in TCPIP to compute the round trip Scheduling Policies for Preemptive Scheduling Two policies 39 Round Robin 39 Multilevel FeedbackQueue Scheduling Round Robin 39 Ready processes are in a queue 39 Every time that a time quantum expires a process is dequeued from the front of the queue and put in running state I The previous running process is added to the end of the queue Round Robin Round Robin cont T10ms Process Burst Time p1 24ms p2 3ms p3 3ms IPI IP2P3 P1 IP1 10 I 3 I 3 I 10 I 4 Average completion time 131630319 6ms Quantum Length Analysis 1 What is the impact of quantum length Assume T10ms Process Burst Time p1 20ms p2 lms p3 lms PI P2P3 p1 10 1 1 10 Average completion time 111222315ms Quantum Length Analysis 1 What if we Choose a smaller quantum lengthAssume Tlms Process Burst Time Tlms p1 20ms p2 lms p3 lms IBIIBZIBEIBII Bllml ml 0 1 1 1 1 1 1 1 Average completion time 23 2239ms Quantum Length Analysis I The shorter the quantum the shorter the average completion time I Based on this we could make the quantum time very small to achieve faster response time What is the catch I We are not considering that context switch takes time I We have to consider the context switch overhead Context Switch Overhead i The context switch overhead is the time it takes to do a context switch as a portion of the quantum time X0verhd 100 XT where Xoverhd y Context Switch Overhead X Context Switch Time T Quantum Time 1 Assume X1ms For T 1 0ms 0vhd100 1101 For T 2ms 0vhd100 125 For T 2ms 0vhd1 00 125 0 Context Switch Overhead I Conclusions 39 The smaller the quantum the faster the response time small completion time but the larger the context switch overhead 39 The larger the quantum the smaller the context switch overhead but the larger the response large completion time 1 The standard quantum time is 1100sec lOms that is a compromise between response time and context switch overhead This may change in the future With faster processors CPU Burst Distribution I Processes are in waiting state most of the time except for the times they need the CPU that is usually for short periods of time These shorts periods of time the processes need the CPU are called CPU bursts Distribution of CPU Bursts I 10mg CPU burst ms CPU Burst Distribution i 90 of CPU bursts are smaller than lOms By choosing lOms to be the quantum length we make sure that 90 of the CPU burst run until completion Without being preempted I This reduces the context switch overhead and reduces the completion time and makes the response time faster HOW to Choose the Size of 21 Quantum Make the quantum small enough to make the response time smaller faster lMake the quantum large enough to have an acceptable context switch overhead Make the quantum large enough so most CPU bursts are able to finish without being preempted Scheduling Policies for Preemptive Scheduling I Multilevel FeedbackQueue Scheduling 39 Instead of a having a single queue of ready processes there are multiple queues of different priorities 39 The scheduler will schedule the ready processes with the highest priority rst 39 Within processes of the same priority round robin is used Multilevel FeedbackQueue Scheduling 39 Problem If you have processes of higher priority low priority processes will never run 39 Solution Use Process Aging The longer a process stays in a queue the priority is arti cially increased The process Will be scheduled at some point After that the priority is reset to the initial priority 39 Also the scheduler bene ts interactive processes by increasing their priority if the CPU burst time is small The smaller the CPU burst estimate the higher the priority The larger the CPU burst estimate the lower priority Multilevel FeedbackQueue Scheduling Priority Lm39e m Cpa IBurst CPU priority 8 P3 P4 Burst priority 7 P10 P11 P12 Review Question I Which scheduling policy gives in theory the best average completion time aRound Robin bMultilevel Feedback Queue Scheduling cFirstCorne FirstServed dShortest Job First CS354 Operating Systems Spring 2009 Instructor Pascal Meunier Computer Science Department Purdue University Preparation for 2nd exam Here are questions created using the slides Part 1 True False Questions Semaphores can be initialized with a negative count Part 1 True False Questions Semaphores can be initialized with a negative count I False Part 1 True False Questions eondwait needs to be executed inside a while loop Part 1 True False Questions eondwait needs to be executed inside a while loop I True Part 1 True False Questions Global variables are shared between threads Part 1 True False Questions Global variables are shared between threads i T rue True False Questions i The calls semawait and semapost Change the semaphore count atomioally True False Questions i The calls semawait and semapost Change the semaphore count atomioally 39 True True False Questions i If all mutexes are always looked in the same order there won39t be a deadlock True False Questions i If all mutexes are always looked in the same order there won39t be a deadlock I True True False Questions i In the readwrite look implementation discussed in Class allowing readers to obtain overlapping looks Without limit can lead to the starvation of writers True False Questions i In the readwrite look implementation discussed in Class allowing readers to obtain overlapping looks Without limit can lead to the starvation of writers I True True False Questions i In a multithreaded server slave sockets are passed to worker threads True False Questions i In a multithreaded server slave sockets are passed to worker threads I True Short questions Desoribe 3 ranges of initial counts that can be given to a semaphore Short questions Desoribe 3 ranges of initial counts that can be given to a semaphore I 0 equivalent to an empty buffer I 1 equivalent to muteX gt1 only N resources are available Short questions Why do you need 2 semaphores to implement a bounded buffer Explain their role Short questions Why do you need 2 semaphores to implement a bounded buffer Explain their role I One that keeps traok of the free space so initialized to N and blocks threads When there is none left I One that keeps track of available entries initialized to zero and blocks threads when the buffer is empty Short questions i What is the difference between deadlock and starvation Short questions i What is the difference between deadlock and starvation I In a deadlock all of the involved threads will never run again i Starvation affects only speci c threads and they may run again at some point in time Short questions i In a system with N lockable resources and M threads where a thread needs to lock resource i and il write a few lines of pseudocode showing how you would request the locks Multiple choice questions Which of these methods doesn39t make a server concurrent a Iterative processing b Fork process after request o Create new thread after request d Pool of threads e Pool of processes Multiple choice questions Which of these methods doesn39t make a server concurrent a Iterative processing b Fork process after request o Create new thread after request d Pool of threads e Pool of processes Multiple choice questions MuteX looks a increase speed b enforce security c enforce atomicity 1 improve parallelism Multiple choice questions MuteX looks a increase speed b enforce security c enforce atomicity 1 improve parallelism Multiple choice questions Which of these isn39t helping synchronization a Spin locks b Mutexes c Pauli Exclusion Principle 1 Semaphores e Monitors Multiple choice questions Which of these isn39t helping synchronization a Spin locks b Mutexes c Pauli Exclusion Principle 1 Semaphores e Monitors Multiple choice questions Which one of these is unfair a Spin locks b Mutexes c Pauli Exclusion Principle 1 Semaphores e Monitors Multiple choice questions Which one of these is unfair a Spin locks b Mutexes c Pauli Exclusion Principle 1 Semaphores e Monitors Short questions Sharing computer resources between services of different priorities or importance is a Violation of which secure programming principle Give an example and describe What might happen Short questions Sharing computer resources between services of different priorities or importance is a violation of which secure programming principle 39 Least Common Mechanism I Give an example and describe What might happen I A low importance service could prevent a more important one from acquiring the resources it needs For example Short questions i A multithreaded program looks a muteX manipulates some shared data structures and then needs to wait on a semaphore Write a few lines of pseudocode calling semawait Short questions i A multithreaded program looks a muteX manipulates some shared data structures and then needs to wait on a semaphore Write a few lines of pseudocode calling semawait 39 muteXunlockampmuteX semawaitampsem muteXlockampmuteX Short questions You have 3 process threads each writing to memory a different character in an in nite loop location modulo X but they each give up the CPU after writing N characters assume that the process threads were all implemented on top of the same kernel thread How could the output differ if those were kernel threads instead Short questions You have 3 threads each writing a different character in an in nite loop I Process threads would output always N characters e g aaaabbbbccccaaaabbbbcccc I Kernel threads would get preempted after printing a variable number of characters because the time required to print N characters would not exactly match a quantum e g aaaabbbccccaaabbbbccc Short questions Explain what a multithreaded counter needs for correctness and What can happen if it doesn39t have it Short questions Explain what a multithreaded counter needs for correctness and What can happen if it doesn39t have it 39 It needs a critical section When accessing and modifying the counter otherwise some operations can be lost Short questions i If a process has 8 threads explain What could happen after a fork operation Short questions De ne threadsafe code Short questions De ne threadsafe code i Threadsafe code can be concurrently executed by multiple threads safely This involves making sure that shared resources are protected from concurrent access While they are in inconsistent states e g by using muteX locks Reentrant code is also thread safe Short questions Is the lazilyinitialized Singleton pattern threadsafe Recall that with lazy initialization the singleton pattern involves code looking like this l5 ngleton Singletoninstance If pInstance 0 pInstance new Singleton return pInstance Short questions Is the lazilyinitialized Singleton pattern threadsafe Ibkn because two threads could proceed to create a new Singleton This could happen if the first thread is interrupted after determining that pInstance is NULL The second thread then runs plnstance is still NULL so a Singleton is created The first thread then resumes and creates another Singleton instance Short questions Explain race conditions and describe an example using threads Programming questions I Implement the muteXlock and muteXunlock functions in Clike pseudocode Programming questions I Implement the muteXlock and muteXunlock functions in Clike pseudocode See class shdes mutexlock mutex spinlock if mutexlock mutexqueuecurrentThread spinpnlock currentHreadsetWaitState GiveUpCPU mutexlock true spinunlock
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'