Operating Systems CS 5523
Popular in Course
Popular in ComputerScienence
verified elite notetaker
This 83 page Class Notes was uploaded by Mireya Heidenreich on Thursday October 29, 2015. The Class Notes belongs to CS 5523 at University of Texas at San Antonio taught by Dakai Zhu in Fall. Since its upload, it has received 12 views. For similar materials see /class/231377/cs-5523-university-of-texas-at-san-antonio in ComputerScienence at University of Texas at San Antonio.
Reviews for Operating Systems
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/29/15
CS 5523 Operating Systems Instructor Dr Dakai Zhu Topics Security c um swmuug 29552 mum System 5mg mcmpmm mamswmwwm bwm KaiA mm i About Midterm Exam II and Project 4 S Midterm statistics 8 Project 4 QuestionsDiscussion C 0139 2 Svunvzmg 25552 Dveiatmvsvstnms 5mg incaivmatn makiiabkmdivviwided bwm mm mm Outline 8 ThreatsAttacks in distributed systems 8 Cryptography symmetric vs asymmetric gt Authentications with symmetricasymmetric keys 3 Secure hash function and digital signature 3 Certificates and authority 8 Key establishment and distribution 8 Kerberos architecture 8 Transport Layer Security Svnnvzmg 25552 Dvevalmvsysfnms slides incaivmak maknabkmdlyviwmed bwm mm Rubbing ThreatsAttacks in Distributed Systems Principal user Network Principal server 36 Interception information leakage eavesdropping 38 Interruption service interference denial of service 38Modification unauthorized modification tampering 8 Fabrication fake information masquerading C 0139 Svnnvzmg 25552 awninst maknabkmdlyviwmed bwm mm Rubbing Policies vs Mechanisms 38 A security policy specifies limits for accessing and sharing resources St A security mechanism enforces or implements a security policy General strategy Policy should be speci ed separately from mechanism Give an example of policy versus mechanism for the computer labs Is the access list a policy or a mechanism C UT Svnnvzmg 25552 Dvevatmvsvstnms slats incaivmatn makviabkmdlyviwmed bwm KaiA Rubbing u Secure Channel Cryptography The enemy WVCiDalB ecure c anne 8 Properties J t u l L L natai 39 39 integrity 6 Employs cryptography J 39 39 y base 39 d on quot39 JAuthentication based on proof of ownership of secrets C 0139 w Svnnvzmg 25552 Dvevatmvsvstnms slats incaivmatn makviabkmdlyviwmed bwm KaiA Rubbing u Overview of Cryptography 3t Cryptography study of processes that encode amp decode messages to hide their information Example quotJ mjlf PTquot 6 shift 19 I like OS X Basic techniques gt Symmetric the same secretshared key gt Asymmetric pair public amp private keys gt Algorithms are known keys are different and must be computationally hard to solve to remain secure Example shift 1 3 Application of cryptography techniques gt Authentication the message comes 39om the one it supposes to be gt Secrecy integrity the message is NOT leakedchanged gt Digital signature HTS Svnnvzmg 25552 mmmsvsm slides Mimi mutusmmwwm bwm KaiA Rubbing 7 Cryptography and Intruder Passive intruder Active intruder only listens to C can alter messages Active intruder can insert messages Piaintext P Encryption Decryption Sender key EK key DK Receiver u Svnnvzmg 25552 mmmsvsm slides Mimi mutusmmwwm bwm mm Rubbing Protagonists amp Notations in Cryptography Alice First participant Bob Second participant Carol Participant in three and fourparty protocols Dave Participant in fourparty protocols Eve Eavesdropper Mallory 39 Sam A server KA Alice s secret key KB B ob s secret key KM Secret key shared between Alice and Bob KA39 Alice s private key known only to Alice KA Alice s public key published by Alice for all to read MK Messaglv encrypted with le lug SW m MK Messaglr signed with 1 K7 9 Symmetric SecretShared Key Encryption 3 For symmetric key encryption gtE encryption algorithm gtD decryption algorithm gtSame key K for E and D Encrypted message EK M MK Decrypted message DKi EK M DK MM M vainvzmg csaaza Dveiaiinvsvstnms siides momma mantisskmalywwnea bwm KaiA Rubbing in Symmetric Key Encryption cont 8 Requirement for symmetricshared key encryption gt M must be hard to get from WK if K is not known 88 Hard computational hard possible gt Usual attack form bruteforce try all possible key values for a known pair M MK gt Analyze encrypted messages patternfrequency of phrases 88Make K sufficiently large 128 bits gtTake years to get the solution not useful by that time 36 For the example shiftKM gttry all possible values of K from 1 to 26 C UT 1 i vainvzmg csssza Dveiatinvsvstnms slides incaivmak makiiabkmdlyviwided mm mm minis Shared Key Encryption Algorithms 38 Typical shared key encryption algorithms gt TEA tiny encryption algorithm s uses 32 rounds with combinations of XOR text sniits 128bi key gt DES Data Encryption Standard 56bit key gt TripleDES applies DES three times 112bit key gt IDEA International Data Encryption Algorithm 128bit key 8 Based on confusion amp diffusion operations on blocks of binary data vainvzmg csssza Dveiatinvsvstnms slides incaivmak makiiabkmdlyviwided mm mm minis TEA Encryption Function 7 7 lgey 1 x 32 Eits void encryptunsigned lo nsignedlongitgtle g plaintext unsigned long y text0 z text1 and result 2 x 32 unsigned long delta 0x9e3779b9 sum 0 int n for n 0 n lt 32 n sum I 39 y zltlt 4 k0 Azsum Azgtgt 5 k1 5 z y ltlt 4 142 A ysum A 095 143 6 i text0 y text1 2 f Exclusive OR 3 logical shift 38 Lines 5 amp 6 perform confusion XOR of shifted text c and diffusion shifting and swapping unit 13 vainvzmg 25552 mmmsvsm siides WWW mmixmawwwm bwm mm Rubbing TEA Decryption Function void decryptunsigned long k unsigned long text unsigned long y text0 z text1 unsigned long delta 0x9e3779b9 sum delta ltlt 5 int n for n 0 n lt 32 n 2 y ltlt 4 k2 Ay sum Ay gtgt 5 k3 y zltlt 4 k0 Az sum Azgtgt 5 k1 sum de ta text0 y text1 z vainvzmg 25552 mmmsvsm siides WWW mmixmawwwm bwm KaiA Rubbing M The Principle of DES 55bit kly General 6 k9 mm i m 35 3quot i i E m c spunv 2mg c5552 Dpuatmv SVStnms sh Cipher Blocks and Chaining RSimple block cipher gtMost algorithms work on 64bit blocks 8 chars gtPlaint text M 9 fixed size blocks gtWeak point repeated patterns can be detected RCipher block chaining CBC Cipher biock chaining CBC p piaintextbiocks n3 n2 mi ciphertext biocks To 25552 aminst mutusmmwwm bwm mm Rubbing Stream Cipher for RealTime Data 8 For realtime information gtTelephone calls 8 Based secure keystream generator keystream p 39n 3 n2 MI E Eiphertext stream Stream cipher piaintext vainvzmg 25552 mmmsvsm mmmwwmm bwm KaiA Rubbing i7 AsymmetricPublic Key Encryption Keys come in pairs K1 and K2 One public amp one private If you encrypt with K1 you can decrypt with K2 and vice versa DK2 EK7 M M and DK7 EK2 M M How to efficiently produce the pairs of keys It must be nearly impossible to compute one key given the other c 0139 i a vainvzmg 25552 mmmsvsm siides incatvmatn mmixmawwwm bwm mm Rubbing RSA Encryption To nd a key pair Ke Kd DKd EKe M DKe EKd M M 1 Choose two large prime numbers P and Q each greater than 10 and form 1 N Px Q Z P71 x Q7 2 For d choose any number that is relatively prime with Z that is such that dhas no common factors with Z P 1 Q77gtN77Z60 9 d13 3To nd 2 solve the equation e d 1 mod Z That is e x d is the smallest element divisible by d in the series Z1 ZZ1 3Z1 d 1 1 1 1 01 e240113157 Encrypt with key Ke lte Ngt M is plain text with k bits 2k ltN E39eN I Me mod N Decrypt with key Kd lt11 Ngt c is cipher text D dNc cdmodN c Rivest Shamlr and Addman proved that E and 17 are mutual inverscs ms um is E D X D E X x for all values ofxin the range 0 st 19 The Heroes Ron Rivest Adi Shamir and Leonard Adleman u vamvzmg c5552 ammsvsm 5mg WWW mmmmwwmm bwm m Rubbing 2n Asymmetric Encryption Algorithms They all depend on the use of trapdoor functions A trapdoor function is a oneway function with a secret exit eg product of two large numbers easy to multiply very hard infeasible to factorize 8 RSA The first practical algorithm Rivest Shamir and Adelman 1978 and still the most frequently used Key length is variable 5122048 bits 35 Elliptic curve new method shorter keys and faster it Asymmetric algorithms are 1000 x slower and are therefore not practical for bulk encryption but their other properties make them ideal for key distribution and for authentication cuses UT vainvzmg 25552 mmmsvsm mwmwwmm bwm KaiA Rubbing Zi Applications of Cryptography 8 Secrecy integrity gtthe message is NOT leakedchanged 8 Authentication gt the message comes from the one it supposes to be 38 Digital signature certificate gtThe message is approved by certain authority vainvzmg 25552 mmmsvsm slats incaivmatn mmixmawwwm bwm KaiA Rubbing 22 Secrecy and Authentication 8 Secret or shared key gt Encrypted messages keep secrecy and gt Only people hold the secret key can decrypt message 8 Publicprivate keys gt Anyone has two keys public vs private public key will be announced to everyone gt Secrecy use Alice s public key encrypt message and only Alice can decrypt the message using the private key gtAuthentication Alice encrypt a message uses private key everyone use public key to verify the message from Alice Talk 23 SpringZDDg 055523 Operating Systems slides lnmrpnrate materials kindly provided vamf kavA Robbins Authentication with Shared Secret Key at Alice and Bob has secret key KAB gt How do AliceBob get KAB 3 How do they know they are talking to each other gt Challengeresponse protocols for authentication 1 A 5 c um sunngzoog 055523 Operating Systems slides lnmrpnrate materials kindly provided vamf kavA Robbins 24 Simplified Protocol and Reflection Attack 1 ARA p 2 Heistan e lt co 3 KABRB First session g Second session gt First session 25 Authentication with KDC 3C KDC key distribution centre gt Hold N keys of participants 3 Alice wants to talk to Bob through secure channel gt Get sharedsecret key from KDC Bob K K KAKDCKAB BKDC A3 KDC generates KM3 c Is there any problem with this approach um Spring 2009 185523 Operanng Syslenis slides incorporate nialenals kindly pioyided by Prof KayA Robbins 25 Authentication with KDC cont 3 KDC sends the ticket for Bob to Alice first 21 Alice passes the ticket to Bob A KA KDAKAB 39 3 Av KEKDCKAE Bob Alice naskmaivpvwmm bwm mm Rubbing c SPiinV 2mg c5552 Dveiatinv SVStnms NeedhamSchroeder Authentication Protocol 3 Random values are used as nonce gt demonstrate the freshness of the transaction gt Eg message 2 is a response to message 1 Bob v 3 V V mm 5 KAIBRB 1 7 25552 mmmsvsm slides incaivmatn mamraskmdivpvwam bwm mm Rubbing Alice SPiinV 2mg Enhanced NeedhamSchroeder Protocol 1 A Bob 38 Protection against malicious reuse of a previously generated c session key Splng znna 055523 Operallng Systems slldEs lncmpmals malerlals klndly pmvldad by PM lltayA Pubblns 29 Mutual Authentication with Publickey 1 KgARA 2 mn R K A A B AB 3 K Alice Bob R AB B 3 Everyone knows herhis private key 3 Public keys are real correct keys for AliceBob C um Splng znna 055523 Operallng Systems slldEs lncmpmals malerlals klndly pmvldad by PM lltayA Pubblns 30 Key Establishment Aiice Bob picks x picks y Alice compuies Bob computes gy mod r1quot 9quot mod my gquoty mod n gquoty mod n 8 Known to public 9 and n 8 Unknown to public x and y c T spunvzmg 255523 Dveiaiinvsvsinms siides meavpmm mamiaiskmaivvvwmea by 7m KaiA Robbins 3i Key Distribution Secret Keys Plaintext P Piaintexi Decryption key K etric key generator Secure channeis with confideniiality and auihenticaiion a C 0139 Spimvzmg 25552 UpuaiinvSvSinms siides min mamiiagkindivviwmed bwm KaiA mm 32 Key Distribution Public Keys Plaintext P Plaintext Public Private keyt K39 key K Asymmetric key generator Secure channel with Secure channel with authentication only con dentiality and authentication C um Svrmvzmg 25552 Dveratmvsvstnms slats mime mutusmmwwm bwm mm mm UT Digital Signature 36 Requirements for digital signature gt Authentic the signer deliberately signed the documents gt Unforgeable protect against forgery gt Nonrepudiable prevent the signer from repudiating a signed document denying their responsibility 8 Needs to bind identity with all information gt Otherwise may copy to other documents Alice s computer Bob39s computer Bob s Alrce s private key public key m K K K lmK quot0 L l K m 34 Secure Digest Functions 38 Encrypting all information in M 9 impractically expensive cure digest instead Secure digest function computes a fixedlength hash HM that characterizes the document M HM should be gt fast to com ute gt hard to invert hard to compute M given HM gt hard to defeat in any variant ofthe Birthday Attack 38 MD5 Developed by Rivest 1992 Computes a 128bit digest 38 SHA 1995 based on Rivest39s MD4 but made more secure by producing a 160bit digest Any symmetric encryption algorithm can be used in CBC cipher block chaining mode The last block in the chain is HM C UT svnnvzma 255523 Dpeiatinvsvstnms slides incaipmatn makiiabkmdiypiwided by mi KaiA Rabbins 35 Birthday Attack of Hash Functions as How hard it is for M and M to get HM HM gt If our hash values are 64 bits long 264 different values and we require only 232 versions of M and M on average gtThis is too small for comfort We need to make our hash values at least 128 bits long to guard against this attack Birthday paradox Statistical result Ifthere are 23 people M in a room the chances are even 50 that 2 of them Will have the same birthday HM h If you want a given day h require 253 people for even chance 6 UT svnnvzma 25552 Dvevatinvsvstnms slats Wilma mmixmawwwm bwm KaiA Rubbing BE Digital Signature with Public Keys Signed doc H M n Signing lt EMi 128 bits DMpunilthpi n f gt Verifying h n 7autnentic forged uiMi C Spilnv 2mg 25552 apeiuiiisvsisms slides iisaipaim maimsiiiaiwwma mini mm Rubbing MACS Lowcost with SharedSecret Key MAC Message Authentication Code used in secure channel Signed doc h Signing Signer and veri er share a sec et key K and no encryption M h HMllt Venfylng h n 7autnentic forged c h 0139 spiiiizmg 25552 apeiuiiisvsisms slides iisaipaim maimsiiiaiwwma mini KaiA Rubbing 38 Certificate Mfg Distinguished Name Public key 1mm Distinguished Name S39gnanne Permd ofvolidizy Not Before Date Not A er Date Administrative Information Version Serial Number 1 1 m Inga 5W 2mg c5552 Dvevatmvsvstnms slides incalvmak makviabkmdlvwwmed bwm K mmquot 39 Certificate Authority ggfm type lcium number Alice s bank account 3 Account 5252525 certificate 4 Certifying authority Bank Bob 5 Signature Digextoieldz eld 3 KW K bpri amp K bpub V 1 Certi cate type Public key Bank Bob s Kpub Name Bank Bob certi cate 3 Public key KEPW 4 Certifying whorigz Fred 7 The Bankers Federation 5 Siser Digmmeldz week Kr W Fred is trustable Certi cate authorities Verisign CREN etc yrs Whose Kspub is well known Svunvzmg 5523 Dvevatmvsvstnms slides incalvmak makviabkmdlvwwmed bwm K mmquot 40 Case study Kerberos 3C Secures communication with servers on a local network gt Developed at MIT in the 1980s to provide security across a large campus network gt 5000 users gt based on Needham Schroeder protocol 36 Standardized and now included in many operating systems gt Internet RFC 1510 OSF DCE gt BSD UNIX Linux Windows 2000 NT XP etc 38 Kerberos server creates a shared secret key for any required server and sends it encrypted to the user39s computer 3 User39s password is the initial secret shared with Kerberos u I svvmvzmg c5552 eveninvsvsams sides msmpm mammskmdlvpvwmm bwm ma mm 41 System architecture of Kerberos ms mar Kerhems KeyDIsIr granting service Aulhenliczl database s a Mrs 512 A mice per lugin sessiun 512 3 mice pEi server sessiun Client Server 512 c mice per sevvevlvansacliun I vainvzmg 25552 Dvevatmvsvslnms slides mama makiiabkmdlvvtwided bwm x mm 42 Kerberos continued X Server machines must take care to store their keys in a safe place 8 Kerberos is implemented as a server running on a secure machine as DES encryption is used but it can be replaced 8 Kerberos is scalable world divided into realms ac Processes can authenticate themselves to servers in other realms through their local TGS gt TGS register with all realms amt 39i 95iiili fi fiji EJXEi il i 9 Transport Layer Security TLS SSL 3 Developed by Netscape 1996 3 Standardized by IETF January 1999 as TLS 10 SSL 30 38 Is supported by most browsers for electronic transactions 3 Has negotiable encryption and authentication algorithms 3 Bootstraps by establishing a secure channel based on publickey encryption 38 Channel is fully configurable so not everything has to be encrypted vainvzmg 25552 mmmsvsm slides minim mmixmawwwm bwm KaiA Rubbing 44 TLS encryption I Uses public key cryptography RSA to provide authentication I Uses secret key cryptography to provide privacy gt Data Encryption Standard DES gt Triplestrength DES 3DES gt Rivest Cipher 2 RC2 gt Rivest Cipher 4 RC4 8 Uses digital signatures to provide data integrity e um vainvzmg 25552 Dvevatinvsvstnms mmiwwmm bwm KaiA mmquot 45 TLS protocol stack changes the secure channel to spec negotiates cipher LS I suite exchanges I certi cates and key 3quot Ch quot9 masters lpro c I e e implements the secure channel WW Oco TLS protocols I Other protocols I 25552 Dvevatinvsvstnms slides immune mmixmawwwm bwm we Robbins 46 I um vainvzmg TLS handshake protocol ChemHEuD Estabhsh prutucui versiun sessmn iD a eipnersmte eurnpressmn methud SenWWW Exchange random start vaiues Certificate Cemmate RE mt opnenany send server certificate and A request ehent eemneate SENErHEHuDunE P Chant Server Send chant certificate response if A E requested Certificate yeng Change CiEhEr Spec Change cipher suite and nish nanusnake inciudes key master ekcnange Che E C 3 5 EB key masteris used by both A and B FWHSHEd O genera e 2 sessmn keys 2 MAC keys kga M C MBA UT spnnv 2mg 55523 Dpemnv svstnms snaes mcmvmak menus kind VDVWmed by 7m kayA Rabbins 47 TLS handshake configuration options Component Description Example Key exchange the method to be used for RSA With publickey method exchange of a session key certi cates Cipher for data the block or stream cipher to be IDEA transfer used for data Message digest for creating message S mction authentication codes MACs C UT Svnnvzmg esa za amtnvsysems simes incawmak memekmaywwma bwm km mmquot 48 CS 5523 Operating Systems Instructor Dr Dakai Zhu Topics Fault Tolerance swmuug 29552 mum Svsiem 5mg mcmpmm mmswawywm bwm um mm Project 4 Questions amp Discussions Class starePraxy Class stare stareSkeletan buyadd buyadd remove remove checkout checkout 41buyvi1v10 Message ROR Amazon Proxy Marshall n AM buy ilem110 StoreClient 3 0R7AM Lrefprox1 ROR AM er ske RRM c refz prox IPpon R0R7AT erz ske M quot7quot 139 2 Review about Security Important Concept 3t Cryptography sym metric vs asymmetric gt Secrecy and authentication Authentications protocols gt Shared keysKDCpublic private keys gt NeedhamSchroeder protocol 3 Key establishment and distribution a Secure Hash Function and Digital Signature gt Certi cates and authority 3 Kerberos architecture 3 Transport Layer Security UTg Svnnvzmg 25552 mmmsvsm naskmalvpvwmm bwm mm Rubbing Outline S Terminology fault error and failures 8 Fault management 3 Fault recovery techniques Redundancy gt Recovery and rollback gt Checkpointing and stable storage a Process resilience and reliable process groups as Reliable communications 8 Recovery in distributed systems gt Consistent checkpointing and message logging C 0139 Svnnvzmg 25552 mmmsvsm slats minim mmsmmwwm bwm mm Rubbing Dependability of Components 8 Components provide services to clients gt For distributed systems either processes or channels gt Component may require the services from other components and depends on them 8 Faults are common gt Machine crash software bugs disks fail packets lost a Faults single machines vs distributed systems gt Distributed systems coordination and agreement 8 Questions gt Can we hide the effects of faults c gt Can we recover from failures UT Svnnvzmg 25552 Dvevatmvsvstnms naskmdlvpvwmm bwm mm Rubbing Fault Tolerance Properties 8 Availability gtWhat percentage of time is a system available for use 8 Reliability gt How long can a system stay up continuously 8 Safety gt Small failures should not have catastrophic effects as Maintainability gt How easy is it to repair faults 8 High reliability may not lead to high availability urge Svnnvzmg 25552 Dvevatmvsvstnms slats incaivmatn matanaskmdlvvvwmed bwm mm Rubbing Terminology 8 Failure gt components not follow specifications 9 a failure occurs an Error gt part of a component s state that can lead to a failure 3 Fault gt cause of an error C UT Svnnvzmg 25552 Dvevatmvsvstems slats mime mutusmwma bwm mm Rubbing Types of Faults 8 Transient faults gt occur once and then disappear gt Eg disturbance during wireless communication as Intermittent faults gtdisappear and reappear unpredictable gt Eg Loose contact on a connector 88 Permanent faults gt Continue to exist until faulty component are repairedreplaced gt Eg software bugs or burnt out chips UTs Svnnvzmg 25552 Dvevatmvsvstems slats mime mutusmwma bwm mm Rubbing Failure Models 38 Crash failure gt component simply halts but behaves correctly before halting 3 Omission failure gt component fails to respond 3 Timing failure gt correct output but lies outside a speci ed realtime interval 3 Response failure gt incorrect output 3 ArbitraryByzantine failure gt ArbitraryMalicious output 3 Crash failures are the least severe arbitrary failures are the worst c UT vainvzmg 25552 Dveiatinvsvstnms slides Mimi mmsmmwwma bwm mm Rubbing Fault Detection as Failstop gt Notifies before crashing 8 Failsilent gt No responses after crashes 8 Failsafe gt Junk output that can be recognized 8 Byzantine failure gt Cannot be detected easily c 0139 vainvzmg 25552 Dveiatinvsvstnms slides Mimi mmsmmwwma bwm mm Rubbing Fault Management 8 Fault prevention gt prevent the occurrence of a fault 3 Fault tolerance gt build a component in such a way that it can meet its specifications in the presence of faults ie mask the presence of faults 3 Fault removal gt reduce the presence number seriousness of faults 3 Fault forecasting gt estimate the present number future incidence and the consequences of faults UT Svnnvzma 25552 Dveiatinvsvstems naskinalvpvwmm bwm KaiA Rubbing ll Fault Tolerance Techniques SE Redundancy and agreement gt Hiding effect of faults 39 Recovery and rollback gt Bringing system to a consistent state Svnnvzma 25552 Dveiatinvsvstems slides incatvmatn makiiabkmdlvvtwided bwm KaiA Rubbing 12 Redundancy Techniques S Redundancy is the key technique to tolerance faults 38 Information redundancy gteg Hamming code 8 Time redundancy gt eg reexecution 2 Physical softwarehardware redundancy gt eg extra cpus multiversions softwares vainvzmg 25552 mmmsvsm slides incaivmatn mmixmawwwm bwm KaiA Rubbing is Triple Modular Redundancy TMR as If A2 fails 9 V1 majority vote 9 B gets good result I galVhat if V1 fails mmixmawwwm bwm KaiA Rubbing M TMR cont 32 Correct results are obtain via majority vote gt Mask ONE fault C UT Svnnvzmg 25552 amimsva slat mm Mattias maywwmm by m KaiA Rubbing 15 Level of Redundancy S Depends on gt How many faults can a system handle gtWhat kind of faults can happen 8 kfault tolerant system gt Can handle k faulty components XAssume crash failure semantics ie failsilent gt k 1 components are needed to survive kfailures C 0139 Svnnvzmg 25552 amimsva slats incalvmak mmixmawwwm bwm KaiA Rubbing lB Level of Redundancy cont SAssume arbitrary but nonmalicious failure semantics and group output defined by voting gt Independent component failures 9 possible same results gt 2k1 components are needed to survive k component failures hard to determine k vs k1 I 88Assume Byzantine malicious failure semantics and group output defined by voting gt Faulty components cooperate to cheat gt 3k1 components are needed to tolerate kfailures 9 two thirds are needed for the agreement on other 2k1 non faulty components Spiinvzmg 25552 Dveiatinvsvstnms slides incaivmatn mamiiaskmdlvpiwmed bwm KaiA Rubbing l7 Byzantine Agreement Problem 8 N generals M traitors 3 Reliable communication channel 3 Problem Traitors can lie others don t know who the traitors are 8 Question Can trusted generals agree on their army sizes Spiinvzmg 25552 Dveiatinvsvstnms slides incaivmatn mamiiaskmdlvpiwmed bwm KaiA Rubbing lE Lamport s Agreement Algorithm S Step 1 Each general sends everyone its army size gt Loyal generals tell the truth gtTraitors can lie ac Step 2 Each general collects received information as a vector S Step 3 Each general sends its vector to others gt Loyal generals send what they have gt Traitors can change the vectors 3 Step 4 Each general determines vector elements by voting among all vectors he receives m n Svnnvzmg 25552 Dvevatmvsvstnms 5m makiiabkmdlyviwmed bwm KaiA Rubbing lB An Example N4 M1 38 N 3M1 for agreement An Example N3 M1 9 fail to agree 1 Got1 2x 2 Got12y 3 Got123 b 1 Got 2 Got 12 3 12 X a b c d ef Faulty process 0 C 0139 Spring ma csssza Operating Systems sides incurpurate materiais may pruvided by F39er KayA Rubbins 21 Fault Recovery 38 Main idea when a failure occurs we need to bring the system into an errorfree state 38 Forward recovery gt Find a new state from which system continue operation gt Eg Errorcorrection codes 38 Backward recovery gt Bring the system back into a previous errorfree state gt Eg packet retransmission O 01 Spring zuua KayA Rubbins 22 Checkpoints 8 Periodically store system states on stable storage SAt errorrecovery go back to the last checkpointed state C UT 23 vainvzmg 25552 Dveiatinvsvstnms slides incalvmatn mamraiskmdlvpvwmm bwm mm Rubbing Stable Storage actor has different value Bad checksum S Main idea replicate all data on at least two disks and keep one copy correct at all times 0139 24 vainvzmg 25552 Dveiatinvsvstnms slides incalvmatn mamraiskmdlvpvwmm bwm mm Rubbing Failure Models in Distributed Systems Response laiiure nil ASpurn 2mg c5552 Dpuaimv Systems Slides manipulate makiiab kindiypvwmm by Vim KayA Rabbins Process Resilience 8 Process group Protect against faulty processes by replicating and distributing computations in a group 8 Flat groups quick detection but more overhead as control is completely distributed hard to implement 8 Hierarchical groups single coordinator 9 not really fault tolerant amp scalable easy to implement Flal group Hlaymchical gmup X Cunrdinamr Agreement in Faulty Systems 38 Process Synchronous 2 operate in lockstep 3amp3 Delays Are delays on communication bounded 3 Ordering Are messages delivered in order of being sent 3 Transmission Are messages sent onebyone or multicast Message ordering Unoraered ordered 9 S a Bounded 3 g Synchronous g g Unbounded a quot39 3 3 Bounded 3 Asynchronous n Unbounded Unicasl Mullicasl Unicast Mumoasr 3 E r Message transmission Reliable Communication 8 Error detection gt Framing of packets to allow for bit error detection gt Use of frame numbering to detect packet loss as Error correction gt Add so much information redundancy that corrupted packetscan be automatically corrected CRC codes gt Request retransmission of lost or last N packets 8 Most of this work assumes pointtopoint 6 communication 0139 28 Svrmvzmg esam Dveialinvsvskms one immune mamrraskmdlvvvwmed bwm mm newquot RPC Semantics with Failures X What may go wrong gt1 Client cannot locate server gt 2 Client request is lost gt 3 Server crashes gt 4 Server response is lost gt 5 Client crashes at 1 Relatively simple just report back to client 8 2 Just resend message 39 spiiizmg 25552 apeiuiiisisims slides iicaipiim mmimiiaiwiwma mm mm Rubbing RPC Semantics with Failures cont as 3 Server crashes are harder as you don t know what it had already done HEQ Server REG Server REG Server Receive Receive Receive Execute e No REP REP Reply Ng gi 4 a b c 8 Problem what we expect from the server gtAtleast oncesemantics The server guarantees it will carry out an operation at least once no matter what gtAtmostoncesemantics The server guarantees it will carry out an operation at most once I I SPWVV 2mg c5552 Dpeiaiinv Systems Slides incaivmak makriab kindivpvwmm by Vim KayA Rabbins RPC Semantics with Failures cont 38 4 Detecting lost replies can be hard because it can also be that the server had crashed You don t know whether the server has carried out the operation gt Solution None ex ept that you can try to make your operations idempotent repeatable without any harm done if it happened to be carried out bef r 3 5 The server is doing work and holding resources for nothing orphan computation gt Orphan is killed or rolled back by client when it reboots gt Broadcast new epoch number when recovering 3 servers kill orphans gt Require computations to complete in a Ttime units Old ones are simply remove C UT svnnvzmg 25552 mmmsvsm slats incalvmatn makiiabkmdivviwided bvmv mm Rubbing Reliable Multicasting 3 Model We have a multicast channel c with two possibly overlapping group gt The sender group SNDc of processes that submit messages to channel 2 gt The receiver group RCVc of processes that can receive messages from channel 2 3 Simple reliability If process P E RCVc at the time message m was submitted to c and P does not leave RCVc m should be delivered to P 8 Atomic multicast How can we ensure that a message m submitted to channel 0 is delivered to process P E RCVc Only if m is delivered to all members of RCVc UTs svnnvzmg 25552 mmmsvsm slats incalvmatn makiiabkmdivviwided bvmv mm Rubbing Reliable Multicasting cont S For LAN Let the sender broadcast the messages to channel 0 and log them gt If P sends message m m is stored in a history buffer gt Each receiver acknowledges the receipt of m or requests retransmission at Pwhen noticing message lost gt Sender P removes m from history buffer when everyone has acknowledged receipt gt Not scalable 8 Multiple pointtopoint reliable channels C UT 33 vainvzmg 25552 mmmsvsm mmmwwmm mm mm mmquot Recovery in Distributed Systems 88 Consistent Recovery State gt Recovery in distributed systems is complicated by the fact that processes need to cooperate in identifying a consistent state from where to recover gt Requirement Every message that has been received is also shown to have been sent in the state of the sender 88 Recovery line Assuming processes regularly checkpoint their state the most recent consistent global checkpoint vainvzmg 25552 mmmsvsm slats WWW mmixmawwwm mm mm mmquot Recovery with Checkpoints Initiai slate Recovery quot9 Checkpoint I i MI Faiiure J I Time gt Message sent from P2 m P1 inconSIsienl coliecilon of checkpomts C umsvvmvzmg 555523 nymmsvsm sides mum mimmmwwm bwm Km mm 35 Cascaded Rollback Domino Effects 38 If checkpointing is done at the wrong instants the recovery line may lie at system sta up time iniiiai state Checkpoint I l l l I I m m Failure P I I I I I I Time A c quotm svunvzmg 555523 aminst mmmmwwm bwm KM mm 3B Independent Checkpointing 8 Each process independently takes checkpoints gt Let CPm denote mlh checkpoint of process Pi and NTIm the interval between CP m 1 and CPm gtWhen process Pi sends a message in interval lNTm it piggybacks im gtWhen process Pj receives a message in interval NTn it records the dependency NTImgtNTI7 gtThe dependency NTmaNT n is saved to stable storage when taking checkpoint CPUn 8 If process Pi rolls back to CPIm Pj must roll back to CPUn 8 Risk cascaded rollback to system startup c UT 37 Svnnvzmg 25552 Dveiatmvsystnms 5mg incaivaiak Malawiainva bwm mm Rubbing Coordinated Checkpointing as Each process takes a checkpoint after a globally coordinated action 8 Simple solution twophase blocking protocol gt A coordinator multicasts a checkpoint request message gtWhen a participant receives such a message it takes a checkpoint stops sending application messages and reports back that it has taken a checkpoint gtWhen a checkpoints have been confirmed at the coordinator the latter broadcasts a checkpoint done message to allow all processes to continue 3 Observation consider processes that depend on coordinator and ignore the rest c 0139 38 Svnnvzmg 25552 Dveiatmvsystnms 5mg incaivaiak Malawiainva bwm mm Rubbing Message Logging 3 Checkpoints are expensive to make gt store messages in a log 2 replay your communication behavior from the most recent checkpoint 36 Assumption piecewise deterministic execution model gtThe execution of each process can be considered as a sequence of state intervals gt Each state interval starts with a nondeterministic event eg message receipt gt Execution in a state interval is deterministic ma vamvzme 25552 mmmsvsm 5mg WW matauabkmdiyvtwided bwm KatA Rubbing 39 Message Logging and Consistency 38 Problem When should we actually log messages 3 Avoid orphans gt Process Q has just received and delivered messages m1 and m2 gt Assume that m2 is never logged gt A er delivering m1 and m2 Q sends message m3 to process R gt Process R receives and subsequently delivers m3 0 crashes and recovers A W n 1 m2 is never replayed Aso neitherlwill m3 I Vx m2 f X13 m2 m3 j R Unlogged message uquot H Logged message p Message Logging Schemes S HDRm message m s header contains its source destination sequence number and delivery number gt A message m is stable if HDRm cannot be lost eg because it has been written to stable storage gtThe header contains all information for resending a message and delivering it in the correct order assume data is reproduced by the application 8 DEPm set of processes to which message m has been delivered as well as any message that causally depends on delivery of m S COPYm set of processes that have a copy of HDRm in their volatile memory tin4 vamvzmg 25552 ammsMM slats WW mmnsmawwma bwm KM Rubbing 41 Message Logging Schemes cont S Orphan If C is a collection of crashed processes then Q C is an orphan ifthere is a message m such that Q E DEPm and COPYm E C 8 If for each message m DEPm E COPYm 9 no orphans 38 Pessimistic protocol for each nonstable message m there is at most one process dependent on m that is DEPm 1 gt An unstable message in a pessimistic protocol must be made stable before sending a next message 0139 vamvzmg 25552 ammsvm mmnsmawwma bwm KM Rubbing 42 Distributed Systems cont 8 Threaded sewer structures as Stateful vs stateless servers as Physical clocktime in distributed systems gt No global time is available 2 Logical clocktime and Happen Before Relation gt Application total ordering multicast 9 consistency 2 Vector clocks causally ordering a Distributed synchronizations Svrinvzmg 25552 mmmsvsm slides minim murmsmawma bwm KaiA Rubbing 52 Threaded ClientsServers 8 Threaded clients for hiding network latency 8 Threaded server for high performance 3 Thread pool concept Thread 2 requests to server Receiptamp 0 V queuing Thread i y I generals QEHIHIIQ gr results gt Requests 39 N threads inputroutput Client Server Svrinvzmg 25552 nmmsm mamraismnaiypvwmm by Vial KaiA Rabbins 53 Multithreaded Clients 38 Main issue is hiding network latency 36 Multithreaded Web client gtWeb browser scans an incoming HTML page and finds that more files need to be fetched gt Each file is fetched by a separate thread by blocking HTTP request gt As files come in the browser displays them 38 Multiple requestresponse calls gt Client makes several calls at the same time each by a different thread gt It then waits until all results have been returned gt Note if calls are to different servers we ma have a linear quotTc speedup compared to doing calls one after the other Svnnvzmg 25552 mmmsvsm mmmwwmm bvmv KaiA Rubbing 54 Threaded Servers as Improved performance and better structure 8 Improve performance gtTo handle incoming requests using threads is cheaper than new process gt Having a singlethreaded server prohibits simply scaling the server to a multiprocessor system gt As with clients hide network latency by reacting to next request while previous one is being replied a Better structure gt High lO demands 9 simple wellunderstood blocking calls simplifies the overall structure gt Simplified flow of control 9 easy understand UTs Svnnvzmg 25552 mmmsvsm slides incalvmak makiiabkindlvvlwided bvmv KaiA Rubbing 55 Alternative Threading Architectures y workers o lO 39 Irernote oueas I a Threadrperrrequest c spunv 2mg 25552 mmmsvsm perrcoririectiori threads 0 gt O o 39 0 objects 0 D b Threadperrconnection naskmdlypvwmm bwm mm Rubbing perrobi ect m reads m remote F I Oobiects c Threadrperrobiect c spunv 2mg Thread Pool Fixed Number of Threads 8 Thread creationdestruction overhead 8 Thread pool fixed number ofthreads workers gt RequestsJobs queue gtWorkers repeatedly check if any requestJjob in the job queue pick one for execution if one is ready sleep if queue is empty gt Queue wake up workers when new requests come gt Synchronization problem on the requestJjob queue gtAdaptive on the number of threads during execution 25552 mmmsvsm slats minim mammawwma bwm mm Rubbing Servers and States Stateful Servers S Keeps track of the status of its clients gt Record that a file has been opened so that prefetching can be done gt Knows which data a client has cached and allows clients to keep local copies of shared data 3 Observation The performance of stateful sewers can be extremely high provided clients are allowed to keep local copies vamvzmg 25552 Dveiatmvsvstnms mmmwwmm bwm KM mm 58 Servers and States Stateless Servers 88 Never keep information about the status of a client after having handled a request gt Don t record whether a file has been opened simply close it after access gt Don t keep track of your clients gt Don t promise to invalidate a client s cache 3 Consequences gt Clients and servers are completely independent gt Less state inconsistencies due to clientherver crashes gt Possible loss of performance eg a server cannot anticipate client behavior think of prefetching file blocks UTs vamvzmg 25552 Dveiatmvsvstnms 5mg incalvmak mmsmawwm bwm KM mm 59 Measuring Time 8 What is a second 3 Time it takes the cesium 133 atom to make exactly 9192631770 transitions 3 International Atomic Time is based on very accurate physical clocks drift rate 1039 8 It is based on atomic time but occasionally adjusted to astronomical time Svnnvzmg 25552 mmmsvsm naskmaiypvwmm bwm KaiA Rubbing EEI Universal Coordinated Time UTC 38 An international standard for time keeping 3 At present the real time is taken as the average of some 50 cesiumclocks around the world 38 Introduces a leap second from time to time to compensate that days are getting longer 35 National Institute of Standard Time NIST operates a shortwave radio station with call letters VWVV and broadcast UTC from radio stations on land and satellite 8 GEOS Geostationary Environment Operational Satellite can provide UTC accurately to 05 msec 3 Computers with receivers can synchronize their clocks with these timing signals UTs swmzmg 255523 Dpeiatinvsystnms slides mcmpmm makiiabkmdiypiwided by mi KaiA Rabbins Bi Computer Clocks and Timing Events 38 Each computer has its own internal clock quartz gt Used by local processes to obtain current time value 8 Skew the difference between the times on two clocks at any instant 8 Clock drift rate the difference per unit oftime from some ideal reference clock 8 Ordinary quartz clocks drift by about 1 sec in 1112 days 10396 secssec 8 High precision quartz clocks drift rate is about 10397 or 10393 secssec c urnu svnnvzmg 25552 mmmsvsm slats math mmixmawwwm bwm mm Rubbing Computer Clocks and Timing Events 8 Processes on different computers can timestamp their events using their own clocks gt Clocks on different computers may give different times gt Computer clocks drift from perfect time and their drift rates differ from one another QQQ Network u svnnvzmg 25552 mmmsvsm slats math mmixmawwwm bwm mm Rubbing Clock Synchronization Principles 8 Principle I Time server scans all machines periodically calculate an average and inform each machine how to adjust its time as Principle Every machine asks a time server for the accurate time at least once every d2r seconds Network Time Protocol 38 Fundamental setting the time back is never allowed smooth adjustments C UT Svrinvzmg 25552 Dverninvsvsfnms slides mime makiiabkmdlvviwided bwm mm Rubbing Network Time Protocol NTP as NTP Mills 1995 defines an architecture for a time service and a protocol to distribute time information overthe Internet 8 Objectives gt Provide a service enabling clients across the Internet to be synchronized accurately to UT gt Provide a reliable service through the use of redundant serverspaths gt Provide protection against interference with the time service whether malicious or accidenta 3 Need an accurate measure of round trip delay interrupt handling and processing messages UTs 5W m 25552 Dverninvsvsfnms slides mime makiiabkmdlvviwided bwm mm Rubbing Network Time Protocol NTP cont 3 Provided by a network of servers located across the Internet 3 Primary servers are connected to UTC sources 3 Secondary servers are synchronized to primary servers 3 Synchronization subnet lowest level servers in users compu ers 39l Z C UT vainvzmg 25552 mmmsvsm slats math mamraskmdlvpvwmm bwm KaiA Rubbing EB Time in Distributed Systems 3t Problem how to measure time accu rater to know the exact time an event occurred in a computer system 311 There is no global clock in a distributed system 3 Logical time is an alternative gt Order of events also useful for consistency of replicated data 8 Algorithms for clock synchronization are useful for gt concurrency control based on timestamp ordering gt Consistency in distributed transactions gt checking the authenticity of requests c UT swmzmg 255523 Dpeiatinvsvstams slides mcmpmm makiiabkmdlypiwided by rm KaiA Rabbins E7 Happened Before Relation 38 Lamportfirst defined a happened before relation 9 to capture the causal dependencies between events 38 Same process A 9 B if A and B are events in the same process and A occurred before B 3 Different processes A 9 B if A isthe event of sending a message m in a process and B is the event of the receipt of the same message m by another process 3 If A98 and B 9 C then A 9 C happenedbefore relation is transitive UT Svnnvzmg 25552 Upuatmvsvstnms mwmwwmm bvmv KaiA mm BE Happened Before Partial Order Pi 39 n Physical r c N ime e f aabat p1 cad atp2 b ac also def 3 Not all events are related by the a relation gt a and 6 different processes and no message chain gtthey are not related by a gtthey are said to be concurrent written as a H 6 0134 Svnnvzmg 25552 Upuatmvsvstnms slats mime mutusmmwvwm bvmv mm mm Logical Time 3 Distributed system environment implies the absence of perfectly synchronized clocks or global time 8 The order of two events occurring at two different computers cannot be determined based on their local time 3 Problem How do we maintain a global view on the 2 systems behavior that is consistent with the happened before relation 35 The notion of logical timeclock is fairly general and constitutes the basis of many distributed algorithms C UT vainvzmg 25552 mmmsvsm slats WWW makiiabkmdlyviwided mm KaiA Rubbing 7D Logical Clocks Lamport 1978 8 Solution attach a timestamp Ce to each event 6 satisfying the following properties 38 P1 If a and b are two events in the same process and aab then we demand that Ca lt Cb 3 P2 For different processes if a corresponds to sending a message m and b to the receipt ofthat message then also Ca lt Cb 8 How to get timestamp 9 consistent logical clocks urge vainvzmg 25552 mmmsvsm slats WWW makiiabkmdlyviwided mm KaiA Rubbing 7i Logical Clocks Lamport 1978 3 Each process Pi maintains a logical clock which is a monotonically increasing software counter no relation to physical clock 8 Update the logical clockcounter following gt For any two successive events that take place within Pi Ci is incremented by 1 gt Each time a message m is sent by process Pi the message receives a timestamp tsm Ci gtWhenever a message m is received by a process P P adjusts its local counter C to maxCj tsm then executes step 1 before passing m to the application vainvzmg 25552 mmmsvsm slats incaivmatn mmixmawwwm mm KaiA Rubbing 72 Logical Clock Properties a e a 9 implies Le lt Le 8 The converse is not true that is Le lt Le does not imply e 9 e eg Lb gt Le but b H e 8 Lamport s happened beforequot relation defines an irreflexive partial order among the events in the distributed system vainvzmg 25552 mmmsvsm slats incaivmatn mmixmawwwm mm KaiA Rubbing 73 Logical Clock Where to Put It S The positioning of Lampon s logical clocks in distributed systems Application layer Adiust local doc Adjusi local clock Middleware layer and Iimeslamp messag Middleware sends message Message is Veceived 6 Network layer UT 74 vainvzmg 25552 Dveialinvsvstnms slides incaivmak mmsmmwwma bwm mm Rubbing Logical Clock Example c 0139 75 vainvzmg 25552 Dveialinvsvstnms slides incaivmak mmsmmwwma bwm mm Rubbing An Example Logical Clock Application 3 Updating a replicated database Initially 1000 Add 100 Add 100 interest i Update 1 r Update 1 is Replicatecl database Update 2 is performed before performed before Result 111 1 Result 1 110 W SPHer 2mg KayA Robbins TotallyOrdered Multicast 38Consider a group ofn distributed processes m s n processes multicasts update messages gt How to guarantee that all the updates are performed in the same order by all the processes 38 Assumptions gt No messages are lost Reliable delivery gt Messages from the same sender are received in the order they were sent FIFO gtA copy of each message is also sent to the sender C UT Spring 2mg KayA Robbins TotallyOrdered Multicast cont 3 Process Pi sends time stamped message msgi to all others The message itself is put in a local queue queuei 35 Any incoming message at P is queued in queue according to its timestamp and acknowledged to every other process 3 P passes a message msgi to its application if gt 1 msgiis at the head of queue gt 2 for each process Pk there is a acknowledgement message msgk in queue with a larger timestamp Svunvzmg 25552 UpuatmvSvStnms slats incaivmatn mmixmawwwm bwm mm Rubbing For The Example 8 S1 sends Requpdate1 20 at time 20 as S2 sends Requpdate2 15 at time 15 8 S1 receives Requpdate1 20 at time 21 and Requpdate2 15 at time 22 send ack for update2 request at time 23 8 S2 receives Requpdate2 15 at time 16 and Requpdate1 20 at time 21 send ack for update2 request at time 22 SOn both S1 S2 gtQueue Requpdate2 15 Requpdate1 20 ack c 0139 7a Svunvzmg 25552 UpuatmvSvStnms slats incaivmatn mmixmawwwm bwm mm Rubbing Vector Clocks as Observation Lamport s clocks do not guarantee that if Ca lt Cb that a causally preceded b gt Event 3 m1 is received P P2 P3 at T 16 gt Event b m2 is sent at T 20 38 We cannot conclude that a causally precedes b C um svunvzmg 25552 Dvevatmvsvstems slats incatvmatn m Vector Clocks cont 3 Vector clocks are constructed by letting each process P maintain a vector V0 with the following two properties gtVC i is the number of events that have occurred so far at P In other words VC i is the local logical clock at process P gtlf VC j k then P knows that k events have occurred at Pf It is thus P s knowledge of the local time at Pf C um 81 svunvzmg 25552 nmmsm makiiabkindlvvtwided bwm mm Rubbing Vector Clock Update 8 Rule 1 Before executing an event Pexecutes VCi HVCi 1 8 Rule 2 When process P sends m to P it sets m s vector timestamp ts m VC after Rule 1 8 Rule 3 Upon the receipt of m process P adjust VCj k e maxVCj k ts mk after Which it executes Rule 1 and delivers m to the application vamvzmg 25552 Dveratmvsystnms 5mg incavvmak matauabkmdlyvrwmed bwm KM mm 82 Causally Ordered Multicasting 8 Ensure to deliver a message only if all causally preceding messages have already been delivered as PX postpones delivery of m from Py until gtR1 tsmy VCxLy 1 9 m is the next message expected from Py gt R2 tsmk S VCJIk for k y 9 Px see all messages from other process that Py saw before Py sent out m vamvzmg 25552 nmmsm makiiabkmdlyprwided by Vm KaiA Rubbing 83 Causally Ordered Multicasting cont P VCD 100 VCU 110 u 1 VC1 111W02110 P I I 1 v02 000 vcz 100 38 For P2 when receive m from P1 tsm 110 but VC2 000 m is delayed as R2 is not satisfied 38 Whe P2 receive m from P0 tsm l 00 with VC2000 9 both R1 and R2 is ok and m is delivered 9 VC2 100 9 m is delivered C UT 84 Svnnvzmg 25552 Dvevatmvsvstnms slats Mimi makiiabkmdlyvlwided bwm mm Rubbing Mutual Exclusion in Distributed Systems 8 To ensure exclusive access to some resource for processes in a distributed system as Solutions gt Centralized server gt Decentralized using a peertopeer system gt Distributed with no topology imposed gt Completely distributed along a logical ring Svnnvzmg 25552 Dvevatmvsvstnms slats Mimi makiiabkmdlyvlwided bwm mm Rubbing Centralized Server n 1 Noreply Queue is 6 empty Coordinator a b C as What is the problem with this scheme C um EB vainvzmg 25552 mmmsvsm slides math mmixmawwwm bwm mm Robbins Decentralized Mutual Exclusion Assume every resource is replicated n times with each replica having its own coordinator 8 Access requires a majority vote from m gt n2 coordinators 8 A coordinator always responds immediately to a request SAssumption When a coordinator crashes it will recover quickly but will have forgotten about permissions it had granted m n vainvzmg 25552 nmmsm mmixmawwwm bwm KaiA Robbins E7 Distributed Ricart amp Agrawala 8 As Lamport except that ack aren t sent Instead replies ie grants are sent only when gt Receive process has no interest in the shared resource or gt Receive process is waiting for the resource but has lower prioritv known through comparison of timestamps 8 resource 0 a ox K Accesses 0 OK 9 CD resource b c vainvzmg 25552 Dveiatinvsvstnms slides Mimi mamraskmdivpvwmed bwm KaiA Rubbing EB Logical Token Ring ac Processes in a logical ring and let a token be passed between them The one that holds the token is allowed to enter the critical region if it wants to a bi What ifthe token is lost vainvzmg 25552 Dveiatinvsvstnms slides Mimi mamraskmdivpvwmed bwm mm Rubbing CS 5523 Operating Systems Topics Process Management c um swmuug 29552 mum System slats mcmpmm mmeviabkmdtmeed bwm KaiA Rubbing l Outline 38 Basic concepts of process gt Representation process control block PCB gt Execution environment address space 38 Basic operations for process management gt Process creationtennination 3 States of process different queues gt ready running or wait etc gt Context switch multiple hardware running contexts 8 Scheduling of process CPU scheduling gt Basic scheduling algorithms FIFO SJF etc 38 Inter process communication gt shared memory and message 0139s svunvzmg 25552 Dveiatmvsvstnms slats incalvmatn matauabkmdlvvlwided bwm KaiA Rubbing 2 Process vs Program 8 Program one or a set of functions gt stored in files gt a passive entity 3 Process a program in execution gt Running of a program gt A program counter what the next instruction is gt A set of associated resources memory open file handles gt Dynamic concept H owwhen do we start a process Svunvzmg 25552 Dveialmvsvstnms naskrnalypvwmm bwm mm Rubbing Process Control Block PCB 8 OS creates a PCB for each process 8 OS manages the process table 9 a link of PCB registers Svunvzmg 25552 Dveialmvsvstnms slats incaivaiak mmlxmawwwm bwm mm Rubbing Example PCB in Unix 3 4 Process 3 Wow Managem ent Pointer to text code segment Re isters Pointer to data segment Program coumequot Pointer to stack segment Program Status Word Stack Pointer Process State x Priority Root directory Scheduling Parameters Working directory Process ID User Id Parent process Group Id Process group Time when process started CPU time used C UT Svnnvzmg 25552 Dvevatmvsvstnms slides Mimi mmsmmwwm bwm mm Robbins Execution Environment Running Context S Registers in addition to general registers gt Program Counter PC contains the memory address of the next instruction to be fetched gt Stack Pointer SP points to the top of the current stack in memory The stack contains one frame for eac procedure that has been entered but not yet exited gt Program Status Word PSW contains the condition code bits and various other control bits 8 Higher level resources open files etc 3 Thread synchronization and communication resource semaphores and sockets urge Svnnvzmg 25552 Dvevatmvsvstnms slides Mimi mmsmmwwm bwm mm Robbins Address Space 2 Range of memory locations gt code section text segment gt data section global variables gt stack temporary data 9 local variables and return address etc gt Auxiliary environment variables and command line argumen s Heap memory for dynamically allocated data items How big is the address space Auxiliary regions Stack 1 Heap Text C UT Svunvzmg 25552 Dvevatmvsvstnms slats incaivmatn mmmmmvwwm bvmv mm mm Base and Limit Registers 3 Special CPU registers OXFFFF gt Base register start of the process s memory partition gt Limit register length of the process s memory pa ion gt Access limited to system mode 33 Address generation gt Logical address location from the process s point of View gt Physical address location in actual memory gt Physical base logical address gt Logical address larger than limit 9 rror UT Svunvzmg 25552 Dvevatmvsvstnms slats incaivmatn mmmmmvwwm bvmv mm mm L OXZOOO OXQOOO Logical address 0x1204 Physical address 0x12040x9000 0xa204 Multiprogramming More Processes 38 Each rocess has its own base OXFFFF and lirr hit registers I P2 X Memory allocation no overlap for protection Pl ids 0 How to keep track free memory How to allocate memory quotl Virtual 7 physical address translation Process Creation and Problems 8 Principal events that cause process creation gt System initialization gt User request to create a new process run a program gt A running process use system call for process creation 8 Parent process creates child processes gt Hierarchy of processes 8 Problems and Issues gtWill the parent and child execute quotconcurrentlyquot gt How their address spaces are related gtWilllshould the parent and child share some resources Ira3A vainvzmg 25552 mmmsvsm slides minim makiiabkindlyviwided bwm KaiA Rubbing iEI Example An Process Tree In Solaris l i pld7775 pid29 i i 6 emacs Vin 7735 pid m as 25552 Upualmvsvstnms slides minim makiiabkindlvvlwided bwm KaiA Rubbing ii C UT System Call for Process Creation UNIX 3 Each process has a process identi er pid a Parent process executes fork to spawn a child process 38 The child process has a separate copy of the parent s address space 8 Both the parent and the child continue execution at the instruction following the fork system call gt Return value of 0 9 new child process continues gt Otherwise pid of child process 9 parent process continues Svrinvzmg 25552 Upualmvsvstnms slides minim makiiabkindlvvlwided bwm KaiA Rubbing 12 Unix fork pi d 25 pid 25 Data Data Text Resources Text Stack Stack Process Status File Process Status u int cpid fork if cpi if cpid o ltchild codegt ltchild codegt exit0 exit0 ltparem codegt ltpZIrent codegt waitcpid wmtmnd c UNIX kernel UT Spurn 2mg Rabbms 13 Load A Different Program after fork SChild process uses execlp to load different program void main int pid pid form if pid lt 0 errormsg else if pid 0 child process execlp binls ls NULL else parent process parent will wait for the child to complete wait NULL exit0 c mu M Svunvzmg esaaza Dvevahnvsvstnms shdes meme makuabkmd vwwmed bwm ma Rabbms Activities in Processes 3t Bursts of CPU usage alternate with periods of HO wait 38 Some processes are CPUbound they don t make many lO requests 38 Other processes are IObound and make many kernel requests iiotai CPU usage CPU bound CPU bursts lO waits lO bound c Totai iO image quot1quot Time D vainvzmg 25552 Dveiatinvsvstnms slides Mimi mmsmmwwm bwm mm Rubbing Process States and Transition Scheduler C 0139 vainvzmg 25552 Dveiatinvsvstnms slides Mimi mmsmmwwm bwm mm Rubbing Process Termination 8 Process executes last statement and asks the operating system to delete it exit gt Output data from child to parent via wait or waitpid gt Process resources are de allocated by operating system 3 Parent may terminate execution of children processes eg TerminateProcess in Win32 8 Process may also terminate due to errors gtWhat if the parent process is terminated eg due to errors What will happen to the children process Svunvzmg 25552 mmmsvsm slides incaivmate mminsmawwm bwm mm Rubbing Context Switch SWhen CPU switches to another process the system must save the state ofthe old process and load the saved state for the new process 8 Contextswitch time is pure overhead the system does no useful work while switching 8 Overhead dependent on hardware support typically 11000 microseconds Svunvzmg 25552 mmmsvsm slides incaivmate mminsmawwm bwm mm Rubbing Context Switch cont pracess Po opeialing system process P interrupt or System call executing save state imo Poin idle reload state lmm PCB imenupr a system call execuiing save state inlu PCE idle reload stare lmm PCB executing 25552 mmmsvsm siides minim mmixmawwwm bwm KaiA Rubbing iB idie C UT Svnnvzmg CPU Scheduling 8 One CPU 9 execute only one process at a time 8 More processes 9 wait for CPU accordingly 8 OS is responsible for the scheduling activities 8 Scheduling queues gt Ready gueue processes in main memory ready and waiting to execu e gt Wait gueue processes waiting for signalsinterrupts gt Device gueues processes waiting for Ho operations 8 Processes move between the various queues u Svnnvzmg 25552 mmmsvsm siides minim mmixmawwwm bwm KaiA Rubbing 2D Scheduling Queues lOqueue H lO request time slice expired child executes interrupt occurs c UTSA 21 spnng 2009 p p KayA Robbins wait for an interrupt When are processes scheduled 38At the time they enter the system gt Common in batch systems gt Two types of batch scheduling Submission of a newjob causes the scheduler to run Scheduling only done when a job voluntarily gives up the CPU ie while waiting for an lO request 38At relatively fixed intervals clock interrupts gt Necessary for interactive systems gt May also be used for batch systems gt Scheduling algorithms at each interrupt and picks the next process from the pool of ready processes c 01 22 spnng 2009 p p KayA Robbins Scheduling Goals 3 All systems gt Fairness give each process a fair share of the CPU gt Enforcement ensure that the stated policy is carried out gt Balance keep all parts of the system busy 38 Batch systems gt Throughput maximize jobs per unit time hour gt Turnaround time minimize time users wait forjobs gt CPU utilization keep the CPU as busy as possible 38 Interactive systems gt Responset e39 respond quickly to users requests gt Proportionality meet users expectations 3t Realtime systems gt Meet deadlines missing deadlines is a system failure c gt Predictability same type of behavior for each time slice UT Svrinvzmg 25552 mmmsvsm slats minim makiiabkmdiyviwided bwm KaiA mmquot 23 Performance Measurement for Scheduling 3 Throughput gt Amount of work completed per second minute hour gt Higher throughput usually means better utilized system 38 Response time gt Response time is time from when a command is submitted until results are returned gt Can measure average variance minimum maximum gt May be more useful to measure time spent waiting 38 Turnaround time gt Like response time but for batch jobs response is the completion of the process 35 Usually NOT possible to optimize for all metrics with the same scheduling algorithm UTs Svrinvzmg 25552 mmmsvsm slats minim makiiabkmdiyviwided bwm KaiA mmquot 24 Scheduling Algorithms S FIFO nonpreemptive based on arrival time gt Long computation process proceeds SSH console R SJFshortest job first preemptive amp nonpreemptive gt Optimal in term of waiting time 8 RR Roundrobin preemptive gt Processes take turns eg 10ms as Prioritybased scheduling gt Realtime systems earliest deadline first EDF 8 Multilevel queue priority classes gt System processes gtfaculty processes gtstudent processes uwu39gaevettssqbesk 39 short 9 long quantum25 naskinalypvwmm bwm Kay First Come First Served FCFS 3 Goal do jobs in the order Currentij queue they arrive 3 6 gt Fair in the same way a bank 3 teller line is fair 3 Simple algorithm 3 Problem long jobs delay every job after them gt Many processes may wait for Execution order a single long job FCFS scheduler 25552 mmmsvsm slats minim mmsmmwwm bwm KaiA Rubbing ZE Current job queue 4 3 6 SJF scheduler Execution order C UT vamvzmg 3 4 6 HI 25552 ammsmms slats minim mmsmmwwm mm mm Robbins Shortest Job First SJF 3 Goal do the shortest job first gt Shortjobs complete rst gt Long jobs delay everyjob r them 383 Jobs sorted in increasing order of execution time gt Ordering ofties doesn t matter 3 Shortest Remaining Time First SRTF preemptive form of SJF 3 Problem how does the scheduler know how long a job will take 38 Round Robin scheduling gt Give each process a xed time slot quantum gt Rotate through ready processes gt Each process makes some progress 3 What s a good quantum gt Too short many proces switches hurt ef ciency gt Too long poor response to interactive requests gt Typical length 10 50 ms C 0139 vamvzmg 25552 ammsmms slats minim mmsmmwwm mm mm Robbins Round Robin RR scheduling gtmoom Priority Based Scheduling 8 Assign a priority to each process gt Ready process with highest priority allowed to run gt Running process may be interrupted alter its quantum x ires 38 Priorities may be assigned dynamically High Ready processes Pawn 4 I Pumit J I I I Priority 2 Priority1 I I I gt Reduced when a process uses U time gt Increased when a process waits or lO 38 Olten processes grouped into multiple queues based on priority and run roundrobin per queue C UT svnnvzmg 25552 mmmsvsm slats incalvmatn makiiabkmdivviwrded bwm KaiA Rubbing 29 Different Schedulers S Processes may be first spooled to a massstorage system where they are kept for later execution at Longterm scheduler or job scheduler selects processes from this pool and loads them into memory for execution gt Controls the degree of multiprogramming gt Good process mix of lO bound and CPUbound processes as The shortterm scheduler or CPU scheduler gt Ready processes and allocates the CPU to one of them C 0139 svnnvzmg 25552 mmmsvsm slats incalvmatn makiiabkmdivviwrded bwm KaiA Rubbing 3D Threelevel scheduling Arriving b5 0Q a memory queu scheduler scheduler 38 Jobs held in input queue until moved into memory gt Pick complementary jobsquot small amp large CPU amp lOintensive gt Jobs move into memory when admitted 32 CPU scheduler picks next job to run as Memory scheduler picks somejobs from main memory and moves them to disk if insufficient memory space Ta 31 vainvzmg 25552 mmmsvsm slats math mamraskmdlvpvwmm bwm mm mm Scheduling Policy Vs Mechanism 8 Separate what may be done from how it is done gt Mechanism allows J Priorities to be assigned to processes J CPU to select processes with high priorities gt Policy set by what priorities are assigned to processes 3 Scheduling algorithm parameterized gt Mechanism in the kernel gt Priorities assigned in the kernel or by users 8 Parameters may be set by user processes gt Don t allow a user process to take over the system gt Allow a user process to voluntarily lower its own priority EAZ QJL EW a 223255532335 t asii i i d 35133153 5 sides MW 32 CPU Scheduling for Multiprocessors S Symmetric all CPUs run OS with self scheduling SAsymmetric one CPU run scheduler master gt Slave CPUs execute assigned processes 8 Process affinity migration or not 8 Load balancing pushpull process from other CPUs 8 Global queue vs separate queues 8 New architectures gt Simultaneously multithreading SMT multiple function units and running context registers more instcycle gt ChipMultiprocessors CMP multiple simple CPUs Tc cores on single 0 ip vainvzme c5552 Dvevatinvsystnms slats mime mutumnmwwm bwm KaiA washing 33 InterProcess Communication IPC process A process A process is M process a Message Passing Shared Memory Tu Svunvzme c5552 ammsysm side mum mmmaiwwm bwm KM hisquot 34 POSIX SharedMemory APIs 8 shmget allocate a shared memory segment gt5hm7id 5hmgetIPC7PRIVATE Size SilRUSRt 71WUSR as shmat attache the segment with one address gt5hm7addr chart 5hmat5hm id NULL 0 8 shmdt detach the shared memory segment gt5hmdt5hm addr 8 shmctl aterthe permission ofthe shared segment gt5hmctl5hm id cmd buf gt cmd SHMiLOCK SHMiUNLOCK I Pcis TAT IPCisET and IPCiRMID UT Svnnv 2mg 255523 Dvevatmv SVStzems shdes mcavpmm matauab kmd vvtwmed by 7m KayA Rabbms 35 IPC with Shared Memory POSIXC include ltsysipchgt include ltsysshmhgt int mainint argc char argv int 5 39d data create the shared segment hmid Shmget100 1024 0644 I IPCCREAT e data shmatshmid void 0 0 a riting share memory nt shmctlshmid IPCRMID NULL c return 0 w u vamvzmg 25552 mmmsvsm 5mg mcatvmatn mammaerva bwm mm mm ata shmctl shmid IPCRMID NULL return 0 39 UT 1 A5pm 2mg 255523 Dummy svsinms Slides meavpmm makiiab kindiyvlwided by 7m KaiA Rubbing 37 Message Passing a general mechanism 38 Message system processes communicate with each other without resorting to shared variables 38 A messagepassing facility provides at least two operations gt send message gt receivemessage gt These operations can be either blocking synchronous or non blocking asynchronous 3 What should we do for processes running on different computers eg in distributed system Shared memory vs message passing urn vainvzmg 25552 mmmsvsm 5mg math mminsmaiwwm bwm KaiA Rubbing 38
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'