CS 4410 Operating Systems Prelim 2, 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 must fill in your name and NETID above and at the top of each (odd-numbered) page. If you fail to do so, we will take off 1 point for each omission.• 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.Question Points Possible 0: Omitting Name or NetID−21: Multiple Choice202: Alternating Bit Protocol203: Hand-over-Hand 204: Oldie but Goodie205: All’s Well ThatEnds Well 202[3]$d) $RPC.$Which&of&the&following&statements&about&Remote&Procedure&Calls&(RPC)&are&true?&Select&all&that&apply.(A) RPCs&require&the&programmer&to&construct&correctly&formatted&network&messages.(B)&A&Remote&Procedure&Call&could&support&a&Python&program&running&on&Linux&to&provide&a&service&to&a&C++& program&running&on&Windows.(C) After&the&client&and&server&stubs&are&compiled,&the&server&program&must&then&define&the&server ’s&interface&using&an&Interface&Def inition&Languag e&(IDL).(D)&If&you&look& at&code&that&invokes&a&Remote&Procedure&Call,&the&call&would&be&indis ting uishable&from&a&local&procedure&call.Your Answer: [2]$c)$Caching$and$Page$Tables.$Which&of&the&following&statements&about&caching&and&page&tables& are&true?& &&Select& all&that&apply.(A) A&Page&Table&i s&a &ca che& for&memory.(B) A&Level &2&Cache&i s&a&ca che& for&a&Level &1&ca che.(C) A&2-Level&Page&Table&is&a&cache&for&a&1-Level&Page&Table.(D) A&TLB&i s&a &cache&for&a&Pag e&Table.(E) DRAM&can& be&used&as&a& cache&for&disk.Your Answer: [3]$b) $RAID.$Recall&that&RAID&Level&1&mirrors& disks.&&In&the&picture,&there& are&four&stripes,&each&of&which&is&mirrored&once.&&Which&of&the&following&statements&about&this&RAID&Level&1&set-up&are& true?&Select& all&that&apply.Your Answer: (A)&RAID&Level&1&can&always&detect&w hen&a&single&bit&flips.(B)&RAID&Level&1&can&always&&detect&and&correct&when&a&single&bit&flips.(C)&RAID&Level&1&can&always&detect&when&two&bits&flip&(note&that&the&two&bits&m ay&or&may&not&be&on&different&disks).(D)&RAID&Level&1&can&always&detect&and&correct&when&tw o&bits&flip.(E)&R AID&Level&1&supports&a&2x&read&perform ance&over&an&un-mirrored&disk&even&while&detecting&bit&flip&errors.[2]$a)$Networking.$Which&of&the&following&are&true&of&UDP? &&Select&all&that&apply.(A) UDP&is&reliable.(B) UDP&is&ordered.(C) UDP&has&a&smaller&header&than&TCP.(D) UDP&controls&netw ork&congestion.(E) UDP&is&the&predom inant&protocol&for&all&web&traff ic.Your Answer: CAB,&DD,&E[20 pts] 1. Multiple Choice Questions3[3]$h) $Networking.$Which&of&the&following&statements&about&Ethernet’s&Carrier&S ense&Multiple&Access& /&Collision&Detection&(CSMA/CD)& Protocol& are&true?&Select& all& that&apply.(A) multiple&hosts&use&CSMA/CD& to&share&the&same&Ethernet&physical&network.(B) CSMA/CD&has&senders&sense&whether&the&Ethernet&is&currently&in&use.(C) CSMA/CD& has&senders&sense&to&determine&whether&a&collision&has&trans pired.(D)&CSMA/CD&prevents&any&single&ho st&from&monopolizing&the&network.(E)&CSMA/CD&guarantees&packet&delivery.Your&Answer:&[2]$g)$File$S ystems.$Which&of&the&following&statements&about&Unix-like&File&S ystem s&&(UFS)&are&true?&Select&all&that&apply.(A) A&File&System&Consistency&Checker&detects &random&bit&fl ips&in&the&data&blocks& of&the&file&system .(B) When&completed,&every&block& in&a&consistent&File& System&must& be& marked&as&either&free&or&in&use.(C) In&a &correctly&structured&Directory& System,&two&distinct&paths&cannot&lead&to&the&same&file.(D) A&Directory& can&consist&of&indirect&blocks& a nd&da ta&blocks,&just&like&a&File.Your&Answer:&[3]$f) $Page$Tables.$Which&of&the&following&statements&about&page&tables&are&true?Select&all&that&apply.(A) Multi- level&pag e&tables&always&require&more&s pace&than&single-level&page&tables.(B) Multi-level&page& tables& generally&have&a&slow er&look-up& time& than&single-level&pag e&tables.(C)&All&page&table&structures&that&are&not&a&simple&single-level&page&table&have&the&fundamental&structure&of&an&array&of&arrays.(D)&Page&tables&need&to&be&invalidated&on&a&context&switch.Your&Answer:&BA,&B,&CB,&D1.$( Continued)[2]$e)$Page$Tables.$In&a&clip&of&the&movie&The&Social&Network&that&was&shown&in&class,&the&Harvard&professor&asks&a&question&about&single-level&page&tables,&paraphrasing:&“assuming&PTEs&ha ve&8&status&bits,&what&would&those &status&bits&be?”&Mark&Zuckerberg&a nswered,&correctly&according&to&the&professor, “1&valid&bit,&1& modi fy&bit,&1&referencebit&and&5&permission& bits.”& &T he&prof essor ’s &ques ti on& i s:&&&( S el ect&all&tha t&apply.)(A) impossible&to&answer&as &there&is&not&enough&inform ation(B) a&very&difficult& question&that&only&a&serious& geek&could& answ er(C) so&easy&that&anyone&with&a&basic&knowledge&of&computer&science&could&have&answ ered&it(D) really&outdatedYour&Answer:&ANETID:________4[20pts]$$2.$A lternating$Bi t$ProtocolThis&question&is&to&test&your&understanding&of&re transmission&protocols&such&as&TCP.& &Suppose& there&are&two&compute rs,&X&and&Y,&c onnected&by&a&single&physi c al&network&link.&&Packets&can&flow&in&both&directions.&Packets&can&get&lost,&but&they&can’t&get&re-ordered& or&d am aged.&&Whil e&unreli able,&i f&one&c omput er&keeps&ret ransmi tt i ng&the&same&packet&(wi t h&the&same&contents),& eventually&at& least&one& copy&will&arrive&at&the &othe r&computer.&& The& minimum&latency&on&t he&l i nk&(the&time&between&sending&a& packet&and&recei ving&i t)&i s&1 &mil li second&and&the&maxi mum&packet &size&is&101&bytes.&&The&bandwi dth&i s&unl imi ted.&&Note&that&because&of&the&set-up,&pac kets& do&not&need&addresse s:& a&packet&sent&on&one& end&of&the&l ink&is&automatically&desti ned&for&the&other.&&The&length&of&a&packet&p is&given&by&function&length(p).Pat&desi gns&an&“alte rnating&bit&protoc ol"& for&reliable& commu nic ation&from&X&to&Y:&& X&and&Y&both&maintain&a&sequence&number&that&count s&t he&number&of&packets&sent& and&rec eived,& respect i vel y.&&A&packet &has& two&fi el ds:&a& 1 &byte&header&and&a&payload&of& at&most&100&bytes.&&Having&o nly&limited&size,&t he&h eader&canno t &sto re&t h e&entire&sequ en c e&n um ber.&&In&this&case,&the&1-byte&header& stores&the&sequence&numbe