Introduction to Operating Systems
Introduction to Operating Systems CSI 4337
Popular in Course
Popular in ComputerScienence
This 19 page Class Notes was uploaded by Melvin Bednar on Saturday October 3, 2015. The Class Notes belongs to CSI 4337 at Baylor University taught by Staff in Fall. Since its upload, it has received 49 views. For similar materials see /class/217938/csi-4337-baylor-university in ComputerScienence at Baylor University.
Reviews for Introduction to Operating Systems
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/03/15
Class Notes Sept 1 2006 Critical Sections The basic problem we had with interfering computations on shared variables is that when I have two computations of the following kind one can be injected inside the other by an interrupt Load R1 Add R1 Store R1 The problem happens when an interrupt occurs between the load and the store This is known as the critical section of a program This is a simple example critical sections can be long and complex The main idea is that while a critical section of one process is executing the critical sections of other processes must be prevented from eecuting The processes can interleave all they want in other respects but the critical sections cannot be interleaved A critical section is always with respect to a particular variable or set of variables For simplicity we assume that a process is structured like this while true critical section remainder section The remainder section is just the part of the program that is not the critical section We assume that the critical section is executed over and over many times Not forever but unpredictably long We could have some remainder section before the critical section too but this really doesn t matter To control access to the critical section we must place some code before the critical section to alert the other processes that a particular process is entering its critical section We must also add code after the critical section to alert other processes that a particular process is no longer in its critical section so the whole thing ends up looking like this while true entry section critical section eit section remainder section Whatever we put in the entry and exit sections must have the following properties 1 Mutual exclusion 7 no two critical sections interleaving their executions 2 Progress 7 no stupid solutions you can t get locked out except by another process 3 Bounded waiting 7 you won t be forced to wait forever because of timing issues Number 3 is normally not present in most solutions because it is normally not an issue in real systems In specialized cases this can change Peterson s Solution We can do this with raw code We need the following assumption however If two processes attempt to assign a value to a variable one of them will succeed The assigned value will not be some combination of the two values but will be distinctly one value or the other int turn boolean ag2 entry section process 1 agl true turn 2 while ag2 ampamp turn 2 critical section exit section process 1 agi false We need both of these things If we use just the turn variable we will need to swap between two processes even if only one process is running If we use just the ag variable both ags can get set simultaneously There are other more complex solutions that work for n processes but the code uses n as one of its parameters These solutions are bizarrely complex and extremely difficult to code correctly Nevertheless it can be done Peterson s solution can also be extended to multiple processes Synchronization hardware Doing mutual exclusion in code teaches us one thing We don t want to do it in code Therefore hardware mechanisms have been invented to do this job for us The most common ofthese is test and set Test and set performs a hardware interlock on the memory module it addresses It performs a readtestandwrite operation while locking out any other processor from the memory module This permits the instruction to execute atomically The test and set addresses a single memory word It sets this word to TRUE and returns the previous value This is done atomically so no two processors can see the original value and set the new value The test and set instruction can be used as follows to enforce mutual exclusion This is an nprocess solution shared boolean Flag false while TestAndSetFlag critical section Flag false Class Notes Sept 6 2006 Synchronization hardware Synchronization hardware solves the problem of mutual exclusion for multiple CPU s however it still gives us the annoyance of having a busy wait The TestAndSet instruction is usually not a privileged instruction so any process can execute it but there is a friendlier way to do mutual exclusion in processes This is to do a system call and request mutual exclusion from the operating system If this is done the waiting process can be put in a wait state and other processes can run while it is waiting The resources used by a process are typically longer term than those used by the OS so it makes sense to use TestAndSet in the OS it is absolutely necessary sometimes and some other mechanism at the process level Several mechanisms have been created for use at the process level The most universal is the semaphore The semaphore is an integer variable that can be accessed only through the functions wait and signal It is essentially a class Wait and Signal are actually system calls so they are executed by the operating system Wait causes the integer to be decremented Signal causes it to be incremented The semaphore is never allowed to become negative so if a Wait operation were to make the semaphore negative the requesting process is forced to wait Each semaphore has a queue of processes that are waiting for it When Signal is executed the queue is examined and if it is nonempty one process is activated and removed from the queue Otherwise the semaphore is incremented Here are some problems that are pretty easy to solve using semaphores l Protecting critical regions 2 Bounded buffer problem 3 Dining philosophers 4 Readers and Writers Class Notes Sept 8 2006 Readers and Writers A more complicated problem is readers and writers Any number of readers can read simultaneously but only one writer can write at a time Furthermore to preserve consistency writers must exclude readers Here s how it works Writer WrtWait Write WrtSignal Reader RdrWait ReadCount if ReadCount l WrtWait RdrSignal Read RdrWait ReadCount if ReadCount 0 WrtSignal RdrSignal Monitors A monitor is a class The syntax in the book is based on Pascal and does not use constructors properly If monitors actually were implemented in C the initialization section would be replaced by a constructor At any given time only one copy of a monitor exists in the system The monitor s data is shared by all processes Only one process can be executing a monitor function at a time There is mutual exclusion between invocations of the same function and between invocations of different functions of the same monitor Wait and signal work differently from semaphores Wait and signal must be executed inside the monitor Signal does nothing if there is nothing waiting Wait breaks mutual exclusion and suspends the current process Signal resumes a waiting process once the current function eXits Or immediately Threads A thread is a cheap process 7 Usually Class Notes Aug 30 2006 If we want to send messages from one process to another here is one way to do this Create a shared array with Size number of elements shared int BufferSize We will also have two shared variables to manage the array one that tells us where the next message should go and one that tells us where the next message should be read from These variables are both initialized to zero shared int SendPos 0 shared int RecPos 0 Then whenever we send a message we will do this BufferSendPos SMsg SendPos Whenever we want to receive a message we will do this RMsg BufferRecPos RecPos There are several problems with these two algorithms First what happens when the buffer is full and I want to send another message Second what happens if the buffer is empty when I want to receive a message Third what happens when SendPos and RecPos become greater than or equal to Size We can x problem 3 like this BufferSendPos SMsg SendPos39 if SendPos gt Size SendPos 0 RMsg BufferRecPos RecPos if RecPos gt Size RecPos 0 Although it is less efficient to do so we can write the increment in one line like this SendPos SendPoslSize RecPos RecPoslSize Detecting an empty buffer is easy too Notice that in the beginning the buffer is empty and SendPos RecPos 0 IfI send one message and receive one message the buffer will be empty and SendPos RecPos 1 So if SendPos and RecPos are equal it is an indication that the buffer is empty We rewrite the receiver code like this while SendPos RecPos RMsg BufferRecPos RecPos RecPoslSize39 Note the semicolon at the end of the while statement This causes the while to execute over and over again until the condition becomes false This is known as a busy wait Busy waits are bad but they work What about the buffer being full If we add Size messages to the buffer without anything being received we will increment SendPos until it is equal to Size But the test at the end will then set SendPos back to zero So SendPos RecPos 0 Unfortunately this condition is identical to the buffer empty condition We can get around this by treating the buffer as full when there is one empty slot To test this condition we can use the following test SendPoslSize RecPos This says Will the buffer become full if I add one more message If the answer is yes then the buffer has one empty slot I modify the sender code like this while SendPoslSize RecPos BufferSendPos SMsg SendPos SendPoslSize Again note the semicolon at the end of the while statement This code works pretty well but this annoyance of having one empty slot in the buffer all the time should be fixable Let s try another approach Let s use a shared variable that tells us how many slots are available in the buffer shared int Slots Size Now we modify the sender and receiver thus while Slots lt l BufferSendPos SMsg Slots SendPos SendPoslSize while Slots Size RMsg BufferRecPos Slots RecPos RecPoslSize This gets rid of the empty slot but unfortunately it doesn t work Why not If the Slots and Slots happen to interleave in the right way the total could be incorrect One or the other could appear not to have been executed Why didn t this problem affect the first solution Here s a quick test For each process create two sets of variables the Read set and the Write set The Read set is all shared variables that are used by the process but not changed The Write set is all shared variables that are changed by the process So for the receiver the sets are Read Buffer SendPos Write RecPos For the sender the sets are Read RecPos Write Buffer SendPos If the write sets of two processes do not intersect then the problems we encountered with updating shared variables cannot occur For the modified algorithms we would have to add Slots to the read set and the write set of both processes This would indicate a potential for interference If a read set intersects with another process s write set there is a potential for inconsistency if the write set contains structures or objects that have internal items that must be consistent with one another Linked list plus counter for example In the bounded buffer case the order of the operations prevents inconsistency from occurring But what happens if we change the order of these two statements BufferSendPos SMsg SendPos SendPoslSize Class Notes Sept 13 2006 Consider the following example of processes in the ready queue We assume that all processes entered the ready queue at time 0 in the order given Process Burst Pl 3 P2 1 P3 4 P4 5 P5 2 Let s use a GANTT chart to compute the average wait time and the average turnaround time for the First Come First Served algorithm P1 P2 P3 P4 P5 l l l l l l 0 3 4 8 1 3 15 Process Burst Wait Turnaround P l 3 P2 1 3 4 P3 4 4 8 P4 5 8 13 P 5 2 13 l 5 Total 30 43 Average 6 86 Now let s try Shortest Job First We rearrange the queue in ascending order by burst time P2 P5 P1 P3 P4 Process Burst Wait Turnaround Pl 3 3 6 P2 1 0 1 P3 4 6 10 P4 5 10 15 P5 2 l 3 Total 20 35 Average 5 7 Shortest Job First reduces the average wait time and the average turn around time in this case We can prove that SJF always gives the minimal wait time Suppose we have the GANTT chart of a schedule that is NOT in SJF order Suppose Pi and Pj are two consecutive processes in this schedule If it WERE in SJF order the burst time of Pi Bi would be less than or equal to the burst time of j Bj Bi S Bj Since this schedule is NOT in SJF order there must be at least one pair of consecutive processes where Bi gt Bj Examine the GANTT chart of this pair of processes Pi Pj l l l 0 X Y If we switch Pi and Pj the number X will not change nor will anything to the left of it Similarly the number Z will not change nor will anything to the right of it The only number that will change will be Y Y BiX The new Y Y is Y BjX Since Bi gtBj Y39lt Y Therefore we have reduced the total wait time by Y Y39 which is a positive number SJF reduces wait time but how can we gure out the burst time In a realtime system you may have timed every logic path and may know the burst times of each In this case you may know ahead of time what the burst time will be In a more typical OS there isn t really any way to tell You can guess The most common way of guessing is to use the exponential average Let 1390 be the initial guess which is determined by averaging burst times over a long period of time months Let I will be our guess for the nth burst and In will be the actual time for the nth burst We can average the two together using a probability 0 S p S l like this Tm tnPTn1P The probability p gives the relative importance of r and In If we substitute this out for the r and end up with a long equation involving just In and 1390 we will have a term n1 containing 1 p thus the term exponential average This is never used in practice In practice priority and roundrobin are used Priority gives a list of queues numbered 0255 usually OS s differ in whether 0 is highest priority or 255 The OS searches the queues from high to low priority and schedules the processes from a particular queue in FCFS order If queue 25 always has a process then queue 26 processes will starve It s possible to move processes from one queue to another to alleviate starvation Sometimes processes are scheduled in RoundRobin fashion This means I run a process for a xed amount of time If it gets done ne If it doesn t it goes back into the ready queue and the next process in FCFS order is scheduled Round Robin can reduce response time below SJF but usually increases wait and turnaround time In round robin a process is run for a xed time called a quantum A timer interrupt is used to enforce the quantum Let s do a GANTT chart for the above algorithm assuming a quantum of 2 Process Burst Wait Resp Turn Pl 3 7 0 10 P2 1 2 2 3 P3 4 8 3 12 P4 5 10 5 15 P5 2 7 7 9 Total 34 17 49 Average 68 34 98 Round robin increases wait and turnaround time over FCFS but has a much better response time than SJF Class Notes Aug 28 2006 We have two sorts of entities in our computer now the operating system and processes Bizarrer enough the OS doesn t do anything except respond to interrupts In that sense the OS is completely passive It provides services that are invoked with interrupts The only thing that can do anything is a process If we look at the lifetime of a process it will look as follows this is in the book These states are normally recorded in the PCB Each state normally represents a different queue within the OS s data space Terminating Ready For uniprocessors the Ready and the Running state do not have to be explicitly different however for multiprocessors it is essential to distinguish between the two When a process requests 10 the following steps take place The process is in the running state System Call OS starts IO Process is placed in waiting state Other stuff goes on for a while An IO interrupt occurs The OS processes the interrupt The OS places the process in the ready state Eventually the process enters the running state again 00899 9 Suppose process A is running process B is waiting for 10 We can switch from one process to another as follows This is called a context switch 1 An IO interrupt occurs 2 Current context is saved 3 IO interrupt is processed 4 Process B is made ready 5 Scheduler runs 6 Process B is selected 7 Process B s context is loaded What exactly is a context anyway It is the contents of all registers in the computer In addition to the other stuff that we placed in the PCB we also have a copy of all the registers These are saved when a process is interrupted and restored when a process enters the running state What creates a process How does a process die How do we communicate between processes How do we handle shared data structures C81 4337 Class Notes for Aug 2123 2006 Read Chapter 1 in the book This will give you one perspective on the how and why of operating systems I want to give you a somewhat different perspective The early designers of computers were faced with a number of problems that urgently needed to be solved They developed the first operating systems in response to these problems The process of solving these problems is straightforward and the solution is reasonable If you had been faced with the same sorts of problems you would probably have come up with a solution that was identical or at least very similar to the operating systems that exist today Here are the problems 1 A computer was an extremely expensive piece of equipment Even the smallest computer cost hundreds of thousands of dollars and a computer of any reasonable size was several million dollars For example one computer that I used extensively back in the early 1970 s had a meg and a half of memory could execute about half a million instructions per second as opposed to billions for today s microprocessors and cost three million dollars It was important to use this very expensive hardware as effectively as possible 2 Only one person could use the computer at a time At one time you would punch your program into a set of cards then go to the computer room and wait in line for your turn to use the computer When your turn came you would go up to the front panel of the computer bootstrap your program into the computer by using the front panel buttons and then wait for the printout Anyone else who wanted to use the computer had to wait until you were done 3 Despite the slowness of early computers IO operations were much slower than ordinary computation The computer was capable of executing thousands of instructions while a single card was being read Nevertheless IO operations were synchronous so the instruction execution unit would interlock waiting for the IO operations to complete thus wasting valuable time doing nothing One solution to problem 3 was asynchronous 10 10 instructions were modified so that they operated independently of the instruction execution unit An IO instruction started the IO operation but the CPU continued to execute instructions while the IO operation was taking place The program had to be written in such a way as to request an IO operation a long time before the data was actually required Then when the program reached the point where it really needed the data it had to execute another instruction to wait for completion of the IO operation This wait instruction was synchronous It interlocked the CPU until the IO operation was complete Despite the use of asynchronous IO most programs spent most of their time waiting for 10 In fact most programs spent over 90 of their time waiting for IO Thus you have a multimillion dollar piece of equipment that is sitting idle 90 of the time even though there are people standing in line waiting to use it This is the sort of thing that is guaranteed to drive most computer scientists crazy Thus we come to the big idea Why not run two programs at the same time We have to be careful with this idea because the CPU really isn t capable of doing this The CPU can only execute one instruction at a time Therefore it can only run one program at a time To make the big idea work we have to do something clever What we have to do is make the CPU jump around from one program to another When one program is waiting for IO we don t interlock the CPU we simply have the CPU jump to a different program and begin executing that program instead Two programs might not be enough to keep the CPU busy all the time but if we can run two programs at the same time we can run three or four or a whole bunch And sooner or later we ll have enough programs running to keep the CPU busy most of the time thus making the best use of our multimillion dollar piece of equipment Running two programs at a time poses several problems 1 What if both programs want to use the same section of memory Can we move one of them What about address constants What about absolute addresses 2 What if one of the programs decides it doesn t want to give up the CPU while it is waiting for 10 How do we force the program to give up the CPU 3 What if one of the programs is malicious and decides to damage the other or the operating system 4 When an IO operation completes how do we find out about it How do we restart a program that is waiting for 10 to complete 5 If I have a choice between running program A or program B which do I choose Once we have the answers to these questions we will have most of what we need to design an operating system Interestingly enough we set out to solve one problem but we have inadvertently solved another one at the same time The problem of only one person being able to use the computer at a time is implicitly solved by allowing more than one program to run simultaneously There are issues that pertain exclusively to this problem and we will examine those when we get to CPU scheduling Class Notes Sept 13 2006 The Clone system call is similar to Fork except a lightweight process is created that shares all data with the parent process This represents a kernel thread because the thread is known to the OS There are three types of multithreading OnetoOne using only Clone type threads where the OS knows about the threads These threads can be used to multithread with system calls like IO ManytoOne using only something like the pthreads package You have many user threads but only one kernel thread so when a system call occurs all threads block ManytoMany mixing Clone with pthreads where there are kernel threads and user threads Threading issues What happens on an exec system call This replaces the current process with a new process How does this work if there are multiple kernel threads Do they all go away In Linux only the thread executing the exec system call is replaced What happens with a signal Do all threads get signaled or only a speci c thread In Linux the kernel thread acts as a process with respect to signals Only one thread gets signaled Scheduling Recall how an interrupt is processed Interrupt Save PC PSW and all registers Figure out what happened Respond to what happened Schedule a new Process Load Registers including PC amp PSW That is the step we want to talk about There are many different algorithms that can be used for scheduling Scheduling means choosing a process from the ready queue and running it Of course processes make many passes through the ready queue and the wait queues We are concerned only with one pass through the ready queue which is called a CPU burst A pass through the wait queue is called an IO burst even if it isn t waiting for 10 In most cases we assume that processes will complete their CPU burst when entering the run queue although this isn t always true There are several measures of quality we want to apply to scheduling algorithms In real operating systems the following are used 1 CPU Utilization 7 the amount of time actually spent executing code as opposed to sitting idle We will not be concerned with this measure because it deals with broader issues than picking processes from the ready queue 2 Throughput 7 The number of processes completed per unit time This also is based on broader issues 3 Wait time 7 The amount of time a process spends in the ready queue without being executed 4 Turnaround Time 7 The amount of time between entering the ready queue and completion of execution 5 Response Time 7 The amount of time between entering the ready queue and start of execution The same as wait time for most algorithms GANTT charts can be used to analyze the performance of algorithms and determine Wait Time Turnaround Time and Response Time Given three processes with the following burst times Pl 1 P2 2 P3 3 We have the following chard l P1 l P2 P3 The wait time and response time are identical We get turnaround times of The average wait time is 43 and the average turnaround time is 103