CS代考 CS 15-213, Spring 2002 Final Exam

Part II The following function traverses the binary tree to locate the node with a given key value.
1: struct tree_node * search(struct tree_node * node,
4: if (node->key == value)
5: return node;
6: else if (node->key > value) {
7: if (node->left == NULL)
8: return NULL;
9: else return search(node->left, value);
11: else {
12: if (node->right == NULL)
13: return NULL;
14: else return search(node->right, value);
Suppose we call search(root, 0x4e). Fill in the blanks the value of these memory location so that it shows the stack when the execution is at line 5. (More space than needed is provided. ) You can assume that the stack stores only arguments, return address, and the ebp register value. The value of ebp is 0xbffff880 when the program calls the function. Write ”rtn addr” for return addresses.
int value)
0xbffff800
0xbffff7fc
0xbffff7f8
0xbffff7f4
0xbffff7f0
0xbffff7ec
0xbffff7e8
0xbffff7e4
0xbffff7e0
0xbffff7dc
0xbffff7d8
0xbffff7d4
0xbffff7d0
0xbffff7cc
0xbffff7c8
0xbffff7c4
Page 7 of 22

Problem 4. (8 points):
In this problem, you will compare the performance of direct mapped and -way associative caches for the
initialization of 2-dimensional array of data structures. Both caches have a size of mapped cache has -byte lines while the -way associative cache has -byte lines.
You are given the following definitions
typedef struct{ float* position;
float velocity[3]; float forces[3]; particle_t *adjacent;
} particle_t;
particle_t cloth[32][32]; register int i, j, k;
Also assume that
sizeof(* float) and sizeof(* particle_t) = 4 sizeof(float) = 4
surface begins at memory address 0
Both caches are initially empty
bytes. The direct
The array is stored in row-major order
Variables i,j,k are stored in registers and any access to these variables does not cause a cache miss
A. What fraction of the writes in the following code will result in a miss in the direct mapped cache?
for (i = 0; i < 32; i ++) { for (j = 0; j < 32; j ++) { for(k = 0; k < 3; k ++) { cloth[i][j].forces[k] = 0.; } Miss rate for writes to surface:____________% B. Using code in part A, what fraction of the writes will result in a miss in the 4-way associative cache? Miss rate for writes to surface: ____________% Page 8 of 22 C. What fraction of the writes in the following code will result in a miss in the direct mapped cache? for (i = 0; i < 32; i ++) { for (j = 0; j < 32; j ++) { for (k = 0; k < 16; k ++) { cloth[j][i].forces[k] = 0; } Miss rate for writes to surface:____________% D. Using code in part C, what fraction of the writes will result in a miss in the 4-way associative cache? Miss rate for writes to surface:____________% Page 9 of 22 Problem 5. (15 points): The following problem concerns the way virtual addresses are translated into physical addresses. The memory is byte addressable, and memory accesses are to 1-byte not 4-byte words. Virtual addresses are 18 bits wide. Physical addresses are 12 bits wide. The page size is 512 bytes. The TLB is 8-way set associative with 16 total entries. The cache is 2-way set associative, with a 4-byte line size and 32 total entries. In the following tables, all numbers are given in hexadecimal. The contents of the TLB and the page table for the first 32 pages, and the cache are as follows: Tag PPN Valid 55 6 0 48 F 1 00 A 0 32 9 1 6A 3 1 56 1 0 60 4 1 78 9 0 71 5 1 31 A 1 53 F 0 87 8 0 51 D 0 39 E 1 43 B 0 73 2 1 Page 10 of 22 Page Table VPN PPN Valid VPN PPN Valid 000 7 0 001 5 0 002 1 1 003 5 0 004 0 0 005 5 0 006 2 0 007 4 1 008 7 0 009 2 0 00A 3 0 00B 0 0 00C 0 0 00D 3 0 00E 4 0 00F 7 1 010 1 0 011 3 0 012 3 0 013 0 0 014 6 1 015 5 0 016 7 0 017 2 1 018 0 0 019 2 0 01A 1 0 01B 3 0 01C 2 0 01D 7 0 01E 5 1 01F 0 0 2-way Set Associative Cache Byte 0 Byte 1 Byte 2 Byte 3 Byte 0 Byte 1 Byte 2 Byte 3 7A 1 02 0 55 1 07 1 09 EE 12 64 60 17 18 19 30 EB C2 0D 03 04 05 06 00 0 7F 1 0B 0 5D 1 99 04 03 48 FF BC 0B 37 8F E2 05 BD 7A 08 03 22 Page 11 of 22 1. The box below shows the format of a virtual address. Indicate (by labeling the diagram) the fields (if they exist) that would be used to determine the following: (If a field doesn’t exist, don’t draw it on the diagram.) VPO The virtual page offset VPN The virtual page number TLBI The TLB index TLBT The TLB tag 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 2. The box below shows the format of a physical address. Indicate (by labeling the diagram) the fields that would be used to determine the following: PPO The physical page offset PPN The physical page number CO The Cache Block Offset CI The Cache Index CT The Cache Tag 11 10 9 8 7 6 5 4 3 2 1 0 Page 12 of 22 For the given virtual addresses, indicate the TLB entry accessed and the physical address. Indicate whether the TLB misses and whether a page fault occurs. If there is a cache miss, enter “-” for “Cache Byte Returned.” If there is a page fault, enter “-” for “PPN” and leave part C blank. Virtual address: 0x1A9F4 1. Virtual address format (one bit per box) 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 2. Addresstranslation TLB Hit? (Y/N) Page Fault? (Y/N) 3. Physical address format (one bit per box) 11 10 9 8 7 6 5 4 3 2 1 0 4. Physical memory reference Block Offset Cache Index Cache Hit? (Y/N) Value of Cache Byte Returned Page 13 of 22 Problem 6. (10 points): This question deals with various aspects of the implementation of dynamic memory allocators. Memory utilization Suppose your memory allocator uses a simple implicit list, and each block in the heap has a 1 word header and footer. Assume that the heap has a unused word at the start of the heap to enforce double-word alignment, followed by a prologue block consisting of only a header and footer. At the end of the heap is a 1 word epilogue header. The allocator’s minimum allocation unit is 8 bytes. The total size of the heap is 2048 bytes. A. If the heap is full (this means a request of malloc(1) will fail), what is worst case memory utilization of the heap? B. Briefly (no more than 2 sentences), describe the difference between internal and external fragmentation. Free list strategies Consider a heap with blocks, where are allocated. For the following questions, express your answer in -notation: A. What is the worst case running time of first fit allocation with explicit free lists? B. What is the worst case running time of first fit allocation with implicit free lists? C. What is the worst case running time of best fit allocation with explicit free lists? Coalescing strategies Immediate coalescing is the strategy we have seen where a block is coalesced with its neighbor(s) immediately after it is freed. Another possible strategy is lazy or deferred coalescing, where free blocks are not coalesced immediately. Usually, coalescing is done when a allocation request cannot be fulfilled. For the following two questions, express your answer in -notation. Borrowing from the previous section, there are blocks in the heap, where are allocated. Assume the allocator uses some form of explicit free lists. A. What is the worst case running time of coalescing using an immediate strategy? B. What is the worst case running time of coalescing using a lazy strategy? For the following situations, describe whether an allocator using immediate or lazy coalesing (coalescing done when an allocation request fails) would be more appropriate. If the choice of coalescing strategy has negligible performance impact, write “does not matter”. D. The allocator allocates only two types of structures that have fixed sizes, and expects heavy reuse patterns. Page 14 of 22 E. The allocator must operate in real time. This means the allocator makes hard performance guarantees that its operations will not take more than some fixed specified amount of time. F. The allocator will alternately allocate and free blocks where the next allocation request is 1/2 the size of the last request. Page 15 of 22 Problem 7. (9 points): Part 1 Consider the C program below. (For space reasons, we are not checking error return codes, so assume that all functions return normally.) #include
#include #define NTHREADS 20
void *thread(void *vargp) {
static int cnt = 0;
printf(“%d\n”, cnt); }
int main () {
pthread_t tid;
for(i = 0; i < NTHREADS; i++) { pthread_create(&tid, NULL, thread, NULL); } pthread_exit(NULL); What are the maximal guarantees you can make about the output of the above program? Check all that apply. Note: Checking all of the boxes implies that the output is 1 2 3 ... 20 20 numbers will be printed. The numbers lie in the range 1 through 20, inclusive. There are no duplicate numbers printed. The numbers will be printed in ascending order. Page 16 of 22 Using mutexes, modify the code to guarantee that the output of the program is 1 2 3 ... 20 The numbers 1 through 20 printed sequentially in ascending order. Here are the mutex operations: int pthread_mutex_init(pthread_mutex *mutex, const pthread_mutexattr_t *mutexattr); int pthread_mutex_lock(pthread_mutex_t *mutex)); int pthread_mutex_unlock(pthread_mutex_t *mutex)); int pthread_mutex_destroy(pthread_mutex_t *mutex)); Here is the code from the previous page. Make the appropriate additions. #include
#include #define NTHREADS 20
% answer: pthread_mutex mutex;
void *thread(void *vargp) {
static int cnt = 0;
% answer: pthread_mutex_lock(&mutex); cnt++;
printf(“%d\n”, cnt);
% answer: pthread_mutex_unlock(&mutex);
int main () {
pthread_t tid;
% pthread_mutex_init(&mutex, NULL);
for(i = 0; i < NTHREADS; i++) { pthread_create(&tid, NULL, thread, NULL); Page 17 of 22 Problem 8. (5 points): This problem tests your understanding of the file sharing between processes. Consider the following program. 1: int main() 2: { int fd_x, fd_y, fd_z; fd_x = Open("file1", O_RDONLY); if (Fork() == 0) { fd_y = Open("file1", O_RDONLY); fd_z = Open("file2", O_RDONLY); Dup2(fd_z, fd_x); The following graph shows the kernel data structure after line 5 is executed. Please draw the kernel data structure when the child process execution stops at line 8 and the parent stops at line 13. Add additional entries to the tables if needed. Remember to update the refcnt field in the open file table. You can assume that 1. there is no error in opening the files, and 2. thevalueoffdx,fdy,andfdzare2,3,3respectively. Descriptor tables Parent’s table fd 0 fd 1 fd 2 fd 3 Child’s table fd 0 fd 1 fd 2 fd 3 Open file table V−node table refcnt = 1 File access Page 18 of 22 Problem 9. (8 points): Part 1 You have just been hired by a software company to complete some database software. You’ve been assigned the task of writing the networking code that will allow server and client software to communicate. The database software is designed to handle many simultaneous connections. Both the server and client’s networking code need to be written. The server will be hosted on DEFAULT PORT and it does not care which IP address on which it’s to be hosted. The connection backlog should be 10. At the moment, you will only be testing the client’s code. Therefore, the client will only connect to the local host (127.0.0.1) while testing. The following function declarations may prove useful. int bind(int sockfd, struct sockaddr *addr, socklen t addrlen) int connect(int sockfd, struct sockaddr *addr, socklen t addrlen) int socket(int domain, int type, int protocol) int listen(int s, int backlog) int accept(int s, struct sockaddr *addr, socklen t addrlen) unsigned long int htonl(unsigned long int hostlong) unsigned short int htons(unsigned short int hostshort) Page 19 of 22 The following is the framework for the server code you are required to write. Note that the function returns a socket descriptor. Assume there are no errors and no error handling is needed. int setup_server() struct sockaddr_in addr; int len = sizeof(struct sockaddr); fd = _______________________________________; bzero(&addr, len); addr.sin_family = AF_INET; addr.sin_port = __________________________; addr.sin_addr.s_addr = _____________________; ____________________________________________; ____________________________________________; ____________________________________________; } Page 20 of 22 The following is your framework for the client code. Note that it also returns a socket descriptor. Again, no error handling is needed. int client_setup() struct sockaddr addr; int fd; fd = _______________________________________; addr.sin_family = AF_INET; addr.sin_port = __________________________; addr.sin_addr.s_addr = 0x___________________; ____________________________________________; ____________________________________________; } Fill in a valid time ordering for the networking functions called by both the client and the server. Use the functions listed below. Some may be used more than once. Only enter one per numbered line. No numbered line is to be left blank 1 2 3 4 5 6 Page 21 of 22 bind socket connect listen accept Problem 10. (9 points): You now need to demonstrate your understanding of concurrency across multiple ways of implementing it. Given a concurrent program using threads, fill in the key blanks of a concurrent program using select() so that it accomplishes the same goal. The following simple program echos the text entered onto 10 different terminals to the screen one character at a time. The code for you to complete is on the following page. int main ( int argc, char *argv[] ) { for ( j = 0; j < 10; j++ ) { pthread_t pthread; int* fd = malloc(sizeof(int)); /* Get a file descriptor for a terminal. * Don’t worry about how. *fd = getNextTerminalFD(); pthread_create ( &pthread, NULL, thread, fd ); } 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com