Andrew login ID: Full Name:
CS 15-213, Spring 2004 Final Exam
May 3, 2004
Instructions:
Copyright By PowCoder代写 加微信 powcoder
Make sure that your exam has 20 pages and is not missing any sheets, then write your full name and Andrew login ID on the front.
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 120 points.
The problems are of varying difficulty. The point value of each problem is indicated. Pile up the easy points quickly and then come back to the harder problems.
This exam is OPEN BOOK. You may use any books or notes you like. You may not use a calculator, laptop or any other electronic or wireless device. Good luck!
TOTAL (123):
Problem 1. (16 points):
This problem tests your understanding of how integers and floating point numbers are stored in memory. For Parts A-D, indicate what the output of the program would be, assuming that there are no errors during the compilation and execution of the program. Assume standard Linux alignment policies.
Consider the following C data structures.
struct point int x, y; ; struct MyStruct
int i; union
struct point p;
double e; ;
int funA(struct MyStruct *m)
m->u.p.x = 5;
m->u.p.y = 10;
int main()
struct MyStruct m;
memset( &m, 0, sizeof(struct MyStruct) ); funA(&m);
printf(“%d, %d n”, m.u.p.x, m.u.p.y);
Continued . . .
(Question 1 cont’d)
int funB(struct MyStruct m)
m.u.p.x = 5;
m.u.p.y = 10;
int main()
struct MyStruct m;
memset( &m, 0, sizeof(struct MyStruct) ); funB(m);
printf(“%d, %d n”, m.u.p.x, m.u.p.y);
int funC(struct MyStruct *m)
int *ptr = (int*)m;
ptr = ptr + 2;
*ptr = 10;
int main()
struct MyStruct m;
memset( &m, 0, sizeof(struct MyStruct) ); funC(&m);
printf(“%d, %d n”, m.u.p.x, m.u.p.y);
Continued . . .
(Question 1 cont’d)
int funD(struct MyStruct *m)
*(int*) &m->u.d = 5; *(int*) (&m->u.d + 1) = 10;
int main()
struct MyStruct m;
memset( &m, 0, sizeof(struct MyStruct) ); funD(&m);
printf(“%d, %d n”, m.u.p.x, m.u.p.y);
Part E: Recall that a float is a 32-bit floating point number. It is divided into a 23 bit frac field, an 8 bit exp field, and a single-bit sign field.
void main()
union hack /* struct that lets us XOR floats */
unsigned u;
max, temp; /* 2 hack unions */
float x = 1.0;
float y = 0.5;
do /* find the largest fp-number < 2.0 */
max.f = x;
while (x != max.f && x < 2.0);
/* Assume now that max.f stores largest fp-number < 2.0 */
temp.f = 1.0;
temp.u = temp.u ˆ max.u;
At the end of this program,
how many bits in temp.u are set to 1? .
Problem 2. (15 points):
This problem tests your understanding of Unix system I/O.
Part 1 (10 pts):
Examine the following C code, and answer the questions below. You may assume that there are neither compilation nor execution errors.
1: int main(int argc, char * argv[]) 2: {
int fd1, fd2, fd3;
fd1 = open("foo", O_RDONLY);
if (fork() == 0) {
fd2 = open("foo", O_RDONLY);
read(fd2, &c, 1);
}else{ wait(NULL);
fd3 = open("bar", O_RDONLY);
dup2(fd3, fd1);
Continued . . .
(Question 2 cont’d)
descriptor table open file table
v−node table
File access
[foo].pos [foo].refcnt
The figure above represents some of the kernel data structures used to manage files. We use to denote file ’s descriptor table entry, which points to file ’s open file table. For example, in the above figure, denotes descriptor table entry created in line 6 by the program on the previous page, which points to file
’s open file table. Correspondingly, and denote the “File pos” and “refcnt” entry in its open file table.
Using the notation described in the previous paragraph and the program on the previous page, please com- plete the following tables. When filling out a row, indicate the state of the system immediately after the line indicated has executed. Ignore table entries marked with a “——-”.
Parent process:
Child process:
6 of 20 Continued . . .
(Question 2 cont’d)
Part 2 (5 pts):
This problem is concerned with a simple client-server application. The server is called dump. It waits for a client connection request on port 3304, and then outputs to stdout every character that it receives from the client. The client is called msger. Its source code is listed below. The header files and the variable declarations are omitted in this source, but you can assume that the code compiles and runs without any errors.
int main(int argc, char * argv[]) {
/* the variable declarations are omitted here */ sock = socket(AF_INET, SOCK_STREAM, 0);
client.sin_addr.s_addr = htonl(INADDR_ANY); client.sin_family = AF_INET; client.sin_port = 0;
server.sin_addr.s_addr = inet_addr("192.168.0.1"); server.sin_family = AF_INET;
server.sin_port = htons(3304);
connect(sock, (struct sockaddr *)&server, sizeof(server));
if (fork() == 0) { dup2(STDOUT_FILENO, sock);
strcpy(msg_buf, "hello world\n"); rio_writen(sock, msg_buf, strlen(msg_buf)); close(sock);
A. This client uses rio writen(), what is the main reason for using rio writen() instead of the standard unix system call write()? Limit your answer to no more than one sentence.
B. Suppose dump is running on a computer with IP address ”192.168.0.1”. You launch msger on a com- puter with IP address ”192.168.0.2”, please fill in the following table with the output on stdout from both computers. Write ”Nothing” if there is no output.
192.168.0.1
192.168.0.2
Problem 3. (10 points):
Consider the source code below, where M and N are constants declared with #define. int array1[M][N];
int array2[N][M];
void copy(int i, int j) {
array1[i][j] = array2[j][i];
Suppose the above code generates the following assembly code:
push %ebp
mov %esp,%ebp
mov 0xc(%ebp),%edx
push %ebx
lea (%edx,%edx,2),%eax
mov 0x8(%ebp),%ebx
lea 0x0(,%ebx,8),%ecx
lea (%edx,%eax,4),%eax
sub %ebx,%ecx
add %ebx,%eax
mov array2(,%eax,4),%eax
add %edx,%ecx
mov %eax,array1(,%ecx,4)
mov (%esp,1),%ebx
pop %ebx
What are the values of M and N? M=
Problem 4. (9 points):
This problem tests your understanding of exceptional control flow.
Consider the following program. You may assume that printf is unbuffered and executes atomically. The program /bin/echo prints its command line argument to stdout.
1 2 3 4 5 6 7 8 9
sigset_t s1;
static int count = 0;
char *argv[] = {"/bin/echo", "Hello", NULL};
pid_t pid;
void handler () {
printf ("Bye\n");
int main () { inti=0;
signal (SIGCHLD, handler);
sigemptyset (&s1);
sigaddset (&s1, SIGCHLD);
sigprocmask (SIG_BLOCK, &s1, NULL);
for(i=0;i<3;i++){ if (fork() == 0) {
execve ("/bin/echo", argv, NULL); }
wait(NULL);
sigprocmask (SIG_UNBLOCK, &s1, NULL); }
Continued . . .
(Question 4 cont’d)
1. What are the possible outputs of the program?
2. When the program reaches line 31, what are the possible values that count may have?
3. Consider the same code, without blocking SIGCHLD, i.e. with lines 20, and 30 removed. Would the output be similar? If you answered no, list one possible output.
Problem 5. (12 points):
The code samples below are designed to test your understanding of multithreading, semaphores, and the effects of multiple threads modifying the same data. For each section, you will be asked to specify how many different outputs the given code can have. Since there may be many possible outputs, you will not be asked to provide the outputs themselves. You may assume, for the purposes of this problem, that printf executes atomically.
sem_t sem;
int main() {
pthread_t tids[3]; sem_init(&sem, 0, 1); for (j=0; j<3; j++) {
pthread_create(&tids[j], NULL, doit, NULL); }
for (j=0; j<3; j++) { pthread_join(&tids[j], NULL);
return 0; }
This is the main function for all three problems below. The only differences in the problems are the details of the thread function, doit listed on the next page.
11 of 20 Continued . . .
(Question 5 cont’d)
int i = 0;
void *doit(void *arg) {
i = i + 1; printf("%d\n", i); V(&sem);
How many different outputs are possible on executing the code above?
int i = 0;
void *doit(void *arg) {
i = i + 1; V(&sem); printf("%d\n", i);
How many different outputs are possible on executing the code above?
int i = 0;
void *doit(void *arg) {
i = i + 1;
printf("%d\n", i); }
When the above code runs, at least one of the four outputs listed below are not possible.
(a) 3 (b)3 (c)1 (d) 1 2331 1311
List the letters identifying the illegal outputs here:
Problem 6. (18 points):
When attempting to debug a program, it is often helpful to look at the stack to determine what functions have been called and with what arguments. This is called a backtrace and can be performed in gdb with the bt command. Your task for this section of the exam is to harness your knowledge of the x86 calling conventions, combined with your understanding of different data representations to perform a manual backtrace. To facilitate this, we have provided you with the contents of the stack in hexadecimal format. We have also provided you with a table mapping certain addresses to strings. Additionally, we have given you the address ranges for the machine code of the various functions. Finally, when the bt is executed you are inside the bar() function and the value of ebp is 0xbffff988.
Your backtrace should terminate at the main() function (and should also include any arguments to main!). You may assume that all arrays of strings are terminated with a NULL pointer.
When providing your answers, please specify the name of the argument and use the following conventions:
characters should be written in single quotes (e.g. character=’c’).
integers should be written in decimal format (e.g. integer=23).
strings should be in double quotes (e.g. string=“This is a string”).
string arrays should be written in square brackets and be comma delimited (e.g. array=[“This”, “is”, “an”, “array”, (NULL)])
pointers should be written as hexadecimal numbers (e.g. pointer=0xbffffa84) For example: main(argc=2, argv=[“/bin/foo”, “Word”, (NULL)])
13 of 20 Continued . . .
The stack is as follows:
Address Data
0xbffff988: 0xbffff9b8
0xbffff98c: 0x08048401
0xbffff990: 0xbffffb28
0xbffff994: 0xdeadbeef
0xbffff998: 0xbffff9a8
0xbffff99c: 0x4002c4ed
0xbffff9a0: 0x00000000
0xbffff9a4: 0x0804833a
0xbffff9a8: 0x000000a0
0xbffff9ac: 0x080483e9
0xbffff9b0: 0xbffff9d0
0xbffff9b4: 0x00000000
0xbffff9b8: 0xbffff9d8
0xbffff9bc: 0x08048378
0xbffff9c0: 0x0000000f
0xbffff9c4: 0x0000002d
0xbffff9c8: 0x000000d5
0xbffff9cc: 0x080483e9
0xbffff9d0: 0xbffff9d0
0xbffff9d4: 0x00000000
0xbffff9d8: 0xbffff9f8
0xbffff9dc: 0x4002c4ed
0xbffff9e0: 0x00000002
0xbffff9e4: 0xbffffa2c
0xbffff9e8: 0x00000004
0xbffff9ec: 0x080483e9
0xbffff9f0: 0xbffff9d0
0xbffff9f4: 0x00000000
0xbffff9f8: 0xbffffa48
0xbffff9fc: 0x00000002
0xbffffa00: 0x75656869
0xbffffa04: 0x4002c3ac
0xbffffa08: 0xbffffb08
0xbffffa0c: 0xbffffb28
0xbffffa10: 0x00000000
0xbffffa14: 0xbffffb38
0xbffffa18: 0x00000000
0xbffffa1c: 0x080483e9
0xbffffa20: 0xbffff9d0
0xbffffa24: 0x00000002
0xbffffa28: 0x00000000
0xbffffa2c: 0xbffffb08
0xbffffa30: 0xbffffb88
0xbffffa34: 0x00000000
0xbffffa38: 0x000d5213
0xbffffa3c: 0x080483e9
0xbffffa40: 0xbffff9d0
0xbffffa44: 0x0000003b
The following table lists a few selected characters and their associated ASCII values.
Continued . . .
(Question 6 cont’d)
The following table lists the addresses at which certain strings are found in the executable.
0xbffffb08
“/bin/foo”
0xbffffb28
0xbffffb48
0xbffffb68
0xbffffb88
0xbffffba8
0xbffffbc8
0xbffffbe8
The following table lists the addresses at which certain functions begin in the executable. You should assume that each function immediately follows the function listed above it in the executable.
0x0804835c
int main(int argc, char *argv[]);
0x08048388
int foo(void *addr);
0x08048392
void fancy(int i, char *str);
0x08048398
int hammer(int a, char c, int i);
0x08048404
char bar(char *str, double *dp);
0x0804840e
double chouse(int i);
Please fill in the following fields as per the guidelines given above. Note that you might not need all of the space provided.
Problem 7. (9 points):
This problem deals with dynamic memory allocators.
Part A: Suppose that you have been asked to implement a dynamic memory allocator for a real-time system with strict bounds on the amount of time for an operation (a malloc, a free, etc). In order to combat false fragmentation, you have decided to use some sort of coalescing. Which type of coalescing (immediate or deferred) should you use, and why? Use at most two sentences for your answer.
Part B: Assume a minimum block size of 32 bytes for this part of the problem. Do implicit free lists or explicit free lists use more memory. That is, will one of these strategies necessarily use more space than the other, assuming that everything else in the allocators are identical, and why? Use at most two sentences for your answer.
Part C: Assume you are designing a special purpose dynamic memory allocator. One of the interesting properties of this system is that only 8 different sizes, all of which you know in advance and all of which are small relative to the page size of the system, will be requested by the user (though there are no guarantees how many times each of these will be requested). What are the most important ways in which your design for this allocator would differ from your design of a general purpose allocator? Use at most 2 sentences for your answer.
Problem 8. (24 points):
You are working for a company that is developing a new processor and the compiler team is way behind schedule. In order to sell your product you need to show high performance on certain kernels important to your potential users. You have been asked to optimize the following kernel. You can’t use assembly because the ISA of the processor may change.
You can assume that N and M are large and that M is always even. The processor will have a cache, it won’t be large compared to N*M. a, b, and e are all 2-D NxM arrays. e may have values other than 0 in it before the call to kernel.
kernel(int N, int M, int* a, int *b, int *e) {
int i,j,k;
for (i=0; i