Computer Design and Assembly Language Programming
Computer Design and Assembly Language Programming CPE 229
Popular in Course
verified elite notetaker
verified elite notetaker
verified elite notetaker
verified elite notetaker
verified elite notetaker
verified elite notetaker
Popular in Computer Engineering
This 0 page Class Notes was uploaded by Mack O'Reilly on Monday November 2, 2015. The Class Notes belongs to CPE 229 at California Polytechnic State University San Luis Obispo taught by Staff in Fall. Since its upload, it has received 34 views. For similar materials see /class/234352/cpe-229-california-polytechnic-state-university-san-luis-obispo in Computer Engineering at California Polytechnic State University San Luis Obispo.
Reviews for Computer Design and Assembly Language Programming
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 11/02/15
O O O O O Administrivia Project 2 due right now As before free extension if you are here For SCPD students put this at top of design doc Caf656 For nonSCPD students put this Midterm Tuesday Open book open notes but not open notebook computer Covers rst 10 lectures of course including today Midterm review section tomorrow Section for Project 3 next Friday I will monitor newsgrouplist for questions Please put quotmidterm in subject of questions about midterm Why is it hard 0 Satisfy arbitrary set of allocation and free s 0 Easy without free set a pointer to the beginning of 0 Problem free creates holes quotfragmentationquot Result some big chunk of memory heap and increment on each allocation DUE allocation I current free position Lots of free space but cannot satisfy request IUUIUIUIZIIIJIquot What is fragmentation really 0 Inability to use memory that is free 0 Two factors required for fragmentation Different lifetimesiif adjacent objects die at different times then f I Different sizes If all requests the same size then no fragmentation tha ragmentau39orn IDIDIHIDIHIHIHUIHIUI f they die at the same time then no fragmentation t s why no external fragmentation w pagin O O O 0 0 0 0 0 Dynamic memory allocation Almost every useful program uses it Gives wonderful functionalitybene ts D Don t have to statically specify complex data structures D Can have data grow as a function of input size D Allows recursive procedures stack growth But can have a huge impact on performance Today how to implement it Lecture draws on Wilson good survey from 1995 Some interesting facts Two or three line code change can have huge nonobvious impact on how well allocator works examples to come Proven impossible to construct an quotalways goodquot allocator Surprising result after 35 years memory management still poorly understood More abstractly freak What an allocator must do BEEE Track which parts of memory in use which parts are free Ideal no wasted space no time overhead What the allocator cannot do Control order of the number and size of requestedblocks Change user ptrs gt bad placement decisions permanent a malloc20 The core ght minimize fragmentation App frees blocks in any order creating holes in quotheapquot Holes too small cannot satisfy future requests Important decisions Placement choice where in free memory to put a requested block Freedom can select any memory in the heap Ideal put block where it won t cause fragmentation later impossible in general requires future knowledge Split free blocks to satisfy smaller requests Fights internal fragmentation Freedom can choose any larger block to split One way choose block with smallest remainder best t Coalescing free blocks to yield larger blocks Freedom when to coalesce deferring can be good ghts I external fragmentation Impossible to solve fragmentation Pathological examples 0 If you read allocation papers to find the best allocator Gwen allocatlon 0f 7 ZObyt h mks All discussions revolve aroundh adeoffs The reason There cannot be a best allocator What s a bad stream of frees and than alocates 0 Theoretical result For any possible allocation algorithm there exist streams of 0 Given a 128byte limit on malloced space allocation and deallocah39on requests that defeat the allocator WhatS a really bad combimhon of mallocs amp frees and force it into severe fragmentation o How much fragmentation should we tolerate Let M bytes of live data 71mm smallest allocation 71max largest iHow much gross memory required 0 Next two allocators best t first t that in practice Bad allocator M gt nmaxnmm work pretty well only ever uses a memory location for a single size quotrtt wll w20fr tu39 under wrkl d Good allocator N M lognmaXnmm P e y e agmena on many 0 Ga 5 Pathological examples Pathological examples 0 Given allocation of 7 20byte chunk l i i IN S What s a bad stream of frees and then allocates What s a bad stream of frees and then allocates Free every other chunk then alloc 21 bytes Free every other chunk then alloc 21 bytes 0 Given a 128byte limit on malloced space 0 Given a 128byte limit on malloced space What s a really bad combination of mallocs 8 frees What s a really bad combination of mallocs 8 frees Malloc 128 1byte chunks free every other Malloc 32 2byte chunks free every other 1 8 2byte chunk Malloc 16 4byte chunks free every other chunk 0 Next two allocators best t rst t that in practice 0 Next two allocators best t rst t that in practice work pretty we work pretty we quotpretty well N20 fragmentation under many workloads quotpretty well N20 fragmentation under many workloads Best t Best t gone Wrong 0 Strategy minimize fragmentation by allocating 0 Simple bad case allocate n m n lt m in alternating space from bIOCk that leaves smalle fragment orders free all the 115 then try to allocate an n 1 Data structure heap is alist of free blocks each has a header Example start with 100 bytes of memory holding block size andpointers to next 11 1 21 19 21 19 3 DC I r r r E m Ell H y Code Search freelist for block closest in size to the request Exact match is ideal During free usually coalesce adjacent blocks Problem sawdust alloc 20 Fails Wasted space 57 bytes Remainder so small that over timeleft withquotsawdustquot 0 However doesn t seem to happen in practice though eVErYWhEre the way real programs behave suggest it easily could Fortunately not a problem in practice 93 mm First t 0 Strategy pick the first block that fits Data structure free list sorted lifo fo or by address Code scan list take the rst one o LIFO put free object on front of list Simple but causes higher fragmentation Potentially good for cache locality 0 Address sort order free blocks by address Makes coalescing easy just check if next block is free Also preserves emptyidle space locality good when paging o FIFO put free object at end of list Gives similar fragmentation as address sort but unclear why 1139 First t Nuances 0 First fit sorted by address order in practice Blocks at front preferentially split ones at back only split when no larger one found before them Result Seems to roughly sort free list by size So Makes rst t operationally similar to best t a rst t of a sorted list best t 0 Problem sawdust at beginning of the list Sorting of list forces a large requests to skip over many small blocks Need to use a scalable heap organization 0 Suppose memory has free blocks If allocation ops are 10 then 20 best t wins When is FF better than best t 1339 Firstbest t weird parallels 0 Both seem to perform roughly equivalently o In fact the placement decisions of both are roughly identical under both randomized and real workloads No one knows why Pretty strange since they seem pretty different 0 Possible explanations First t like best t because over time its free list becomes sorted by size the beginning of the free list accumulates small objects and so ts tend to be close to best Both have implicit quotopen space hueris cquot try not to cut into large open spaces large blocks at end only used when have to be eg rst t skips over all smaller blocks iAaa Subtle pathology LIFO FF 0 Storage management example of subtle impact of simple decisions 0 LIFO first fit seems good Put object on front of list cheap hope same size used again cheap good locality 0 But has big problems for simple allocation patterns Eg repeatedly intermix shortlived Znbyte allocations with longlived n 1byte allocations Each time large object freed a small chunk will be quickly taken leaving useless fragment Pathological fragmentation 1 23 First t Nuances 0 First fit sorted by address order in practice Blocks at front preferentially split ones at back only split when no larger one found before them Result Seems to roughly sort free list by size So Makes rst t operationally similar to best t a rst t of a sorted list best t 0 Problem sawdust at beginning of the list Sorting of list forces a large requests to skip over many small blocks Need to use a scalable heap organization 0 Suppose memory has free blocks If allocation ops are 10 then 20 best t wins When is FF better than best t Suppose allocation ops are 8 12 then 12 gt rst t wins 1339 Some worse ideas 0 Worstfit Strategy ght against sawdustby splitting blocks to maximize leftover size In real life seems to ensure that no large blocks around 0 Next t Strategy use rst t but remember where we found the last thing and start searching from there Seems like a good idea but tends to break down entire list 0 Buddy systems Round up allocations to power of 2 to make management faster Result Heavy internal fragmentation 153 Slab allocation Bonwick Known patterns of real programs 0 Kernel allocates many instances of same structures 0 So far we ve treated programs as black boxes E g39r a 17 KB taskstruc for Every Process 0 SIVStam 0 Most real programs exhibit 1 or 2 or all 3 of the o Often want contiguous physical memory for DMA fOHOWing Patterns 0f aHOCdeallom Ram S accumulate data monotonicall overtime o Slab allocation optimizes for this case p y A slab is multiple pages of contiguous physical memory m A cache contains one or more slabs Each cache stores only one kind of object xed size Peaks allocate many objects use brie y then free all 0 Each slab is full empty or partial o Eg need new taskistruct by 39 LOOk inthe taSke r mt Che Plateaus allocate many objects use for a long time If there is a partial slab pick free taskistruct inthat Else use empty or may need to allocate new slab for cache byquot 0 Advantages speed and no internal fragmentation mm 1739 Pattern 1 ramps Pattern 2 peaks a 39I I 3 a 39 9 I 39 a e 39 I 3 I 5 a I E I I3 a e I a I a e 39 I 3 a E I a I a I I time WAT trace from an LRU simulator Trace of gcc compl Ing With full optlmlza on o In a practical sense ramp 2 no free 0 Peaks allocate many objects use briefly then free all Implication for fragmentation Fragmentation a real danger What happens if you evaluate allocator with ramp programs What happens if peak allocated from contiguous memory only lnterleave peak amp ramp lnterleave two different peaks 1239 1939 Exploiting peaks Pattern 3 Plateaus 0 Peak phases alloc a lot then free everything So have new allocation interface alloc as before but only support free of everything Called quotarena allocationquot quotobstackquot object stack or alloCaprocedure call by compiler people Bytes in use 0 Arena 2 a linked list of large chunks of memory Advantages alloc is a pointer increment free is quotfreequot time NO 733501 5P3 for tags or 115 190mtars Truce of perl running a string processing script 0 Plateaus allocate many objects use for a long time What ha ens if overla with eak or different lateau free pom rer39 PP P P P zuaa 2136 Fighting fragmentation o Segregation 2 reduced fragmentation Allocated at same time N freed at same time Different type N freed at different time 39I IIIIII 0 Implementation observations Programs allocate small number of different sizes Fragmentation at peak use more important than at low Most allocations small lt 10 words Work done with allocated memory increases with size Implications 22m Typical space overheads 0 Free list bookkeeping alignment determine minimum allocatable size Store size of block Pointers to next and previous freelist element I amdmmmxho C Machine enforced overhead alignment Allocator doesn t know type Must align memory to conservative boundary Minimum allocation unit Space overhead when allocated 2436 Faults resumption power 0 Resuming after fault lets us emulate many things quotevery problem can be solved with layer of indirectionquot 0 Example subpage protection 0 To protect subpage region in paging system km Set entire page to weakest permission record in PT w Write fault Any access that violates perm will cause an access fault Fault hanle checks if page special and if so if access allowed Continue or raise error as appropriate 2536 Simple fast segregated free lists 0 Array of free lists for small sizes tree for larger Place blocks of same size on same page Have count of allocated blocks if goes to zero can return page 0 Pro segregate sizes no size tag fast small alloc 0 Con worst case waste 1 page per size even wo free after pessimal free waste 1 page per object 23m Getting more space from OS 0 On Unix can use sbrk Eg to activate a new zerofilled page sbrk4096 l nddrbytuofvnlidvirmladdmsspacc39l nggfrfruMmiwd quotwhen p Ifth warmu rrort39virtml quotluluy nountun rem p o For large allocations sbrk a bad idea May want to give memory back to OS Can t with sbrk unless big Chunk last thing allocated So allocate large chunk using map s MAPJNUN 2539 More fault resumption examples 0 Emulate accessed bits Set page permissions to quotinvalidquot On any access will get a fault Mark as accessed 0 Avoid saverestore of F P registers Make rst FP operation fault to detect usage Emulate nonexistent instructions 0 Give inst an illegal opcode OS fault handler detects and emulates fake instruction 0 Run OS on top of another OS Slam OS into normal process privileged When does something quotprivilegedquot real OS gets woken up with a fault lf op allowed do it otherwise kill IBM s VM370 Vmware sort of 2736 Not just for kernels Distributed shared memory 0 Userlevel code can resume after faults too Remote machines o mprotect protects memory 0 sigaction catches signal after page fault Return from signal handler restarts faulting instruction 0 Many applications detailed by Appel 8 Li 0 Example concurrent snapshotting of process Mark all of process s memory readonly w mprotect One thread starts writing all of memory to disk Othar thread keeps aem ng 0 Virtual memory allows us to go to memory or disk On faulti write that Page to disk make writable resume But can use the same idea to go anywhere Even to another computer Page across network rather than to disk Faster and allows network of workstations NOW 2236 2939 Persistent stores Garbage collection 0 In safe languages run time knows about all pointers o Idea Objects that persist across program invocations So can move an objed if you change allthe pointers Eg objectoriented database useful for CAD CAM type apps 0 What memory locations might a program access Achieve by memorymapping a le Any objects whose pointers are currently in registers 0 But only write changes to file at end if commit 39 RectumE13quot any Pommsm Objects it might access USE dirty bits to detect which Pages must be written out Anything else is unreachable or garbage memory can be re used Or emulate dirty bits with mp rotectsigaction using write faults Example Stopand39copy garbage Comedion o On 32bit machine store can be larger than memory 39 Mammy fun Temporarily Pause ngmm allocate new heap But single run of program won t access gt 4GB of objects COPY an DblEds Pei tad to by ragiSters into new heap D Mark old copied objects as copied record new location Keep mapping betw 32bit mem ptrs and 64bit disk offsets Start scanning through new heap For each pomter USE faults to bring mpages from disk as necessary D Copied already Adjust pointer to new location After reading page translate pointersiknown as swizzling D Not copied Than copy it and adjust Pointar Free old heapiprogram will never access itiand continue zuaa 3139 Concurrent garbage collection Heap over ow detection 0 Idea Stop 8 copy but without the stop 0 Many GCed languages need fast allocation Mututor thread runs program collector concurrently does GC Eg in lisp constantly allocating cons cells 0 When collector invoked Allocation can be as often as every 50 instructions Protect from space 81nscanned to space from mutator Fast allocation is just to bump a pointer Copy objects in registers into to space resume mutator char mextjree All pomters m scanned to space point to to space Char rheapilimit If mutator accesses unscanned area fault scan page resume void alloc uns igned size 1f nextjree 5128 gt heap71imit 1 scanned unscanned invokeigarbag collector O 2 area area Char e e ret 7 re mutator faults next free Size i i ccess from space to space 0 But would be even faster to eliminate lines 1 8 2 3239 3339 Heap over ow detection 2 Reference counting o Seemingly simpler GC scheme 0 Mark page at end of heap inaccessible Each object has quotref countquot of pointers to it mprotect heapilimit PAGESIZE PRUTJIUNE Increment when pointer set to it 0 Program will allocate memory beyond end of heap Decmmmted Wham Pointer killed OHr 0 Program will use memory and fault des 39uctors handy for such smartpointersquot Note Depends on speci cs of language Wid C a But many languages will touch allocated memory immediately cgtrefcnt gtr fcn1 o Invoke garbage collector Must now put just allocated object into new heap 0 Note requires more than just resumption Faulting instruction must be resumed ref count 0 Free obect But must resume with different target virtual address 11 h Doable on most architectures since GC updates registers works well for lerarc lcal data StruCtures Eg pages of physical memory zAaa 3539 Reference counting proscons 0 Circular data structures always have ref count gt 0 No external pointers means lost memory 0 Can do manually wo PL support but errorprone o Potentially more efficient than real GC No need to halt program to run collector Avoids weird unpredictable latencies o Potentially less efficient than real GC With real GC copying a pointer is cheap With reference counting must write ref count each time 3536 University of California Berkeley College of Engineering Computer Science Division EECS Fall 2009 John Kubiatowicz Midterm I October 19 2009 CS162 Operating Systems and Systems Programming Your Name SID Number Circle the letters of CS 162 Login First abcdefgthklmnopqrstuvwxyz Second abcdefgthklmnopqrstuvwxyz Discussion Section General Information This is a closed book exam You are allowed 2 pages of notes both sides You may use a calculator You have 3 hours to complete as much of the exam as possible Make sure to read all of the questions first as some of the questions are substantially more time consuming Write all of your answers directly on this paper Make your answers as concise as possible On programming questions we will be looking for performance as well as correctness so think through your answers carefully If there is something about the questions that you believe is open to interpretation please ask us about it Problem Possible Score 20 18 24 20 18 100 Page 120 CS 162 Fall 2009 Midterm I October 19 2009 This page left for 7 314159265358979323846264338327950288419716939937510582097494459230781640628620899 Page 220 CS 162 Fall 2009 Midterm I October 19 2009 Problem 1 TrueFalse 20 pts Please EXPLAIN your answer in TWO SENTENCES OR LESS Answers longer than this may not get credit Also answers without an explanation GET NO CREDIT Problem 1a2pts Apple was the rst company to develop mice and overlapping windows True False Explain Problem 1b2pts A direct mapped cache can sometimes have a higher hit rate than a fully associative cache with an LRU replacement policy on the same reference pattern True False Explain Problem 1c2pts Threads within the same process share the same heap and stack True F alse Explaln Problem 1d2pts A microkernelstyle operating system uses multiple address spaces inside the operating system 7 with components such as the le system network stack and device drivers all running at user level True False Explain Problem 1e2pts An operating system that implements ondemand paging on a machine with software TLB miss handling such as MIPS must use an inverted page table True False Explain Page 320 CS 162 Fall 2009 Midterm I October 19 2009 Problem 1f2pts If the banker39s algorithm nds that it39s safe to allocate a resource to an existing thread then all threads will eventually complete True False Explain Problem 1g2pts The Nachos operating system uses Mesastyle condition variables for all synchronization True False Explain Problem 1h2pts The lottery scheduler prevents CPU starvation by assigning at least one ticket to each scheduled thread True False Explain Problem 1i2pts Multicore chips ie processor chips with more than one CPU on them are only here for the short term next few years until the transistor feature size reaches 10nm True False Explain Problem 1j2pts Thread pools are a useful tool to help prevent the Slashdot effect from crashing Web servers True False Explain Page 420 CS 162 Fall 2009 Midterm I October 19 2009 Problem 2 Synchronization 18 pts Problem 2a3pts Consider a Hash table with the following interface 1 public class HashTable 2 public void Putint Key int Value 3 public int Getint Key ll Return 0 if no previous Put on Key 4 public void Removeint Key ll Noop if no previous Put on Key 5 l Assume that Get must return the valid Value for any Key that has been written by previous Put methods Ifa Put method on a given Key is happening at the same time as a Get method then the Get method may return an earlier Value In our attempt to make the HashTable threadsafe ie usable by multiple threads at the same time we might decided to make all three methods synchronized methods e g Java synchronized statements Would this have negative performance implications Explain carefully fully justify your answer if the answer is yes explain why you think you could get better threadsafe performance If the answer is no explain why this is the best threadsafe performance you could expect Problem 2b2pts Explain the difference in behavior between S emapho re V and CondVar s ignal when no threads are waiting in the corresponding semaphore or condition variable Problem 2c3pts Explain how Nachos is able to implement the correct semantics for CondVar s ignal using Semaphore V Be explicit and make sure to explain why the different of 2b is not an issue here Problem 2d2pts Give two reasons why this is a bad implementation for a lock lockacquire disable interrupts lockrelease enable interrupts Page 520 CS 162 Fall 2009 Midterm I October 19 2009 Problem 2e8pts Suppose that we want a nite synchronized FIFO queue that can handle multiple simultaneous enqueue and dequeue operations Assume that enqueue and dequeue are not allowed to busywait but rather must sleep when the queue is either full or empty respectively Here is a sketch of an implementation utilizing a circular buffer 1 static final int QUEUESIZE100 2 class FlFOQueue 3 Lock FIFOLocknew Lock 0 Methods acquire and release CondVar CVlnew CondVar FIFOLock Methods wait signal broadcast 4 5 CondVar CV2new CondVarFIFOLock Methods wait signalbroadcast 6 Object FIFOQUEUESIZE Finite circular queue of Objects 7 int head 0 tail 0 Start out empty 8 9 void EnqueueObject newobject lO Enqueue Method Spin until can enqueue ii 12 Object Dequeue l3 Dequeue Method Spin until can dequeue l4 15 Implement the Enqueue and Dequeue methods using monitor synchronization You should enqueue using the tail variable and dequeue at the head Remember that spin waiting is not allowed You should have no more than 10 lines for each method Hint make sure to account for wrapping of head and tail pointers and assume Mesa scheduling of the monitors void EnqueueObject newobject Object Dequeue Page 620 CS 162 Fall 2009 Midterm I October 19 2009 This page intentionally left blank Page 720 CS 162 Fall 2009 Midterm I October 19 2009 Problem 3 Deadlock and the Cephalopod Banquet 24pts Problem 3a4pts Name and explain the four conditions for deadlock Problem 3b 2pts Suppose that we utilize the Banker s algorithm to determine whether or not to grant resource requests to threads The job of the Banker s algorithm is to keep the system in a SAFE state It denies resource requests by putting the requesting thread to sleep if granting the request would cause the system to enter an UNSAFE state waking it only when the request could be granted safely What is a SAFE state Problem 3c3pts Explain how the Banker s algorithm prevents deadlock by removing one or more of the conditions of deadlock from 3a Be explicit Page 820 CS 162 Fall 2009 Midterm I October 19 2009 Problem 3d 4pts Suppose that we wish to evaluate the current state of the system and declare whether or not it is in a SAFE state In order to do this we will need to keep explicit track of the resources in the system In particular if there were only two types of resource we could describe the state of the system with the following data structures class FreeResources int FreeResA FreeResB Number of copies of resource that are free Per thread descriptor of thread resources class ThreadResources int MaxNeededA MaxNeededB Max number copies of resource needed int CurHeldA CurHeldB Current number resources hel ThreadResources ThreadRes Assume that FreeRes and ThreadRes have been initialized to re ect the current state of the system Here is a sketch for how we could check for safety 1 boolean IsSAFEFreeResources FreeRes ThreadResources ThreadRes 2 Int FreeA FreeResFreeResA FreeB FreeResFreeResB 3 boolean ThreadFinished new booleanThreadReslength 4 int RemainingThreads ThreadReslength 5 boolean finished false 6 while lfinished 7 finished true 8 for int i 0 i lt ThreadReslength i 9 if lThreadFinishedi 10 Missing Code ll 12 l3 14 return RemainingThreads SAFE if no threads left 15 Provide the missing Code at line 10 This code should have no more than 8 lines and should not alter the external variables arguments Hint work through the threads that can complete Code for Line 10 Page 920 CS 162 Fall 2009 Midterm I October 19 2009 The Cephalopod Diners Problem Consider a large table with identical multievenarmed cephalopods e g octopuses In the center is a pile of forks and knives Before eating each diner must have an equal number of forks and knives one in each arm e g if octopuses are eating they would each need four forks and four knives The creatures are so busy talking that they can only grab one utensil at a time They also grab utensils in a random order until they have enough utensils to eat After they nish eating they return all of their utensils at once Diners are implemented as threads that ask for utensils and return them when nished Consider the following sketch for a CephTable class to implement the Cephalopod Diners problem using monitor synchronization 1 class DinerUtensils 2 public int forksknives utensils held by creature 3 clearly forksKnives lt NumArms 4 public class CephTable 5 Lock lock new Lock acquire release 6 CondVar CV new CondVar lock wait signal broadcast 7 public DinerUtensil Diners Accounting utensils for each diner 8 int NumArms Number of arms for every diner 9 int IdleForks IdleKnives Number of forksknives on table 10 11 public CephTableint NumDiners int NumArms int Forks int Knives 12 Diners new DinerUtensilsNumDiners info about each Diner 13 ThisNumArms NumArms Number of arms per Diner 14 This1dleForks Forks Number Forks on table initially 15 This1dleKnives Knives Number Knives on table initially 16 17 public void GrabUtensilint CephalopodID boolean WantFork 18 Try to grab a utensil from table 19 20 public void DoneEatingint CephalopodID 21 Return all chopsticks to pile 22 lockacquire 23 IdleForks DinersCephalopod1D forks 24 IdleKnives DinersCephalopod1D knives 25 Diners CephalopodID forks 0 26 Diners CephalopodID knives 0 27 CVbroadcast 28 lockrelease 29 30 boolean CephCheckint CephalopodID int numforks int numknives 31 See if ok to give dinner numforks forks and numknives knives 32 33 Problem 3e3pts In its general form the Banker s algorithm makes a decision about whether or not to allow an allocation request by making multiple passes through the set of resource holders threads See for instance the fact that there are two loops in 3d to determine safety Explain why a Banker s algorithm dedicated to the Cephalopod Diners problem namely the CephCheck routine could operate with a single pass through the resources holders Page 1020 CS 162 Fall 2009 Midterm I October 19 2009 Problem 3f4pts Implement the CephCheck method of the CephTable Object namely ll in code for line 31 above This method should implement the Banker s algorithm return true if the given Cephalopod can be granted numforks forks and numknives knives without taking the system out of a SAFE state Do not blindly implement the Banker s algorithm this method only needs to have the same external behavior as the Banker s algorithm for this application Note that this method is part of the CephTable Object and thus has access to local variables of that object This code should not permanently alter the local variables of the Ceph Table Object although it can do so temporarily Do not worry about making this routing threadsafe it will be called with a lock held We will give full credit for a solution that takes a single pass through the diners partial credit for a working solution and no credit for a solution with more than 15 lines Hint it is easier to rst check the requesting Cephalopod then the rest Code for Line 31 Problem 3g4pts Implement the code for the GrabUtensilO routine namely ll in code for line 18 above Its behavior is that it should check to whether or not it is ok to grant the requested type of utensil to the caller and if not sleep until it is ok This code should call the CephCheck routine as a subroutine and should be threadsafe namely it should be able to deal with multiple threads accessing the state simultaneously You should implement this routine as a monitor and assume Mesa scheduling It is up to the Cephalopod to eat and subsequently call DoneEating you should not do that in GrabUtensilO This routine can be written in 8 lines but you can use up to 12 Code for Line 18 Page 1120 CS 162 Fall 2009 Midterm I October 19 2009 This page intentionally left blank Page l220 CS 162 Fall 2009 Midterm I October 19 2009 Problem 4 Virtual Memory 20 pts Consider a multilevel memory management scheme with the following format for Virtual addresses Virtual Page Virtual Page Offset l 10 bits 10 bits 12 bits Virtual addresses are translated into physical addresses of the following form Physical Page Offset 20 bits 12 bits Page table entries PTE are 32 bits in the following format stored in big endian form in memory ie the MSB is first byte in memory gt z a Physical Page OS 1 at g 3 S g C E lt De ned O 0 0g 3 8 g g a g g 4 20 hm 3 bits 0 g g a 0 quot a 9 D Here Valid means that a translation is valid Writeable means that the page is writeable User means that the page is accessible by the User rather than only by the Kernel Note the phrase page table in the following questions means the multi level data structure that maps virtual addresses to physical addresses Problem 4a2pts How big is a page Explain Problem 4b Zpts Suppose that we want an address space with one physical page at the top of the address space and one physical page at the bottom of the address space How big would the page table be in bytes Explain Problem 4c2pts What is the maximum size of a page table in bytes for this scheme Explain Problem 4d2pts How big would each entry of a fullyassociative TLB be for this management scheme Explain Page 1320 CS 162 Fall 2009 Midterm I October 19 2009 Problem 4e2pts Sketch the format of the pagetable for the multilevel virtual memory management scheme of 4a Illustrate the process of resolving an address as well as possible Problem 4f10pts Assume the memory translation scheme from 4a Use the Physical Memory table given on the next page to predict what will happen with the following loadstore instructions Assume that the base table pointer for the current user level process is Ox 0 O 2 O 0 O 0 O Addresses are virtual The return value for a load is an 8bit data value or an error while the return value for a store is either 0 or an error Possible errors are invalid read only kernel only Hint Don t forget that H exidecimal digits contain 4 bits Instruction Result Instruction Result Load Store 0x00001047 oxso 0x02001345 Store Load 0x00C07665 0k 0xFF80078F Store ERROR Load 0x00C005FF read only 0xFFFFF005 Load Test And Set 0x00003012 0xFFFFF006 Page 1420 CS 162 Fall 2009 Midterm 1 Physical Memo All Values are in Hexidecimal October 19 2009 Address 0 1 2 3 4 5 6 7 8 9 A B 00000000 0E 0F 10 11 12 13 14 15 16 17 18 19 00000010 1E 20 21 22 23 24 25 26 27 28 29 00001010 4B 00001020 00 00001030 BB 00001040 03 00002030 00 00002040 70 00002050 00 00004000 00004010 00004020 00100000 00 00 10 65 00 00 20 67 00 40 07 00100010 00 00 50 03 00 00 00 00 00 00 00 00103000 11 22 00 05 55 66 77 88 99 CC EE FF 00 00103010 22 33 44 55 66 77 88 99 DD FF 00 67 001FE000 04 15 00 00 48 59 70 7B 8C AE BF E1 F2 03 001FE010 10 15 00 67 10 15 10 67 10 20 67 15 30 67 001FF000 00 00 00 00 00 00 00 65 00 10 67 00 00 00 001FF010 67 67 65 001FFFFO 00 00 00 00 00 00 00 00 10 00 67 10 30 65 00200000 00 10 00 07 00 10 10 07 00 10 20 07 00 10 30 07 00200010 00200020 00 10 00 07 00 00 00 00 00 00 00 00 00 00 00 00 00200FFO 00 00 00 00 00 00 00 00 00 1F E0 07 00 1F F0 07 Page 1520 CS 162 Fall 2009 Midterm I October 19 2009 Problem 5 Scheduling 18pts Problem 5a2pts Give two ways in which to predict runtime in order to approximate SRTF Problem 5b2pts What scheduling problem did the original Mars rover experience What were the consequences of this problem Problem 5c3pts Five jobs are waiting to be run Their expected running times are 10 8 3 1 and X In what order should they be run to minimize average completion time State the scheduling algorithm that should be used AND the order in which the jobs should be run HINT Your answer will explicitly depend onX Page 1620 CS 162 Fall 2009 Midterm 1 October 1911 2009 Problem 5d5pts Here is a table of processes and their associated arrival and running times CPU Time Process ID Arrival Time Process 3 Show the scheduling order for these processes under 3 policies First Come First Serve FCFS Shortest RemainingTimeFirst SRTF RoundRobin RR with timeslice quantum 1 Assume that context switch overhead is 0 and that new RR processes are added to the head of the queue and new F CFS processes are added to the tail of the queue Time Slot FCFS 0 Page 1720 CS 162 Fall 2009 Midterm I October 19 2009 Problem 5e3pts Can any of the three scheduling schemes FCFS SRTF or RR result in starvation If so how might you x this Problem 5f3pts Explain why a chess program running against another program on the same machine might want to perform a lot of super uous IO operations Page 1820 CS 162 Fall 2009 Midterm I October 19 2009 Scratch Page Do not put answers here Page 1920 CS 162 Fall 2009 Midterm I October 19 2009 Scratch Page Do not put answers here Page 2020