Andrew login ID (Use block letters): Full Name (Use block letters):
15-213 (18-243), Fall 2010 Final Exam
Friday, December 10. 2010
Instructions:
Copyright By PowCoder代写 加微信 powcoder
• Make sure that your exam is not missing any sheets, then write your Andrew login ID and full name on the front. Please write using clear block letters!
• This exam is closed book, closed notes, although you may use two 8 1/2 x 11 sheets of paper with your own notes. You may not use any electronic devices.
• The exam has a maximum score of 98 points.
• The problems are of varying difficulty. The point value of each problem is indicated. Good luck!
TOTAL (98):
Page 1 of 22
Problem 1. (20 points):
Short answer and multiple choice questions on a variety of stimulating and refreshing topics.
1. Label the following networking system calls 1,2,3,4 or 5, in the order they should be called. [2 pts] (label with an X if the call is not used; a blank will receive no credit)
Client Server listen ____ ____ connect ____ ____ accept ____ ____ socket ____ ____ bind ____ ____
The remaining questions are multiple choice. Write the correct answer for each question in the fol- lowing table:
2. Which of the following is NOT a universal property of reader-writer locks?
(a) Readers can only look at a shared item; writers can also modify it.
(b) If a writer has access to the item, then no other thread also has access.
(c) Any number of readers can read the item at the same time.
(d) A writer waiting for an RW lock will get preference over subsequent read requests.
3. Starvation (in relation to threads) refers to:
(a) A thread waiting for a lock indefinitely.
(b) A semaphore that gets locked but the thread never unlocks it after use.
(c) A thread is spawned but never joins the main thread when finished.
(d) A process fails to spawn a new thread because it’s hit the maximum number of threads allowed.
4. How does x86 assembly store the return value when a function is finished?
(a) The ret instruction stores it in a special retval register.
(b) By convention, it is always in %eax.
(c) It is stored on the stack just above the (%ebp) of the callee.
(d) It is stored on the stack just above all the arguments to the function.
Page 2 of 22
5. In IEEE floating point, what would be an effect of allocating more bits to the exponent part by taking them from the fraction part?
(a) You could represent fewer numbers, but they could be much larger.
(b) You could represent the same numbers, but with more decimal places.
(c) You could represent both larger and smaller numbers, but with less precision. (d) Some previously representable numbers would now round to infinity
6. Consider the following two blocks of code, found in separate files:
/* main.c */
int main() {{
foo(); printf(‘‘%d’’, i);
return 0; } }
What will happen when you attempt to compile, link, and run this code?
(a) It will fail to compile.
(b) It will fail to link.
(c) It will raise a segmentation fault. (d) It will print “0”.
(e) It will print “1”.
(f) It will sometimes print “0” and sometimes print “1”.
7. Which of the following is an example of external fragmentation?
(a) A malloc’ed block needs to be padded for alignment purposes.
(b) A user writes data to a part of the heap that isn’t the payload of a malloc’ed block. (c) There are many disjoint free blocks in the heap.
(d) A user malloc’s some heap space and never frees it.
8. Which of the following is NOT the default action for any signal?
(a) The process terminates all of its children.
(b) The process terminates and dumps core.
(c) The process terminates.
(d) The process stops until restarted by a SIGCONT signal.
/* foo.c */
void foo()
Page 3 of 22
9. Which of the following is FALSE concerning x86-64 architecture?
(a) Adoubleis64bitslong.
(b) Registers are 64 bits long.
(c) Pointers are 64 bits long.
(d) Pointers point to locations in memory that are multiples of 64 bits apart.
10. Consider the following block of code:
int main() {
int a[213];
//int j = 15;
for(i = 0; i < 213; i++) a[i] = i;
a[0] = -1; }
Which of the following instances of ’bad style’ is present?
(a) Dead code.
(b) Magic numbers. (c) Poor indentation. (d) All of the above.
Page 4 of 22
11. Consider the following structure declarations on a 64-bit Linux machine.
struct RECORD { long value2;
double value;
char tag[3];
struct NODE {
int ref_count;
struct RECORD record; union {
double big_number;
char string[12];
Also, a global variable named my node is declared as follows:
struct NODE my_node;
If the address of my node is 0x6008e0, what is the value of &my node.record.tag[1] ?
(a) 0x6008f8 (b) 0x6008fa (c) 0x6008f9 (d) 0x6008f5 (e) 0x6008f1
12. With reference to the previous question, what is the size of my node in bytes ?
(a) 48 (b) 44 (c) 40 (d) 42 (e) 50
13. Which of the following x86 instructions can be used to add two registers and store the result without overwriting either of the original registers?
(d) None of the above
Page 5 of 22
14. Which of these uses of caching is not crucial to program performance?
(a) Caching portions of physical memory (b) Caching virtual address translations (c) Caching virtual addresses
(d) Caching virtual memory pages
(e) None of the above (that is, they are all crucial)
15. Assuming all the system calls succeed, which of the following pieces of code will print the word
”Hello” to stdout?
(a) int fd = open("hoola.txt", O_RDWR); dup2(fd, STDOUT_FILENO); printf("Hello");
fflush(stdout);
(b) int fd = open("hoola.txt", O_RDWR); dup2(fd, STDOUT_FILENO); write(STDOUT_FILENO, "Hello", 5);
(c) int fd = open("hoola.txt", O_RDWR); dup2(fd, STDOUT_FILENO); printf("Hello");
(d) int fd = open("hoola.txt", O_RDWR); dup2(STDOUT_FILENO, fd);
write(fd, "Hello", 5);
(e) int fd = open("hoola.txt", O_RDWR); dup2(fd, STDOUT_FILENO);
write(fd, "Hello", 5);
16. Consider the following piece of code. Note that the file name is the same for both calls to open, and assume the file one.txt exists.
int fd = open("one.txt", O_RDWR); int fd2 = open("one.txt", O_RDONLY);
Which of the following statement is true?
(a) fd and fd2 will share the same file offset
(b) fd2 will be invalid because you cannot have two open file descriptors referring to the same file at the same time.
(c) Both fd and fd2 will have an initial file offset that is set to the end of the file
(d) Whatever is written to the file through fd, can be read using fd2
(e) In total, there will be two copies of the file one.txt in memory, one associated with fd and the other with fd2. Any changes made in a copy will not be reflected in the other copy.
Page 6 of 22
17. In malloclab, we provided code for an implicit list allocator (the naive implementation). Many stu- dents improved this code by creating an explicit linked list of free blocks. Which of the following reason(s) explain(s) why an explicit linked list implementation has better performance?
I. Immediate coalescing when freeing a block is significantly faster for an explicit list
II. The implicit list had to include every block in the heap, whereas the explicit list could just include the free blocks, making it faster to find a suitable free block.
III. Inserting a free block into an explicit linked list is significantly faster since the free block can just be inserted at the front of the list, which takes constant time.
(a) I only.
(b) II only.
(c) III only.
(d) II and III only.
(e) All I, II and III.
18. Supposealocalvariableintmyintisdeclaredinafunctionnamedfunc.Whichofthefollowing is considered safe in C?
(a) func returns &my int and the caller dereferences the returned pointer.
(b) func returns &my int and the caller prints the returned pointer to the screen
(c) func sets the value of a global variable to &my int and returns. The global variable is un- changed up to the point another function dereferences the global variable.
(d) None of the above
19. If a parent forks a child process, to which resources might they need to synchronize their access to prevent any unexpected behavior?
(a) malloc’ed memory (b) stack memory
(c) global variables (d) file descriptors
(e) None of the above
Page 7 of 22
Problem 2. (10 points):
Floating point encoding. In this problem, you will work with floating point numbers based on the IEEE floating point format. We consider two different formats:
Format A: 8-bit floating point numbers:
• There is one sign bit s. s = 1 indicates negative numbers. • Therearek=4exponentbits.Thebiasis2k−1−1=7. • There are n = 3 fraction bits.
Format B: 9-bit floating point numbers:
• There is one sign bit s. s = 1 indicates negative numbers.
• Therearek=4exponentbits.Thebiasis2k−1−1=7.
• There are n = 4 fraction bits.
1. How would you represent positive infinity using format A? Binary representation for positive infinity: _____________
2. How would you represent √−100 using format B?
Give an example binary representation: _____________
3. For formats A and B, please write down the binary representation and the corresponding values for the following (use round-to-even):
Description
Format A binary
Format A value
Format B binary
Format B value
0 0000 000
0 0000 0000
Largest normalized value
Smallest positive number
Negative one
Page 8 of 22
Problem 3. (6 points):
Accessing arrays. Consider the C code below, where H and J are constants declared with #define. int array1[H][J];
int array2[J][H];
void copy_array(int x, int y) { array2[y][x] = array1[x][y];
Suppose the above C code generates the following x86-64 assembly code:
# On entry: # %edi=x # %esi=y # copy_array:
movslq %esi,%rsi
movslq %edi,%rdi
leaq (%rsi,%rsi,8), %rdx addq %rdi, %rdx
movq %rdi, %rax
salq $4, %rax
subq %rdi, %rax
addq %rsi, %rax
movl array1(,%rax,4), %eax movl %eax, array2(,%rdx,4) ret
What are the values of H and J? H=
Page 9 of 22
Problem 4. (8 points):
Assembly/C translation. Consider the following C code and assembly code for an interesting function:
int rofl(int *a, int n) {
for(i = 0; i < n; i++) {
if(i == k) {
________; }
if(________)
return k; }
a[i] = ________;
a[k] = k; }
return ________;
40055c
40055c: test
40055e: jle
400560: mov
400563: mov
400568: mov
40056b: cmp
40056d: je
40056f: movslq
400572: lea
400576: mov
400579: cmp
40057b: je
40057d: mov
400580: mov
400583: add
400586: add
40058a: cmp
40058c: jg
40058e: mov
400593: mov
400595: retq
40058e
400583
400593
400568
A. Using your knowledge of C and assembly, fill in the blanks above with the appropriate expressions. B. Extracredit(1point).Brieflydescribewhattheroflfunctiondoes.Hint:Thinkaboutwhathappens
when every integer k in the array a satisfies 0 ≤ k ≤ n − 1.
Page 10 of 22
Problem 5. (9 points):
Representing and accessing structures. The following problems concern the compilation of C code involv- ing struct’s.
A. InthefollowingCcode,thedeclarationsofdatatypestype1_tandtype2_taregivenbytypedef’s, and the declaration of the constant CNT is given by a #define:
typedef struct { type1_t y[CNT];
type2_t x;
} a_struct;
void p1(int i, a_struct *ap) { ap->y[i] = ap->x;
Compiling the code for IA32 gives the following assembly code:
# i at 8(%ebp), ap at 12(%ebp) p1:
pushl %ebp
movl %esp, %ebp
movl 12(%ebp), %eax movsbl 28(%eax),%ecx
movl 8(%ebp), %edx
movl %ecx, (%eax,%edx,4) popl %ebp
Give a combination of values for the two data types and CNT that could yield the above assembly code:
type1_t: type2_t: CNT:
Page 11 of 22
B. In the following C code, the declaration of data type type_t is given by a typedef, and the declaration of the constant CNT is given by a #define:
typedef struct { int left;
type_t m[CNT];
int right;
} b_struct;
int p2(int i, b_struct *bp) { return bp->left * bp->right;
For some combinations of type_t and CNT, the following x86-64 code is generated: # bp in %rsi
movl 24(%rsi), %eax imull (%rsi), %eax ret
For each of the combinations below, indicate whether it could (Y) or could not (N) cause the above code to be generated:
Generated? (Y/N)
struct { int i; double d[2]; }
Page 12 of 22
Problem 6. (0xa points):
The stack discipline. This problem deals with stack frames in Intel IA-32 machines. Consider the following C function and corresponding assembly code.
struct node_t;
typedef struct node_t{
void * elem;
struct node_t *left;
struct node_t *right;
void oak(node * tree, void (*printFunc)(node *)){ /*POINT A*/
00000000
0: 55 push
1: 89 e5 mov
3: 83 ec 18 sub
6: 89 5d f8 mov
9: 89 75 fc mov
c: 8b 5d 08 mov
f: 8b 75 0c mov
12: 89 1c 24 mov
/*POINT A*/
$0x18,%esp
%ebx,0xfffffff8(%ebp)
%esi,0xfffffffc(%ebp)
0x8(%ebp),%ebx
0xc(%ebp),%esi
%ebx,(%esp)
25: e8 fc ff
2a: 8b 43 08
31: 89 74 24
35: 89 04 24
38: e8 fc ff
3d: 8b 5d f8
40: 8b 75 fc
call 26
mov 0x8(%ebx),%eax
test %eax,%eax
je 3d
mov %esi,0x4(%esp)
mov %eax,(%esp)
call 39
mov 0xfffffff8(%ebp),%ebx
mov 0xfffffffc(%ebp),%esi
mov %ebp,%esp
pop %ebp ret
(*printFunc)(tree);
if (tree->left) {
/*POINT B*/
oak(tree->left,printFunc);
if (tree->right) {
oak(tree->right,printFunc);
call *%esi
mov 0x4(%ebx),%eax
test %eax,%eax
je 2a
mov %esi,0x4(%esp)
mov %eax,(%esp)
Page 13 of 22
/*POINT B*/
Please draw a picture of the stack frame, starting with any arguments that might be placed on the stack for the oak function, showing the stack at each of points A, and B, as specified in the code above. Your diagram should only include actual values where they are known, if you do not know the value that will be placed on the stack, simply label what it is (i.e., ”old ebp”).
Page 14 of 22
Stack A: Stack B:
Page 15 of 22
Problem 7. (7 points):
Cache memories. In this problem, we will consider the performance of the cache. You can make the following assumptions:
• There’s only one level of cache. • Block size is 4 bytes.
• The cache has 4 sets.
• Each cache set has two lines.
• Replacement policy is LRU.
Consider the following function which sets a 4 × 4 square in the upper left corner of an array to zero. You should assume that only operations involving array change the cache, that array[0][0] is at address 0x1000000, and that the cache is empty when clear4x4 is called.
#define LENGTH 8
void clear4x4(char array[LENGTH][LENGTH]){ int row, col;
for(col = 0; col < 4; col++){ for(row = 0; row < 4; row++){
array[row][col] = 0; }
A. (3 pts) How many cache misses will there by when clear4x4 is called? Number of cache misses: _________________
B. (3 pts) If LENGTH is changed to 16 how many cache misses will clear4x4 have when called? Number of cache misses: _________________
C. (1 pt) If LENGTH is changed to 17, will calling clear4x4 have a larger, smaller, or equal number of cache misses than when LENGTH is 16? Circle the correct answer.
• 16 × 16 will have MORE misses than 17 × 17.
• 16 × 16 and 17 × 17 will have an EQUAL number of MISSES. • 17 × 17 will have MORE misses than 16 × 16.
Page 16 of 22
Problem 8. (6 points):
Processes vs. threads. This problem tests your understanding of the some of the important differences between processes and threads. Consider the following C program:
#include "csapp.h"
/* Global variables */ int cnt;
sem_t mutex;
/* Helper function */ void *incr(void *vargp) {
P(&mutex);
V(&mutex);
return NULL;
pthread_t tid[2];
sem_init(&mutex, 0, 1); /* mutex=1 */ /* Processes */
A. What is the output of this program?
Procs: cnt = ___ Threads: cnt = ___
(i=0; i<2; i++) { incr(NULL);
if (fork() == 0) {
incr(NULL);
for (i=0; i<2; i++)
wait(NULL);
printf("Procs: cnt = %d\n", cnt);
/* Threads */
for (i=0; i<2; i++) {
incr(NULL);
pthread_create(&tid[i], NULL, incr, NULL); }
for (i=0; i<2; i++) pthread_join(tid[i], NULL);
printf("Threads: cnt = %d\n", cnt);
exit(0); }
Page 17 of 22
Problem 9. (10 points):
Virtual memory. You are taking an operating systems class where you must write a kernel that supports virtual memory. Unfortunately, you have been stuck with a not-so-bright partner who is under the illusion that address translations are performed by the kernel. Without consulting you, he went ahead and wrote a translation function, called log to phys, which is shown on the following page.
Address translations are actually done by hardware of course, but you realize that by studying your partner’s code, you can learn some valuable information about the system – information that will earn you 10 points on your 213 final exam!
As you study your partner’s code, keep in mind the following things:
1. Pointers and unsigned int’s are both 2 bytes long on this particular system (i.e., sizeof(unsigned int) = 2 and sizeof(void *) = 2).
2. You do not have to worry about any type of pointer arithmetic in this problem.
3. Although the code is silly in the sense that translations are not done in software, you can assume that the functionality is correct.
Page 18 of 22
/* Note to self: Recall that on this machine, sizeof(unsigned int) = 2 and sizeof(void *) = 2 */
* log_to_phys - logical is a variable which contains a virtual
address. The physical translation is returned. * log_to_phys (void * logical, void ** pd_base)
Casting to unsigned int is done so you don’t
have to worry about any pointer arithmetic */ unsigned int logical_addr = (unsigned int) logical; unsigned int pd_base_u = (unsigned int) pd_base;
unsigned int offset = logical_addr & (0x1F); unsigned int temp = logical_addr >> 5; unsigned int index1 = (temp & 0x780) >> 7; unsigned int index2 = temp & 0x7F;
unsigned int * pde_addr = (unsigned int *) (pd_base_u + (index1 << 1)); unsigned int entry1 = *pde_addr;
/* Check valid bit */ if(!(entry1 & 0x1)) {
/* This is how you throw a page fault, right? */
return NULL;
/* Discard the valid bit now */ entry1 = entry1 & ( ̃0x1);
unsigned int * pte_addr = (unsigned int *) (entry1 + (index2 << 1)); unsigned int entry2 = *pte_addr;
/* Check valid bit */ if(!(entry2 & 0x1)) {
/* This is how you throw a page fault, right? */
return NULL;
/* Discard the valid bit now */ entry2 = entry2 & ( ̃0x1);
/* This is the logical address! */
return ((void *) (entry2 | offset)); }
Page 19 of 22
The following questions refer to the code on the previous page:
1. How many bytes are the pages (virtual and physical pages are the same size)?
2. How many entries are in the page directory for this architecture?
3. How many bytes long is each entry of the page directory?
4. How many entries are in each page table for this architecture?
5. How many bytes long is each entry of a page table?
Page 20 of 22
Problem 10. (6 points):
Signals. Consider the following two different snippets of C code. Assume all functions return without error, no signals are sent from other pr
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com