CS代考 SIZE 512

electronic devices are allowed.
Virtual Memory System-Level IO Cache Memories
Signals Assembly Network Programming Floating Point Dynamic Memory 1 Dynamic Memory 2 Stack 1 Stack 2 Multithreading
1 (20): 2 (15): 3 (20): 4 (15): 5 (15): 6 (10): 7 (15): 8 (10): 9 (10):

Copyright By PowCoder代写 加微信 powcoder

10 (20): 11 (30): 12 (20):
TOTAL (200):
Andrew login ID (please print in capital letters):
Full Name: Recitation Section:
15-213/18-243, Spring 2009 Final Exam
Tuesday, May 12, 2009
Instructions:
• 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 200 points.
• This exam is OPEN BOOK. You may use any books or notes you like. No calculators or other
Page 1 of 34

Problem 1. (20 points):
VM On a Boat
In this question you will perform a virtual to physical address translation for a hypothetical virtual memory architecture.
The specifications for the system are as follows:
• Virtual addresses are 16 bits in length
• The page size is 64 bytes
• The system operates on a two level page table structure, which is organized as follows:
– The page directory has 16 entries, each of which is 2 bytes in length – Each page table has 64 entries, each of which is 2 bytes in length
• Each page directory entry encodes the address of the page table in its upper bits, and the lowermost bit is a valid bit, where P = 1 indicates that the page table is present.
• Each page table entry encodes the physical page number in its upper bits, and the lowermost bit is a valid bit, where P = 1 indicates that the page frame is present.
Below is a memory dump of various regions of memory. The left column of each table stores the address, and the right column stores the value at that address.
Address Value Address
0x0200 0x1401 0x0206 0x1481 0x020c 0x1501 0x0212 0x1581 0x0224 0x1600 0x0228 0x1681 0x022c 0x1700 0x0230 0x1781 0x1408 0x3201 0x1410 0x3301 0x1420 0x3400 0x1440 0x3501 0x1480 0x3600 0x1488 0x3701 0x1490 0x3800 0x14a0 0x3901 0x14c0 0x3a01 0x1500 0x3b01 0x1508 0x3c00 0x1510 0x3d01 0x1520 0x3e01 0x1540 0x3f01 0x1580 0x4001
Page 2 of 34

Process 1 is trying to read at virtual address 0x683B. The page directory base register for this process stores the value 0x0200. Answer the following questions. Use the space below for your calculations and working. To facilitate the awarding of partial credit, please note down any memory addresses looked up, and the values they contained.
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
1. What is the address of the page directory entry?
2. What is stored in the page directory entry?
3. What is the address of the page table entry? OR The page table is not present (circle if true)
4. What is the physical address accessed? OR There was a page fault (circle if true)
Page 3 of 34

Process 2 is trying to write to virtual address 0x44A3. The page directory base register for this process stores the value 0x0220. Answer the following questions. Use the space below for your calculations and working. To facilitate the awarding of partial credit, please note down any memory addresses looked up, and the values they contained.
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
1. What is the address of the page directory entry?
2. What is stored in the page directory entry?
3. What is the address of the page table entry? OR The page table is not present (circle if true)
4. What is the physical address accessed? OR There was a page fault (circle if true)
Page 4 of 34

