New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Hertha Tremblay


Hertha Tremblay
GPA 3.59

Michael Dillencourt

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Michael Dillencourt
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 110 page Class Notes was uploaded by Hertha Tremblay on Saturday September 12, 2015. The Class Notes belongs to CompSci 143 at University of California - Irvine taught by Michael Dillencourt in Fall. Since its upload, it has received 73 views. For similar materials see /class/201901/compsci-143-university-of-california-irvine in ComputerScienence at University of California - Irvine.

Similar to CompSci 143 at UCI




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
Part 11 Memory Management Chapter 7 Physical Memory Chapter 8 Virtual Memory Chapter 9 Sharing Data and Code in Main Memory CompSci 143A Spring 2009 7 Physical Memory 71 Preparing a Program for Execution Program Transformations LogicaltoPhysical Address Binding 72 Memory Partitioning Schemes Fixed Partitions Variable Partitions Buddy System 73 Allocation Strategies for Variable Partitions 7 4 Dealing with Insuf cient Memory CompSci 143A Spring 2009 Preparing Program for Execution Program Transformations 7 Translation Compilation 7 Linking 7 Loading innsiuuon Linking Loading hxetuuon um modui mtmoi y Figure 71 Compsci 143A Spring 2009 Address Binding Assign Physical Addresses Relocation Static binding Programming time Compilation time Linking time Loading time Dd namic binding Execution time CompSci 143A Spring 2009 Static Address Binding Static Binding At Programming Compilation Linking andor Loading Time innciion function f f m i r 120 1120 Linker Loader store 20 Wore izn more 11211 hunch branch 11 bianch 1000 Object loud module load module module in secondary in min mommy mcmolj Figure 72 Spring 2009 CompSci 143A Dynamic Address Binding Dynamic Binding At Execution Time 0 mu unclion unciion f f m UZU Execution Lmilcr Iure2l smreiZO mm 120 a gt map branch f bxanch 0 branch 0 Figure 74 CompSci 143A Swing 2009 Address Binding HOW to implement dynamic binding Perform for each address at run time pa addressmapla Simplest form of addressmap Relocation Register pa Ia RR More general form Page Segment Table Chapter 8 CompSci 143A Spring 2009 Memory Partitioning Schemes Fixed Partitions Singleprogram systems 2 partitions OSuser Multiprogrammed partitions of different sizes How to assign processes to partitions cf Fig 75 Separate queue for each partition Some partitions may be unused Single queue More complex but more exible Limitations of xed partitions Program size limited to largest A artition Internal fragmentation unused space within partitions CompSci 143A Spring 2009 Memory Partitioning Schemes Fixed partitions 1 queue per partition vs 1 queue for all partitions Opclaml n g Figure 7 5 CompSci 143A Spring 2009 9 Variable Partitions Memory not partitioned a prion39 Each request is allocated portion of free space Memory Sequence of variablesize blocks 7 Some are occupied some are free holes 7 External fragmentanon occurs memory may be divided into many small pieces Aduacent holes rivht left or both must be coalesced to prevent increasing fragmentation Releasemjy y y y we w Figure 394 b C d CompSci 143A Spn39ng 2009 10 Linked List Implementation 1 Type Size tags at the start of each Block Holes contain links to predecessor hole and to next hole 7 Must be sorted by physical address Checking neighbors of released block b block C below 7 Right neighbor easy Use size of b Left neighbor clever Use sizes to nd rst hole to b s right follow its predecessor link to rst hole on Us left and check if it is adjacent to b Successor pointers Predecessor painter Figure 77a CompSci 143A Spring 2009 Linked List Implementation 2 Better solution Replicate tags at end of blocks need not be sorted Checking neighbors of released block b 7 Right neighbor Use size ofb as before 7 Left neighbor Check its adjacent type size tags Figure 77b Cnmpsn 143A Spnng 2009 12 Bitmap Implementation Memory divided into Xsize blocks States of the blocks represented by a binary string the bitmap State of each block represented by a bit in the bitmap O free 1 allocated Can be implemented as char or int array or in Java as a byte array Operations use bit masks Release amp Boolean bitwise and Allocate Boolean bitwise or 39 Search for free block Find leftmost 0 bit Repeatedly check leftmost bit and shift mask right CompSci 143A Spring 2009 13 Example Assume A 3 KB Free Memory broken into B 2 KB Occupied blocks of s1ze lKB C 5 KB Occupied Use arrays 01 bytes Ior D 1 KB Occupied memory map E 1 AU F Release block D rec B1 B1 amp 391101111139 Allocate rst 2 blocks B0 Bm Ofblock A 00011111 11100000 B0 B0 391100000039 CompSci 143A Spring 2009 14 The Buddy System Compromise between xed and variable partitions Fixed number of possible hole sizes typically 2quot Each hole can be divided equally into 2 buddies Track holes by size on separate lists 1 list for each partition size When n bytes requested nd smallest i so that ngi If hole of this size is available allocate it Otherwise consider a larger hole Recursively split hole into two buddies continue with one and place the other on appropriate free list for its size until smallest adequate hole is created Allocate this hole On release recursively coalesce buddies Buddy searching for coalescing can be inef cient CompSci 143A Spring 2009 15 The Buddy System Sizeszl 2 4 8 16 Figure79 7 7 7 7 a 3 blocks allocated 3 amp 3 mes left ll S s39llllllllvlli 0 b Block of sizel A allocated E WMIW A W A A 0113456759101213145 lll g c Block1213 released W 01 sunllzulus kc CompSci 143A Spring 2009 16 Allocation Strategies With Variable Partitions Problem Given a request for n bytes nd hole 2 n Goals Maximize memory utilization minimize external fragmentation Minimize search time Search Strategies F irst fz39t Always start at same place Simplest Next t Resume search Improves distribution of holes Best t Closest t Avoid breaking up large holes Worst t Largest fit Avoid leaving tiny hole fragments First Fit is generally the best choice CompSci 143A Spring 2009 17 Measures of Memory Utilization HOW many blocks are used how many are holes HOW much memory is wasted Average hole size is not the same as average block size CompSci 143A Spring 2009 18 Used Blocks vs Holes How many blocks are used how many are holes 50 rule Knuth 1968 holes p x fubocks2 p probability of inexact match ie remaining hole In practice p1 because exact matches are highly unlikely so Of the total number of occupied blocks and holes 13 are holes CompSci 143A Spring 2009 19 How much memory is unused wasted Utilization depends on the ratio khoesizebocksize When p1 p is probability of inexact match unusedmemory kk2 Intuition When k gtoo unusedmemory gt1 100 empty When k1 unusedmemory gt13 50 rule When k gt0 unusedmemory gt0 100 full What determines k The block size b relative to total memory size M Determined experimentally Via simulations When bs M10 k022 and unusedmemory01 When bM3 k2 and unusedmemoryz05 Conclusion M must be large relative to b CompSci 143A Spring 2009 20 Dealing With Insuf cient Memory Memory compaction How much and What to move Swapping Temporarily move process to disk Requires dynamic relocation Overlays Allow 1 rourams large than 1 hi sical memory Programs loaded as needed accordinv to calling structure CompSci 143A Spring 2009 21 Dealing with Insuf cient Memory Memory compaction V Figure 710 at m a d Initial Complete Partial lV nimal Movement CompSci 143A Spring 2009 22 Dealing with Insufficient Memory Overlays Allow programs large than physical memory Programs loaded as needed according to calling structure h E n M c k2 D E a CompSci 143A Spring 2009 quotl C b Figure 711 2 Processes and Interactions 21 The Process Notion 22 De ning and Instantiating I I39OCCSSCS Precedence Relations Implicit Process Creation Dynamic Creation With fork And join Explicit Process Declarations 23 Basic Process Interactions Competition The Critical Section Problem Cooperation 24 Semaphores Semaphore Operations and Data Mutual Exclusion ProducerConsumer Situations 25 Event Synchronization CompSci 143A Spring 2009 Processes A process is the activity of executing a program on a CPU Also called a task Conceptually Each process has its own CPU Processes are running concurrently Physical concurrency parallelism This requires multiple CPUs Logical concurrency timeshared CPU Processes cooperate shared memory messages synchronization Processes compete for resources CompSci 143A Spring 2009 Advantages of Process Structure Hardwareindependent solutions Processes cooperate and compete correctly regardless of the number of CPUs Structuring mechanism Tasks are isolated with welloeImeo mterIaces CompSci 143A Spring 2009 De ningInstantiating Processes Need to De ne What each process does Specify precedence relations When processes start executing and stop executing relative to each other Create processes CompSci 143A Spring 2009 Si ecifd inv 1 recedence relations Process ow 39raA hs unrestricted Properly nested expressionsgraphs also known as seriesparallel graphs CompSci 143A Spring 2009 Process ow graphs Directed graphs Edges represent processes Vertices represent initiation termination of processes CompSci 143A Spring 2009 Examples of Precedence Relationships Process Flow Graphs S I l m 1 P2 Pia Ill 1 4 I77 P3 a F a Serial 1 Parallel e Sclicsparallcl d Genexal prcccdcncc Figure 21 CompSci 143A Spiing 2009 Process ow graphs a b c d e f gives rise to I 1 f r a b c d Emmi a um 11W WP Figure 2 2 CompScI 143A Spmg 2009 Unrestricted PrOCess LIOW graphs Any directed acylic graph DAG corresponds to an unrestricted process ow graph and conversely May be too general like unrestricted goto in sequential programming CompSci 143A Spring 2009 Properly nesteu expressions Two primitives which can be nested Serial execution Expressed as Spl p2 Execute pl then p2 then Parallel execution Expressed as Ppl p2 Concurrently execute p1 p2 A graph is properly nested if it corresponds to a properly nested expression CompSci 143A Spring 2009 10 Examples of Precedence Relationships Process Flow Graphs S I l m 1 P2 Pia Ill 1 4 I77 P3 a F a Serial 1 Parallel e Sclicsparallcl d Genexal prcccdcncc Figure 21 CompSci 143A Spiing 2009 11 PI OA er1 nested A rocess ow vraA hs 0 corresponds to the proper ested expression Sp1 P002 8003 Pp4 105 p6 Pp7 138 d is not properly nested i proof text page 44 G I u s quun a CompSci 143A Spring 2009 1 2 Process Creation Implicit process creation cobegln coend forall statement Explicit process creation forkjoin Explicit process declarationsclasses CompSci 143A Spring 2009 13 Implicit Process Creation Processes are created dynamically using language constructs Process is not explicitly declared or initiated cobegincoend statement Data parallelism forall statement CompSci 143A Spring 2009 14 Cobegincoend statement syntax cobegin C1 02 Cn coend meaning All C1 may proceed concurrently When all of the Ci s terminate the statement following the cobegincoend can proceed cobegincoend statements have the same CXA ressive A ower as SP notation Sab E a b sequential execution by default Pab E cobegin a b coend CompSci 143A Spring 2009 15 cobegincoend example Tun 7mm V Lminm KN L Figure 24 cobegin TimeDate Mail ll Edit cobegin Compile Load Execute Edit cobegin Print Web coend oend coend CompScx 143A Spnng 2009 Data parallelism Same code is applied to different data The fora statement syntax forall parameters statements Meaning Parameters specify set of data items Statements are executed for each item concurrently CompSci 143A Spring 2009 17 Example of forall statement Examl le Matrix Multil l forall i1n j1m AiJ39 0 for k1 kltr k Aii AiJ39 BikCkj Each inner product is computed sequentially All inner products are computed in parallel CompSci 143A Spring 2009 18 Explicit Process Creation Using forkjoin Explicit process declarationsClasses CompSci 143A Spring 2009 19 Explicit program creation forkjoin cobegin coend are limited to properly nested graphs 0 f orall is limited to data parallelism f ork join can express arbitrary functional parallelism an39 A recess ow vral h CompSci 143A Spring 2009 20 The fork and join primitives Syntax fork X Meaning create new process that begins executing at label x Syntax join ty Meaning t t 1 if O goto y The operation must be indivisible Why CompSci 143A Spring 2009 21 fork join example Example Graph in Figure 21d 9 t1 2 t2 3 p1 fork L2 fork L5 m fork L7 quit L2 p2 fork L3 fork L4 quit L5 p5 join t1L6 quit L7 p7 join t2L8 quit L4 p4 join t1L6 quit L3 p3 join t2L8 quit L6 p6 join t2L8 quit m L8 p8 quit a CompSci 143A Spring 2009 22 The Unix fork statement procid fork Replieates calling process Parent and Child are identical except for the Vdueofprocid Use procid to diverge parent and Child if procid0dqchildprocessing else dqparentprocessing CompSci 143A Spring 2009 23 Explicit Process Declarations Designate piece of code as a unit of execution FaCilltaLeb prugi39cuu su ucturing Instantiate Statically like cobegin or Dynamically like fork CompSci 143A Spring 2009 24 EXphClt Process Declaratlons process p process p1 declarationsforpl begin end process type p2 declarationsforp2 begln end begin do new p2 end CompSci 143A Spring 2009 25 Thread creation in Java De ne a runnable class Class MyRunnable implements runnable run Instantiate the runnable instantiate and start a thread that runs the runnable Runnable r new MyRunnableO Thread t new Threadr tstart CompSci 143A Spring 2009 26 Process Interactions CompetitionMutual Exclusion Example Two processes both want to access the same resource Cooperation Example Producer Buffer a Consumer CompSci 143A Spring 2009 27 Process Interactions Competition The Critical Section Problem x 0 cobegin p1 x if p2 x x 1 Co39eund After both processes execute we should have x2 CompSci 143A Spring 2009 28 The Critical Section Problem Interleaved execution due to parallel processing or context switching p1 R1 x p2 R2x R1 R1 1 R2R21 xR1 xRZ X has only been incremented once The rst update xR1 is lost CompSci 143A Spring 2009 29 The Critical Section Problem Problem statement cooegm p1 while1 CS1 program1 p2 while1 082 program2 if pn while1 CSn programn coend Guarantee mutual exclusion At any time at most one process should be executing Within its critical section Csi CompSci 143A Spring 2009 30 The Critical Section Problem In addition to mutual exclusion prevent mutual blocking 1 Process outside of its CS must not prevent other processes Irom enter1ng1ts Lb N0 dog in manger 2 Process must not be able to re eatedld reenter its CS and starve other processes Q aimess 3 Processes must not block each other forever n0 deadlock 4 Processes must not repeatedly yield to each other after you after you no livelock CompSci 143A Spring 2009 31 The Critical Section Problem Solving the problem is subtle We will examine a few incorrect solutions before describing a correct one Peterson s algorithm CompSci 143A Spring 2009 32 Algorithm 1 Use a single tu rn variable int turn 1 cobegin p1 while 1 while turn 1 CS1 turn 2 program1 p2 while 1 while turn 2 wait CS2 turn 1 program2 coend Violates blocking requirement 1 dog in manger CompSci 143A Spring 2009 33 Algorithm 2 Use two variables 61 1 when p1 wants to enter its CS C21 when p2 wants to enter its CS int 01 0 02 O cobegin p1 while 1 c1 1 while C2 IW39dLI CS1 01 O program1 02 7 while 01 wait C82 02 0 program2 coend Violates blocking requirement 3 deadlock Processes may wait forever CompSci 143A Spring 2009 34 Algorithm 3 Like 2 but reset intent variables C1 and C2 each time int 01 0 c2 0 cobegm p1 while 1 c139t if c2 c1 0 go back try again else 081 c1 O program1 p2 while 1 c239t if 01 02 0 go back try again else 082 02 0 program2 coend Violates blocking requirements 2 and 4 fairness and livelock CompSci 143A Spring 2009 35 Peterson s algorithm Processes indicate intent to enter CS as in 2 and 3 using 01 and 02 variables After a A rocess indicates its intent to enter it politely tells the other process that it will wait using the wiIIWait variable It then waits until one of the following two conditions is true The other process is not trying to enter or The other process has said that it will wait by changing the value of the wiIIWait variable CompSci 143A Spring 2009 36 Peterson s Algorithm int 01 0 02 0 willWait cobegin p1 while 1 c1 1 willWait 1 while 02 ampamp willWait1 wait CS1 61 O program1 72 while 1 02 1 willWait 2 while 01 ampamp willWait2 wait CSZ 02 O roram2 coend Guarantees mutual exclusion and no blocking CompSci 143A Spring 2009 37 Software solutions to Critical Section problem Drawbacks Dif cult to program and to verify Processes loop while waiting busywait Applicable to only to critical section problem competition for a resource Does not address cooperation among processes Alternative solution special programming constructs semaphores events monitors CompSci 143A Spring 2009 38 Semaphores A semaphore S is a nonnegative integer Operations P and V are de ned on S Semantics PS if sgt0 decrement 5 else wait until sgt0 Vs increment s by l Equivalent Semantics PS While Slt1Wait sS1 Vs ss1 The Operations P and V are atomic indiVisible Operations CompSci 143A Spring 2009 39 Notes on semaphores Invented b7 Di kstra As we will see in Chapter 4 the waiting in the V operation can be implemented by Blocking the process or Busywaiting Etymology P s often written Wait s think Pause P from assaren ass in Dutch or from rola an u u 7 combmlng proberen try and verlagen decrease V s often written Signal s think of the V for Victory 2 nger salute V from vrigeven release or verhogen increase CompSci 143A Spring 2009 40 Mutual Exclusion W Semaphores semaphore mutex 1 cobegin p1 while 1 Pmutex CS1Vmutexprogram1 p2 while 1 PmutexCSZVmutexprogram2 pun while 1 PmutexCSnVmutexprogramn coend CompSci 143A Spring 2009 41 Cooperation Cooperating processes must also synchronize Example P1 waits for a signal from P2 before P1 proceeds Classic generic scenario Producer Buffer a Consumer CompSci 143A Spring 2009 42 Signal Wait With Semaphores semaphore s 0 cobegin p1 Ps wait for signal ll p2 Vs send signal saend CompSci 143A Spring 2009 43 Bounded Buffer Problem semaphore e n f 0 b 1 cobegm Producer while 1 Producenextrecord Pe Pb Addtobuf Vb Vf H Consumer while 1 Pf Pb Takefrombuf Vb Ve Processrecord coend CompSci 143A Spring 2009 44 Events An event designates a change in the system state that is of interest to a process Usually triggers some action Usually considered to take no time Principally generated tnrough Interrupts and traps end of an IO operation expiration of a timer machine error invalid address Also can be used for process interaction Can be synchronous or asynchronous CompSci 143A Spring 2009 45 Synchronous Events Process CXA licitlv waits for occurrence of a speci c event or set of events generated by another process Constructs Ways to de ne events Epost generate an event EWait wait until event is posted Can be irnplernent Wth semaphores Can be memoryless posted event disappears if no process is waiting CompSci 143A Spring 2009 46 Asynchronous Events Must also be de ned posted Process does not explicitly wait Process provides event handlers Handlers are evoked Whenever event is posted CornpSci 143A Spring 2009 47 Event synchronization in UNIX Processes can signal conditions using as nchronous events kipid signal Possible signals SIGHUP SIGILL SIGFPE SIGKILL Process calls sigaction to specify What should happen when a signal arrives It may catch the signal with a speci ed signal lldllLuUf ignore signal Default action process is killed Process can also handle signals synchronously by blocking itself until the next signal arrives pause command CompSci 143A Spring 2009 48 Case study Event s nch cont Windows 2000 WaitForSingleObject or WaitForMultipleObjects Process blocks until object is signaled process all threads complete thread terminates semaphore incremented muteX released event posted timer expires le IO operation terminates queue item placed on queue CompSci 143A Spring 2009 49 4 The OS Kernel 41 Kernel De nitions and Objects 42 Queue Structures 43 Threads 44 Implementing Processes and Threads Process and Thread Descriptors Implementing the Operations 45 Implementing Synchronization and Communication Mechanisms Requesting and Releasing Resources Semaphores and Locks Building Monitor Primitives Clock and Time Management Communications Kernel 46 Interrupt Handling CompSci 143A Spring 2009 Kernel De nitions and Objects Basic set of objects primitives data structures processes Rest of OS is built on top of kernel Kernel de nesprovides mechanisms to implement various policies Process and thread management Interrupt and trap handling Resource management Inputoutput CompSci 143A Spring 2009 Queue Structures OS needs many different queues Singlelevel queues Implemented as array Fixed size Ef cient for simple FIFO operations Implemented as linked list Unbounded size More overhead but more exible operations CompSci 143A Spring 2009 Queues Multilevel queues priority queues Support multiple priority levels Implemented as multiple singlelevel queues Implemented as heaps CompSci 143A Spring 2009 Priority Queues Multiple queues 0mm pointer Figure 43a CompSci 143A Spring 2009 Priority Queues Binary Heap 75 To profcase J n I E II x m l x 4 s s 7 s u a l 15 115 7 sun LSn um 200 iizs 1301 70quot I I T I I 139 I I 139 I I I I I I I I I I I To prac2lt clt Figure 4 30 CompScl 143A Spnng 2009 Processes and threads Process has one or more threads Prams Code All threads in a process share Memory space m1 m2 Other resources Each thread has its own PCTH CPU state registers program counter Stack smckl mo Implemented in user space or Shared data kernel space Threads are efficient but lack protection from each other Figure 44 CompSci 143A Spring 2009 Process status types Running Ready Blocked Running the process is currently running on a processor Ready the process is ready to run waiting for a processor Blocked the process cannot proceed until it is granted a particular resource eg a lock a le a semaphore a message Active Suspended Internal process may suspend other processes to examine or modify their state e g prevent deadlock detect runaway process swap the process out of memory CompSci 143A Spring 2009 Implementing Processes and Threads Process Control Block PM 133 P C B CF USML E39 State Vector Information WSW m chemn Slant Resources w M M mmy necessary to run pI OCCSS p L OWE Hm V tleRemurces 5mm Type Li s BaSIC types39 Runnlng Cmationjme Pam Cm Ready Blocked mm o types Oiherinfon39nation Readyactive Readysuspended Figure 45 Blockedact1ve CompSci 143A Blockedsuspended Spring 2009 Implementing Processes and Threads State Transition Diagram Schedu at V A cuwle Requen a Creme Suspend Release Rclcasc Acmuw Suxpcml Figure 46 CnmpSm 143A spnng 2009 Process Operatlons Create C39reatesO m0 pi pid p GetNewPCB pid GetNewPIDO pgtD pid pgtCPUState 0 pgtMemory m0 pgtPriority pi pgtStatusType readys pgtStatusList RL pgtCreationTreeParent self pgtCreationTreeChild NULL 39insertseIfrgt CreationTreeChild p insertRL p Scheduler Gompsci 143A Spring 2009 11 Process Operations Suspend Suspendpid p GetPCBpid s pgtStatusType if s bockeda s bockeds pgtStatusType blockeds else pgtStatusType readys if s running cpu pgtProcessorD pgtCPUState nterruptcpu Scheduler Gompsm 143A Spring 2009 12 Process Operations Activate Activatepid p GetPCBpid if pgtStatusType readys pgtStatusType readya Scheduler else pgtStatusType blockeda CompSCi 143A Spring 2009 13 Process Operations Destroy Destroypid p GetPCBpid KillTreep Scheduler KillTreep for each q in p gtCreationTreeChild KillTreeq if pgtStatusType runningU cpu p gtProcessorID Interruptcpu Removep gtStatusList p ReleaseallpgtMemory Releaseallp gtOtherResources Closeallp gtOpenFiles DeletePCBp Gompsci 143A Spring 2009 14 Implementing Synchronization and Communication Mechanisms Semaphores locks Generic code to request a monitors messages time resource etc are resources Generic code to request a Rele6136063 r r 39 I esou Ge Deallocateres self RequeStreS if ProcessBockedinrespr if Freeres Allocateres self AllocateUeS Pr ese Unblockpr res Scheduler Blocksef res Scheduler CompSci 14393A Spring 2009 15 Speci c Instantiations of Resource Request Release P and V operations on semaphores Operations embedded in monitor procedures Calls to manage clocks timers delays timeouts Sendreceive operations CompSci l43A Spring 2009 16 Implementing semaphoreslocks Special hardware instruction testandset Implementing binary semaphores Implementing general semaphores With busy waiting Avoiding the busy wait Implementing general semaphores with blocking CompSci 143A Spring 2009 17 TestandSet Instruction Special testandset instruction TSRX Operates on variable X register R Behavior R X X O Always set variable X O Register R indicates Whether variable X changed R1 if X changed 1 gt0 RO if X did not change O gtO TS is indivisible atomic operation CompSci 143A Spring 2009 18 Binary Semaphores Binary semaphore Sb only 0 or 1 Also known as a Spin lock or a spinning lock Spinning Busy Waiting Two atomic operations Pb and Vb Behavior is Pbsb if Sb1 Sb0 else wait until sb becomes 1 Vbsb Sb1 Indivisible implementation of Pb and Vb using T8 instruction Pbsb do TSRsb while lRwait oop Vbsb Sb1 Note Sb is shared but each process has its own R CompSci 143A Spring 2009 19 General Semaphores w busy wait PS nhibitnterrupts Pbmutexs s 31 if s lt O Vbmutexs Enablelnterrupts Pbdelays Vbmutexs Enablelnterrupts VS CompSci l43A nhibitnterrupts Pbmutexs s 31 if 5 lt 0 Vbdelays else Vbmutexs Enablelnterrupts Spring 2009 nhibitinterru pt prevents deadlock due to context switching Two binary semaphores used delays implements the actual wait and may be held for a long time mutexs needed to implement critical section with multiple CPUs only held for a few instructions Note than When V executes the call Pbmutexs the corresponding Vbm utexs may be executed by P 20 General Semaphores w busy wait Pltsgt vsgt g g gb39t t39nterguptsi 1 Inhibit Interrupts muexsss if S lt O Ptmutexs 31 Blockself Ls 39f 3 lt 0 Vbmutexs Enablenterrupts UnblockqLs Scheduler Vbmutesx Enablenterrupts 93956 Scheduler Vbmutexs ilse Enablenterrupts Vbmutexs Enablenterrupts LS is a blocked list associated with the semaphore s CompSci 143A Spring 2009 21 Implementing Monitors Need to insert code to Guarantee mutual exclusion of procedures enteringleaving Implement cwait Implement csigna Implement 3 types of semaphores 1 mutex for mutual exclusion 2 condsemc for blocking on each condition C 3 urgent for blocking process after signal to implement special highpriority queue CompSci l43A Spring 2009 22 Implementing Monitor Primitives Code for each procedure Code for Csigna PmUteX if condcntc procedurebody if urgentcnt gt 0 Vurgent urgentcnt urgentcnt 1 else Vmutex VCondsemc Purgent urgentcnt urgentcnt 1 Code for CWait condcntc condcntc 1 if urgentcnt gt 0 Vurgent else Vmutex Pcondsemc condcntc condcntc 1 CompSci 143A Spring 2009 23 Clock and Time Management Most systems provide hardware ticker issues periodic interrupt countdown timer issues interrupt after a set number of ticks Build higherlevel services using this hardware Wall clock timers Countdown timers how to implement multiple logical timers using a single hardware countdown timer CompSci 143A Spring 2009 24 Wall clock times Typical functions UpdateCock increment current time typically number of clock ticks since some known time GetTime return current time SetTimetnew set time to tnew Must maintain monotonicity for two successive clock readings the second time should always be 2 the rst time So how do we set the clock back if we notice it is running fast CompSci 143A Spring 2009 25 Countdown Timer Main use as alarm clocks Typical function Delaytdel block process for tdel time units Implementation using hardware countdown Delaytdel SetTimertdeI set hardware timerl Pdelsem wait for interrupt Timeout caed at interruptl Vdelsem CompSci l43A Spring 2009 26 Logical countdown timers Provides at a minimum the following functions tn CreateLTimer create new timer DestroyLTimertn SetLTimertntdeI block process and call Timeout at interrupt Each process will want one or more logical times of its own Implement multiple logical countdown timers using a single hardware timer Two approaches Priority queue with absolute wakeup times Priority queue with time differences CompSci 143A Spring 2009 27 Priority queue with absolute wakeup times Store wakeup times of logical timers in a priority queue T Q Function of SetLTimertntdel Compute absolute wakeup time using wall clock wnew tdeltnow Insert new request into T Q ordered by absolute wakeup time If new request is earlier than previous head of queue set hardware countdown to tdel CompSci l43A Spring 2009 28 Comde 143A Clock and Time Management Absolute Wakeup Times Example SetLTimer tn 35 Countdown Hard ale me 5 rum qucuc Figure 48 Spring 2009 Priority queue with time differences Priority queue T Q records only time increments no wallclock is needed Function of SetLTimertntdel Find the two elements L and R between which new request is to be inserted add differences until tdel is reached split the current difference between L and R into difference between L and new element and difference between new element and R If new request goes at front of T Q reset the countdown time to tdel CompSci l43A Spring 2009 30 Clock and Time Management Time Differences Example SetLTimer tn 35 Coumdmxn Hardware unel 335279 I I I a Figure 49 Comde 143A Spring 2009 31 Communication Primitives send and receive each use a buffer to hold message process 4 process p sz39nd pm rareire mm sbuf rbuf cm Figure 410a 1 How does sender process know that Sbuf may be reused 2 How does system know that rbuf may be reused overwritten CompScl 143A Spring 2009 32 Possible Solutions Reusing Sbuf Use blocking send Reuse when send returns Provide a ag or interrupt for system to indicate release of Sbuf Reusing rbuf Provide a ag for sender to indicate release of rbuf These solutions are awkward CompSci l43A Spring 2009 33 Communication Primitives Better solution Use pool of system bu ers 51w Figure 410b System Buffers i run SEW WW CompSci 143A send copies sbuf to a system buffer send is free after copy is made Sender may continue generating messages System copies or reallocates full buffers to receiver receive copies system buffer to rbuf rbuf is overwritten with next message on nextcall to receive which is controlled by the receiver Spring 2009 Communications Kernel Copying of buffers is usually handled by a specialized communications kernel Involves considerable additional processing Breaking into transmission packets Routing packets through network Reassembling message from packets at the destination Handling transmission errors CompSci l43A Spring 2009 35 Interrupt Handling Standard interrupthandling sequence 1 2 3 CompSci 143A Save state of interrupted processthread Identify interrupt type and invoke appropriate interrupt handler III 1H services interrupt Restore state of interrupted process or of another one Figure 4 1 121 Spring 2009 36 Typical Interrupt Handling Scenario User process p calls device interface procedure Fn Fn initiates device then blocks OS takes over selects another process to run When device terminates it generates an interrupt which invokes IH IH services interrupt unblocks P and returns control to OS Ilnldluarc maria mmer lulhncr39 p 0 ollmr process in ms Inruuffmr mumjan fulsrrupl Figure 41 la CompSci 143A Spring 2009 37 Interrupt Handling Main challenges Fn must be able to block itself on a given event If Fn is written by user requires knowledge of the OS kernel possibly modi cation of the OS kernel H must be able to unblock p IH must be able to return from interrupt Classical approach specially designed kernel mechanisms Another approach extend process model into the hardware so H is included and use standard synchronization constructs such as monitors CompSci l43A Spring 2009 38


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


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'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Janice Dongeun University of Washington

"I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.