Andrew login ID (pleaseprint in BLOCK capital letters):Full Name:Recitation Section (or TA):15-213/18-243, Fall 2009Final ExamMonday, Dec 14, 2009Instructions:• Make sure that your exam is not missing any sheets, then write your full name, Andrew login ID, andrecitation section (A–H) on the front.• The exam has a maximum score of 141 points.• This exam is OPEN BOOK. You may use any books or notes you like. No calculators or otherelectronic devices are allowed.• Please make sure we can read your andrew ID. It needs to be in block capital letters.Page 1 of 24Multiple Choice 1 (18):Virtual Memory? 2 (18):Stack 3 (16):Signals 4 (9):Assembly 5 (12):Network Programming 6 (12):Floats and Ints 7 (10):Processes and Threads 8 (12):Synchronization 9 (14):Concurrency 10 (10):File I/O 11 (10):Extra Credit 12 and 13 (0):TOTAL (141):Page 2 of 24Problem 1. Multiple Choice (18 points):A. Which of these uses of caching is not crucial to program performance?(a) Caching portions of physical memory(b) Caching virtual memory pages(c) Caching virtual addresses(d) Caching virtual address translations(e) None of the above (i.e., they are all crucial)B. For which values can X not be equal to Z in the code below (circle all that apply):int X = CONSTANT;float Y = X;int Z = Y;(a) For large positive values of CONSTANT (e.g., >1,000,000,000)(b) For large negative values of CONSTANT (e.g., > -100)(c) For small positive values of CONSTANT (e.g., < 100)(d) For small negative values of CONSTANT (e.g., < -1,000,000,000)(e) None of the above (i.e., X==Z in all of these cases)C. What is the maximum number of page faults per second that can be serviced in a system with a diskthat has the following characteristics: 10,000 RPM rotation speed (6ms per full revolution), averageseek time of 7ms, 1000 sectors per track. (Assume that all in-memory pages that get replaced areclean.)(a) 50(b) 100(c) 77(d) Not enough information to determine the answerD. If a parent process forks a child process, to which resources might they need to synchronize theiraccess to prevent unexpected behavior?(a) file descriptors(b) malloc’ed memory(c) stack(d) None of the aboveE. Which of the following is not a situation that results in a signal being sent to a process?(a) A process terminates(b) A process accesses an invalid memory address(c) A new connection arrives on a listening socket(d) A divide by zero(e) None of the above (i.e., all result in a signal being sent)F. Mr. Fred says that, if one of a process’s memory addresses is bigger than a second one, then itscorresponding value must appear before the second one’s value in physical memory. True or False?(a) True.(b) False.Page 3 of 24Problem 2. Virtual Memory? (18 points):In this question you will write macros that will can be used to implement virtual memory on an x86 32-bitmachine. You won’t be writing any virtual memory code, just some helpful macros.Here is the layout for our VM structure with 32-bit virtual and physical addresses, and 4kb pages:Virtual addresses are structured as such:31 22 21 12 11 0+-------+---------+---------+| PDI | PTI | PPO |+-------+---------+---------+A Page Directory Entry (PDE) is structured as such:31 12 11 1 0+-------------+-----------+-+-+| PTBA | Unused |W|P|+-------------+-----------+-+-+Writable?---ˆ ˆPresent?---|A Page Table Entry (PTE) is structured as such:31 12 11 1 0+-------------+-----------+-+-+| PBA | Unused |W|P|+-------------+-----------+-+-+Writable?---ˆ ˆPresent?---|You do not need to know how these values connect for this question, just know where each value is bitwise.Page 4 of 24Each of these should easily fit on a single line. Do not make any assumptions about the type of the valuespassed to these macros!/*Given a virtual address, returns the Physical Page Offset.*/#define VA_GET_PPO(virtual)/*Given a virtual address, returns the page table index.*/#define VA_GET_PTI(virtual)/*Given a virtual address, returns the page directory index.*/#define VA_GET_PDI(virtual)/*Given a page directory entry, returns the page table base address.*/#define PDE_GET_PTBA(pde)/*Given a page table entry, returns the page base address.*/#define PTE_GET_PBA(pte)/*Returns one if this page table entry is present.*/#define IS_PRESENT(pte)/*Returns one if this page table entry is writable.*/#define IS_WRITABLE(pte)/*Returns a new Page Table Entry with the present bit set to the*value in Present (either 1 or 0)*/#define SET_PRESENT(pte, pres)/*Returns a new Page Table Entry with the writable bit set to the*value in Writable (either 1 or 0)*/#define SET_WRITABLE(pte, write)As a closing note: you just wrote the hardest part of virtual memory translations: congratulations!Page 5 of 24Problem 3. The Stack Question (16 points):Answer the following questions about x86 stack convention (in 32-bit mode):A. How does the call instruction modify the stack?B. How does the leave instruction modify the stack?C. How does the ret instruction modify the stack?D. How are arguments passed to a function?E. How are return values passed back to a calling function?F. Please draw a stack region that details how a function would callprintf("I lost %d %s.\n", 5, "marbles");The first argument to printf (the format string) is located at 0xcafebeef and the string "marbles"is located at 0xbeefbabe. Please draw the stack area modified/created during this function call fromthe argument build area to the top of the stack as it exists just after the call instruction.Page 6 of 24G. Why is this code potentially harmful? (Hint: it has to do with the stack!)int fd = accept(server,&clientAddr,&clientlen);pthread_create(&tid,NULL,handle_request,(void*)&fd);Confession time: Did you do that on proxylab?Page 7 of 24Problem 4. Signals (9 points):Consider the C code below. Assume that no errors prevent any processes from running to completion andthat a process terminated by an uncaught signal has an exit status of 0.int count = 0;void killhandler(int sig){printf("SIGKILL received\n");return;}void childhandler(int sig){int status;wait(&status);count += WEXITSTATUS(status);return;}main(){int i; // for loop iteratorpid_t pid[3]; // pids of child processesSignal(SIGKILL, killhandler);Signal(SIGCHLD, childhandler);// Fork 3 child processesfor(i=0; i<3; i++){pid[i] = fork();if(!pid[i]){ // If child processSignal(SIGKILL, SIG_DFL);exit(5);}}// Parent process onlyfor(i=0; i<3; i++){kill(pid[i], SIGKILL);}sleep(5);printf("count = %d\n", count);exit(0);}A. What is the maximum number of times
View Full Document