Problem 2. (15 points):
File Descriptor the file ./file1.txt has the following contents:
And we have the following C files compiled to ./program1 and ./program2, respectively.
#include
#include
int main() {
int pid, fd_x, fd_y, fd_z;
char buf[8];
fd_x = open(“file1.txt”, O_RDWR);
fd_y = open(“file1.txt”, O_RDWR);
fd_z = open(“file1.txt”, O_RDWR);
read(fd_x, buf, 2);
read(fd_y, buf+2, 4);
if ((pid = fork()) == 0) {
dup2(fd_x, STDOUT_FILENO);
dup2(fd_y, STDIN_FILENO);
execl(“program2”, “program2”, NULL);
wait(NULL);
read(fd_y, buf+6, 2);
write(fd_z, buf+6, 2);
write(fd_x, buf+4, 2);
write(fd_x, buf+2, 2);
close(fd_x);
close(fd_y);
close(fd_z);
Program1 */
Page 5 of 34

Program2 */
#include
#include
int main() {
char buf[2];
read(STDIN_FILENO, buf, 2);
write(STDOUT_FILENO, buf, 2);
What is the contents of file1.txt after ./program1 executes? Assume that reads and writes are not cached.
Page 6 of 34

Problem 3. (20 points):
We consider a 128 byte data cache that is 2-way associative and can hold 4 doubles in every cache line. A double is assumed to require 8 bytes.
For the below code we assume a cold cache. Further, we consider an array A of 32 doubles that is cache- aligned (that is, A[0] is loaded into the first slot of a cache line in the first set). All other variables are heldinregisters.Thecodeisparameterizedbypositiveintegersmandnthatsatisfym*n = 32(i.e.,ifyou know one you know the other).
Recall that miss rate is defined as #misses . #accesses
float A[32], t = 0;
for(int i = 0; i < m; i++) for(int j = 0; j < n; j++) t += A[j*m + i]; Answer the following: 1. How many doubles can the cache hold? 2. How many sets does the cache have? 3. Form = 1: (a) Determine the miss rate. (b) What kind of misses occur? (c) Does the code have temporal locality with respect to accesses of A and this cache? Page 7 of 34 4. Form = 2: (a) Determine the miss rate. (b) What kind of misses occur? 5. Form = 16: (a) Determine the miss rate. (b) What kind of misses occur? (c) Does the code have spatial locality with respect to accesses of A and this cache? Page 8 of 34 Problem 4. (15 points): You may have taken 15-251 and learned that there is no oracle for the halting set, meaning it’s impossible to write a program that will determine if an other arbitrary program will halt for a given input. A 213 TA, Punter Hitelka, is determined to disprove this using a program called autolab that makes students do such determinations for credit. Congrats, you are the guinea pig! For this problem, you must determine if the following code halts or not, then tell us why. By halt, we mean that the parent process eventually exits. You do not need to tell us if any child processes are maintained as zombies. Write your answer in the blank space below each of the three code blocks. When grading this problem, we will only read the first 30 words of each response, so keep your answers clear and concise! 1. Does this program terminate? Justify. void main() { int *x = malloc(sizeof(int)); int cpid = fork(); if(cpid == 0) { return 0; } Page 9 of 34 2. Does this program terminate? Justify. void handler(int signum) exit(1); } void main() { sigset_t s; sigaddset(&s, SIGUSR1); sigprocmask(SIG_BLOCK, &s, NULL); signal(SIGUSR1, handler); if((cpid = fork()) == 0) printf("I’m a child"); continue; } sigprocmask(SIG_UNBLOCK, &s, NULL); printf("I’m on a boat!"); kill(cpid, SIGUSR1); waitpid(cpid, NULL, 0); Page 10 of 34 3. Does this program terminate? Justify. void sig_kill_handler(int signum) printf("I’m not gonnaaa stooppppp\n"); continue; } void main() { signal(SIGKILL, sig_kill_handler); if((cpid = fork()) == 0) printf("Looping Forever\n"); while(1) continue; kill(cpid, SIGKILL); waitpid(cpid, NULL, 0); Page 11 of 34 Problem 5. (15 points): Following is a series of three C snippets with associated disassemblies. Each snippet contains one or zero errors. If there is an error, circle it and provide a brief explanation of why it is wrong in the space below the code. If there is no error, state that there is no error. Note that the error (if one exists) is in the C → assembly translation, not in the logic or behavior of the C code. Please write your answers only on this page. int squareNumber(int x) { return (x * x); 08048344 :
int fourth(char *str) {
return str[3];
int unrandomNumber() {
0804835e :
804835e: 55
804835f: 89 e5
push %ebp
mov %esp,%ebp
mov 0x4,%eax
pop %ebp
8048361: a1
8048366: 5d
8048367: c3
c3 ret
push %ebp
mov %esp,%ebp
mov 0x4(%ebp),%eax
imul %eax,%eax
pop %ebp
0804834f :
804834f: 55
8048350: 89 e5
8048352: 8b 45 08
8048355: 83 c0 03
8048358: 0f be 00
804835b: 5d
804835c: c9 leave
804835d: c3 ret
push %ebp
mov %esp,%ebp
mov 0x8(%ebp),%eax
add $0x3,%eax
movsbl (%eax),%eax
pop %ebp
Page 12 of 34

Problem 6. (10 points):
Crummy Networks
Error Handling
Below is some code for a concurrent echo server. We have left out the error handling code for the three functions socket, send, and recv. These blanks are marked with
/**** WRITE CODE BELOW *******/

/***** WRITE CODE ABOVE *****/
Please fill in those blanks with appropiate error handling code. Do not print out any messages, just modify the control flow.
Page 13 of 34

#include
#include #include
#include
#include
#include
#include
#include
#include
#define BUFF_SIZE 512
#define SERVER_PORT 15213
char buffer[BUFF_SIZE];
void * handleConnection(void *);
int main(){
int server_sock;
struct sockaddr_in serverAddr, clientAddr;
pthread_t tid;
/*ignore the SIGPIPE signal*/
signal(SIGPIPE,SIG_IGN);
/*open server_socket */
if((server_sock = socket(AF_INET,SOCK_STREAM,IPPROTO_TCP))<0){ /**** WRITE CODE BELOW *******/ /***** WRITE CODE ABOVE *****/ serverAddr.sin_addr.s_addr = htonl(INADDR_ANY); serverAddr.sin_port = htons(SERVER_PORT); serverAddr.sin_family = AF_INET; if(bind(server_sock,(struct sockaddr *)&serverAddr, sizeof(struct sockaddr)<0)){ /*handle bind failing*/ Page 14 of 34 if(listen(server_sock,15)<0){ /*handle listen failing*/ } while(1){ int client_socket; size_t clientLen = sizeof(struct sockaddr); if((client_socket = accept(server_sock,(struct sockaddr *)&clientAddr, &clientLen))<0){ /*handle failing of accept*/ pthread_create(&tid,NULL,handleConnection,(void *) client_socket); /*handle data on this socket*/ void * handleConnection(void * sock){ int socket = (int) sock; int recvSize; pthread_detach(pthread_self()); if((recvSize = recv(socket,buffer,BUFF_SIZE,0))<0){ /***** WRITE CODE BELOW*******/ /***** WRITE CODE ABOVE ******/ if(send(socket,buffer,recvSize,0)<0){ /***** WRITE CODE BELOW *******/ /****** WRITE CODE ABOVE *****/ }while(recvSize >0);
/*once the code reaches this point, we have received 0 bytes from the recv
close(socket);
pthread_exit(NULL);
Page 15 of 34

Network Bugs
Assuming all system calls succeed (and therefore the error handling code you wrote in part A is never executed), please locate the 2 logic bugs in this code and describe them. (A logic bug is one where the pro- grammer misunderstood the way in which their program will execute and will produce unwanted behavior under certain input conditions).
Page 16 of 34

Problem 7. (15 points):
You’ve been asked to design the floating-point unit for . Bovik’s new microprocessor. Harry is sure that he wants to use the IEEE standard for floating-point numbers, but he isn’t sure of some of the other design parameters. He has some questions for you:
If floats are represented with 12 bits, with 1 bit for the sign, 6 for the exponent, and 5 for the fraction: 1. What is the largest non-infinite number representable?
2. What is the smallest positive number representable?
3. What does the number 255 round to using this format?
Harry is concerned about precision in his system. He’d like to be able to represent positive integers up to 255 without having to round.
What is the least number of fraction bits and the least number of exponent bits to make this possible? (Note that the total number of bits may change)
4. Number of Fraction Bits:
5. Number of Exponent Bits:
Page 17 of 34

Harry decided to extend his floating point format by one bit.
First he wonders about the effect on the range (defined as the difference between the smallest and largest representable finite number). Which of the following is true?
6. The range will be increased
(a) By adding the bit to the fraction bits (b) By adding the bit to the exponent bits (c) By both
(d) By neither
Next he worries about the rounding error. Which of the following is true?
7. The rounding error for all numbers remains unchanged or is reduced
(a) By adding the bit to the fraction bits (b) By adding the bit to the exponent bits (c) By both
(d) By neither
Page 18 of 34

Problem 8. (10 points):
The Curse of Abalienation!!
For this question, we will be looking at the 32-bit libc implementation of malloc.
• The libc implementation uses an 8 byte alignment of the payload areas. • The libc implementation uses the following layout for free blocks:
header prev next payload footer (4 bytes) (4 bytes) (4 bytes) (arbitrary size) (4 bytes)
Whereprev, nextandfooterarestoredinsidethespaceforthepayload. • The libc implementation uses the following layout for allocated blocks:
header payload
(4 bytes) (arbitrary size)
Your friend, . Bovik, is taking 15-123, where one of the assignments is to write a linked list imple- mentation of a dictionary. Harry is experiencing a strange bug where his dictionary works on everything except for 12 letter words, on which it generates a Segmentation Fault. After some debugging you find that it also doesn’t work on words of size 20 and 28 (you don’t test any further).
Here is Harry’s addWordDict method:
int addWordDict(dictionary * dict, char * word){
int result;
char * wordCopy;
if (dict == NULL){
return ERR_NULL_DICT;
if(word == NULL){
return WARN_INVALID_ARGUMENT;
/*add the word */
/*We’re going to make a copy of the word because the word buffer
gets reused. This wordCopy will get free’d when we remove
the word from the dictionary. */
wordCopy = (char *)malloc((strlen(word)) * sizeof(char));
strcpy(wordCopy,word);
result = addItemLL(((dict)->wordList),(void *) wordCopy);
dict->count = ((dict)->wordList)->count; /*update the count */
return result;
Page 19 of 34

1. What is wrong with Harry’s addWordDict method?
2. Why does this code work on words of sizes other than 12, 20, 28… but not on these sizes? (Be as detailed as possible)
Page 20 of 34

Problem 9. (10 points):
. Bovik is working on some code and needs your help. He is writing a malloc package with the intent that it should compile and run correctly on both x86 and x86-64 machines, but to keep things simple he’s never allowing the heap to grow larger than 4GB, so he can use 4 byte headers. He’s using the block layout shown below, which should look familiar to you.
+—————————————————————-+
| header (4 bytes) | payload (varies) | footer (4 bytes) |
+—————————————————————-+
When Harry gets to his free implementation, he decides to write a macro to abstract the pointer arithmetic details out of his code. The first thing he needs to do is determine a block’s size given a pointer to the payload of that block, to be used like so:
void free(void *p) {
int size = HEADER(p) & ̃0x7;
Fill in the blanks in the table below, indicating with “Yes” or “No” whether each macro will perform cor- rectly on either x86 or x86-64.
#define HEADER(p) (*(long *)((char **)(p) – 1))
#define HEADER(p) (*(char *)((char *)(p) – 4))
#define HEADER(p) (*(int *)((char *)(p) – 2))
#define HEADER(p) (*(long *)((char *)(p) – 2))
#define HEADER(p) (*(char *)((long *)(p) – 2))
#define HEADER(p) (*(int *)((long *)(p) – 1))
#define HEADER(p) (*(char *)((int *)(p) – 1))
#define HEADER(p) (*(long *)((long *)(p) – 2))
#define HEADER(p) (*(int *)((int *)(p) – 1))
x86 x86-64 __________ __________ __________ __________ __________ __________ __________ __________ __________ __________ __________ __________ __________ __________ __________ __________ __________ __________
Page 21 of 34

Problem 10. (20 points):
Consider the following C program running on a 32-bit machine.
int fact (int n) {
if (n == 1)
return n * fact(n – 1);
int main (void) {
int a = fact(2);
The assembly dump of the two functions is printed below.
8048344 :
804836c