Name Login University of California at Berkeley College of Engineering Department of Electrical Engineering and Computer Sciences CS61c Summer 2001 Aner Ben Artzi Jeremy Lin Mark Marron Songhwai Oh Woojin Yu Final Exam This is a closed book exam No calculators please You have 2 hours Each question is marked with its number of points This exam booklet should have 15 pages Check to make sure that you have all the pages Put your name and login neatly on each page Show your answers in the space provided for them Write neatly and be well organized If you need extra space to work out your answers you may use the back of previous questions However only the answers appearing in the proper answer space will be graded Good luck Problem 1 2 3 4 5 6 Total Maximum 11 15 25 15 14 20 100 1 Score Name Login MIPS instructions Important please note The MIPS instructions shown in this table are the ones that you must use on the entire exam Do not use any instructions that are not in this table If you use any instructions not listed below you will lose points The columns under format show the bit fields of the instructions The number in the parentheses following each name is the number of bits in that field In the table PC refers to the program counter You may carefully tear this page from your exam booklet for easy reference name Format Op 6 add sub and or sll srl slt jr 0 0 0 0 0 0 0 0 Op 6 addi andi ori lw sw lui beq bne rt 5 rd 5 shamt 5 0 0 0 0 0 0 0 rs 5 rt 5 0 meaning func 6 0 0 32 34 36 37 0 2 42 8 add rd rs rt sub rd rs rt and rd rs rt or rd rs rt sll rd rt shamt srl rd rt shamt slt rd rs rt jr rs rd rs rt rd rs rt rd rs AND rt rd rs OR rt rd logical shift rt left shamt bits rd logical shift rt right shamt bits if rs rt set rd 1 else rd 0 PC rs addi rt rs immed andi rt rs immed ori rt rs immed lw rt immed rd sw rt immed rd lui rt immed beq rs rt label bne rs rt label rt rs immed rt rs AND immed rt rs OR immed rt MEMORY rd immed MEMORY rd immed rt rt immed shifted left 16 bits branch if equal branch if not equal immediate 16 8 12 13 35 43 15 4 5 Op 6 j jal rs 5 syntax target address 26 2 3 j label jal label 2 jump jump and link Name Login Question 1 11 points Part a was worth 3 points and the rest were worth 2 points each a Give following float value in IEEE 754 single precision format in hexadecimal 118 125 dec hex Answer 1 110110001 x 26 42EC4000 hex b Give the truth table and the gate diagram for NOT P OR Q where P and Q are inputs P 0 1 0 1 Q 0 0 1 1 Output 1 0 1 1 c Describe how the relocation information in an object file is used and name a program that makes use of this information Answer The linker uses the relocation information to help it figure out what parts of an object file to relocate and where to relocate them when it builds the final executable Loader was also accepted as a program that uses the relocation information d How does the cache block size affect performance Answer Increasing the block size increases performance up to a point but performance decreases if the block size is too large e List one pro and one con of increasing the size of the TLB Answer Increasing the TLB size tends to decrease TLB misses but it also increases the complexity of the hardware makes it harder to make it fast etc 3 Name Login Question 2 15 points a In UNIX directories are special files that contain information about the files in the directory For example say you are trying to read the file final sol txt which is in a directory called secret Then before the OS can read the file it has to read the special directory file corresponding to secret and find out where final sol txt is stored on disk In order to make accessing the directory files fast what general area of the disk would be ideal for storing the directory files Briefly but specifically explain why Assume that no caching of disk reads is involved This part was worth 2 points Answer It should be stored on the middle tracks since the disk heads are closest to these tracks on average You got 1 point if you said that it should be placed closest to where the disk heads were or something similar b For this part use the information and assumptions given in Part a On UNIX your incoming mail is delivered by appending the message contents to a regular file called the mail spool it basically serves as your inbox So if your username was wooj new mail might typically be written to the file var mail wooj a file named wooj in the directory var mail remember that directories can contain directories Suppose that you have PINE your email client set up to display your inbox on startup i e PINE will read the mail spool on startup Assuming that all other non disk related work takes negligible time You know these disk parameters Average seek time 20 ms Rotational speed 3000 RPM Block size 4 KB Transfer rate 0 4 MB sec Overhead from controller filesystem etc negligible 0 seconds and that Your disk is so fragmented blocks belonging to a file are effectively spread out on disk randomly The three directories accessed on the way to the mail spool are var and mail The size of is 4 KB var is 4 KB and mail is 128 KB Your mail spool is 4 MB large How long do you expect to wait for PINE to start up Show your work This part was worth 6 points Answer From the rotational speed the average rotational latency is 10 ms The average seek time is given as 20 ms Transfer time takes about 10 ms per block There are 1024 32 1 1 1058 blocks total Since the blocks are distributed randomly on disk rotational latency and seek time come into play on every block Thus 1058 10 ms 20 ms 10 ms 42 32 seconds Because of slight variations in interpretation of megabytes and kilobytes and such we also accepted close answers such as 40 or 41 sec assuming that the general idea of the calculations was correct 4 Name Login c If you leave PINE open it will tell you when you get new mail It does this by periodically checking polling to see if your mail spool file has changed You love getting mail and you …
View Full Document
Unlocking...