Andrew login ID: Full Name:
15-213/18-243, Spring 2011 Final Exam
Tuesday, May 3, 2011
Page 1 of 33
Copyright By PowCoder代写 加微信 powcoder
Instructions:
• Make sure that your exam is not missing any sheets, then write your Andrew login ID, full name, and section on the front.
• This exam is closed book and closed notes. A notes sheet is attached to the back.
• Write your answers in the space provided below the problem. If you make a mess, clearly indicate
your final answer.
• The exam has a maximum score of 200 points.
• The problems are of varying difficulty. The point value of each problem is indicated. Good luck!
1 (24): 2 (14): 3 (20): 4 (14): 5 (14): 6 (10): 7 (14): 8 (25): 9 (15):
10 (14): 11 (14): 12 (14):
13 (8): TOTAL (200):
Page 2 of 33
Problem 1. (24 points):
Multiple choice.
Write the correct answer for each question in the following table:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
1. Which of the following is a legitimate difference between IA-32 and x86-64?
(a) Buffer overflow exploits are impossible under x86-64.
(b) IA-32 has caller- and callee-saved register conventions, while x86-64 does not. (c) Under x86-64, any instructions that take 32-bit operands are illegal.
(d) None of the above.
2. Which of the following is the best justification for using the middle bits of an address as the set index into a cache rather than the most significant bits?
(a) Indexing with the most significant bits would necessitate a smaller cache than is possible with middle-bit indexing, resulting in generally worse cache performance.
(b) It is impossible to design a system that uses the most significant bits of an address as the set index.
(c) The process of determining whether a cache access will result in a hit or a miss is faster using middle-bit indexing.
(d) A program with good spatial locality is likely to make more efficient use of the cache with middle-bit indexing than with high-bit indexing.
3. Which of the following is not true about POSIX-style signals?
(a) Certain signals cannot be blocked.
(b) A process can send a signal to itself.
(c) A signal handler executing as the result of a received signal can never be interrupted by another incoming signal.
(d) Signals can only be delivered when returning from system mode.
Page 3 of 33
4. Which of the following is not a benefit of virtual memory?
(a) It allows the virtual address space to be larger than the physical address space
(b) No process can accidentally access the memory of another process
(c) The TLB is more effective since without it dereferencing a virtual address now requires two or more memory accesses
(d) Different processes can have overlapping virtual address spaces without conflict
5. Which of the following is a difference between blocking and ignoring a signal?
(a) Once a blocked signal is unblocked, it will be handled by the process. A signal that comes while it is being ignored will never be handled.
(b) SIGSTOP and SIGINT can be ignored, but not blocked.
(c) Ignoring a signal only causes it to have no effect, while blocking a signal returns the signal to its sender.
(d) None of the above
6. Whereisthefirstargumenttoafunctionlocatedin32-bitassemblycode,immediatelyafterthecall instruction is executed?
(a) %ebp + 0x4 (b) %ebp – 0x4 (c) %esp + 0x4 (d) %exp – 0x4
Page 4 of 33
7. Consider the following piece of code, where out.txt’s contents are “abc”:
int main(int argc, char** argv)
int fd = open(“out.txt”, O_RDWR);
char str[] = “xyz”;
write(fd1, str, 1);
read(fd1, &c, 1);
write(fd1, &c, 1);
What is the contents of out.txt after the code is run? Assume all system calls succeed.
(a) xbb (b) xba (c) xac (d) boat
8. Which of the following is the best reason to choose FastCGI over CGI?
(a) Superior support by web servers like Apache
(b) Lower process creation costs
(c) Lower process communication costs
(d) Better process locality (all tasks can be executed locally)
9. Which of the following system calls can fail due to a network failure?
(a) socket(…)
(b) listen(…)
(c) bind(…)
(d) gethostbyname(…)
10. Which of the following are copied on fork and preserved on exec?
(a) Global variables.
(b) File descriptor tables. (c) Open file entry structs. (d) None of the above.
Page 5 of 33
11. Why would the kernel designer opt for a 2-level page table when a full 2-level page table takes up more memory than a full 1-level page table?
(a) 2-level tables can translate virtual addresses faster.
(b) 2-level tables can reference more memory than 1 level tables.
(c) Most of the time, a 2-level page table will take up less memory than a 1 level page table. (d) They wouldn’t. Adding more tables offers no advantages.
12. What section of memory holds the assembly for printf?
(b) Kernel memory (c) Shared libraries (d) Heap
13. Every thread has its own .
(b) Global values (c) Stack
(d) Text data
14. Why is gethostbyname not thread safe?
(a) Only one thread at a time can do a DNS lookup (b) It doesn’t have a mutex around it
(c) It returns a pointer to global shared memory (d) It shares instructions with other threads
15. If a page table on a 32-bit system is 2KB in size, how many entries does it contain?
(a) 2048 (b) 1024 (c) 512 (d) 256
Page 6 of 33
16. What is the function of the TLB?
(a) Caches data
(b) Caches instructions
(c) Caches translation of virtual addresses
(d) Translates physical addresses to virtual addresses
17. What is distinctive about superscalar processors?
(a) Can run at frequencies over 3.5GHz
(b) Can address over 4GB of memory
(c) Can perform more than one instruction per cycle (d) Can have more than 2 levels of cache
(e) Have more than one core per processor
18. True/False: When requested to send 20 bytes over a network socket, execution will block until all 20 bytes have been sent.
(a) True (b) False
19. True/False: When printf returns, the programmer cannot be guaranteed that the data has appeared on the user’s terminal.
(a) True (b) False
20. Which of the following tools would you first use to debug an application which is exiting with the error “Segmentation fault”?
(b) strace (c) strings (d) objdump
Page 7 of 33
21. Which of the following tools would you first use to debug a network application that never appears to accept any connections?
(b) strace (c) objdump (d) valgrind
22. Which of the following tools would you first use to debug an application which is exiting with a glibc error: double free detected?
(b) strace
(c) wireshark (d) valgrind
23. A 256-byte 4-way set associative cache with 16 byte blocks has
(a) 4 sets (b) 16 sets (c) 64 sets (d) No sets
24. Imagine a floating point format with no sign bit, one exponent bit, and one fraction bit. Which of the following is not a number?
(e) None of the above
Page 8 of 33
Problem 2. (14 points):
Stack discipline.
Consider the following C code and assembly code for two mutually recursive functions:
int even(unsigned int n)
return 1; }
return odd(n – 1);
int odd(unsigned int n)
return 0; }
return even(n – 1);
push %ebp
mov %esp,%ebp
sub $0x8,%esp
cmpl $0x0,0x8(%ebp)
jne 0x8048424
movl $0x0,-0x4(%ebp)
jmp 0x8048435
mov 0x8(%ebp),%eax
sub $0x1,%eax
mov %eax,(%esp)
call 0x80483e4
mov %eax,-0x4(%ebp)
mov -0x4(%ebp),%eax
0x080483e4
0x080483e5
0x080483e7
0x080483ea
0x080483ee
0x080483f0
0x080483f7
0x080483f9
0x080483fc
0x080483ff
0x08048402
0x08048407
0x0804840a
0x0804840d
0x0804840e
0x0804840f
0x08048410
0x08048412
0x08048415
0x08048419
0x0804841b
0x08048422
0x08048424
0x08048427
0x0804842a
0x0804842d
0x08048432
0x08048435
0x08048438
0x08048439
Imagine that a program makes the procedure call even(3). Also imagine that prior to the invocation, the value of %esp is 0xffff1000—that is, 0xffff1000 is the value of %esp immediately before the execution of the call instruction.
Page 9 of 33
push %ebp
mov %esp,%ebp
sub $0x8,%esp
cmpl $0x0,0x8(%ebp)
jne 0x80483f9
movl $0x1,-0x4(%ebp)
jmp 0x804840a
mov 0x8(%ebp),%eax
sub $0x1,%eax
mov %eax,(%esp)
call 0x804840f
mov %eax,-0x4(%ebp)
mov -0x4(%ebp),%eax
A. Note that the call even(3) will result in the following function invocations: even(3), odd(2), even(1), and odd(0). Using the provided code and your knowledge of IA32 stack discipline, fill in the stack diagram with the values that would be present immediately before the execution of the ret instruction for odd(0). Cross out each blank for which there is insufficient information to complete.
+——————————–+
| | 0xffff1004
+——————————–+
| | 0xffff1000
+——————————–+
| | 0xffff0ffc
+——————————–+
| | 0xffff0ff8
+——————————–+
| | 0xffff0ff4
+——————————–+
| | 0xffff0ff0
+——————————–+
| | 0xffff0fec
+——————————–+
| | 0xffff0fe8
+——————————–+
| | 0xffff0fe4
+——————————–+
| | 0xffff0fe0
+——————————–+
| | 0xffff0fdc
+——————————–+
| | 0xffff0fd8
+——————————–+
| | 0xffff0fd4
+——————————–+
| | 0xffff0fd0
+——————————–+
| | 0xffff0fcc
+——————————–+
| | 0xffff0fc8
+——————————–+
| | 0xffff0fc4
+——————————–+
| | 0xffff0fc0
+——————————–+
B. What are the values of %esp and %ebp immediately before the execution of the ret instruction for odd(0)?
Page 10 of 33
Problem 3. (20 points):
Assembly/C translation.
Consider the following C code and assembly code for a curiously-named function:
typedef struct node
void *data;
struct node *next;
0x4005d0: mov
0x4005d5: mov
0x4005da: xor
0x4005dc: mov
0x4005e1: sub
0x4005e5: test
%rbx,-0x18(%rsp)
%rbp,-0x10(%rsp)
%r12,-0x8(%rsp)
$0x18,%rsp
0x40061e
0x8(%rdi),%rdi
node_t *lmao(node_t *n, int f(node_t *)) 0x4005e8: mov
0x4005eb: mov
0x4005ee: je
0x4005f0: mov
0x4005f4: callq 0x4005d0
0x4005f9: mov %rbx,%rdi
0x4005fc: mov %rax,%r12
0x4005ff: callq *%rbp
0x400614: mov
0x400617: mov
0x40061b: mov
0x40061e: mov
0x400622: mov
0x400627: mov
0x40062c: add
0x400630: retq
(%rbx),%rdx
%r12,0x8(%rax)
%rdx,(%rax)
(%rsp),%rbx
0x8(%rsp),%rbp
0x10(%rsp),%r12
$0x18,%rsp
node_t *a, *b;
if(________________)
return NULL;
a = ________________;
if(________________)
b = ________________;
b->data = n->data;
b->next = ________________;
return ________________;
0x40061e
$0x10,%edi
Using your knowledge of C and assembly, fill in the blanks in the C code for lmao with the appropriate expressions. (Note: 0x400498 is the address of the C standard library function malloc.)
Page 11 of 33
0x400601: mov
0x400603: mov
0x400606: test
0x400608: jle
0x40060a: mov
0x40060f: callq 0x400498
Problem 4. (14 points):
Process control.
Consider the following C program:
int main() {
pid_t pid;
int status, counter = 4;
while(counter > 0)
pid = fork();
counter /= 2;
printf(“%d”, counter); /* (1) */
waitpid(-1, &status, 0);
counter += WEXITSTATUS(status);
waitpid(-1, &status, 0);
counter += WEXITSTATUS(status);
printf(“;%d”, counter); /* (2) */
return counter;
Page 12 of 33
Use the following assumptions to answer the questions:
• All processes run to completion, and no system calls fail.
• printf is atomic and calls fflush(stdout) after printing its argument(s) but before returning. For each question, there may be more blanks than necessary.
A. List every individual digit that can be emitted by a call to printf. Include any digits that can be printed along with the semicolon by the printf annotated with (2). For example, if 1521;3 were a possible output of the program, the solutions would include 1, 2, 3, and 5.
________ ________ ________ ________
________ ________ ________ ________
B. Notice that the printf annotated with (2) emits a semicolon in addition to a digit. List all of the digit sequences that can be printed before the semicolon is emitted. For example, if 1521;3 were a possible output of the program, 1521 would be one solution.
C. Now list all of the digit sequences that can be printed after the semicolon is emitted. ________ ________ ________ ________
________ ________ ________ ________
Page 13 of 33
Problem 5. (14 points):
Concurrency.
Consider the following implementation of reader writer locks. A reader writer lock is a concurrency mech- anism that allows either multiple readers to have access to a critical section or a single writer.
struct rwlock {
sem_t *sem; int readers; int writers;
void rwlock_init(struct rwlock *lock)
sem_init(&lock->sem, 1);
lock->readers = 0;
lock->writers = 0;
void readlock(struct rwlock *lock)
while(1) {
sem_wait(lock->sem);
if(lock->writers == 0) {
lock->readers++; break;
sem_post(lock->sem);
void writelock(struct rwlock *lock)
while(1) {
sem_wait(lock->sem);
if(lock->readers == 0 && lock->writers == 0) {
lock->writers = 1; break;
sem_post(lock->sem);
void unlock(struct rwlock *lock)
sem_wait(lock->sem);
if(lock->readers > 0)
lock->readers–;
lock->writers–;
sem_post(lock->sem);
Page 14 of 33
A. What is the problem with the above implementation?
B. Starvation is a problem where one thread, or kind of thread (think reader or writer), is unable to acquire a resource. After fixing the previous problem, is starvation possible? How?
Page 15 of 33
Problem 6. (10 points):
The following problems refer to a file called numbers.txt, with contents the ASCII string 0123456789.
You may assume calls to read() are atomic with respect to each other. The following file, read and print one.h, is compiled with each of the following code files.
#ifndef READ_AND_PRINT_ONE
#define READ_AND_PRINT_ONE
#include
#include
static inline void read_and_print_one(int fd) {
read(fd, &c, 1);
printf(“%c”, c); fflush(stdout);
A. Consider the following code:
#include “read_and_print_one.h”
#include
#include
int main() {
int file1 = open(“numbers.txt”, O_RDONLY);
int file2;
int file3 = open(“numbers.txt”, O_RDONLY);
file2 = dup2(file3, file2);
read_and_print_one(file1);
read_and_print_one(file2);
read_and_print_one(file3);
read_and_print_one(file2);
read_and_print_one(file1);
read_and_print_one(file3);
return 0; }
Page 16 of 33
List all possible outputs of the above code.
Page 17 of 33
B. Consider the following code:
#include “read_and_print_one.h”
#include
#include
#include
#include
int main() {
int file1;
int file2;
int file3;
file1 = open(“numbers.txt”, O_RDONLY);
file3 = open(“numbers.txt”, O_RDONLY);
file2 = dup2(file3, file2);
read_and_print_one(file1);
read_and_print_one(file2);
pid = fork();
if (!pid) {
read_and_print_one(file3);
close(file3);
file3 = open(“numbers.txt”, O_RDONLY);
read_and_print_one(file3);
wait(NULL);
read_and_print_one(file3);
read_and_print_one(file2);
read_and_print_one(file1);
read_and_print_one(file3);
return 0; }
List all possible outputs of the above code.
Page 18 of 33
Problem 7. (14 points):
Deadlocks and Dreadlocks
Two threads (X and Y) access shared variables A and B protected by mutex a and mutex b respectively. Assume all variable are declared and initialized correctly.
P(&mutex_a);
P(&mutex_b);
V(&mutex_b);
V(&mutex_a);
P(&mutex_b);
P(&mutex_a);
V(&mutex_a);
V(&mutex_b);
A. Show an execution of the threads resulting in a deadlock. Show the execution steps as follows
P(&mutex a) A+ = 10 P(&mutex b)
P(&mutex b) …
Page 19 of 33
B. There are different approaches to solve the deadlock problem. Modify the code above to show two approaches to prevent deadlocks. You can declare new mutex variables if required. Do not change the order or amount of the increments to A and B. Rather, change the locking behavior around them. The final values of A and B must still be guaranteed to be incremented by 60.
Page 20 of 33
Problem 8. (25 points):
Thread Safety
A fellow 213 student works on cutting edge research finding prime numbers. He wants to speed up his code by making it multi-threaded. He is running into some issues while implementing a thread safe version of the next prime function and asks for your help.
struct big_number *next_prime(struct big_number current_prime) {
static struct big_number next;
next = current_prime;
addOne(next);
while (isNotPrime(next)) {
addOne(next);
return &next;
struct big_number *ts_next_prime(struct big_number current_prime) {
return next_prime(current_prime);
A. Why is the function ts next prime thread-unsafe?
Page 21 of 33
B. Assume the mutex guarding the call to next prime is initialized correctly in the following code. struct big_number *ts_next_prime(struct big_number current_prime) {
struct big_number *value_ptr;
sem_wait(&mutex);
value_ptr = next_prime(current_prime);
sem_post(&mutex);
return value_ptr;
The following modification to the function is still not thread safe. Explain why, and show an example execution with two threads showing the problem?
Show the execution steps as follows
sem wait(&mutex)
value ptr = next prime(current prime)
sem wait(&mutex);
Thread 1 Thread 2
Page 22 of 33
C. Fill in the blanks below to fix ts next prime.
struct big_number *ts_next_prime(struct big_number current_prime) {
struct big_number *value_ptr;
struct big_number *ret_ptr = __________________________________;
sem_wait(&mutex);
value_ptr = next_prime(current_prime);
__________________________________;
sem_post(&mutex);
return ret_ptr;
Why does this fix work? :
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com