Intro Oper System
Intro Oper System EECS 482
Popular in Course
Popular in Engineering Computer Science
This 111 page Class Notes was uploaded by Ophelia Ritchie on Thursday October 29, 2015. The Class Notes belongs to EECS 482 at University of Michigan taught by Staff in Fall. Since its upload, it has received 16 views. For similar materials see /class/231546/eecs-482-university-of-michigan in Engineering Computer Science at University of Michigan.
Reviews for Intro Oper System
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/29/15
EECS 482 Operating Systems Lecture Notes Department of EECS University of Michigan Professor Atul Prakash OS Security We looked at few aspects of operating systems security already 0 Isolating processes from each other 0 Separation between users and OS Basic aspects of security 0 Authentication proving who you are or verifying a service s identity 0 Access control controlling what a user is allowed to do once authenticated Some other aspects 0 Con dentiality may want to exchange or store data securely o Integrity may want to ensure that any tampering of data is detected 0 Availability preventing denialof service attacks 0 Threat model When designing a security solution you generally have to assume something about capabilities of the adversary You design a system to be secure against what you believe to be reasonable resources for an attacker Eg your house is secure when locked provided the adversary does not have the key or is able to replicate the key Additional assumptions may be required here Authentication 0 Passwords on accounts on operating systems 0 Why needed What is the threat model that passwords handle 0 Who veri es whom 0 ATM card or debit card PIN o Is this better than a password in some way 0 Biometrics ngerprint scans iris scans o How does compare with passwords With ATM PIN What if the user wishes to authenticate over a network One solution 0 Simulate a terminal over the network 0 telnet User ID password sent over TCP Remote OS login server sends accept or reject 0 Problems 0 Threat model assumes network is secure What if the network is not secure What can an adversary do on a network during network communication 0 Read messages attack on con dentiality 0 Modify or inject messages attack on integrity 0 Replay messages special case of modifyinject messages 0 Prevent delivery denialofservice 0 Drop messages Can be detected but hard to prevent o Saturate link to prevent message delivery hard to prevent 0 Spoof identity 0 Pretend to be the remote machine to the client and vice versa 0 Maninthemiddle attack 0 Combination of read messages and modify messages Guarantees we want to provide 0 Confidentiality 0 Integrity any modification of data even if done cleverly is detected Freshness no replay Authentication a form of integrity source integrity Solution rely on cryptography Basic functions 0 EncryptclearteXt ekey cipherteXt 0 DecryptcipherteXt dkey clearteXt For the above to work the ekey and dkey are chosen so that the above are inverses of each other DecryptEncryptclearteXt ekey dkey clearteXt Some necessary properties 0 Given cipherteXt must not be able to determine dkey 0 Given clearteXt cipherteXt must not be able to determine the keys Attacker may be able to obtain samples of both clearteXt and cipherteXt in some cases How 0 Given multiple cipherteth one must not be able to gure out anything about corresponding plainteth Bad encryption function 0 Ceaser cipher eg Rotl3 0 Easy to determine from cipherteXt and plainteXt pair 0 XOR 0 Why Good encryption functions 0 Generate randomlooking output from clearteXt 0 Even one bit change in clearteXt generates an uncorrelated output Symmetric encryption 0 dkey and ekey are the same The sender and the receiver share a common key The key can be used for both encryption and decryption Think ofa symmetric key as the key to a box It can be used to both open and close a box Using symmetric encryption sender and receiver share a common key No one else has the key 0 Ann can send a message to Bob after encrypting it putting it on a CD and send it through an untrusted courier Eve Guarantees provided 0 0 Con dentiality Eve does not have the key Can t decrypt it Authentication Bob knows the message from Ann if it decrypts properly Attacks on the above protocol 0 O O 0 Suppose Iwant to send you your grade securely I Encrypt A yourkey What can Eve an eavesdropper do I With reasonable assumptions he can t read Can he modify the message I Sure I But then you will get jibberish hopefully on receipt How will you know with con dence that the message is tampered with I You could try to interpret the message E g grades are AE Decrypting to anything else means tampering But what if this data is binary eg data block for a le system We want more robust and general purpose mechanisms 0 Detecting modi cations using checksums o I could include a checksum in the message I Encrypt A key l checksum e g checksum is a parity bit on encrypted message You would check the parity bit on receipt This does not work Why Still does not work if the parity bit is on clearteXt Why 0 I could include a long checksum or special value that you can verify on receipt where tampering would lead to the value failing to match Eg I Encrypt000000000 l A key On receipt you would check that the message contained the right checksum or special value Attacks on checksum I If the checksum is long enough the attacker is unlikely to be successful 0 E g with 128bit checksum odds of getting it right are 239128 for good encryption functions This is very small 7 attacker is unlikely to succeed even after many tries 0 Replay attacks are still possible however 0 Solution I Include a sequence number I Both sides must remember the sequence numbers 0 O Let s revisit the secure login problem between the client and a machine Client needs to provide his userid and password securely to the login service on the machine What key do the client and the server use Simplest thing 0 Use the password as the key Technically key is derived from the password because the password may not be the right length to be used as a key directly What sequence number does the client use 0 How about zero Is that secure Ann gt Server userid Encryptuserid lwish to login l 0 key 0 What about n1 where n is the sequence number used at previous login More general solution is to use nonces numbers that used only once Any reuse ofa nonce is detected Eg attempt Ann gt Server This is Ann Iwish to login noncel Server gt Ann Hi Ann prove your identity nonce2 Ann gt Server Ann EncryptAnn noncel nonce2 key Server gt Ann Success Encryptnoncell key Server is con dent that the Ann s second message is fresh because it encrypts nonce2 Ann is con dent that the server s second message is fresh because it encrypts noncel For the above to work noncel and nonce2 should be either sequence numbers nonrepeating or random values from a large space Otherwise the attacker could save lots of sessions and nd ways to replay an old session that used the same nonces Usually the goal of authentication is to establish a session key that is used for encrypting further exchanges The nal message from Server to Ann could contain a session key The session key should be a randomly generated key so that it is hard to guess for an attacker They could continue to use the password as the session key but generally it is a bad idea to use the same key too often Project 3 protocol It is a very simple protocol password used as a key for all exchanges Replays within a session are prevented because of persession sequence numbers Different clients distinguished using session numbers Session numbersequence number are like a nonce 9 any reuse is detected by the server But small changes could make the protocol very insecure 0 Suppose sessions were not active for the life of the le server Attacks may be possible on the current system as well 0 Identify them Hint related to the above question about session lifetime and server lifetime In real protocols 0 Bad idea to use longterm keys e g passwords for encrypting session data Instead use longterm keys for authentication only and to agree on session shortterm keys Subtle attacks have been discovered sometimes many years after a protocol is claimed to be secure Public key encryption ekey and dkey are not the same The keys must be related of course for them to work as matching encryption decryption keys This will be logically similar to symmetric key encryption if one key could be easily derived from the other 0 Possession of ekey would imply that you could get the dkey and vice versa In a publickey cryptosystem a pair ekey dkey is generated from some common seed data The seed data is then thrown away After that it is computationally hard to derive one key from the other 0 Possession of ekey does not lead to an easy discovery ofthe dkey even though they are related Typical use scenario Each person issued a dkey private key Make ekey public to the world public key of the person Often e g RSA encrypt decrypt We will just use crypt for both functions when using asymmetric keys Sending a con dential message to the person 0 Ann gt Bob cryptmessage Bob s ekey 0 Only Bob can read this message Digital signing 0 Bob gt Ann Bob cryptmessage Bob s dkey Ann and the rest of the world can verify that Bob must have sent the message No one else could have generated the crypt part Think of the crypt part above as a digitally signed message 0 Why include Bob in the message 0 Is the above different from Bob gt Ann Bob Encryptmessage symmetrickey of Ann and Bob Yes I Nonrepudiation Ann can prove to a thirdparty that Bob must have sent the message Only possible with asymmetric keys Asymmetric keys are typically much longer than symmetric keys to be resistant to bruteforce attacks on breaking the keys 0 Typical symmetric key lengths 128 bits 256 bits for really sensitive uses 0 Typical asymmetric key lengths 1024 bits 2048 for more sensitive uses 0 Keys are longer because the keys can be derived from each other if they are too short 0 Implication asymmetric key encryption and decryption is orders of magnitude times slower than symmetric key encryption I Wherever possible limit the use of asymmetric key operations unless absolutely needed Using public key systems for con dentiality and digitally signing both together 0 Ann gt Bob from Ann cryptcryptmessage Annprivate Bobpublic Would the following also work Ann gt Bob from Ann cryptcryptmessage Bobpublic Annprivate Is there a difference in security guarantees Ensuring integrity Sometimes one doesn t need confidentiality Only a way to verify that the data has not been tampered with by an attacker Using cryptographic hashes is an efficient way to do this Eg MDS is a cryptographic hash function It generates a 128bit message digest Try md5sum le on a Linux system Properties of good cryptographic hash functions They may in nite set of messages to a limited space eg 128bit value Thus collisions are possible But given the large destination space collisions should be very rare The function is oneway In other words given a hash value it is dif cult to nd a corresponding message However given a message it is easy to nd its hash Using cryptographic hashes in digital signatures clearteXt crypthashclearteXt authorprivatekey The above is much more ef cient to compute since hash is much shorter than clearteXt Veri cation Receiver computes hashclearteXt Receiver computes crypt2quotdpart of above message authorpublic key Receiver compares the above two values If they match message is signed correctly Else it is not Revising Password Veri cation on a Machine How does the OS know that a user has typed the correct password One possibility is for the OS to store every user s password on its local disk ala project 3 What are the risks with that A more secure solution 0 The OS stores ltuserid hashpasswordgt pairs 0 When a user types a password its hash is computed and looked up to see if it matches the stored value Linux does this It stores the hash in etcshadow les Also a good idea for designing secure web sites Web sites often get broken into You don t want someone to steal all the passwords Better to lose the hashes than the passwords Access Control Assuming that the user has authenticated the OS still needs to decide what rights to give to the user Given userid operation and an object the access control module will reply YES or NO Several ways to implement this Let s consider an example lel readwrite by Ann read by Bob and no rights for anyone else owner Ann le 2 owner Bob Readwriteexecute by Bob readexecute by Ann no rights for anyone else Access Control Matrix Onerow for each user One column for each object ACLs accesscontrollists Store column values for each le Capabilities store row values for each user In a capabilitybased system capability is often carried by the user Eg your passport a cash debit card your driver license your Michigan ID card Examples 0 Unix les and directories ACLbased but only limited sizeACL Owner rights rwx x means execute for les and the ability to enter the directory for directories Group rights rwx Other rights rwx Each ledirectory is associated with exactly one group The above examples are not easy to handle in Unix but can be handled using groups 0 For le 1 0 For le 2 0 What would be an example set of permissions on a le that cannot be handled in a Unix le system Sample commands ls 71 shows permissions chmod ugorwx le give readwriteexecute access to everyone chmod orwx le give no rights to others chown newowner le changes the owner Who should be allowed to do this chgrp newgrp le changes the group Who should be allowed to do this 0 AFS ACLbased But afull list afs setacl 7dir ltdirnamegt acl ltusernamelgroupnamegt ltpermissionsgt afs listacl setacl leaves existing permissions intact It is a delta on existing permissions lel file2 ACLs versus capabilities Capabilities are more portable User carries it Could be more appropriate for highly distributed systems Capabilities are harder to revoke E g risk of misuse of your passport or ID or gift card even if you cancel it The enforcement point must know that your capability is canceled 7 sometimes that knowledge does not propagate Harder to give public access with capabilities Every user s capability must be modi ed or ACLs used in some way in addition to capabilities Harder to take away a previously granted access to a user If the user has cash on their debit card hard for the bank to change the amount of cash Capabilities must be designed to be tamperproof Capabilities could be easier to give away in some cases eg give a gift card to a friend EECS 482 Operating Systems Lecture Notes Department of EECS University of Michigan Professor Atul Prakash Introduction Readings Tanenbaum Chapter 1 Sample questions this topic addresses What is an operating system and what does it do What is the difference between applications and an operating system What are system calls What is a Virtual machine Why should you be interested in studying them Do hardware and usage trends affected the design of operating systems Give examples of evolution of operating systems due to changes in hardware and its desired usage What is buffering multiprogramming spooling and time sharing and why did they become important What is an Operating System You learned about hardware in EECS 370 39 Interface Machine instructions program counter memory interrupts IO ops 39 Details registers CPU cache TLB clock etc You learned about programming in EECS 280 and 281 39 Executing programs using le and terminal 10 from CC programs etc 39 If your program crashes normally you do not have to reboot your machine 39 You can run multiple programs on the same machine email browser editor compiler 39 Question Could you do all the above in EECS 281 if you only had the hardware knowledge form EECS 370 What would it take OS as Virtual machine At a very highlevel operating system is the software that converts the hardware into something that the application programmers want It provides a virtual machine interface to the physical machine eturn w results Virtual machine System and user applications sical machine Ph Hardware CPU memory regs devices Virtual machine provides an easiertouse interface for interacting with the hardware in the form of system calls Examples The code that implements the system calls and interacts with the hardware is called the Operating System kernel When your C program is writing to cout or reading from cin your program is eventually invoking a system call to read from a device The details of how to read from the device whether it is a disk or a terminal are handled by the operating system Device drivers Help provide a software interface to a hardware device OS as a magician makes computer appear to be more than it really is each process appears to have its own machine with its own memory etc Usersprocesses are protected from each other How do we make that happen OS as a Coordinator of Resources Another way to look at an operating system is as a Resource Manager The OS has to give each application an illusion that it has dedicated hardware provide good performance even when some devices are slow not crash the entire system even if individual applications have serious bugs protect applications from each other and manage sharing of the hardware across different applications Why are Operating Systems interesting to study 39 Many different concepts come together in OS design 0 hardware efficient data structures software abstractions languages good software engineering reliability simplicity 39 Design of highperformance systems By studying operating systems you will learn a variety of techniques for getting around performance problems that you can apply in your work even if you are not working on an operating system code 39 Be a more sophisticated programmer You will learn how to write clientserver systems manage simultaneous access of servers by multiple users do basic network programming and understand performance implications of major design decisions Evolution of Operating Systems Operating systems keep changing over time depending on problems posed by the available hardware its performance and cost and what users wanted to do with the hardware In fact one very good way to understand what operating systems are today is to examine the history of how operating systems have evolved over the years What you will see is that concepts that were considered obsolete at one time can become current at a later time depending on how hardware is changing When looking at this evolution see if you can come up with your own predictions on how n current computing devices eg pcs PDAs cell phones will evolve as computing devices becomes faster smaller and cheaper History Phase 1 hardware expensive humans cheap Goal make or c t t i In the beginning user worked at CPU console to debug lights and switches one user at atime no overlap ofcomputation andl s rst eared as a subroutine library ofcommonlyused functions for doing 10 etc Source http vawcwlzardcomcwlzardlmagesumvaclglf Challenge CPU very expensive How to make more ef cient use of CPU 5 05 55555555555555 55555555 1555555 555555555 5555 555555 U555 5555555555 555 gm awayr 55 55555 5555555555 5555 3955 555 1555 5555 555555 55 55555 55 555 5 5555555555 5555555555 5555555 55 555555555 55 55555 5555 55 5555555555 55555555 cm 55 55 5555 55 5555555 555555 555 5555 5555555 55 555555 5555 555 5555 5555 campunnvelyvexydnw 5 555555555555 55555 55555555555515510 555555 5555 555555 5555555555 555 cm 55 55 55 55555555 cPU5555555 5555555 T5555 5555555 55555555555555 555551 05555555 05555 5555 55 5 5 5555555 5555 5555 5555 555 SPOOL 5555515555555 P55 5515155555 53555555 555555 05555 55 5555555 555 555555 555 5155 51555555 5555555 555555 5 5155155 5515155 55555 05 55555 5555 51555555555 3915 555 55 55551555 555555 Wh cPLv55555 5555155355 55551555555 F55 555m 5355 5 555 3915 555555 55 51555 55555555 3915 55k 555 15555 5 5155155 55155555555555 What is the key difference between disks and tapes Is CPU working on multiple jobs at a time Can multiple users submit jobs Why does the CPU throughput improve Do tapes still have to be carried backandforth BUFFERING Disks were ordersof magnitude faster than printers and card readers but still very slow compared to CPUs CPU would still be idle when trying to read or write bytes from a disk Memory buffers helped reduce that bottleneck o Writes CPU gt Memory buffer gt Slow disk device 0 Reads Slow disk or 10 deVice gt memory buffer gt CPU 0 What is the difference between spooling and buffering 39 Remaining problems 0 Still one job at atime so utilization often bad 0 No protection User job could overwrite the OS 0 Shortjobs wait for long ones Memory protection relocation OS runs in privileged mode and its memory protected from users As we will see later this required special hardware support 0 What things one should not be able to do in user mode ie only be able to do in privileged or supervisory mode Write anywhere directly to disk Write anywhere directly to memory 39 Multiprogramming several users share the system Small jobs nish fast 0 While one job is waiting for 10 to complete another job could be run Later the waiting job would continue from where it was suspended O 0 IO interrupts to tell the OS when IO was completed so that a waiting job could be resumed DMA directmemoryaccess to avoid having CPU be involved in small IO operations IO channels special IO processors could readwrite multiple bytes of data directly to memory and then interrupt the CPU only when the entire operation was complete 0 OS now had to manage interactions between concurrent things Memory management became an important issue so that memory could be shared between multiple jobs CPU scheduling also became important so that short jobs didn t have to wait much for long jobs OS es nally begin to be an important science People got interested in OS es because they didn t work eg Multics 08360 and still continue to be a challenge to make robust secure functional and reliable History Phase 2 hardware cheap humans expensive make more ef cient use of people time get people back closer to hardware Interactive timesharing o Terminals are cheap so let the user interact with the system 0 File systems now became necessary to enable interactive use via terminals History Phase 3 hardware becoming cheaper and faster humans expensive 39 Personal computing Computers are cheap put one in each terminal The OS became a subroutine library again at first eg Macs DOS just like early in Phase 1 Over time they added additional features that were found in multiuser systems such as Unix DOS gt Windows 31 gt Windows 95 gt Windows NT gt Windows XP History Phase 4 networking 39 Networking allow different machines to share resources easily Led to substantial work in distributed systems parallel computing etc Led to work on distributed file systems such as AFS and NFS storage can be anywhere OS administration tools for multiple machines common passwords etc etc Current trends 39 Question to think about what are future hardware trends likely uses of the hardware and how will it affect OS design Some examples 0 As computer became cheaper and smaller new computing deVices have since emerged programmable calculators and PDAs On PDAs the OSes again became singleuser and without multiprogramming 0 Storage is becoming essentially free a few dollars for a GB of storage What will it mean for le systems design 0 How will availability of highbandwidth in homes affect OSes Will we see more multimedia applications Will ensuring realtime performance so that there are no gaps in audiovideo become crucial o How will lack of sufficient bandwidth affect OSes on small devices as more functionality is added to them 0 How can OSes be made more secure and reliable Number of attacks on systems via the Internet have been exponentially increasing over the years 0 How can I provide seamless secure and efficient access to data and services in a mobile world Course Outline Operating systems have two general functions 39 Coordinator allow several things to work together in efficient and fair ways 39 Standard library virtual machine provide standard facilities that everyone needs Most of the lecture material will deal with the coordination aspect making many things work well together In projects you will see much more of the Virtual machine aspect Key things to be coordinated Managing multiple ongoing processes Several processes may request access to the same printer or ask to update the le system around the same time How does an OS ensure correct access when processes are running at the same time CPU how do we share one or more CPUs among multiple processes Memory Each process needs to use some main memory OS must coordinate their usage so they can share it How does it swap information back and forth between disk and main memory so the system can run even if the total memory needed by all processes is greater than the size of the memory How does it protect users from trashing each other s memory Files Each user owns a collection of les The OS coordinates how space is used for les so that they can all t on the same disk It also needs to protect les from unauthorized access Introduction to Processes and Threads Readings Tanenbaum 21224 Sample questions that this topic addresses What is a process and why is it a useful concept What is a thread and why is it useful What is the difference between a process and a thread Why two concepts Uniprogramming and multiprograrnming Process state versus thread state Examples from OSes Keeping track of processes and threads Running multiple threads on a single CPU Processes We want to run multiple jobs at the same time on a system Historically it was to make better use of the CPU IWith many things happening at once in a system need some way of separating them all out cleanly so that they are protected from each other and appear to be independent activities That is a process Important concept decomposition Given hard problem chop it up into several simpler problems that can be solved separately What is a process An intuitive de nition is just a running piece of code along with all the things that the code can affect or be affected by Key aspect of a process Processes protected from each other Each process is given the illusion that it has protected state What constitutes process state Is a process the same as a program Threads I What happens if a process needs to do multiple things in parallel 0 Editor waiting for input while doing some formatting or backup in background 0 A web browser fetching a document from a server while allowing user to interact with the displayed windows 0 A web server handling multiple user requests in parallel A thread can touch all the address space of its process no memory protection between threads within a process This is normally good we want threads to cooperate with each other I Why separate Threads and Processes I Creating threads normally a createithread call that takes a function pointer and a parameter as an argument I Thread status 0 Show a state diagram showing the state transitions between different status of a thread 0 Created Runnable Running Blocked Done Zombie Done I Thread State kept in thread control block 0 Some state shared by all threads in a process global variables address space open le handles 0 Some state quotprivatequot to each thread each thread has its own copy program counter registers execution stack What is the execution stack 0 Note that there is no enforced protection between threads in the same process A poorlycoded thread can overwrite the stack of another thread for example trashing it Example OSes MSDOS MacOS 1 address space one thread per address space Traditional Unix multiple address spaces one threadaddress space Mach Solaris VMS HPUX NT multiple address spaces multiple threads per address space Interthread and Interprocess communication Readings for this topic Tanenbaum Section 23 Questions Why do r threads need to 39 What are race conditions Why is atomicity important Independent Threads Independent thread one that can t affect or be affected by the rest of the universe Its state isn39t shared in any way by any other thread Deterministic input state alone determines results Reproducible Can stop and restart with no bad effects only time varies Example a program that sums the integers from 1 to 100 Cooperating threadsprocesses Machine must model the social structures of the people that use it People cooperate so machine must support that cooperation Cooperation means shared state e g a single le system shared among multiple user processes Cooperating threads are those that communicate Via share state Problem with cooperating threads 0 Results may be nondeterministic 0 They may not be easy to reproduce Debugging can be dif cult Example 0 one process writes ABC to the terminal 0 another process writes CBA to the same terminal What are the potential outputs on the terminal Are these cooperating processes How When discussing concurrent threads a single CPU vs multiple CPU does not matter Both lead to equally unpredictable results in the above example assuming that with a single CPU the contextswitch among threads can occur at any time 0 A given thread runs on only one processor at a time 0 A thread may run on different processors at different times move state assume processors are identical 0 Cannot distinguish multiprocessing from multiprogramming on a very fine grain Basic assumption for multithreaded programs is that the order of some operations is irrelevant certain operations are independent of certain other operations Only a few things matter Example A 1 B 2 has same result as B 2 A 1 Another example A Bl B 2B Results depend on the order of operations Another example suppose A l and A 2 are executed in parallel What can be the final value of A Ifthe results of execution depend on the order of execution of threads we have a race condition Don39t know what will happen depends on which one goes fastest What if they happen at EXACTLY the same time with multiple CPUs Can t tell anything without more information Could end up with A3 Atomic operations Before we can say ANYTHING about parallel threads we must know that some operation is atomic ie that it either happens in its entirety without interruption or not at all Cannot be interrupted in the middle Key point If you don39t have an atomic operation you can 39t make one Fortunately the hardware guys give us atomic ops References and assignments are atomic in almost all systems AB will always get a good value for B will always set a good value for A but not necessarily true if A and B are arrays or records Example 1 Suppose initially A 2 B 3 Thread 1 A B if A cout ltlt they are equal else they are not equal Thread 2 B A1 Can you predict what will be printed by Thread 1 Can you state possible final values of A and B Which of the following A B values are possible That can really make debugging multithreaded programs hard because by looking at just one thread we cannot say anything about the values of variables at any statement Of course the above is not a very interesting example because the code does not seem to be doing anything useful Consider the following examples where threads do need to cooperate more closely Example 2 bank transfer example Two people use an ATM card for the same account to initiate a withdrawal of 100 almost simultaneously A thread is created to execute each transaction The account has 150 in it initially What can potentially happen if the two threads execute the following code Thread 1 if savings gt 100 savings savings 100 Thread 2 if savings gt 100 savings savings 100 Is it possible that both people end up withdrawing 100 Is bank guaranteed to detect the problem Example 3 Computerized milk buying Too much milk problem Anne Bob look in fridge look in fridge if no milk if no milk go to Kroger go to Kroger Buy Milk Buy Milk Put milk in fridge Put milk in fridge The following execution is possible What is needed to address the above problems If you have any atomic operation we need to be able generate higher level atomic operations and make parallel programs work correctly This is the approach we ll take in this class Example 2 revisited Thread 1 begin atomic operation if savings gt 100 savings savings 100 end atomic operation Thread 2 begin atomic operation if savings gt 100 savings savings 100 end atomic operation Now no multiple withdrawals will be possible Some terminology 0 critical section A section of code that only 1 thread can execute at once eg the code The code appears to execute atomically even though other threads may execute in parallel Critical sections have the following required property 0 mutual exclusion Only only 1 thread must be allowed to execute in a critical section at a time others must be prevented from entering the critical section Thus only 1 thread accesses and updates the savings variable at a time 0 vacation property If a thread is outside the critical section ie on vacation other threads should not be prevented from going into the critical section 0 no speed assumption No assumptions should be made about relative speeds of threads or the number of CPUs 0 A thread should not have to have to wait forever to enter the critical section In the banking example we want the two lines of code in the threads to form a critical section Solution to the critical section problem Locks A lock 0 prevent someone from doing something e g before shopping leave a note on the fridge Three elements of locking 0 must aqcuire lock before doing something e g entering critical section accessing shared data 0 must release lock unlock when done 0 must wait to acquire if someone else has it locked Example 3 revisited In general wherever shared variables are manipulated you need to worry about using locks to make a set of statements atomic ie turn them into a critical section How to implement ocks Suppose that for now we restrict ourselves to only using atomic load and store operations as the building block Let s discuss the computerized milkbuying problem Too Much Milk Solution Attempt 1 basic idea 1 leave a note if you re going to buy milk remove note when you return 2 don t buy if the other person left a note Example 3 revisited Use a note Wait until there is no note Leave a note before entering the critical section Solution Does this work in the computerized world At this point before reading on you should try to improve the solution and make it correct Some possible solutions that you may come up with Toomuchmilk Solution Attempt 2 What if we use two notes and make Anne and Bob hang around to make sure they enter the critical section Anne Bob NoteAnne true NoteBob true whileNoteBob loop while NoteAnne loop if no milk if no milk Buy Milk Buy Milk NoteAnne false NoteBob false ritical section requirements satis ed Toomuchmilk Solution Attempt 3 Strict alternation What if Anne and Bob alternate Then there will be no deadlock Anne Bob whileAnneTurn loop if no milk Buy Milk AnneTurn false while AnneTurnloop if no milk Buy Milk AnneTurn true The above enforces the mutual exclusion condition Prove it Any problem with the solution Toomuchmilk Solution Attempt 4 Peterson s Solution If we combine solution 2 and solution 3 we can come up with a correct solution The idea is to break ties using turns only if we run into a deadlocklike situation Anne Bob NoteAnne true turn Anne whileNoteBob ampamp turn Anne loop if no milk Buy Milk false NoteBob true turn Bob whileNoteAnne ampamp turn Bobloop if no milk Buy Milk NoteBob false proof of correctness Correct but the solution is ugly 0 complicated hard to convince yourself that it s right 0 while Bob or Anne are waiting they consume CPU time in the while loop This is called busy waiting Busy waiting is bad 0 Hard to see how to generalize the solution to more than 2 threads Fortunately there is a better way 0 have hardware provide better higherlevel primitives than atomic load and store we ll cover this next 0 the OS provides higherlevel abstractions for implementing critical sections based on this new hardware support eg locldunlock lock atomically wait til lock is free then grab it unlock release lock let anyone who39s waiting for it try Lock acquirerelease must be atomic If two threads are waiting for the lock and both see it s free only one grabs the lock locks make quotToo Much Milkquot really easy to solve Anne or Bob Lock mutex global shared lock to both Anne and Bob mutexlock if noMilk buy milk mutex unlock Semaphores Questions What are the requirements for a locking mechanism Waiting for conditions why we need another kind of synchronization besides locks Semaphores a single mechanism to implement both locks and conditional waiting How to solve the Producer amp Consumer Bounded Buffer problem using semaphores Brie y look at another example Readers and Writers Problem Motivation The toomuchmilk solution is much too complicated The problem is that the mutual exclusion mechanism was too simpleminded it used only atomic reads and writes This is suf cient but unpleasant It would be unbearable to extend that mechanism to many processes Let s look at more powerful higherlevel mechanisms and what they need to do Implementing Critical Sections We need to be able to implement critical sections Some requirements for critical section mechanism Mutual Exclusion Only one process should be executing in a critical section at a time Progress If several requests at once must allow one process to proceed Vacation Property Processes must be able to go on vacation outside critical section Desirable properties for a mutual exclusion mechanism 0 Bounded waiting no starvation there must eXist a bound on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted Ef cient don t use up substantial amounts of resources when waiting E g no busy waiting Simple should be easy to use eg just bracket the critical sections Rules for processes using the mechanism 0 Always lock before manipulating shared data 0 Always unlock after manipulating shared data 0 Do not lock again if already locked 0 Do not unlock if not locked by you 0 Do not spend large amounts of time in critical section Having a lock primitive provided by the OS would address the problem Lock mutex global shared lock to both Anne and mutex lock start of critical section if noMilk buy milk end of critical section mutex unlock We will see later how to implement locks efficiently In fact you will be doing that in Project 1 Another need for a mechanism Scheduling Unfortunately locks alone are not adequate for threads to work together Consider the following problem This problem is important Producer amp Consumer Problem also called Bounded Buffer problem Often one thread creates information that needs to be used by another thread as shown in the following picture data 1 Data 2 Data 3 Data A Data 5 em l em l eml em l empty in y p y p y p y Read next data Add next data omt 9 buffer to the buffer Consumerthread Producer thread Producer thread repeatedly adds items to the buffer Consumer threads empties the buffer by reading items from it Examples of bounded buffer problem OUniX pipes tar cf foo gzip gt footargz The tar process writes its output to a shared buffer The gzip buffer reads from the buffer There is one producer thread tar and one consumer thread gzip 0 Servers One thread receives requests from clients and puts them in a buffer queue One or more service threads grab requests from the queue and process them There is one producer thread one receiving the requests and multiple consumer threads the service threads that execute the requests 0 Printer spooler Multiple processes send les to a printer The les are queued in a spooler directory A printer process grabs les from the queue and prints them In this case there are multiple producers processes sending les to the printer queue and one consumer printer process In general there could be multiple producer threads writing to the shared buffer and multiple consumer threads reading from the shared buffer as illustrated in the above examples Also in some cases the shared buffer may be an unbounded queue rather than a bounded queue Producer and consumer threads shouldn t have to operate in perfect lock step producer should be able to get ahead of consumer Correctness constraints 0 Mutual exclusion 0 Scheduling We can implement mutual exclusion using locks How do we implement the scheduling constraints One possibility to address a scheduling constraint 0 If buffer is full producers periodically check for a buffer to empty This involves busy waiting 7 not very good A more ef cient mechanism that has been proposed is semaphores This was invented by Edsger Dijkstra a Dutch computer scientist in the mid 60 s Semaphores can be used to implement both locks and enforce scheduling constraints A semaphore s is an OSprovided object that has a value gt 0 and provides two operations to threads sdownO or sP The thread waits for semaphore to become positive and then atomically decrements it by l Proberen in dutch means down sup or sV The thread atomically increments semaphore by l verhogen in Dutch means up Note that if one or more threads is waiting for the semaphore value to become positive in sdown doing a sup operation will cause one of the threads executing the down operation to complete the down operation Implementing mututal exclusion using semaphores Mutual exclusion can be easily implemented using semaphores All we need is a semphore s that is initialized to the value 1 0 To acquire a lock do a sd0wn 0 To release a lock do a sup Too much milk problem with semaphores Show why there can never be more than one process buying milk at once Boundedbuffer problem using semaphores You can nd solution to the boundedbuffer problem in Tanenbaum I will present a different solution here that may be conceptually simpler and easier to see how to apply it to other problems As mentioned earlier there are three constraints to enforce one mutual exclusion constraint and two scheduling constraints Mutual exclusion constraint can be enforced using a binary semaphore mutex as in the too muchmilk problem To enforce the two scheduling constraints we need to create one additional semaphore for each constraint 0 OkToProduce This semaphore is initialized to number of empty locations in the buffer 0 OkToConsume This semaphore is initialized to 0 ie number of full locations in the buffer initially The solution is as follows Producer Threads Consumer Threads produceItem get an item to add OkToProduce down mutexdown bufferadditem mutexup OkToConsume up consumeI tem 0kToConsumedown mutexdown item bufferdeleteItem mutexup 0kToProduceup consume the item Important questions discussed in the lecture 0 Why does producer do OkToProducedown but OkToConsumeup Is the order of down s important Is order of ups important How would this be extended to have multiple consumers and multiple producers Semaphores aren t provided by hardware I ll describe implementation later But they have several attractive properties Machine independent Simple Work with many processes Can have many different critical sections with different semaphores Can acquire many resources simultaneously multiple P s Can permit multiple processes into the critical section at once if that is desirable Key Idea is layering pick some powerful and exible intermediate primitive to implement in the OS and apply to a large number of problems The primitives in this case are the operations are create a semaphore with an initial nonnegative integer value up operation on the semaphore down operation on the semaphore Note that we do not need an operation to read or write the value of the semaphore In fact we do not want such an operation Only up and down operations are sufficient for all thread synchronization needs Another Classical Problem Readers and Writers Problem this is optional for the lecture but you should go through it and ask TAs to discuss it if needed Another example of semaphore usage a shared database with readers and writers It is safe for any number of readers to access the database simultaneously but each writer must have exclusive access Must use semaphores to enforce these policies Example checking account Note that writers are actually readers too Scheduling constraints that need to be enforced among threads 0 Writers can only proceed if there are no active readers or writers use semaphore OKToWrite 0 Readers can only proceed if there are no active or waiting writers use semaphore OKToRead Note that we don t want to make the access to the entire database as a critical section because then only one reader will be able to read at a time We want multiple readers to be able read the database simultaneously 7 results in better response time for readers since a short read does not have to wait for a long read to complete To enforce scheduling constraints we need to keep track of who39s reading and writing We thus introduce some shared variables to track that information 0 AR number of active readers 0 initially 0 WR number of waiting readers 0 initially 0 AW number of active writers 0 initially 0 WW number of waiting writers 0 initially Variables introduced to enforce scheduling constraints are sometimes called state variables These variables will be read and written by multiple threads We thus must introduce a mutual exclusion constraint to make sure that only one thread manipulates state variables at once we will use a semaphore MuteX for this Initialization of semaphores 0 OKToRead 0 0 OKToWrite 0 0 MuteX 1 Our strategy in implementing readers and writers will be to always check the state variables before deciding to access the database If it is not OK to access the database then a reader will do a down operation on OkToRead and a write will do an up operation on OkToWrite When the read is completed by the last reader the reader will be responsible for waking up one waiting writer if there is one When the write is completed by a writer it will wake up all waiting readers allowing them to read the database The readers and writers execute the following code Reader threads Writer threads getreadaccess getwriteaccess read data write data releasereadaccess releasewriteaccess N 0 te that access control on the database is enforced in the two procedures getireadiaccesso and getiwriteiaccesso The other two methods are called by the threads to inform the enforcement mechanism that the operation is completed The code for the procedures is as follows getreadaccess MuteXdown mutual exclusion constraint on state variables if AWWW 0 AR AR1 a new reader being activated OkToReadup give advanced read permission to self else WR WR1 Mutexup end mutual exclusion constraint OkToReaddown wait until permission granted releasereadaccess enforce mutual exclusion constraint one less active reader Mutexdow wake up a writer if appropriate AR ARl if ARO ampamp WWgtO OKToWriteup important to remember that we woke W AW1 WW WW1 up a writer before releasing muteX lock MuteXup finished updating state variables getwriteaccess0 mutual exclusion enforcement Mutexdown wait until no one else active if AWAR O I OkToWriteup give advance permission to self tell others that we are waiting else WW WWl done accessing state variables Mutexdown OkToWritedown wait until permission to write releasewriteacess Mutexdow AW if W AW1 WW WW1 else no writer activated wake up waiting readers while WR gt O OKToReadup wake up one waiting reader WR WRl Mutexup Try going through several examples and gure out what happens 0 Reader enters and leaves system 0 Writer enters and leaves system 0 Two readers enter system 0 Writer enters system and waits 0 Reader enters system and waits 0 Readers leave system writer continues 0 Writer leaves system last reader continues and leaves Questions to think about work it out yourself 0 In case of con ict between readers and writers who gets priority 0 How would you change the solution so that the priority is switched Can readers or writers get locked out if other threads keep coming in Can you change the solution so that lockout does not occur hint have new readers give priority to any waiting writers and have writers give priority to any waiting readers Can the lines incrementing AR and decrementing WR in releaseiwriteiaccesso be moved to getreadaccess just after the OktoReaddown Can OKToRead ever get greater than 1 What about OKToWrite Is the rst writer to execute MuteXdown in getwriteaccess guaranteed to be the rst writer to access the data Thread Synchronization with Monitors Let s revisit the producerconsumer example The original problem that we were trying to solve was to address two concerns 0 Provide a locking mechanism for implementing critical sections 0 Provide a way for enforcing scheduling constraints such as a consumer having to wait until there is full slot in the buffer With semaphores we can solve the problem but the solution is not as intuitive as it can be The use of a counting semaphore works but it is not straightforward to see how to apply it to solve more general scheduling constraints For example if we wanted a consumer to proceed only if there was M items in the buffer it is not easy to see how to use a semaphore to model that situation Monitors provide a simpler solution for enforcing locking and scheduling constraints The key idea is to provide separate mechanisms for the two different types of constraints locking and scheduling Locking Mechanism To implement critical sections monitors provide methods to create lock objects and to acquire and release locks For example Lock mutex mutexlock critical section code mutexunlock Usually only one lock is used to enforce mutual exclusion on related operations Condition variables Queues to wait on To enforce scheduling constraints monitors provide methods for threads to wait in a queue when the shared state does not permit progress and for other threads to wake them up when the shared state is appropriate for progress of the waiting threads Queues on which threads wait are identi ed by names called condition variables Note that condition variables are not really variables that can be assigned values but objects to wait on The only methods allowed on a condition variable c are 0 cwaitLock mutex release monitor lock put thread to sleep on a queue c When the thread is woken up Via csignal or cbroadcast it reacquires monitor lock and then continues in the critical section code 0 csignal39 wake up one thread waiting on the queue c typically FIFO If no threads are waiting 0 signal has no ef ect no history 7 this is very different from semaphore up operation which has history 0 cbroadcast39 wake up all threads waiting on the condition variable queue c If no threads are waiting do nothing no history As a general principle all these three operations must be called in the critical section protected by the mute lock A typical pattern for a thread that needs to wait for some condition to become true is Lock mutex ConditionVariable cv othercv mutexlock always the 1 step 2mi step below is optional Only there if there is a scheduling constraint that forces a wait while shared state does not satisfy the scheduling constraint cvwaitmutex assertion synchronized constraint is satisfied 3m step update shared state and state variables if necessary code for with the shared state 4U1 step wake up another thread if shared state may permit another thread to progress if scheduling constraints of others potentially satisfied othercvsigna1 othercv identifies the constraint queue mutexunlock always the last step In the above code cv and othercv are two queues on which threads can potentially wait Each thread rst acquires a lock before going into the critical section Then it waits until any scheduling constraints are satis ed by calling the wait primitive on the condition variable 0 The semantics of wait is that the waiting thread releases the mute lock while it is waiting and reacquires it sometime after it is woken up and before it continues in the critical section After the thread wakes up from the wait just to be sure that nothing has gone wrong between the time it wakes up and the time it reenters the critical section it re verz39 es that the scheduling constraint is satis ed before continuing Otherwise it goes back to waiting 0 Why reverify After the scheduling constraint is satis ed the thread continues in the critical section First it makes any updates to the shared state Then it wakes up any other threads for which the scheduling constraints can be satisfied Finally it release the critical section lock The above pattern largely works for almost all thread synchronization problems We illustrate it on two classical problems below Producerconsumer Problem Using locks and condition variables we get a fairly intuitive solution to the producerconsumer problem Lock mutex ConditionVariable OkToProduce Queue buffer shared state variables to enforce int numEmpty N number int numFull O Number critical section lock OkToConsume queues for waiting buffer scheduling constraints of empty slots in the buffer of full slots in the buffer produceItemItemType item Item consumeItem mutexlock while numEmpty 0 0kToProducewaitmutex bufferadditem numEmpty numFull 0kToCbnsumesigna1 mutexunlock Go through several scenarios to show that the above solution works 01mportant Question Is while loop to reverify the scheduling constraint necessary NOTE There is a difference from the book here There two basic variations of the wait signal mechanism Hoare semantics and Mesa semantics Tanenbaum like many OS texts describes only Hoare s semantics in its code simply because it was proposed first historically Key difference between the two is 0 In Hoare s semantics signalled thread continues 0 O O Signaling thread releases the mute lock immediately and the signaled thread continues The signaled thread is guaranteed to be the next thread in the monitor Thus provided it was woken up when its scheduling constraint was satisfied the signaled thread does not need to recheck the scheduling constraint Because of the guarantee we can often use an if statement to check the scheduling constraint rather than the while loop 0 In Mesa semantics signaller continues 0 O Signaling thread does not release the mute lock It continues in the critical section At some later point possibly much later the signaled thread enters the critical section when the lock becomes available However other threads could sneak in into the critical section before the signaled thread eg someone else buying the JC Penney shirt before you get there The scheduling constraint could thus become false by the time the signaled thread runs Thus while loop is essential to recheck scheduling constraint before continuing Almost all real implementations use Mesa semantics because it is the most practical to use and implement In this course we will always use Mesa semantics unless otherwise speci ed This is different from the textbook Convince yourself that the code works when consumers block due to scheduling constraints Does the code work when there are multiple producers and consumers Can signals be replaced by broadcasts 0 Would it be OK to check the scheduling constraint rst and then acquire the lock In other words switch step 2 and step 1 Question How do cwait and csignal compare to semaphore up and down Reader and writers problem with monitors Procedures which require synchronization between them are declared as monitor procedures The entry procedures are 0 getreadaccess 0 getwriteaccess 0 releasereadaccess 0 and releasewriteaccess Writer threads do the following in sequence 0 call getwriteaccess this must block until safe to write 0 update the database when getwriteaccess returns 0 call releasewriteaccess Reader threads do the following in sequence 0 call getreadaccess this must block until safe to read 0 read the database when getreadaccess returns 0 call releasereadaccess Scheduling Constraints 0 Need a way for reader to block in getireadiaccesso if a writer is currently active or waiting we give priority to writers in this solution To enforce 0 Use the condition variable OK ToRead 0 state variables AW and WW for of active and waiting writers 0 Need a way for writer to block in getiwriteiaccesso if a reader or writer is currently active 0 Use the condition variable OK ToWrz39te 0 state variables AR for active readers Question Is the database access itself in a critical section Answer As a rule 0 all monitor procedures need to use a mute lock wait signal and broadcast need to be called in the critical section 0 state variables are shared Thus they should only be manipulated in the critical section See the solution below Lock mutex ConditionVariable OkToRead OkToWrite int Aw 0 I R 0 0i void getreadaccessU mutexlock step 1 acquire lock step 2scheduling constraint while AWWW gt 0OKToReadwaitmutex step 3 update state variables AR no step 4 no one to wake up step 5 release lock mutexunlock void releasereadaccess mutexlock step 1 step 2 no scheduling constraint step 3 update state variables AR step 4 wake up anyone necessary if ARO ampamp WWgtO OKToWritesignal mutexunlock step 5 void getwriteaccess mutexlock step 1 acquire lock step 2 enforce scheduling constraint while AWAR gt O WW OKToWritewaitmuteX WW step 3 update state variables AW no one needs to be woken up step 5 release mutex lock mutexunlock void releasewriteaccessO mutexlock step 1 acquire lock step 2 no scheduling constraint for this method step 3 update state variables One less active writer A wake up anyone that can potentially progress OKToReadbroadcast multiple readers can progress mutexunlock step 5 release lock Can the while loops be replaced by if conditionals Note that we are using Mesa semantics Could all of the signals be broadcasts Is WW and WW7 necessary in getiwriteiaccess Exercise for you how would you modify the releaseiwriteiaccesso code so that waiting readers are given priority over waiting writers Hint do you need an additional state variable Where would that state variable be updated Thread Implementation We ve been talking about 0 using threads concurrency 0 getting them to cooperate 0 using sempahores or monitors to enforce mutual exclusion constraints and scheduling constraints Today we ll talk about how one actually builds them This material is very relevant to Project 1 First note how a process is laid out Process 0 body of code 0 global data 0 one or more stacks one per thread Implementing threads Each thread has illusion of its own CPU Yet on a uniprocessor all threads share the same physical CPU How does this work We need to be able to do the following operations on threads Thread state Need to save the state of the thread somewhere when it is not running That structure is called the Thread control block It consists of everything that could be potentially overwritten by another thread Queues With a single CPU only one thread can run at a time When a thread is not running put it actually its TCB on a queue Ready queue contains threads that are runnable Condition variable queue one per condition variable contains threads that are waiting on a condition variable Lock queues one per lock contains threads that are waiting to acquire a lock 10 or timer wait queues contains threads that are waiting for events such as 10 completion or timers to expire You do not have to implement these in Project 1 When a thread is created it is put on the ready queue The OS would run threads from the queue one by one according to some scheduling policy One possible policy is to simply run threads in order from the queue A thread essentially either runs or get moved to a queue after its state is saved in its TCB Example Thread creation thread forking Let s say that a thread needs to be created that will call fooarg We need to allocate a stack and TCB for the thread and make it call foo When it is has completed foo we need the thread to destroy itself The sequence of operations are 0 allocate a stack for the thread 0 create and initialize a TCB for the thread with SP pointing to the new stack Put the name of the function to be called and its argument on the stack set its PC in the TCB to point to a special function startThread so that the thread will call startThreadfoo arg startThread is responsible for calling fooarg and cleaning up thread s state when the call to fooarg returns startThread never returns 0 Why shouldn t the PC be initialized to the code for fooarg 0 Similar thing happens with the main thread inside a process The main thread would start with a special procedure startProcess which calls mainargc argV and then marks the thread as DONE so that it can be later deleted by the OS 0 Add the the TCB to the Ready Queue atomically The new thread will run sometime in the future Question Does the last operation need to be atomic Switching Threads We switch threads when interrupts such as timer events occur thread needing to block on locks or condition variables traps eg divide by 0 voluntary yield threadiyield IO requests Below we will just look at how switching on voluntary yields can be implemented On yields we need the current thread do something like the following scheduleAnotherThread Turn off interrupts t next thread from the ready queue Current thread puts its TCB at the end of the ready queue SWITCH the current thread with thread t so that t starts running SWITCHt the new thread now is running Old thread will continue from here later when it is switched back Turn on interrupts SWITCHt does the following 0 pack up the current thread s state in its TCB unpack the state of the new thread t from its TCB Thus t automatically continues from where it was saved 0 Packing a thread s state into its TCB 0 We need to save all the thread s registers tricky since you need registers to do the saving Must be done in assembly very carefully without overwriting the registers that you are trying to save Question Why does the scheduleAnotherThreadO operation need to be made atomic by turning off interrupts Think about what would happen if there was a context switch to another thread in the middle because of an interrupt Question Can interrupts be enabled just before doing the SWITCH Thus we do a SWITCH while interrupts are still off The rule is that all threads always call SWITCH while interrupts are off and turn on the interrupts after the SWITCH Thus the other thread will turn on interrupts Thread A Thread B disable interrupts SWITCH schedule B gt back from SWITCH enable interrupts disable interrupts SWITCH lt back from SWITCH enable interrupts If you just look at Thread A s column you will notice that SWITCH appears like a normal procedure call to A except that between the time it is called and the time it returns many other threads can run Also notice that interrupts appear to be turned off and turned on correctly in Thread A despite the fact that thread B ran during the SWITCH Also notice that interrupts were turned on correctly while B was running Basic Rule again Interrupts must be turned off sometime before the switch is called They must be turned on sometime after the switch Thread Termination The key difference with thread yielding is that the current thread should not put itself on the ready queue before the SWITCH Also it should mark itself as ToBeDestroyed prior to the SWITCH The thread that runs next should clean up any ToBeDestroyed threads 0 The current thread marks itself as quotToBeDestroyedquot 0 if another thread is waiting for you to terminate put it on the ready queue useful for implementing thread J 0in operation 0 Thread puts itself to sleep by calling sleep 0 mark your status BLOCKED 0 nd another thread to run from the ready queue 0 Switch to the other thread Note a thread can t destroy itself eg its own stack Why not Locks Attempt 1 One bad but correct solution Atomic loads stores as in Peterson s solution Has busy wait and thus inefficient Works but not good and no reason to use it Attempt 2 run user code with interrupts disabled lock disable interrupts unlock enable interrupts then user program can call lock unlock around critical section Many problems Attempt 3 main idea waiting thread gives up processor goes on the lock queue until woken up by someone releasing the lock class Lock ThreadQueue q int value BUSY or FREE Lock lock Lock unlock Note that sleep has similar code to threadiyield except that the current thread is not put on the ready queue sleep also switches threads by using SWITCH Q why does lock check value in a while loop Won39t it only get woken up by the unlocker so it knows lock is free Q Can lock reenable interrupts before going to sleep Why would the solution break 1 before putting thread on wait queue scenario that breaks this 2 after putting thread on wait queue but before going to sleep scenario that breaks this Thus we must leave interrupts disabled when a thread calls sleep The next thread to run has the responsibility of reenabling interrupts See picture earlier for SWITCH Question With the above solution are threads guaranteed to get locks in the order that they request the locks Question Modify the solution so that threads are guaranteed to get locks in the order that they request them Condition variables This is something for you to gure out and implement In implementing the waitmuteX operation think very carefully about where interrupts should be disabled and enabled And recall from the monitor lecture that the wait operation should rst cause 1 the mute lock to be released and 2 the thread to be added to the condition variable queue Then the thread should sleep ie switch execution to another thread When the thread is woken up by a signal it should always reacquire the mute lock Locks on Multiprocessors On a multiprocessor system usually disabling interrupts on one CPU does not disable interrupts on other CPUs Thus disabling interrupts to ensure atomicity does not work Threads on other processors will continue to run Fortunately every modern processor architecture provides some kind of atomic readmodifywrite instruction Atomically 0 read value from memory into register 0 write new value Examples of atomic readmodifywrite instruction 0 testampset most architectures O writes quotIquot to a memory location quotsetquot returns the value that used 0 to be there quottestquot 0 note that only 1 thread can get transition from 0gtl Other threads will simply go from lgtl 0 exchange X86 swap value between register and memory Here is a solution using atomic testampset instruction initially value O lock while testampsetvalue 1 unlock value O A more ef cient solution Don t busy wait for the a thread s entire critical section Instead use waiting queues Replace disabling of interrupts by testampset locks Look at the the attempt 3 for locks earlier and compare with solution below lock while testampsetguard this is like quotinterrupt disablequot while value put on queue of threads waiting for lock go to sleep value BUSY guard 0 this is like quotinterrupt enablequot unlock while testampsetguard like interrupt disable operation earlier value FREE if anyone on queue of threads waiting for lock take waiting thread off queue put on ready queue guard O this is like quotinterrupt enablequot