OPERATING SYSTEMS CSCI 4730
Popular in Course
Popular in ComputerScienence
This 40 page Class Notes was uploaded by Ulises Graham Jr. on Saturday September 12, 2015. The Class Notes belongs to CSCI 4730 at University of Georgia taught by Staff in Fall. Since its upload, it has received 14 views. For similar materials see /class/202315/csci-4730-university-of-georgia in ComputerScienence at University of Georgia.
Reviews for OPERATING SYSTEMS
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/12/15
Chapter 6 Process Synchronization Part I 0 Why is synchronization needed CSCI 4730 0 Definitions Operating Systems What are race conditions What are critical sections What are atomic operations Synchronization P r o How are locks implemented a 1785 Maria Hybine le UGA Maria Hybinene UGA o o 39 Why does cooperatlon requ1re W o o 3 I o 7 quot synchronlzatlon an Example Executlon 0 Example Two threads narla and Tuc lter share an 1 Initialization balance 100 account With shared variable balance in memory 2 Maria deposit 200 d epOSit Maria I I 3 Tucker deposit 103d RegisterA 100 0 Code to depos1t 0 Compiled to assembly add RegisterA 200 void deposit int amount deposit deposit store RegiSterAi balance lead RegisterA balance load RegisterA balance balance balance add RegisterA amount add RegisterA amount depOSit TuCker amount store RegisterA balance store RegisterA balance 0 load RegisterA 300 add RegisterA 10 I store RegisterA balance 0 Both Maria amp Tucker depOSIts money into account Memory 39 Initialization balance 100 balance 310 v Maria deposit 200 Which variables are RegisterA 310 shared Which private Tucker deposit 10 Maria Hybine le UGA Maria Hybine le UGA 4 Memory 4 Memory balance 300 balance 110 RegisterA soo Concurrency RegisterA no Another Example o What happens if M amp T deposit 9 deposit concurrently I Who wms Assume any interleaving is possible 1 RegisterA balance No assumption about scheduler Observation When a thread is interrupted content of registers are saved and restored by interrupt handlers add Regi s terA amount store RegisterA balance deposit Maria deposit Tucker load RegisterA balance load RegisterA balance add RegisterA 200 add RegisterA 10 store RegisterA balance store RegisterA balance Time Maria Hybine le UGA Maria ybine is UGA Aside What program data is shared Local variables are not shared private E gtgt Each thread has its own stack gtgt Local variables are allocated on private stack Weird Bugs Never pass variable on another thr Race Condition 0 Results depends on order of execution Result in nondeterministic bugs hard o ln s e or store a pointerto a local eads stack Global variables and static objects are shared Stored in the static data segment accessible by any threads Dynamic objects and otherheap objects are shared Allocated from heap with mallnclfree 0 new a 12 e t r el 7 Deterministic lnput alone determines results ie the same in uts always produceth e results mum is o Intermittent time depended bug a small change may hide the real bug eg print statements can hide the real bug because the slo w dow processing and impact the timing of the threads my amn vs How to avoid race conditions time Pr0Vl o Idea Prohibit one or more threads from reading and wr lng shareddata at the same Cr Critical Sections 3 0 Problem 39 in ace con on 39e 4 provide mutual exclusion is not suffl I having threads cooperate correctly and e Mutual Excluslon ef cie ly a Section Part of program where What a shared memory is acc recon gmnn adieumt minim l t in s 5 int i 11mm 1mm new i ut ifno one gets into the critical section ven if several threads wants to get in y What about if someone mama m altsal waits outside the critical aturn FT quot i mama ma Mutual Exclusion Marla elle my critical tee Critical Section Problem Properties wielmetnmmaalmnn Required propen V 0 Mutual Exclusion Only one thread in critical section at a time mgssmm 0 Progress eg someone gets the CS y Not block others ust allo YchlXNucled We 394 WM mchthth maxim quotmmquot man is i there are requests to enterthe he to proceed eg no deadlocks Must not depend on threads outside critical section 7 lfno one is in cs then must let someo 39 o Bounded waiting starvationfre mum is e y Must eventually allow each waiting thread to enter Critical Section Problem Properties Required Properties 0 Mutual Exclusion 0 Progress someone gets the CS 0 Bounded waiting starvationfree Desirable Properties 0 Ef cient gtgt Don t consume substantial resources while waiting Do not usy wait ie spin wait 0 Fair gtgt Don39t make some processes wait longer than others 0 Simple Should be easy to reason about and use Man no ma Disabling Interrupts o Kernel provides two system calls Acquire a d 7 mmquot Releasa dasahle inuxruyls o No preemption when interrupts are off quot39 No clock interrupts can occ r o Disadvantages U m Elana nwise to give processes power to turn of errupts enable intemms e Exampe Problem Never turn interrupts on again Does not work on multiprocessor W 7 Only disables one CPU the other CPU can still access shared memory 0 When to use Good for kernel itself to disable interrupts for ew instructions while it is updating variables or lists Man Miner ma Attempt 1 Shared Lock Variable 0 Single shared lock variable Heinlein lt1n gf ise Wu naiea mime void deposillintnamnunl me i 2 has 5 z 39amnunl 1 Critical quotexam iaei t e an 0 Uses busy waiting 0 Does this work Which principles is violated Man no ma Critical Section Problem Need Atomic Operations 0 Basics Need atomic operations gtgt No other instructions can be interleaved gtgt Completed in its entiray without interruption 0 Examples of atomic operations gtgt Loads and stores of word load terl st re terZ 11 gtgt Code between interrupts on uniprocessors e isable timer interrupts don t do any IID gtgt Special hardware instructions later 7 load storequot 39n one instruction 8t e 7 Compare ampSwap Man no ma Software Solutions 0 Assumptions atomic loads atomic stores 0 Notation True mean unavailable False means available eg no one is in CS Man Miner ma Attempt 1 Shared Variable mums um Era15 prumss tucker Emu cs me o M reads lock sees it as false 0 T reads lock sets it as false k 0 Two threads in critical Section Man no ma Attempt 1 Lock Variable Problem amp Lesson 0 Problems gtgt No mutual exclusion Both processes entered the CS 0 Lessons Failed because two thr ds read th e lock variable simultaneously and both thought it was their tum to get into the critical section Progress Eounded someone wamng No shared Lock variable Man Mmle ma Attempt 2 Strict Alternation Murman ED Nbquot IS hlnckmul 1 Process tucker tucker IS not Imumm In cs Initialize Mariais 0 ampTucker is 1 o M reads turn sees hert urn M done and change turn to other o T never requests cs no money Man Mm ma Attempt 2 Strict Alternation 0 Problem Progress 0 Lesson Why did strict alternation fail Pragmatically Problem with the turn variable is that we need state information about BOTH processes We should not wait for a thread that does not need if they don t need to get to the critical section 0 Idea We need to know the needs of othe s r Check to see if other needs it Don t get the lock until the other is done with it Man Mmle ma Attempt 2 Strict Alternation o Idea Take turns turn determines which thread can enter set to thread ID s 0 or 1 m cm e n1 shaxed mason void depositi int mount l My whi1e1lllxn 0 pm l u wan el cs am We l 0 Does this work Mutual exclusion Progress someone gets the cs if enpty no deadlock WWW WA Bounded Waiting no starvation Attempt 2 Strict Alternation 0 Problems No progress 7 if no one is in a critical section and athread wants in it should be allowed to enter gtgt Ef ci 7 Pace execmion Dictated by the slower ofthe two threads IF Tucker uses its CS nly one per o hourwhile Maria would like to use it at a rate of 1000 times per hour Tucker s slow spee then Maria has to adaptto d lvutual Exclusion strict Alteration Man Mm ma Attempt 3 Check State then Lock 0 Idea Each thread has its own lock lock indexed by tid 0 1 Check other s needs hoolean incklz false mint tam shazed void deynsm intv am ckli e nu l l 39I39 wait 3 txlle 7amounl magical section quot65 luckhid fa1n 0 Does this work Mutual exclusion Progress someon e gets the CS if empty no deadlock Bounded Waiting no starvation Man Mmle ma Attempt 3 Check then Lock Attempt 3 Check then Lock uv Pumas a l s 1 cs 1 Process tucker Emu cs o M checks 1r Tucker 1s Interested and he Isn39t o T checks 1r Nhna 1s Interested and she Isn39t o Swmch back to Nhna she now sas hIs lock 0 Swmch Hack to Tucker he sas hIs lock Attempt 4 Lock then Check 0 idea Each thread has its own lock lock indexed by tid 0 1 Check other s needs zfalse fagquot J enema hnnle am 391Iick2 1 he 1 demon x 0 Does this work Mutual exclusion Progress someone gets the CS if empty no deadlock Bounded Waiting no starvation Man new UBA Attempt 4 Lock then Check u Pincus nuns Mona mus lor lurln 1 Process tucker rum walls 11 Mm me o Mmual Exclusion Yes 0 Deadlocks Each thread waits for the other Each one thinks that the other is in the critical section Man women UBA 0 Problems No Mutual Exclusion 0 Lesson Process lock s the critic l sect AF the process has checked It is available but before it enters the section 0 idea Lock the section rst then lock Mltual Excluslon No check then Lock Man women UBA Attempt 4 Lock then Check u when on 1 Process lurker nme Mutual Exclusion o aria s View Once Maria sets her oc gtgt Tuckercannotenteruntll Nhna 1s done 0 So yes Mmual Exclusion Man new UBA Attempt 4 Lock then Check o Problems w No one gets the critical section h thread insisted on its right to get the CS and did back off from this position I Lesson Again a state problem athread misunderstood the state ofthe othe thread I lied Allow athreadt back off to give the other a chance to enteri 5 cr al section 1 Eac not Eounded wmng starvauon Stnct Alteratuon Face Hmled Io sowest process check then Lock Attempt 5 Defer backoff lock Attempt 5 Deferral I Idea Add an delay tnxIh E E OK as in OK in mail 1 PmcEs mcier 5 0K1 eryn OK I iinl DK21IHynu raw cs m I Mmual Exclusion Yes I Live Lock sequence can be broken if you are lucky CS Normally wedlock iguameea not 39 to be ableto proceed E cs gtgt Not starvation threads starves when a 39 process repeatedly looseto the other threads here both loose Attempt 5 Deferral Lessons I Problems lvutual Exclusion strict Alteration Pace med Io wwesi process check then Look Lock then check Deferral Not really Man Miner ueA Attempt 6 Careful Turns I Take careful turns Mmeam uca I PI enters CS no later than P I We need to be able to observe the state of both processes Lock not enough I We most impose an order to avoid this mutual courtesy ie after youafter you I Idea use tum variable to avoid mutual courtesy tes who has the right to insist on entering his lcal section Man Miner ueA Dekker s Algorithm Correctness Mutual Exclusion Mu ual Exclusion Two threads cannot bei the critical region simultaneously Suppose they are then for each point orview an r 1lnc1 l true 7 zincml raise r llncl true 7 Alncl l V lg 1 t2lt M so F0 check lock1 is ialse before enteringits csi t2 7 3 mu 3 imlll uuen remanstiue sn 12 lt13 gtgt sot1ltt2ltt5lttA eut lockM cannot becomeralse until F0 exits c Mmeam uca Attempt 6 Dekker s Algorithm Attempt 7 Peterson s Algorithm 0 Idea also combines turn and separate locks I Take careful turns 0 When 2 processes enters simultaneously setting turn to the other releases the other process from the while loop one write will be as a Mutual Exclusion Key Observation tum cannot be both 0 and 1 at the same time Mm HWle UEA Mm HWle UEA Peterson s Algorithm Intuition Summary Software Solutions al axolusion Enter critical section if and only if gtgt Other thread does not want to en er Otherthread wants to enter but yourt r Mltual o Progrs Both threads cannot wait forever at while loop EXquot quot quot Completes irotner process does not want to enter other process matching turn will eventually finish a Bounded waiting slrlct Alta39atlon lgt Each process waits at most one critical section Pace rmed Io slowest Nocess Not really Sl Wel emu tter V 41593 Jamie34412253 Man Wm M Man Wm M Lamport s Bakery Algorithm Bakery Algorithm a Pick next highest ticket may have ties I Ida Bakery each thread plcks next hlghest tlcket may have es o Enter CS when my tlcket Is the lowest 0 Enter critical section when have lowest ticket 0 Data Structures size N s39 i true iff Pi in the entry protocol Value of ticket one more than rmx number 1 gtgt Threads may share the same number 0 Ticketisapair numbertid i o Lexicographical order a b lt e d ifaltcorifacmnbltd number l139l lt nunlbezltidtid MamHvblmm UEA CSCI 4730 Operating Systems Synchronization Part 1 vlas Mm Hybmette USA 0 o W Why does cooperation require if synchronlzatlon Rev1ew 0 Example Two threads Maria and Tucker share an account with shared variable balance in memory 0 Code to deposit 0 0 Compiled to assembly void deposit int amount deposit load RegisterA balance balance balance amount add RegisterA amount store RegisterA balance 0 Both Maria amp Tucker deposits money into account Initialization balance 100 Maria deposit 200 which variables are shared which private Tucker deposLt 10 Marla Hvbmele UGA 4 Memory 4 Memory balance 300 balance 110 RegisterA 300 RegisterA 110 o What happens if M amp T deposit concurrently deposit Assume any interleaving is possible had RegiSterAl balance No assumption about scheduler add RegiSterAl 31mmquot Observation Nhen athread i slime rrupted 5t re RegiSterA balance e restored by interrupt handlers deposit Maria deposit Tucker load RegisterA balance load RegisterA balance add RegisterA 200 add RegisterA 1 0 store RegisterA balance 2 store RegisterA balance Mane ybmet a UL Chapter 6 Process Synchronization 0 Why is synchronization needed 0 Definitions What are race conditions gtgt What are critical sections What are atomic operations 0 How are locks implemented Mane Hybmel 2 USA Example Execution 1 lnitializationba1ance 2 Maria deposit 200 3 Tucker deposit 10 deposit load RegisterA balance add RegisterA amount store Regis terA balance RegisterA 310 Time Mane Hvbmel 2 USA Q7 7 we w deposit Maria load RegisterA 100 add RegisterA 200 i tore RegisterA balance deposit Tucker load RegisterA 3 00 add RegisterA 10 s tore RegisterA balance Aside What program data is shared 0 Local variables are not shared private gtgt Each thread has its own stack gtgt Local variables are allocated on private stack gtgt Weird Bugs Never pass share or store a pointer to a local variable on another threads stack 0 Global variables and static objects are shared gtgt Stored in the static data segment accessible by any threads 0 Dynamic objects and other heap objects are shared gtgt Allocated from heap with mallocfree or newdelete Mane Hybmet a USA Race Co nditio n Oksu s mm a s on omu Mureumnn Resultlnnon amwwm hugs mmmw mmnm w m Memms Mm t 0 me was my yum mt Mm o lmunlltzm 4m newsman nug lulll clung ny mamng bug 241 pnm m an mum val hug heuuselhe mw down Dunc Ila Ind mm m mung mm Ima ib Critical Sections 0 Prnhlm Avnmlng ncecmdnlnni mm Dmvme mmquot excluslnnhsnm aim mm mvlm mmas mutant cone lynd qr lem y mum n noun gets mm mm semen W n severzl mm MS to get W nsumsmuhecmmzl mquot Critical Section Problem Properties lemma pm M m mpem 0mm mm mm mm WWW Estmnmmldsmmmm o Rounded mnlng nrmmnmen How m avoid race conditions It 2 lugml wnmu 5mm mum L m o cum mm Sumoquot Pm Morngnm Mel newly s Imam Mutual Exclusion Critical Section Problem Properties MW may Muml Mum ymgtssxsomm Wm 51 Emndedwmtlng xmmmm utmmt mptmts men Dmccrsmveslhstm2l msmesmle mm um ammo svnwztl Mmmmemtsemuwmnmm Critical Section Problem Need Atomic Operations 0 Basics Need atomic operations gtgt No other instructions can be inter aved Completed in its entiretywithout interruption 0 Examples of atomic operations gtgt Loads and stores of word 7 load eg terl ore registerz st gtgt Code between int n errupts on uniprocessors Disable timer interrupts don t do any IID Special hardware instructions later 7 load storequot in one instruction 7 Te 8t et 7 CompareampSNap Mmeamt m Software Solutions 0 Assumptions atomic loads atomic stores 0 Notation True mean unavailable False means available eg no one is in CS ManaMbmet m Attempt 1 Shared Variable n umss Malia Emr l as EmerCS lime o M reads lock sees it as false 0 T reads lock sets it as false 0 Two threads in critical Section Mmeamt m Mm we Man Home Mmeamt m Disabling Interrupts o Kernel provides two system calls mi mull gtgt Acquizeo and amine lutexxmts Release u A A m r r gtgt No clock interrupts can occur 0 Disadvantage 39 39 I enable mum l mu Release l w rum ui interr s e Neverturn interrupts on again gtgt Does not work on multiprocessor 0 When to use gtgt Good for kernel itself to dis ble interrupts for a fewinstructions while It is upda in variables or lists m m Attempt 1 Shared Lock Variable 0 Single shared lock variable hoolean lock void aepnsmm ram shalei mm L ammmll Emlycs whilel lock mu n In Wait 1m me CS amm K mum mum section 0 Uses busy waiting 0 Does this work m Which principles is violated mutual progress bounded Attempt 1 Lock Variable Problem amp Lesson 0 Problems gtgt No mutual exclusion Both processes entered the CS 0 Lessons Failed because two threads read the lock variable simultaneously and both thought it was their tum39 to get into the critical section Progress Eounded someone wamng No gets the cs 5 rvation ta shared Lock Variable Attempt 2 Stri Alternation o Idea Take turns turn determines which thread can enter set to thread ID s 0 or 1 in t n shaled valiahle void deposili int mum i t Em39VCS39 whilet um i new i I39 wait I i s We ll cxitical section 0 Does this work Mutual exclusion gtgt Progress someone gets the CS if empty no deadlock WWW W Bounded Waiting no starvation Attempt 2 Strict Alternation 0 Problems No progress if no o e 39 in a critical section and athread wants in it should be allowed to enter Efficiency 7 Pace of execution Dictated by the slower ofthe two threads IF Tucker uses its cs only one per hour while Maria would like to use it at a rate of 1000 times per hour then Maria has to adapt to Tucker strict Aiteraiion Mamtime m Attempt 3 Check State then Lock 0 Idea Each thread has its own lock lock indexed by tid 0 1 Check other s needs hnnlean 1nck2 z ma serum t false false shned mum i witnei lockDrlid mie i t I Wait Em39ycs39 lockhid mic halance ilt amount ll cxitical section quot55 quot henna false 0 Does this work Mutual exclusion Progress someone gets the CS if empty no deadlock Bounded Waiting no starvation Mmetime ucu Attempt 2 Strict Alternation muss m i a izi ii 1 pmoess Yuma Tucker is not imeresed in cs hymn Initialize Maria is 0 ampTucker is if M reads turn sees herturn M done and change turn to other e T never requests cs no money mumtime ucu Attempt 2 Strict Alternation 0 Problem Progress 0 Lesson Why did strict alternation fail Pragmatically Problem with the turn variable is that we ne sta e in ormation about BOTH We sho Id not wait for a thread that does not need if they don t need to get to the critical section 0 Idea We need to know the needs of othe s r Check to see if other needs it Don t get the lock until the other is done with it Mamtime m Attempt 3 Check then Lock II pimss Maia mic cs 1 pmoess Yuma Enter cs M checks If Tucker is interested and he isn39t T checks IflIhrla is interested and she isn39t swmch back to Maria she now sas his iock swmch Hack to Tucker he sets his iock Attempt 3 Check then Lock 0 Problems No Mutual Exclusion 0 Lesson Proce s lock39s the critical section AFTER the process has checked It is avallable but before it enters the sec i n o Idea Lock the section first then lock checkthen Lock mum am m Attempt 4 Lock then Check ll plum lama 1 pmmss rum ilrne Mutual Exclusion o aria s View Once Maria sets her E39 n x 2 u s o E n a o 13 0 So yes Mmual Exclusion Minimum m Attempt 4 Lock then Check o Problems W No one gets the critical section Each thread insisted on its right to get the CS and did not back off from this position I Lesson Again a state problem athread misunderstood the state of the other thread I Idea Allow athread t back off to give the other a chance to enter its cr al section Mutual Excluslon Stnct Alteration Face men 10 slam process check then Lock Lock then check Attempt 4 Lock then Check 0 Idea Each thread has its own lock lock indexed by tid 0 1 Check other s needs hnnlean lock2 319 false ll shued mu deposill m mum l 1ncktid mm Em39ycs39 quotnun luckmuu Lute l U I mmw CS 131 K mum magnum quot65 quot lacuna false 0 Does this work Mutual exclusion Progress someone gets the CS if empty no deadlock Bounded Waiting no starvation mum am m Attempt 4 Lock then Check ll plum lama Mnna wuva lucka 1 pmmss rum 2 rum walls 1m Mam ilrne o Mmual Exclusion Yes Deadlocks Each thread is in the critical section Minimum m Attempt 5 Defer backoff lock 0 Idea Add an delay hnnlean 1nck2 false false Shazed Inl l void deposilt int amn lockhid mm quotnun lockDrtid mu Emlycs lockuid 3159 delay lockuid mu CS halancelt amount ll cxitical section WEE lockhid 31quot mum am m waits for the other Each one thinks that the other Attempt 5 Deferral I Dims me la l Attempt 5 Deferral 1 Pmm lumu nck2 hnnlean falser mo ummi m mm D false Not starvation threads starves when a process repeatedly looseto the other threads here both loose Deferral Mmeem ucu Lessons ivmual E xclusion No Yes Face armed lo slows Names No 0K 2m nu 0K Inn Vnuun 0 Problems eryn OK I on OK me ynu nne Strict Alteration o MLtual Exclusion Yes 0 Live Lock sequence can be broken if check then Lock you a lucky gtgt Not really a deadlock guaranteed not L k thequot we to be able to proceedi Yes Yes Not really Attempt 6 Careful Turns 0 We need to be able to observe the state of both processes Lock not enough hnnlean 1nck2l false 3159 ll shazed in can n H shaxed valid1 mu deposit inc amount i 0 We most impose an order to avoid this i l i 1ncktidl rue mUtual courtesy Lequot after you after you quotM121 lucklrtid lxlle D If whack othex ldea39 in man Jena l lhEl cm cu insist use turn variable to avoid mutual courtesy lockmd false ll than I def while in In 39cates who has the right to insist on entering his luckmd m al section halance K mum ll clitical quotoutquot nun 1 e no luckhid 3159 WWW UBA 0 Take careful turns ManaMblnet UBA Dekker s Algorithm Mutual Exclusion Two threads cannot be in Attempt 6 Dekker s Algorithm the critical region simultaneously Suppos they are then for each point vle n r 1lnc1 l true 7 Zlncl l false hnnlean 1nck2 7 false 315 lhazed in m n Shaxed vazi e vnid deposit inc mount l l1 e llncml true luckhid mu 7 Marlin raise vgt whilst leekneciu clue l H Cher nlhex 0 PH enters CS no later than P1 gtgt rzltwso check lockmis raise before i quot391quot 7 entering cs hound n 1 def gtgt 27 IlAlldH quotM19 e Merllncl l xruenrenznstruesntzm 9 39 quot 1 k quot97 gtgt WWW b emm cs halancelt mane Critical section autlockiocannotbecorneiaiseunui P0 exits mm 1 7 u 39 um 1 t andwe assumedtnatbotn P0 and P1 were In W l 7 99 no i z E thecsatthesanietinie us itisinipossibleto k 1 P1 39 1 k 1 1 39 have checked flag and Minnow ucu 0 Take careful tu rns Mmeem ucu CSCI 4730 Operating Systems Th reads Ills Mane Hybmelle UGA Review What is a Process Chapter 4 Threads Questions A process is a program in execution o Execution stream gtgt stream of instructions gtgt sequential sequence of instructions gtgt thread of control 0 Process context gtgt Everything needed to run restart the process Registers program counter stack pointer general purpose gtgt Address space Everything the process can access in memory Heap stack code Mane Hvbmel 2 USA What are are problem s with Processes o How is a thread different from a process 0 Why are threads useful 0 How can POSIX threads be useful 0 What are userlevel and kernellevel threads 0 What are problems with threads Maria Hybmel 2 USA Review What Makes up a Process o How do processes independent memory space Communicate Not really that simple Message passing Shared Memory Set up a shared memory area 0 Problems Overhead Both methods add some kernel overhead lowering performance Complicated IPC is not really that natural increases the complexity of your code Mane Hybmel 2 USA Mane Hvbmel 2 USA Program code text Data heap Process stack OS Resources data Registers User Mode Address gtgt global variables gtgt heap dynamically allocated memory stack gtgt function parameters gtgt return addresses text gtgt local variables and functions U 1 m o to gtgt program counter stack pointer dress space are the shared resources ol all lhreads in a program 4 Processes versus Threads Solution A thread is a lightweight process LWP 0 An execution stream that shares an address space gtgt Overcome data flow over a file descriptor gtgt Overcome setting up tighter memory space 0 Multiple threads within a single process Examples 0 Two processes copies of each other examining memor address 0xffe84264 see different values ie different contents gtgt same frame of reference 0 Two threads examining memory address 0xffe84264 see same value ie same contents Mane Hybmel 2 USA What Makes up a Thread Single and Multithreaded Process Armless Own registers quotW awn program l Own stack pointer State running sleeping T I Signal mask stzk code data les a dless Space alelhe shale lesculces 7 Mm mum UBA mam WE quot 3 WWquot Mm mum UBA Why Support Threads Why Support Threads 0 Dividelarge task across severalcooperative tlile39adls o DivideLlarge taskiacros s several cooperative threads I Multithreaded task h rformanc I V y I V 39 0 Examples 0 Adapt to slow devices Web Server create threads to One thread waits for device while other threads message from client Get URL data from disk Conpose response Tisen res 9quot I o Parallelism gtgt Ward Pmcessor Create threads to gtgt Each thread runs simultaneously on a multiprocessor o Defer work gtgt One thread performs noncritical work in the background when idle Display graphlcs Read keystrokes from users Perform spelling and gramrmir checking in background Minimum Minimums m Why are Threads Challenging Why Threads instead of a Processes PThread Example Ouput l 0 Advantages of Threads pumaan u m Thread operations cheaper than corresponding rr39lthma m Chquot quotquot92 Unread m P700955 uParanaquots rat 7 pthma icmahet n1 um pang 1mm 39lmsg n Creation termination context switching rem Pthmm Lcmahet uir quotI39LL printJn mid quotivM2 l u re re IPC cheap through shared memo u H a l 0 need to invoke kernel to corrlnunicate between fprintflstden r quotmum pthxeaLcmacea failedn li thread exitlll l o DIsadvantages of Threads Emmyum H mm H y nweadjninl t2 mm H Concurrent programmlng Is achallenge Print quotThread 1 and thread 2 cmlemw H threads needed to use l Synchronlza I ma printiinlvnid 3917tr on betwee shared variables more on this later minimum char whptrn Min Whine UBA Min hymns Why are Threads Challenging 0 Example Transfer 50 00 between two accounts and output the total balance of the accounts M Balance in Maria s account begin 5100 T Balance in Tucker s account begin 550 B Total balance oTasks T 50 M 100 M M 50 00 T T 50 00 B M T 13 mumamt m Common Programming Models 0 Managerworke r gtgt Single manager handles input and assigns work to the worker threads 0 Producerconsumer gtgt Multiple producer threads create data or work that is handle by one ofthe rrultiple consurnert reads 0 Pipeline gtgt Task is divided into series of subtasks each ofwhich is an led in series by a different thread Why are Threads Challenging 50 M 100 o Tasks T M M 50 00 one thread debits amp credits T B T 5000 M T one thread totals MM5000 M I 5000 BMT TT5000 BMT MM5000 BMT T 5000 TT5000 14 mumamt m gt Thread Support 0 Three approaches for thread support Userlevel threads Kernellevel threads Hybrid of Userlevel and Kemellevel threads 16 WWW m WWW m Latenc1es UserLev el Threads o Manytoone thread mapping 0 Comparlng userlevel threads kernel threads and Implemented by quotsemevel rumime processes libraries o Null fork the timeto create schedule execute and Create schedule Synchronimthreads at r 39 39 userlevel of creating a thread os is not aware of userlevel threads I SignalWait the time for an entity to signal a waiting entity 7 OS thinks each process contains only a and then wait on a condition overhead of synchronization Single thread of control 0 Advantages Procedurelzll 7us User Level Kernel Level P gtgt Does not reouire ossupport Portable mm quotquot5 Threads Threads quot7095595 Czrrrl scheduling policyto meetapplication user level Null fork 34 948 11300 Lowerovrerhead thread operations since I39IQSlsfem calls Signalwait 37 441 1840 O Disadvantages gtgt Cannot leverage rnultiproc39essors no true parallelism 17 39 mumamt m WWW B gntire process blocks when one thread blocks 13 Blocked UL Threads Jacke ng o Avoids blocking39 on system calls that block eg IIO 0 Solution KernelLev el Threads 0 Onetoone thread mapping gtgt 05 provides each userlevel thread with a kernel thread gtgt lnstea of ca ling a blocking system call ca n Each kernel thread scheduled independently a plication level llojacket routine nonblocking call Thread warm 5 creation schedu in gtgt Jacket routine provides code that deterrrl39nes whether II synchronization perfo med by 05 d 39 39 usy Busy 7 Thread enters the ready state and passes control to another 0 AdVa tages thread gtgt Each kernellevel thread can run in parallel on a 7 Control returns to thread it retries 39 rocessor Idle W en one39threadblocks otherthreads from process can 7 Thread is allowed to make system call he Sch dul I Disadvantages 19 Maugham ma Mmeam M Higher overhead for thread oper 39on oskrrust scaleywell with increasing TwoLevel Model oneone amp strict manytomany gtgt 05 provides each userlevel thread with a kern read gtgt Supports both bound an unbound threads 7 Bound threads permanently bo nd to a single kernel level thread 7 Unbound threads may move to other kernel threads o Advanta Hybrid of Kernel amp User Level Threads in n thread mapping many Application creates m to many ds gtgt 05 provides pool of n kernel threads gtgt Few userlevel threads mapped to each kernellevel thread I Advantages Flexible best or two worlds Disadvan a gtgt More complicated can get best or userlevel andkernellevel implementations s well given many shortlived userthreads mappe constantsize pool I Disadva Manama m Howto select mapp39ng 7 llowto determine the best number or kernel threads 7 Userspeclfl r s dynamically adjusts numberdependlng on system load Thread Models Threading Issues fork amp exec o fork Duplicate all threads 0 Kernel Level Windows 9598NT2000 Solaris Linux 0 User Level POSIX Pthreads Mach Cthreads Solaris threads 0 Hybrids IRIX HPUX True 64 UNIX Older Solaris models Resulting new process is single threaded o exec Mmeam ma Replaces the process including all threads Mmeam ma Threading Issues Cancellation 0 Example 1 User pushes top button on a web owsers while other threads are images one thread per image 0 Example 2 Several threads concurrently searches data ase and one thread finds targe data 0 Asynchronous Cancellation Immediate 05 need to reclaim resources 0 Deferred Cancellation Thread terminates it self when notices it is scheduled or termination mummm UBA Other Thread Issues Threading Issues Threads and Signals 0 Problem To which thread should OS deliver signal 0 Option 1 Require sender to specify thread ID instead of process id gtgt Sender rmy not know about individual threads 0 Option 2 05 picks destination gtgt POSIX ignals thread Each thread has signal mask disable speci ed l gtgt 05 delivers signal to all threads without signal mas ed gtgt Application determines which thread is most appropriate anding signal 0 Synchronous delivered to the same process that caused the signal 0 Asynchronous event is external to running process 0 Creating thread is costly o No bound of number of threads Mansthmete m Scheduler Activations 0 Provides better 05 support for user level threading Dynamic adjustment of number of kernel level threads to user level threa s Eg TWo level and the m n thread models need to maintain appropriate ratios Key Idea Kernel noti es thread scheduler of all kemel events via upcalls mummm UBA 26 mm m Thread Pools 0 Create a number of threads in a pool where they await work 0 Advantages Usually slightly faster to service a request with an existing thread than waiting to create a new threa Allows the number of threads in the applications to be bound to the size of the pool 0 The number of threads can be s Mansthmete m 0 Use an intermediate data structure 0 Details User level threads run and are sche u ed ythe user level sc e uler on virt gtgt A data stmcture or lightweigh proce mummm UBA et heuristically based on the hardware and can n be dynamically adjusted taking into account user statistics Scheduler Activations etween userkemel level threads ual processor we LWP that is between the kernel thread and the user threa WP is attached to a kernel thread and kernel threads are what the OS schedules to run on physical processors l CSCI 4730 Operating Systems File System 175 Mm Hybmettg UGA Motivation IO is Important Chapter 1011 File System 0 Applications have two essential components Processing gtgt InputOutput IIO What applications have no input no output 0 HO performance predicts application performance gtgt Amdahl s Law If continually improve only part of application eg processing then achieve diminishing returns in speedup Example infinite speedup and affect only 15 of the overall task roughly 1I1015 118 times faster max f portion of application that is improved eg processing speedupf speedup of portion of application SpeedupApplication 1 1 f fspeedupQ Examples o f 15 speedup 2 speedupm 108 o f 12 speedup 2 speedupm 133 o f 13 speedup 2 speedupm 120 Maria Hybmei 2 USA Abstraction File 0 What are files What is file metadata o How are directories organized o What operations can be performed on files 0 How are directories organized o What is the difference between hard amp soft links 0 How are files protected Mane Hybmel 2 USA Role of OS for IO 0 User view Named collection of bytes defined by user Untyped or typed Examples text source object executables applicationspecific Permanently and conveniently available 0 Operating system view Map bytes as collection of blocks on physical non volatile storage device Magnetic disks tapes NVRAM batterybacked RAM Persistent across reboots and power failure Maria Hybmet 2 USA 0 Standard library Provide abstractions consistent interface Simplify access to hardware devices 0 Resource coordination gtgt Provide protection across usersprocesses gtgt Provide fair and efficient performance 0 User processes do not have direct access to devices Could crash entire system gtgt Could readwrite data without appropriate permissions gtgt Could hog device unfairly 0 OS exports higherlevel functions File system Provides file and directory abstractions gtgt File system operations mkdir create read write Mane Hybmei 2 USA Files Attributes MetaData System information associated with each le Name only information kept in humanreadable form Type needed for systems that support different types Location pointer to file location on devicedisk Size current le size Protection bits controls who can do reading writing executing Time date and user identification data for protection security and usage monitoring Special file Directory Symbolic link Metadata is stored on disk Conceptually metadata can be stored as a array on disk eg directory atlasmaria143 ls lig ch11ppt 231343 rw r r 1 profs 815616 Nov 4 2002 ch11ppt Maria Hybmet 2 USA Mm Whine UBA 0 Directory system function Maps ASCII names onto d ta what is needed to locate the a Abstraction Directories Organization technique Map file name to blocks of le on disk data Actually rmp le name to le metadata which enables one to nd data on disk Simplest approach Singlelevel directory gtgt Each le has unique name special part of disk holds directory listing 7 Contains lt le name metadata indexgt pairs 7 How should this data structure be organized Twolevel directory gtgt Directoryfor each user Specify le with user name and le name gtgt Disadvantage Each user cannot organize les Directory Implementation 0 Where do we store the files attributes Mall Home m Mm mama UBA gtgt A simple directory xed sized entries attributes stored 39 h the entry Directoryin each entry just refers to an inode UNIX inplementation File System Expanded data om Mall Home us Mm mama UBA Directories TreeStructured gtgt Directory is stored and treated like a le Special bit set in metadata for directories 7 User programs can read directories 7 Only system programs can write directories characters eg or I Special directories Root Fixedindex for metadata eg 2 o in gtlt m 3 E 35 5 r n r H ill a ctory listing contains ltname indexgt but name can be cto gtgt Read 9 verify no c exists allocate c and add c to directory Mm Whine UBA Directory Structure 0 A directory file is a sequence of lines each line holds an inode number indexnode and a file name o The data is stored as binary so we cannot simply ew it cat to VI but some UNIXs allow an octal dumpquot other formats also available atlasmlaximl 39l ad in nnn n 1252 312 n t n um n nnnnnzn n t n nnz n n n nno mum in a x i a c n 1 gnnunsu n no n n q n n n n AcyclicGraph Directories 0 More general than tree structure gtgt Add connections across the tree no cycles gtgt Create links from one le or directory to another 0 I gtgt Io Can use name a or hquott0 ard link In a bquot aquot must exist alread to same le data gtgt lrrplementation Multiple directory entries point to same maadata 1ink mariahtm1quot tuckerhtm1quot i q 311 r w n Why Links Creating Links o A link is a pointer to afile 0 Useful for sharing files A f can be shared by giving each person their own link pointer to it n ltexist1nqef11egt ltnewepointergt o Mariatypes in directory lmaria ckeritodotxt hometuckertodotxt Mm mime UBA Seeing Links I Changes to a le alfect every link atlas l cat file Mm mime UBA Removing a Link tanmu 1 a s 71 me le 111e 0 Compare status information mu 3 up m1 limes date path 0 Look at inode number saitxonmmlml 1 71 me a me 11 me c 3534 me 1534 me 11 t11e c drmrmrx 2 inset 61 17m 1 1151 dnl samomm 1 main dnl no samomm n 5 71o on ex usexs an rm 1 1151 dnl This is because subdirectories eg directories inside dir have a link back to their parent Man Home m Linking Dilectories o Removing or deleting a link does not necessarily remove the file why 0 Only when the file and every link is gone will the file be removed Man Home m Symbolic Links 0 Should it be permitted 0 Problem Cycles in afile system degrades performance 7 Avoid traversing portion of le system multiple times gtgt Daermine deletion reference count m be nonzero even if there is no possible wayto refer nd to le or directory Selfreferencing o How do we guarantee no cycles gtgt Allow only links to le not subdirectories gtgt Garbage collection mark everything that can be accessed via root directorythen delete everything else gtgt Every time a newlink is added use a cycle detection algorithm to determine whether it is OK Mm mime UBA o The links described so far are hard links A hard link is a pointer to a le which must be on the same le system 0 A symbolic link is an indirect pointer to a file Stores the pathname of the file that it points to Symbolic links can link across le systems 0 Symbolic links are listed differently n e an lunixdSdix end an lun1xdsoh 1 9111 staff 3 1 11px 2151 IhmneingridunixdSdix egt an dxmrnrx 3 9111 staff 1n2 1 11px 2139 111 saffxoningxid62 1 saffxoningxid62 ls Mm mime UBA CSCI 4730 Operating Systems File System 1 7B 5 Maria Hybinette UGA Motivation V0 is Important 0 Applications have two essential components Processing InputOutput HO 0 HO performance predicts application performance Maria Hybinet e UGA Maria Hybinet e UGA Chapter 1011 File System o What are files What is file metadata o How are directories organized o What operations can be performed on files 0 How are directories organized o What is the difference between hard amp soft ans o How are files protected Maria Hybinet e UGA lO performance predicts application performance o Amdahl s Law If continually improve only part of application eg processing then achieve diminishing returns in speedup Example infinite speedup and affect only 15 of the overall task roughly 1l1015 118 times faster is max 0 f portion of application that is improved eg processing 0 Speedupf speedup of portion of application speedupApplication fspeedupf Examples Amdahrstaw f 15 speedupf 2 speedupapp 108 f 13 speedupf 2 speedupapp 120 f 12 speedupf 2 speedupapp 133 Speedup Example When only 10 of the application is sequential the maximum speedup using infinite number of processors is 10 Maria Hybinet e UGA Role of OS for V0 0 Standard library Provide abstractions consistent interface Simplify access to hardware devices 0 Resource coordination Provide protection across usersprocesses Provide fair and efficient performance Requires understanding of underlying device characteristics 0 User processes do not have direct access to devices Could crash entire system Could readwrite data without appropriate permissions Could hog device unfairly 0 OS exports higherlevel functions File system Provides file and directory abstractions File system operations mkdir create read write Maria Hybinet e UGA Abstraction File 0 User view Named collection of bytes defined by user Untyped or typed Examples text source object executables applicationspeci c Permanently and conveniently available 0 Operating system view Map bytes as collection of blocks on physical non volatile storage device Magnetic disks tapes NVRAM batterybacked RAM Persistent across reboots and power failure Maria Hybinel e UGA Abstraction Directories 0 Organization technique Map file name to blocks of file data on disk Actually indirectly map le name to le metadata which enables one to nd data on disk 0 Simplest approach Singlelevel directory Each le has unique name Special part of disk holds directory listing Contains ltfile name metadata indexgt pairs How should this data structure be organized o Twolevel directory Directory for each user Specify le with user name and le name Disadvantage Each user cannot organize les Maria Hybinel e UGA Directory Implementation 0 Directory system function Maps ASCII names onto what is needed to locate the data 0 Where do we store the files attributes A simple directory xed sized entries attributes stored with the entry games attributes mail attributes news attributes work attributes Directory in each entryjust refers to an inode UNIX implementation attributes attributes attributes Files Attributes MetaData System information associated With each file Name only information kept in humanreadable form Type needed for systems that support different types Location pointer to le location on devicedisk Size current le size Protection bits controls who can do reading writing executing Time date and user identi cation data for protection security and usage monitoring 0 Special le Directory Symbolic link Metadata is stored on disk Conceptually metadata can be stored as a array on disk eg directory atlaszmariaz143 ls lig ch11ppt 231343 rwrr 1 profs 815616 Nov 4 2002 ch11ppt Maria Hybinel e UGA Directories TreeStructured 0 Directory listing contains ltname indexgt but name can be directory Directory is stored and treated like a le Special bit set in metadata for directories User programs can read directories Only system programs can write directories Specify full pathname by separating directories and les with special characters eg or I 0 Special directories Root Fixed index for metadata eg 2 This directory Parent directory 0 Example mkdir abc Read metadata 2 by default 2 is root in linux look for a find lt a 5gt Read 5 look for b find lt b 9gt Read 9 verify no c exists allocate c and add c to directory Maria Hybinel e UGA Directory Structure o A directory file is a sequence of lines each line holds an inode number indexnode and a file name 895690 quot 288767 quot 287243 mariahtm1quot 287259 gunnartxtquot o The data is stored as binary so we cannot simply cat to view it but some UNIXs allow an octal dump other formats also available atlaszmariaz187 od c 0000000 0 r 252 312 0 f 0 001 0 0 0 0 004 g 377 0000020 0 f 0 002 0 0 0 004 b 013 0 024 0 n 0000040 m a r i a h t m 1 0 0 0 004 b 033 0000060 0 024 0 n g u n n a r t x t 0 0 Maria Hybinel e UGA File System Expanded direl tnry data data dirertnry data data data max 39 a hunl Minimum m Why Links 0 A link is a pointer to a le 0 Useful for sharing les gtgt A le can he shared by giving each person their own link pointer to it n ltexistingsfilegt ltnew7pointergt o Mariatypes in directory Imaria keritodo txt mometuckertodo txt Mam aims m Seeing Links 9 ma 1971 52 I a up ham um dale panama 0 Look ati samamananns s 1 ma ma mg 1514 h a 1514 h 11 am my o Directories may appearto have more links saffxonmmlml 15 dd dn node number drmrmrx 2 mm usexs an inn 1 1151 dnl saffxnnlilallal 1 mkdn linthello samummiaunn 15 dd an rmrx usexs an inn 1 1151 dnl This is because subdirectories eg directories inside dirhave a link back to their parent Minimum m AcyclicGraph Directories 0 More general than tree structure gtgt Add connections across the tree no cycles gtgt Create links from one le or directory to another 0 Hard link In a bquot aquot must exist already gt ea Can use name a or h to get In same le data gtgt lnplementation Multiple directory entries point to same metadata link mariahtm1quot tuckerhtm1quot 1 Minimum m Creating Links I Changes to a le affect every link atlas cat fileia This is file A atlas lh fileia fueib atlas cat fileib i file A atlas echo appending this to b gtgt fileib atlas cat fileib This is file A appending this to b Mam aims m Removing a Link 0 Removing or deleting a link does not necessarily remove the file why 0 Only when the file and every link is gone will the file be removed Minimum m CSCI 4730 Operating Systems Structures amp System Design wrunan um Review I When does operating system get to run startup system calls inten39upts39 traps in HMan ma Questions I What services does an operating system provide to users processes and other systems I What are details of the communication mechanism to the operating system I Howis an operating system structured and what are the principles of operating systems design rm Wuhan qu Review last time Key Questions in System Design An operating system is a complex collection of software too singie entity I What does the OS look like to the user I What are the major operating system components I What services does an operating system provide quotW Mmry Mznlgemen Chapter 2 Outline I Operating System Services I User Operating System Interface I System Calls I Types of System Calls I System Programs I Operating System Design and Implementation I Operating System Structure I Wrtual Machines I Operating System Generation I System Boot in HMan ma Operating System Services Provide functions that are helplul to the user 0 Provide a user interface to the system command line batch graphical gtgt oading mnning and terrmnate 0 Provide safe mechanisms to perform IIO operations le or an no device 0 Filesystem manipulation operations read write searching creating permission ownership 0 Facilitate communication between processes shared memory between processes ormessage passing 0 Error detection and handling gt7 CPU and memory errors eg memory or powerrailures Io devices user programs mama qu Operating System Services User Operating System Interfaces Provrde functions that are helpful to ensure efficient execution Resuurce allocation First two are 39tradIIional approaches how users interface with the OS oca ing resources to multiple users orjobs 7 CPU cycles main memory le storage 0 Command line Interface Via a command Interpreter 0 Accounting 0 Graphical user interface GUI record usage of resources for account billing 0 Protection and Security speeCh track and is controlled Security of the system from outsiders requires user authentication extends to defending external IIO devices from invalid access attenpt n 39 link 39 Nara leneme oca Nara leneme oca Command Line Interpreters CLI Graphical User Interfaces GUI o Fetches a command from user and executes it gtgt builtin conmands or names of other p ams s Ira named command adding newreatures doesn t require user39fr39endly de5kt p memphor 39merface interpreter modi cation Usually mouse keyboard and monitor 0 rmcunnndlindsSenncmnslusrhinrm a system program In umx a system programs Ike mostUle commands Icons represent les programs actmns etc 0 Advantages command interpreter is smallerand can easin extend as Innctiomlity oyadding system programs Disadvamaqes sloner than direct necutinn most landle parameters also inconsistencies oetneen commands 0 Where are interpreters implemented 5 in the interface Various caus rmation options mouse buttons over bject e various actions provide info execute function open directory known as afolder Invented at Xerox PARC 1973 and propelled by In Kernel Apple s Macintosh Not in Kernel s a special program that is initiated upon login s UNIX Windows XP 0 Multiple command interpreters to choose between eg UNIX s shells oars Murine oca oars Murine oca CLIs and GUIs System Calls Process Operating System Interface 0 Many systems now Include both CLI and GUI System calls provide th me Interfaces progra Microsoft Windows GUI yvith GLI command shell Typically wn en in a highlevel language c or OH gt Apple Mac 05 X as Aqua GUI Interface Wlth UNIX Some low level tasks eg accessing certain hardware kernel underneath and shells avallable rmy require assemblylanguage instmctions Solaris is CLI with optional GUI interfaces Java 0 Mostly accessed by programs via a highlevel D s KDE Application Program Interface API rather than direct ace between a running 5 stern gtgt Three most conInon APIS are Win32 API for Windows POSIX API for POSlXbased systems including virtually all versions of UNIX Linux and Mac OS X and Java API or the Java virtual machine JVM Why use APIs rather than system calls W Home osa W mm W systemscall names user trlrougnourtnls text and slldes are genen 12 Why use APIs rather than system calls System Call Sequence o Portability An application programmer designing a program using an API can expect her program to compile and run on any system with the same API 0 Easier to work with System calls can often be more detailed and difficult to work with Mara Hybinette UGA Example of Standard API 0 Example copy the contents of one file to another file calls a number of system calls source file I l destination file Example System Call Sequence Acquire input file name Write prompt to screen Accept input Acquire output file name Write prompt to screen Accept input Open the input file if file doesn39t exist abort Create output file if file exists abort Loo Read from input file Write to output file Until read tails Close output file Write completion message to screen Terminate normally Mara Hybinette UGA System Call Implementation 0 Consider the ReadFile function in the o Win32 API a function for reading from a file return value l BOOL ReadFile c HANDLE file LPVOID buffer DWORD bytes To Read parameters LPDWORD bytes Read LPOVERLAPPED ovl function name O A description of the parameters passed to ReadFile gtgt HANDLE file the file to be read gtgt LPVOID buffer a buffer where the data will be read into and written from gtgt DWORD bytesToRead the number of bytes to be read into the buffer gtgt LPDWORD bytesRead the number of bytes read during the last read gtgt LPOVERLAPPED ovl indicates if overlapped IIO is being used Mara Hybinette UGA API System Call OS Relationship 0 Typically a number associated with each system call Systemcall interface maintains a table indexed according to these numbers 0 The system call interface invokes intended system call in OS kernel and returns status of the system call and any return values 0 The caller need know nothing about how the system call is implemented Just needs to obey API and understand what OS will do as a result call Most details of OS interface hidden from programmer by API Managed by runtime support library set of functions built into libraries included with compiler Mara Hybinette UGA Standard C Library Example open open A user mode I system call interface kernel I mode Implementation of open system call retu rn Mara Hybinette UGA o C program invoking printf library call which calls write system call include ltstdiohgt int main printf quotGreetingsquot return 0 user mode standard C library kernel mode Qrite gt write system call Mara Hybinette UGA System Call Parameter Passing System calls may need parameters to pass information type of information vary according to OS and call 0 Three general methods used to pass parameters to the OS Registers Pass the parameters in registers simplest In some cases may be more parameters than registers Block Parameters stored in a block or table in memory and address of block passed as a parameter in a register Linux and Solaris Stack Parameters stored or pushed onto the stack by the program and popped off the stack by the operating system 0 Block and stack methods do not limit the number or length of parameters being passed Mar a Hybinette UGA Steps in Making a System Call Addre 0 Consider the UNIX read system call OxFFFFFFFF read library call makes the actual User Space call gtgt count readr fd buffermbytes reads nbytes of data froma le P 6 am given a file descriptor fd into a buffer 0 11 steps 6 gtgt 1 3 push parameters onto stack gtgt 4 call library routine gtgt 5 code for read placed in register 6 trap to OS Increment stack pointer Call read um Push fd W s luau w N Push 5 buffer Push nbytes 9 gtgt 7 8 OS saves state calls the Kernel Space appropriate handler 75 232 gtgt 9 10 return control back to user Program 0x0 gtgt 11 pop parameters off stack 21 Mar a Hybinette UGA Process Control MSDOS MSDOS is a singletasking 08 single user single process 0 Command interpreter is invoked when the computer is started 0 To run a program that quot1er program is loaded into 39 memory overwriting some of E the command inter reter m U t p t o pon program ermlna Ion Kemel Km control is returned to the At Startup Running a Program command Interpreter which reloads its overwritten parts can get some of bene ts of multiprogramming via quotterminate amp stay resident system call forces reserves space so that process code remains in memory 23 Mar 3 Hybinette UGA Parameter Passing Via Table X register X parameters for call load address X from table X SyStem system call 13 gt call 13 7 use parameters Code for user program operating system 20 Mar a Hybinette UGA Types of System Calls 0 Process control gtgt fork execv waitpid exit abort 0 File management gtgt open close read write 0 Device management gtgt request device read write 0 Information maintenance get time get date get process attributes 0 Communications message passing send and receive messages createdelete communication connections Shared memory map memory segments 22 Mar a Hybinette UGA Process Control UNIX UNIX is a multitasking 08 multiple users multiple processes 0 Each user runs their own shell command interpreter eg sh csh bash To start a process the shell executes a fork system call the selected program is loaded into memory via an exec system call and the new process executes depending on the command the shell may wait for the process to finish or else continue as the process runs in the quotbackgroundquot when a process is done it executes an exit system call to terminate returning a status code that can be accessed by the shell Recall most UNIX commands are implemented by system programs Running Multiple 24 Mar a Hybinette UGA Debug Facilities Solaris 10 dtrace System Programs alld psrsp xclock XEventsQusued 0 System programs provide a convenient environment for dtrace script alld matched 52377 probes CPU FUNCTION program development and execution Some of them are 0 gt XEVentSQueued U simply user interfaces to system calls others are 0 gt XEventsQueued U 0 gt K11Tmnseytesseadab1e U conSIderably more complex The can be lelded into 0 lt XllTransBytesReadable U O gt XllTr ansSocketBytesReadable U File manlpulatlon O lt X11Tr ansSocketBytesr eadable U Text editors search commands O gt ioctl U g gt 10C K Status information gt getf K O gt setactivefd K Date time I O lt K I I I I CG 1 e asse ex E J 0139 o lt getf K File modification 0 gt getudatamodel K o lt getudatamodel K Programming language support operaingsysem 5 gt releasef K Program loading and execution O gt Cl A fd CompuerHardware o lt cliii iiiiigd E CompIersa debuggers 9 quotgt CV bmadcast K Communications u lt cvbroadcast K g to easef i Application programs 393 byggiiogueued g 0 Most users view of the operation system is defined by 0 lt KKK lentseueuee U 25 system programs not the actual system calls 26 Mar a Hybinette UGA Mar a Hybinette UGA Operatlng System D3513quot and Operatlng System Des1gn and Implementation Implementatlon Cont 0 Design and implementation of OS is not solvable Important principle to separate but some approaches have proven successful Policy What will be done Mechanism How to do it The separation of policy from mechanism is a very important principle it allows maximum flexibility if policy decisions are to be changed later 0 Internal structure of different Operating Systems can vary widely 0 Start by defining goals and specifications Affected by choice of hardware type of system User goals operating system should be convenient to use easy to learn reliable safe and fast 0 Example Timer construct to prowde CPU System goals operating system should be easy to protection in UNIX design implement and maintain as well as flexible Mechanism is to use a timer to provide protection reliable errorfree and effluent Policy How long the period to check is the policy 27 28 Mar a Hybinette UGA Mar a Hybinette UGA Simple Structure MSDOS Layered Structure Early UNIX G M l UNIX limited by hardware functionality the original UNIX 08 had a 39n39mlzespace 39 application program quot limited structuring consisting of two separable layers written to prowde the residentsystem program quot least amount of space 0 The kernel he Consists of everything Slmple layered StrUCture below the SYStem39Caquot pslystemclibretirieps t NOt into mOdUIGS interface and above the systemcallinterfaceto the kernel carefuuy ROM BIOS deVice drivers physlcal hardYVa re E signals terminal file system CPU scheduling Interfaces and levels of gtgt va39des the System Wiser Dagmar functionality are not wequot 2 terminal drivers disk and tape drivers virtual memory separated 0 Current hardware ope ragingsys tem kernel interface to the hardware functions a large number terminal controllers device controllers memory controllers lelvel IlaUglne atpcess 0 NO dual mode and no of functions for one level terminals disks and tapes physical memory 0 0W 9V9 r0quot 39quot95 hardware protection 29 Mar a Hybinette UGA Monolithic Kernels o Earliest and most common OS architecture UNIX MSDOS 0 Every component of the OS is contained in the Kernel 0 Examples 08360 VMS and Linux Memory Ap Keaton A plication Ap lication Protection 113352 Monolithic ardware Mara Hybinette UGA Layered Approach igm o DIVIdes the OS Into a number of layers levels i I I each built on top of lower layers bottom layer 0 is the hardware highest the UI 0 With modularity I application I I application I I m layers are selected such that each uses p i k quot1 functions operations and services of I System services I me only lowerlevel layers I le system I I IO management I I memory management I I process scheduling I i I hardware I Mara Hybinette UGA Layered Approach 0 Problem Efficiency IIO layer memory layer scheduler layer hardware I application I I application I IIO operations triggers may call three I I user V V lay e rs 39 I system services I kernel Each layer passes parameters modifies 39 data etc I le system I Lots of layers adds overhead I 10 layer I I memory layer I I process scheduling I l I hardware I 35 Mara Hybinette UGA Monolithic Kernels 0 Advantages highly efficient because of direct communication between components Susceptible to malicious code all code execute with unrestricted access to the system c Disadvantages Difficult to isolate source of bugs and other errors Hard to modify and maintain Kernel gets bigger as the OS develops Memory Appli cat on A Heation AP licntion Protection 1 rapucs subSyStem Monolithic m Hardware Mara Hybinette UGA 0 Approach Higher level layers access services of lower level functions Example Device driver for backing store disk space used by virtual memory must be lower I application I I application I than memory managers because memory I I user management uses the ability of the device l l driver I system services I kernel 0 Problem Which level should be lower a I les39mm I device driver for backing store of scheduler Example I memory management I Backing store need the scheduler because the I backing store I driver may need to wait for IIO and the CPU can be rescheduled at that time I process scheduling I CPU scheduler need to use backing store I because it may need to keep more space in 39 memory than is physically available I hardware I 34 Mara Hybinette UGA 0 Examples THE Windows XP and LINUX have some level of layering 0 Advantages Modular Reuse o Disadvantages Hard to define layers Example CPU scheduler is lower than virtual I a nation I I a cation I memory driver driver may need to wait for IIO pp pp yet the scheduler may have more info than can I I user fit in memory quot quot 1 1 I system services I eme EffICIency slower each layer adds overheads I I le system I l I memory and IO devices I l I process scheduling I l v I hardware I Mara Hybinette UGA Layered OS s Trend 0 Trend is towards fewer layers ie OSI2 A application programming interface sle sym e 37 Mara Hybinette UGA M1crokernel System Structure 0 Advantages Easier to extend a microkernel S t U add functionality does not y mses pfegesses need to modify kernel thread m C gt Easier to port the operating system to new architectures us network CPU Q More reliable less code is er support SChedu39mg 0 running in kernel mode md O I I o Less pomts of failures 6 m 0 More secure micr o Disadvantages I o Slow Performance overhead of aquot 3quotquot user space to kernel space communication communication lowlevel VM control protection processor Examples Mach MacOS X Windows NT 39 Mara Hybinette UGA Modules 0 Most modern operating systems implement kernel modules dynamically loadable modules Uses objectoriented approach Each core component is separate Each talks to the others over known interfaces Each is loadable as needed within the kernel 0 Overall similar to layers but with more flexible module can call any other module 41 Mara Hybinette UGA Microkernel System Structure 0 Approach Separate kernel programs into system and user level programs or libraries Moves as much from the kernel into user space Minimal kernel only essential components Kernel process memory and communication management main function of kernel Communication takes place between user modules using message passing Mara Hybinette UGA System r o ses thread file C system system us network er support od CPU schedang User pr cesses O O 00 K ker micr nel o communication low level VM protection processor mo kern de el control 38 Microkernel System Structure 0 Windows NT first version that used pure layered microkernel approach and moved code into higher layers but later moved them back to kernel space for performance reasons System tread system c o ses file system us network er support od CPU schedang User processes 00 ker I micr nel 0 communication low level VM protection processor mo kern de el control Examples Mach MacOS X Windows NT Mara Hybinette UGA Solar1s Modular Approach schedu ng device and Classes bus drivers core Solaris miscellaneous kernel lOadable modules System calls STREAMS executable modules formats 42 Mara Hybinette UGA Mac OS X Structure Virtual Machines 0 Hybrid structure using a layered structure 0 Kernel environment at one level Mara Hybinette UGA Mach micro kernel provides memory management support for RPC amp IPC message passing thread scheduling BSD provides BSD command line interface support for networking and file system Posix APl s pthreads lO Kit Dynamically loadedable modules extensions o A virtual machine takes the kernel environment application environments and common services layered approach to its logical conclusion It treats hardware and the processes processes A l V V processes operating system kernel as BSD Mach though they were all hardware kernel kernel kernel 0 A virtual machine provides an kernel VM1 VM2 m virtualmachine Interface Identical to the hardware hardware Virtual Machines Cont underlying bare hardware 0 The operating system creates the illusion of multiple processes each executing on its own processor with its own virtual o The resources of the physical computer are shared to create the virtual machines CPU scheduling can create the appearance that users have their own processor Mara Hybinette UGA Spooling and a file system can provide virtual card readers and virtual line printers A normal user timesharing terminal serves as the virtual machine operator s console Limitation disk drives gt minidisks Virtual Machines Cont memory 43 44 Mara Hybinette UGA O O V1rtual Mach1nes Cont processes processes processes processes r v L L praggfrggmg kernel kernel kernel kzel VM1 VM2 VMB virtualmachine implementation hardware hardware a b a Nonvirtual machine b virtual machine 45 46 Mara Hybinette UGA Virtual Machines o The virtualmachine concept provides complete protection of system resources since each virtual machine is isolated from all other virtual machines This isolation however permits no direct sharing of resources 0 A virtualmachine system is a perfect vehicle for operating systems research and development System development is done on the virtual machine instead of on a physical machine and so does not disrupt normal system operation 0 The virtual machine concept is difficult to implement due to the effort required to provide an exact duplicate to the underlying machine Mara Hybinette UGA 0 Advantages The virtualmachine concept provides complete protection of system resources since each virtual machine is isolated from all other virtual machines This isolation however permits no direct sharing of resources A virtualmachine system is a perfect vehicle for operating systems research and development System development is done on the virtual machine instead of on a physical machine and so does not disrupt normal system operation 0 Disadvantages The virtual machine concept is difficult to implement due to the effort required to provide an exact duplicate to the underlying machine 47 48 Mara Hybinette UGA CSCI 4730 Operating Systems Operating Systems Overview i735 Mane Hybmelle UGA Questions 0 What are the major operating system components 0 What are basic computer system organizations 0 How do you communicate with the operating systems 0 What services does an operating system provide Mane Hybmei a USA Computer System Layers Computer system can be divided roughly in four components 0 Hardware 0 Operating system 0 Application programs 0 Users H ardware Operating System Mane Hybmel 2 USA Outline 0 What is an Operating Systems 0 Computer System Layers 0 Computer System Component Architecture Mane Hybmei a USA What is an Operating System 0 A program that acts as an intermediary between a user of a computer and the computer hardware Execute user programs and make solving user problems easier 0 Operating system goals Make the computer system convenient to use Use the computer hardware in an efficient manner Combination of the above Mane Hybmei a USA Computer System Layers 0 Hardware provides basic computer resources CPU Memory O Devices H ardware Operating System Mane Hybmel 2 USA Mm Whine Computer System Layers I Hardware I Operating system Controis and coordinates use or hardware among ppircatrons and various e usa Computer System Layers I Hardware I Operating s ystem I Application programs I Users Man warm u gt Peopie machines other computers BA What Do Operating Systems Do I 05 is a resource allocator Manages all resources Mm mama usa Decides between con icting requests for efficient and fair resource use I 05 is a control program Controls execution of programs to prevent errors and improper use of the computer Computer System Layers I Hardware I Operating system I Application pr a s gt define the Ways in which the to soive the computing prooiems or the users ompriersweo browsers database systems videu Mm mama usa Computer System Layers Computer system can be divided roughly in four components I Hardware I Operating system I Application programs I Users Man warm usa What Makes up the Operating System 0 No universally accepted definition 0 Everything a vendorships when you ordera operating system is good approximation wildly 0 Operating System is the Kemel n ut varies the one program running at all times on the computer everything else is either a system program ships with the operating system or an ram 7 application prog Mm mama usa Compuler Starlup A mamp Dmgnm n t Dmgnm s lumen t pom MD at mum Storedtrmrmwarem w mmqu Stored on am we mmhabuard parmboar l Izes u quotum 11 Luna manna Sylun lam Ind m momquot a Inn a c Irvn outrun sylun nr a 05 Booting om hard disk Wk Mdmdadm y mm m a m w mm 1mm in Partition Layout Hammock comm mam Svecmcpmyzmtmt t5 weazmmmum tum umx 215mmquot 1th Suvamock me syiemtyv mm mam agemamuwungsx k ruvvb 5 EL mnmemmber un quhmmm mm m t ntnatcmmmIm CMOSBIOS Con guration Uti ity W t 4 Entire Disk amp Booting Computer Mlu Bum newn war m 7 pm 5m to mt mmpma ganer and mdmg addrasm 939V Da mun A Dmgnmmg the 9121 am Innn outrun sylun nr mos m rum H van m Ind unsettle the Man he mum a tmva mon mm mthe Danton tame rsadsm my mocklthehom mam mum A Computer System Organization one or um cm 5 dance onllnllels Ennnaj Ihmluh cnmmn bus Dmvtdtng Iccssln 5mm quotawry Cnmunuvl mean an quotmy WEIes nn McPus Ind dances compamlq Computer System Operations Marta Hybmet 2 USA CPU the processor that perform the actual computation IIO controllers gtgt take commands in registers generate flags and interrupts gtgt each device controller is in charge of a particular device type has a local buffer for 0 CPU moves data fromto main memory tolfrom local buffers IIO is from the device to local buffer of controller Device controller informs CPU that it has finished its operation by causing an interrupt Common Functions of Interrupts Interrupts Marta Hybmei 2 USA When the CPU is interrupted it stops what it is doing and transfer execution to a fixed location in memory gtgt This location an index to a service routine to handle the interrupt Interrupt transfers control to the interrupt service routine generally through the interrupt vector which contains the addresses of all the service routines Interrupt architecture must save the address of the interrupted instruction Incoming interrupts are disabled while another interrupt is being processed to prevent a lost interrupt Interrupt Timeline 0 Occurrence of an event is signaled by interrupts either by software or hardware 0 A trap is a softwaregenerated interrupt caused either by an error or a user request 0 Modern operating systems are interrupt Marta Hybmet 2 USA driven Interrupt Handling Marta Hybmei 2 USA CPU user process executing LI U IO interrupt processing idle transferring IlO transfer IO transfer request done request done O Jevice o The operating system preserves the state of the CPU by storing registers and the program counter o Determines which type of interrupt has occurred polling vectored interrupt system 0 Separate segments of code determine what Marta Hybmei 2 USA action should be taken for each type of interrupt IO Structure o Synchronous IIO After IIO starts control returns to user program only upon IIO completion gtgt Wait instruction idles the CPU until the next interrupt gtgt Wait loop contention for memory access gtgt At most one No request is outstanding at a time no simultaneous Il0 processing 0 Asynchronous IIO After IIO starts control returns to user Marta Hybmei 2 USA program without waiting for IIO completion gtgt System call request to the operating system to allow user to wait for Ho completion gtgt Devicestatus table contains entry for each Il0 device indicating its type address and state gtgt Operating system indexes into No device table to determine device status and to modify table entry to include interrupt 24 Two IO Methods DeviceStatus Table Synchronous Asynchronous mom We elce mel dam Silver lmzrlupl handler lme39ruvl haan o r to mm to 23 Direct Memory Access Structure Storage Structure 3 Used for highspeed quot0 devices able to 0 Main memory only large storage mediathat the CPU transmi lnfornution at close to memory Wquot quot955 quot9 s a 0 Secondary storage extension ormain memory that D m H t f M k M t provides large nonvolatile storagecapacity 39 9quot m 939 WIS 9395 S 3 a 0 Magnetic disks rigid metal orglass platters covered from buffer storage directly to nuln memory Wm magnetic recording quotm W39th CPU quot797 me Disksurrac logically divided into tmclswhich are I Only one interrupt is generated per block 5quot quot quot9quot t The disk controllerdeter ines the logical interaction quotthequot quot393 quot the quot 39merrupt 9 quot byte39 between the device and the computer o r to 27 mom to 28 Storage Hierarchy Caching Storage syshems 0 Use of highspeed memory to hold recentlyaccessed organized in hierarchy data grew 0 Performe at many levels in a computer Gn hardware cm operating system software o lnronnation in use copied from slowerto raster storage volatility I empmmv 95quotquotquot9quot quotV39quot9 39 o Faster storage cache checked rst to determine if information into raster infoma oquot is mere 23 d s inlormation sed directly lrorn the cache llastl 39V o llnot data copiedto cache and used there secondary u we 0 Cache smaller than storage being cached v Cache management important design problem Cache size and replacement policy 9 3n Performance ofVarious Levels of Storage Maniprogramming Mumprogrammlog needed or emcleney o 5 le user cannol keen CPU and V0 uevices husy an all limes o Mu n oorammino nrgznizvsjnhs lcoue anu ualalso CPU always has onelo exec o A sulsel ollolaljohs in syslem is kenl In memory 0 0nejoh selecleu and run viajoh scheuulino has In miillorlo lor llllhe examplel os swilches In anolher joh n enovv lavoul Hardware Protection 0 DualMode Operation 0 lie Protection 0 Memory Protection 0 CPU Protection on Timesharng n mummy new exam use heme woe on n orll emvroeo try lurde e eweesaonllvloalslneolsn Mal sveem is running user mdeurkan co e sa me war as Drlvltegedi in lernel n N gration ofInteger A from Disk lo Register ullilaskino environmenls mu lhe carel lln ice mnsl recenl value no mailer where u IS sloreu In lhesloraoe hierarchy when Ltan o Mullinrocessor environmenl must provide cache coherency in harumresuch lhal all CPle have lhe mnsl re nlvalue39 heir cache 0 D39slrihuleu environmenl silualion even more cnmplex v semi comes MI allum un exls1 v vnoos oluuons covenel n ellelem Timesharing Multitasking rah caeswrenesoar in m ufrewem v Mana9 aannleaellvrneacmov meoawme weal interacth ammo n nselimeshoulu helt secon 1 u as an leasl one program execuuno In emory bprncvss o llseveraljohs ready In run an lhe same lime a CPU scheuulino 0 ll processes dnn39l l in memorysmnnino moves lhem in a nu nulln run 0 Vinual memory zllnm execulion ol processes nnl comnlelely in memory DualMode Operation uzlrmnde oneralion zllnm 05 In nrolecl ilsell anu olher syslem cnmpnnems mom mooeono lanamonuor e a onions designam unty Emulate ode W em mH changes modem lernelnelornnon mH resaslt to user Transition from User to Kernel Mode 0 nmeto prevent in nite loop lprooess noonno resouroes unter acre generatean lmerruvi smedullng Dmcessto regain controi urtermlnate programthat acemsaiimtedtlme e W meteor H ttiKM lllwii W W Memory Protection o Must provide memory protection memory two registers that range oilegal lell rad ottne rm ser 7 contans the size ne 0 Memory outsidetne de ned range is protected An Operating System s Core Tasks o Process Management o Memory Management o File Management o IID System Management o Protection Sstem 0 Protection o All IID instruction are privileged instructions hat a user 4 program could never gain control ortne computer in kernel mode ie a user program that a part orit quotquot execution store a new address intne interrupt vector tacal quotonto made so we no system cailw vemml to some as ke CPU Protection o Timer interrupt computer after peci ied period to ensure operating system maintain control Timer 395 decremenled every clack lick wnen er reaches the valuen an interrupt nccuis o Timer commonly used to implement time sharing 0 Time also used to compme the current time 0 Loadtimer is a privileged instructio Process Management o A process is a program in execution tan active entity ie a running program asc unll mwnrk on a mmputer s Exanples corrptlaoon process wnm prooesstno process A process needs cetan resources u memenarymteavoeaucsta emanate ltstask many processes at once teg using at o Atime sharing system tsucn as ulllxl run several processes by multiplexing hetweentnem Process Management Activities Memory Management The operating system is responsible for the following I Programs become processes when they are activities in connection with process management load quot3930 ed i memory and start executing gt All data in memory before and after processing creating and deleting both user and System x All instructions in memory in order to exe e procesSes I Memory nunagement daermines vvhati 39 memory when suseevdmg and refume processes r Optimizing CPU utilization and computer 0 ProVIdlng mechanisms for process synchronization response to users 0 Providing mechanisms for process communication 39 memory nagemem ac Vi es r Keeping track ofwhich parts of memory are 0 ProVIdlng mechanisms for deadlock handling c r emly being used and bywhom gtl Deciding which processes or parts thereof and data to move into and out of memory gtl Allocating and deallocating memory space as needed Mamamt UBA Mm Mme UBA File Management MassStorage Management 0 05 provides uniform logical view of information storage 0 Main memory is volatile and limited in size Use disks to store overflow and data that needs to be 39 persistent 5 Wm meg to phwca demes o Disks are slowerthan main memo and rocessors Each medium is controlled bydevice ie disk drive tape ry p drive Entire speed of conputer operation hinges on disk sys em and its algorithms 7 Varying properties include access speed capacity datatransfer rate access method sequential or random 0 05 mass storage management actIVItIe o FileSystem ma agement gtgt Freespace nunagement Files usually organized into directories Storage allocation gt 39 Disk scheduling 0 Some storage need not be fa gtgt 05 activ Ies Inc 7 Creating and deleting les and directories 7 Primitives to manipulate les and dirs 7 Mapping files onto secon ry a 7 Backup les onto stable nonvolatile storage media W as m lude Tertiary storage includes optical storage magnetic tape Still nust be ma a Varies between WORM writeonce readnunytimes and RW readwrite Mari thvime unA IO Subsystem Management Protection and Security 0 One purpose of OS is to hide peculiarities of hardware devices from the user u 39 39 processes or users to resources de ned bythe OS I 9 1 quot e 39 39 o IIO subsystem responsible for masks Memory nunagement of no i c ding Huge range including denialofservice worms viruses identity 7 buffering storing datatemporarily while it is being the he WWW transf d u 39 39 39 tn storming e caching storing parts of data in faster storage for Who 0aquot do What performance User identities user IDs security IDs include name and e spooling the overlapping ofoutput of onejob with input of 5 i39a 9d quotquotmberj quot P 5939 hmobs User lDthen associated with all files processes ofthat user to determine access control Gmem dev39ce39dr39ver 39quotmm ce Group identifier group ID allows set ofusers to be defined and Drivers for speci c hardware devices controls managed then also associated with each process file rights Wm M Mm Mme UBA
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'