CPS$210$Qualifying$Exam$January$9,$2002$Answer$all$questions.$$Allocate$your$time$carefully.$$Your$answers$will$be$graded$on$content,$not$style.$$Any$kind$of$pseudocode$is$fine$as$long$as$its$meaning$is$clear.$$You$have$180$minutes.$Problem(1.((Show$how$to$emulat e $g eneral$(co u n t in g ) $se mapho re s $sa f el y $u si n g $b in a r y$semaphores.$Problem(2.""You$are$to$implement$the$core$of$a$process$manager$for$a$multiprogrammed$operating$system$kernel.$$The$process$manager$is$a$class$called$Process$that$track s $parent/child/sibling$relationship s$a m o n g$p ro ce sse s$as $ne ed e d,$an d $co o rd ina tes $th e$processMrelated$kernel$services$(e.g.,$the$fork,$exit,$and$wait$system $c a lls $in $Unix).$$Yo u r $solution$must$impleme nt$three$key$m ethods$to$ope rate$on$a$Process$object$p.$p1>Birth(Process*"parent)$registers$this$pro c e ss $p$as$a$child$o f$it s$p a r e n t.$p1>Death(int"status)$indicates$that$th is $p ro c e ss $p$has$exite d $with$the$sp e cif ie d $st a tu s .$int"status"="p 1>Join()$waits$for$p$to$e x it$( i.e .,$to $c a ll$Death),$and$returns$p’s $e x it$s ta t u s.$To"help"guide"your"solution.$$Write$only $what$yo u$need$t o $implement$th e s e $t h re e $methods,$assuming$the$following$context.$$Each$Process$object$P$has$a n $a ss o ci a te d $thread$that$animates $the$pro cess .$$The$threa d$bo un d$to$P$calls$Birth$and$Death$on$P"as$part$of$the$implem enta tion $o f$th e $sy ste m$calls$for$p ro ce ss $cr ea tio n $(e .g.,$fork )$and $destru ction$(e.g.,$exit).$$Join$on$P$ma y $b e $ca ll e d $o n ly $b y $the$threa d $b o u n d$to$the$p a r ent$of$P.$$Y o u$do$not$need$to$create$these$threads$or$enforce$these$restrictions;$they$are$intended$to$simplify$the$pr ob le m .$Required"synchronization."Death$on$P$blocks$u n til $(1 ) $th e $c h il d re n $o f $P$have$e x ite d ,$a n d $(2)$the$parent$of$P$h a s $e x ite d $o r $h a s$e x e c u te d $a $Jo in$o n $P.$$The$in t e n t $is $that$the$e x i t$status$and$process$object$for$P$m ay $be$safely $d e st ro y e d $a ft e r$Death$return s.$Be$sure$t h a t$your$solution$is$free$of$race$conditions,$deadlock,$and$dangling$references.$To$simplify$matters$I$suggest$that$you$use$a$single$mutex$and$condition$variable$for$your$synchronization.$$"You$may$assume$any$reasonable$set$of$list$primitives$if$their$meaning$is$clear,$and $you $may$add$other$methods$for$Process$as$need ed$to$supp o r t$t h e $fu n c ti ons$of$Birth,$Death,$and$Join.$$(Problem(3.((Sketch$rough$graphs$(“back$of$napkin”)$illustrating$the$relationships$among$the$following$qu an tities.$$Note$any$important$assumptions$underlying$your$analysis.$a) Page$fault$rate$as$a$function$of$page$size.$$What$page$sizes$are$typical$for$current$processors$and$operating$systems?$b) Disk$access$latency$as$a$function$of$rotation$speed.$$What$rotation$speeds$and$access$latencies$are$typical$for$current$disk$drives?$c) Peak$disk$read$bandwidth$and$read$latency$as$a$function$of$read$block$size$(request$size).$$What$peak $ban dw idth s$are$typical$for$curren t$disk$drives? $d) Peak$read$bandwidth,$I/O$operation$throughput$(IOPS),$and$access$latency$as$a$function$o f$th e$n u m b e r$o f$dr ive s$in $a$R A ID $st or ag e$u n it.$e) Utilization,$response$time,$and$throughput$as$a$function$of$request$arrival$rate$for$a$queueing$service$center.$f) I/O$block$cac he $hit$ratio$as $a$func tion $of$cach e$size ,$for$rand om $reference s$uniformly$distributed$across$the$I/O$block$space.$g) I/O$block$cache $hit$ratio$a s$a$fun ction $of$cach e$size ,$for$sequ en tial$refe ren ces .$h) Network$bandwidth$as$a$function$of$perMmessage$CPU$overhead.$Problem(4.$$Most$m o dern$pr o c e s sors$and $o p e r ating$systems$enforce$protection$boundaries$that$prevent$programs$from$interfering$with$one$another$or$with$the$operating$system,$and$that$allow$the$operating$system$to$securely$mediate$and$monitor$all$accesses$to$shared$resources$in$accordance$with$a$security$policy.$$Briefly$summarize$the$most$imp orta nt$m ec han ism s$un de rlying $OS $prote ction $and $secu rity.$$$Your$an sw er$should$be$comprehen sive$and$prec ise,$but$succinct.$Problem(5.$$Distribu te d$file$syst e ms$use$c a c h ing$to$im prove$p e r fo r mance$a nd$scala b i lit y .$$NFSv3$uses$block$caching$with$validation,$AFS/Coda$uses$wholeMfile$cachin g$with$callbacks,$and$other$systems$use$block$caching$with$file$leases$(e.g.,$NQMNFS$and$NFSv4).$$Suppose$that$there$is$a$fixed$universe$of$files,$each$client$generates$requests$at$a$fixed$rate,$client$failures$occur$with$some$fixed$probab ility$per$time$unit,$and$all$files$have$a$fixed$prob a b ility$o f$re fer en c e$fo r$e ac h$r eq u es t.$H ow$will$each $o f$the se $sc he mes$beha ve $as $the$numb er$of$clients $increa ses$an d/ or$as$the ir$distan ce$from $th e$server$increase