1Question Points Possible 0: Name & NetID21: Multiple Choice142: Multicore Synchronization153: Scheduling204:Threads and Processes145: Synchronization206: Deadlocks15Tot al 100CS 4410 Operating Systems Prelim I, Fall 2015Profs. Bracy and Van RenesseNAME: NetID:• This is a closed book examination. You have 120 minutes. No electronic devices of any kind are allowed.• You get 1 point for filling in your name and NETID above. You get another point if you fill in your NETID on each (odd-numbered) page. You get 0 points for the whole exam if you don’t do any of these…• For Coding Questions: You may use pseudo-code. Descriptions written mostly in English will get no credit. In addition to correctness, elegance and clarity are important criteria for coding questions. • Show your incomplete work for partial credit. Make any other assumptions as necessary and document them. Brevity is key.• Please write your solutions within the provided boxes as much as possible. Write clearly. Use the scratch paper at the end if you need to practice your answer first.2[2]$a) $Which'of'the'f ollow ing'is'the'best'w ay'to'wait'for'two'predicates'to'be'true?(A)with lock:while not condA or not condB:if not condA: condA_cv.wait()if not condB: condB_cv.wait()(B)with lock:while not condA: condA_cv.wait()while not condB: condB_cv.wait()(C)with lock:while not condA or not condB:condA_cv.wait()condB_cv.wait()(D)with lock:if not condA or not condB:while not condA: condA_cv.wait()while not condB: condB_cv.wait()Your'Answer:'[2]$b)$Which'of'the'following'are'(virtually)'shared'by'threads'w ithin'a'single'process?'In'other'words,'is'it'instantiated'per'process'instead'of'per'thre ad?''Select'all'that'apply.(A)'Heap(B)'S tack(C)'Code'/'Program'Text(D)'R egistersYour'Answer:'AA,C[14pts]$$1.$Multiple$Choice$ Questions[2]$c)$Which'of' the' following' opera tions'require' the' execut ing'code' to' be' operating'with'high' privilege?' Select'all'that'apply.(A)'Im plem enting'a'monitor(B)'Performi ng' a'semaphore'P'operation'(C)'Accessing'the'device'registers'of'an'I/O'device,'e.g.'the'disk,'keyboard,'or'network'card(D)'Disabling'interrupts(E)'Making'a'system'callYour'Answer:'C,DCheck & t h e&12&Comma n d ments3[2]$g) $Which'of'the'follow ing'statements'about'threads'is'false?Select'all'that'apply.(A)'Multi-thr eading'is'only'useful'on'a'multi-proces sor.(B)'Multi-threading'is'only'useful'when'a'task'can'be'parallelized.(C)'There'are'performance'benefits'to'running'threads'of'the'same'process'one'after'the'other' on'the' same' processor.(D)'Multi-thread ing'requires'operating'system'support'for'managing'multiple'PCBs.Your'Answer:'[2]$f ) $Which'of'the'follow ing'statements'about'deadlocking'is'true?'Select'all'that'apply.(A)'If'a'system'is'not'deadlocked'at' time' T,'it'can'always'avoid'being'deadlocked'at'time'T+1.(B)'If'a'system'is'in'a'safe'state'at'time'T,'it'can'always'avoid'being'deadlocked'at'time'T+1.(C)'When'reducing'a'Resource'Allocation'Graph,'you'should'begin'with'the'process'which'currently'holds'the'most'resources.(D)'Modern'operating'systems'use'the'Banker’s'Algorithm'to'determine'whether'it'is'safe'to'give'a'particular'process'a'particular'resource.Your'Answer:'[2]$e)$You'are'using 'a'semaphore'package'w hich'provides'3'functions:'init(),'P(),'and'V().'Which'of'the'follow ing'changes'to'the'package'could'affect'the'correctness'of'your'code?Select'all'that'apply.(A)'P is'modified's o'that'it'busy-waits'instead'of'yielding'when'a'resource'isn’t'available .(B)'init is 'modified'so'that'it'only' accepts' 0' or' 1' as'an' initial' v al ue.(C)'The'implementation'stores'the'count'in'an'unsigned'int instead'of'a'signed'int.(D)'V is 'm odified's o'that'it'wakes'the'thread'that'most'recently'called'P.(E)'Asserts'are'removed'from'all'three'functions.Your'Answer:'[2]$d)$Which'of'the'following'statements'about'systems'calls'are'tru e?Select'all'that'apply.(A)'A'system'call'can'be'caused'by'events'external'to'the'CPU.(B)'All'registers'must'be'saved'w hen'performing'a'system'call.(C)'The'old'privilege'mode'must'be'saved'when'performing'a'system'call.(D)'The'privilege'm ode'must'be'changed'to'“kernel'mode”'w hen'performing'a'system'call.(E)'The's ys tem'call'handler'can'run'on'the'stack'of'the'user'p rocess'that'issued'the'call.Your'Answer:'C,DBA,DBNETID:________Recall:&implementation&should& not&affect&abstraction!![15pts]$$2.$Multicore$Synchronization$using$Compare-and-SwapFor'this'question' you'may'as sume'reading'and'writing'i ndividua l' memory'locations'of's ize'‘int’'are'at omi c'and't hat'size of(int)'= =' size of(int *),'i.e.,&pointers'and'i ntegers'have'the'same'size.'Al so,'the'“ C”-like'language'below'is'really'pseudo-code.''Don’t'worry'about'casting'poi nters'to'integers'or'vice'versa.''A'memory'locati on'is'a'memory'location!Also,'in'the'soluti on s'you' are'allow ed'to'busy-wa it .a) [3]'Implement'a'Te st-And-Set'function'using'CAS'that'does'( not'counting'fetching'instructions)'a'single'memory'bus'read'an d'at 'most'a'si ngle'bus'wri te'c ycl e:bool TAS(int *addr) {return'!CAS(addr,'0,'1);'TAS'returns'0'if'the' lock'is'succ essfully'grabb ed,'whe reas'CAS'retur ns'1'up on 'success,'hence' the'‘!’ '(negation)}b)'[3 ]'' Using'CAS,'i mplement'an'atomic'increment'operat ion:'INC(&x)'i ncrements'x by'1 .''In'the'absence'of'cont ention'(i.e.,&no'mul ti ple't hreads'trying't o'i ncrement '*add r at'th e 's ame'time) ,'your'cod e ' should, ' at'mo st,'read ' memo ry'tw ic e ' and'wri t e'memo ry'once'(i.e.,&at'mo st'th ree 'memo ry'bu s' accesse s).'' You'can'assum e ' that ' lo cal'f unction ' variables'are'kept'in 'CPU'registers.void INC(int *addr) {register'int oldval ='*addr;while'(!CAS(addr,'oldv al,' oldv al +'1))oldval ='*addr;//&Loop&requ i red & in& c ase&mu l tiple& th reads&tr y&to& update&* addrat&the&same&time}4Many'CPU'architectures'pro vide'a'Compare-And -Swap'(CAS)'instruction' wit h'th e' foll ow ing'se mantics' (here'addr is'the'address'of'some'memory'location).''Note'that'(not'countin g'the'fe tch ' of'the 'instru cti on 'itself,'whic h 'is'hopefully'from't he'cache)'CAS'involves'a'single'read'and'at'most'a's ingle ' write' cyc l e' on'th e ' memor y'bus'(reading'and'writin g'* addr):ATOMIC bool CAS(int *addr, int oldval, int newval) {if (*addr != oldval)return FALSE;*addr = newval;return TRUE;}c)'[3]'Use' CAS'to'complete'the'i mplementati on'of'an'append-only'lock-free&list'(i.e.,'you'are'not't