Instructions:
Andrew login ID (please print in BLOCK capital letters):
Full Name: Recitation Section (or TA):
15-213/18-243, Fall 2009 Final Exam
Copyright By PowCoder代写 加微信 powcoder
Monday, Dec 14, 2009
• Make sure that your exam is not missing any sheets, then write your full name, Andrew login ID, and recitation 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 other
electronic devices are allowed.
• Please make sure we can read your andrew ID. It needs to be in block capital letters.
Page 1 of 24
Multiple Choice Virtual Memory? Stack Signals Assembly Network Programming Floats and Ints Processes and Threads Synchronization Concurrency File I/O Extra Credit
1 (18): 2 (18): 3 (16):
4 (9): 5 (12): 6 (12): 7 (10): 8 (12): 9 (14):
11 (10): 12 and 13 (0):
TOTAL (141):
Page 2 of 24
Problem 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 disk that has the following characteristics: 10,000 RPM rotation speed (6ms per full revolution), average seek time of 7ms, 1000 sectors per track. (Assume that all in-memory pages that get replaced are clean.)
(d) Not enough information to determine the answer
D. If a parent process forks a child process, to which resources might they need to synchronize their access to prevent unexpected behavior?
(a) file descriptors
(b) malloc’ed memory (c) stack
(d) None of the above
E. 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 its corresponding value must appear before the second one’s value in physical memory. True or False?
(a) True. (b) False.
Page 3 of 24
Problem 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-bit machine. 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 24
Each of these should easily fit on a single line. Do not make any assumptions about the type of the values passed 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 24
Problem 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 call
printf("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 from the argument build area to the top of the stack as it exists just after the call instruction.
Page 6 of 24
G. 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 24
Problem 4. Signals (9 points):
Consider the C code below. Assume that no errors prevent any processes from running to completion and that a process terminated by an uncaught signal has an exit status of 0.
int count = 0;
void killhandler(int sig){
printf("SIGKILL received\n");
void childhandler(int sig){
int status;
wait(&status);
count += WEXITSTATUS(status);
int i; // for loop iterator
pid_t pid[3]; // pids of child processes
Signal(SIGKILL, killhandler);
Signal(SIGCHLD, childhandler);
// Fork 3 child processes
for(i=0; i<3; i++){
pid[i] = fork();
if(!pid[i]){ // If child process
Signal(SIGKILL, SIG_DFL);
exit(5); }
// Parent process only
for(i=0; i<3; i++){
kill(pid[i], SIGKILL);
printf("count = %d\n", count);
A. What is the maximum number of times “SIGKILL received” could be printed? B. List all possible values of count that could be printed:
Page 8 of 24
Problem 5. Assembly – Leaping to Conclusions (12 points):
Your classmate Meddie Tartan is trying to write a more advanced proxy. Her goal is to write a cache that keeps track of several different things about the request, so that the proxy can better match clients’ requests. She wants to keep track of it in a struct as follows:
struct cache_entry {
char *url;
char *browser_signature;
char *http_referrer;
char *content;
Since cache entries are stored in a global data structure, once the information is parsed out of the information the server sent, it needs to be copied into a malloced area that will stay around after the present stack frame goes away. Since each member of the cache entry struct is a string of arbitrary length, malloc needs to be called many times in the course of building the entry.
Since she remembered having to handle error cases appropriately during proxylab, Meddie’s first idea was to write code that called malloc each time, and if any of them fail, return an error code, like so:
struct cache_entry *allocate_entry(int url_length, int signature_length,
int referrer_length, int content_length)
struct cache_entry *entry = malloc(sizeof(struct cache_entry));
if (!entry)
return NULL;
entry->url = malloc(url_length+1); /* +1 for null terminator */
if (!entry->url)
return NULL;
entry->browser_signature = malloc(signature_length+1);
if (!entry->browser_signature)
return NULL;
entry->http_referrer = malloc(referrer_length+1);
if (!entry->http_referrer)
return NULL;
entry->content = malloc(content_length+1);
if (!entry->content)
return NULL;
return entry;
A. Briefly explain (one sentence) what can go wrong with the above code.
Page 9 of 24
After Meddie Tartan realizes her mistake, she finds a fancy proxy binary that claims to do correctly what she wants her program to do. However, its source code was not available, so she tries disassembling it to see what the control flow looks like. She deduced a basic skeleton, as follows, of what this proxy’s version of the same function does, but needs your help filling in the specifics (she thinks one or more uses of goto might be involved).
struct cache_entry *allocate_entry(int url_length, int signature_length,
int referrer_length, int content_length)
struct cache_entry *entry = malloc(sizeof(struct cache_entry));
if (!entry)
____________________
entry->url = malloc(url_length+1); /* +1 for null terminator */
if (!entry->url)
____________________
entry->browser_signature = malloc(signature_length+1);
if (!entry->browser_signature)
____________________
entry->http_referrer = malloc(referrer_length+1);
if (!entry->http_referrer)
____________________
entry->content = malloc(content_length+1);
if (!entry->content)
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
B. Fill in the blanks above, using the assembly code on the next page.
Page 10 of 24
000000000040058c
40058c: 48 89 5c 24 d8
400591: 48 89 6c 24 e0
400596: 4c 89 64 24 e8
40059b: 4c 89 6c 24 f0
4005a0: 4c 89 74 24 f8
4005a5: 48 83 ec 28
4005a9: 89 fd
4005ab: 41 89 f4
4005ae: 41 89 d5
4005b1: 41 89 ce
4005b4: bf 20 00 00 00
4005b9: e8 aa fe ff ff
4005be: 48 89 c3
4005c1: 48 85 c0
4005c4: 74 7a
4005c6: 8d 7d 01
4005c9: 48 63 ff
4005cc: e8 97 fe ff ff
4005d1: 48 89 03
4005d4: 48 85 c0
4005d7: 74 5a
4005d9: 41 8d 7c 24 01
4005de: 48 63 ff
4005e1: e8 82 fe ff ff
4005e6: 48 89 43 08
4005ea: 48 85 c0
4005ed: 74 3c
4005ef: 41 8d 7d 01
4005f3: 48 63 ff
4005f6: e8 6d fe ff ff
4005fb: 48 89 43 10
4005ff: 48 85 c0
400602: 74 1e
400604: 41 8d 7e 01
400608: 48 63 ff
40060b: e8 58 fe ff ff
400610: 48 89 43 18
400614: 48 85 c0
400617: 75 27
mov %rbx,-0x28(%rsp)
mov %rbp,-0x20(%rsp)
mov %r12,-0x18(%rsp)
mov %r13,-0x10(%rsp)
mov %r14,-0x8(%rsp)
sub $0x28,%rsp
mov %edi,%ebp # 1st argument
mov %esi,%r12d # 2nd argument
mov %edx,%r13d # 3rd argument
mov %ecx,%r14d # 4th argument
mov $0x20,%edi
callq 400468
mov %rax,%rbx
test %rax,%rax
je 400640
lea 0x1(%rbp),%edi
movslq %edi,%rdi
callq 400468
mov %rax,(%rbx)
test %rax,%rax
je 400633
lea 0x1(%r12),%edi
movslq %edi,%rdi
callq 400468
mov %rax,0x8(%rbx)
test %rax,%rax
je 40062b
lea 0x1(%r13),%edi
movslq %edi,%rdi
callq 400468
mov %rax,0x10(%rbx)
test %rax,%rax
je 400622
lea 0x1(%r14),%edi
movslq %edi,%rdi
callq 400468
mov %rax,0x18(%rbx)
test %rax,%rax
jne 400640
mov 0x10(%rbx),%rdi
callq 400488
mov 0x8(%rbx),%rdi
callq 400488
mov (%rbx),%rdi
callq 400488
mov %rbx,%rdi
callq 400488
400619: 48 8b 7b 10
40061d: e8 66 fe ff ff
400622: 48 8b 7b 08
400626: e8 5d fe ff ff
40062b: 48 8b 3b
40062e: e8 55 fe ff ff
400633: 48 89 df
400636: e8 4d fe ff ff
40063b: ba 00 00 00 00 mov
400640: 48 8b 1c 24 mov
400644: 48 8b 6c 24 08 mov
400649: 4c 8b 64 24 10 mov
40064e: 4c 8b 6c 24 18 mov
400653: 4c 8b 74 24 20 mov
400658: 48 83 c4 28 add
(%rsp),%rbx
0x8(%rsp),%rbp
0x10(%rsp),%r12
0x18(%rsp),%r13
0x20(%rsp),%r14
$0x28,%rsp
40065c: c3 retq
Page 11 of 24
Problem 6. Network Programming (12 points):
A. Consider a logging daemon, whose purpose is simply to accept messages from clients and log them to a file. (This is sometimes used in secure networks to ensure that, even if a cracker breaks into one computer, he can’t erase his traces from the logs because they are stored elsewhere.)
In the following table, please list the system and/or library calls that each side of the connection would make. Each row should contain the name of a single system or library call, placed in the appropriate column. Please list the calls in the order they are called, not the order they return.
Please only include network-related operations (accept, bind, close, connect, listen, read, socket, and write).
You should make the following assumptions:
• The server finishes initializing before the client starts.
• The server only serves a single client.
• The client already knows the server’s IP address.
• The client only sends one message before closing the connection.
Page 12 of 24
B. Consider a simple network protocol for a webcam, in which a client connects to the server, and the server sends back 4096 bytes of image data. Suppose the client contains the following snippet of code to receive data from the server:
#define IMAGE_SIZE 4096
char *image_buf = malloc(IMAGE_SIZE);
if (!image_buf) {
fprintf(stderr, “Out of memory.\n”);
exit(1); }
int err = recv(server_fd, image_buf, IMAGE_SIZE, 0);
if (err < 0) {
fprintf(stderr, "Error reading from server: %s\n", strerror(errno));
exit(1); }
/* BUG: Even if malloc and recv succeed, sometimes the data in image_buf
only partially matches the image the server sent. -- hqbovik */
What is the most likely cause of the bug?
Page 13 of 24
Problem 7. Floats and Ints (10 points):
Conversion from float to int is a notoriously expensive operation. Not all processors do this in hardware. A clever technique uses the normalization step in double-precision floats. Imagine if you could normalize a (non-negative) floating point number so that the low-order significand bit represents 20. Then the significand would be an integer.
Assume a double where, after taking the exponent into account, the low-order bit represents 1 (20). What does the “implied leading 1” of the significand represent?
Now, assume a double x is known to be in the range 0 <= x < 232. To force the low-order bit of x to represent 1 (20), you should (circle one:)
• addor • multiply
by (fill in the blank:)
After this operation, you can store the double to memory and read the (circle one:)
• upper 32 bits (the end with the sign bit == 0), or • lower 32 bits (the other end)
as an unsigned integer to get the integer value of the original double. This algorithm will round (circle one:)
• toward zero,
• to the nearest even.
• double-precision significand has 52 bits
• double-precision exponent has 11 bits
• double-precision sign-bit is (of course) 1 bit
Page 14 of 24
Problem 8. Processes and Threads (12 points):
Consider the C code below. Assume all system calls are successful and that all processes run to completion.
#include
#define NUM_FORKS 4
char array[NUM_FORKS+2];
int pos = 0;
char outs[9] = {’1’,’1’,’8’,’5’,’2’,’2’,’4’,’1’,’3’};
void work(void* id){
int index = (*((int*)id))*2;
char writeMe = outs[index];
array[pos++] = writeMe;
int main(){
char three = ’3’;
int pid[NUM_FORKS];
for(i = 0; i
#include
char array[NUM_THREADS+2];
int pos = 0;
char outs[9] = {’1’,’1’,’8’,’5’,’2’,’2’,’4’,’1’,’3’};
void* work(void* id){
int index = (*((int*)id))*2;
char writeMe = outs[index];
array[pos++] = writeMe;
return NULL;
int main(){
char three = ’3’;
pthread_t tid[NUM_THREADS];
for(i = 0; i
id_to < 0 || id_to >= NUM_ACCOUNTS) {
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com