15-213 Introduction to Computer SystemsExam 2April 10, 2007Name:Andrew User ID:Recitation Section:• This is an open-book exam.• Notes and calculators are permitted, but not computers.• Write your answer legibly in the space provided.• You have 80 minutes for this exam.• We will drop your lowest score among questions 1–6.Symbols and LinkingVirtual Address TranslationProcess ControlSignalsGarbage CollectionCycloneProblem Max Score1 152 153 154 155 156 15Total 7511. Symbols and Linking (15 points)In this problem we consider issues of symbols and linking. Consider the following threefiles.File polygon.h:struct Node {float pos[2];int marked; /*only for GC*/struct Node*next;struct Node*prev;};typedef struct Node node;node*alloc(); /*allocated new node*/void init(); /*initialize store*/void gc(); /*call garbage collector*/File main.c (with portions of the function elided)#include "polygon.h"node*root_ptr; /*root pointer, for GC*/int main () {node*p;init();p = alloc();root_ptr = p; /*GC root is first allocated pointer*/...gc();...return 0;}File gc.c (with function bodies elided)#include "polygon.h"#define N (1<<20)static node polygon[N]; /*polygon array*/static node*free_ptr; /*free list*/static node*root_ptr; /*root pointer, for GC*/void mark(node*v) {...}void sweep () {...}void gc () {...}void init () {...}node*alloc () {...}2Possible definition of the functions in gc.c are revisited in Problems 5 and 6 althoughthis is not relevant here.Recall that a line #include "file" will literally be replaced by the contents of "file" bythe C preprocessor. We compile the files to obtain an executable object file polygon withgcc -o polygon main.c gc.c. Questions related to symbols and linking thereforerefer to the expanded versions of the files.1. (9 points) Fill in the following tables by stating for each name whether it is local orglobal, and whether it is strong or weak. Cross out any box in the table that doesnot apply. For example, cross out the first box in a line if the symbol is not in thesymbol table, or cross out the second box in a line if the symbol is not global (andtherefore neither weak nor strong).main.cLocal or Global? Strong or Weak?root ptrinitmaingc.cLocal or Global? Strong or Weak?Npolygonroot ptralloc32. (3 points) Explain why linking succeeds to create an executable despite the fact thatsome symbols are declared in both files.3. (3 points) Explain why the executable fails to be correct despite the fact that it com-piles and links without warning. Propose how to fix the bug. Be clear in yoursuggestion correction (for example, replace the line . . . with . . .).42. Virtual Address Translation (15 points)In this problem we consider virtual address translation using a two-level page table. Theparameters of the machine are as follows:• The memory is byte addressable.• Virtual addresses are 32 bits wide.• The 32 bits of the virtual address are divided into 8 bits for VPN1, 8 bits for VPN2,and 16 bits for the VPO.• Physical addresses are 24 bits wide.1. (3 pts) Given the parameters above, fill in the blanks below.(i) The page size is .(ii) The maximal physical memory size is .(iii) Assuming a page table entry is 32 bits, the size of a page table is .Next we consider the behavior of address translation using the two-level page table.We assume that page table entries have the following form, where unspecified bits areirrelevant for this problem:• Level 1:– Bits 31–16: High 16 bits of level 2 page table physical base address– Bit 0: 1 = Present in physical memory• Level 2:– Bits 31–24: PPN– Bit 0: 1 = Present in physical memoryFor the following questions, assume that the VPN is not cached in the TLB, so we haveto consult the page tables. The PTBR is set at 0xC80000.Address Content0xC80000 0xCA1C00010xC80004 0xCA1B00000xC80008 0xCA1D00010xC8000C 0xCA1B00010xC80010 0x000000000xC80014 0xCA1B00010xC80018 0xC80000000xC8001C 0xCA1B0001Address Content0xCA1B00 0x070000010xCA1B04 0xFF0000000xCA1B08 0x080000010xCA1B0C 0xCA0000010xCA1B10 0x010000000xCA1B14 0x000000000xCA1B18 0x090000010xCA1B1C 0xCA00000052. (6 points) For the virtual address 0x0300F218, indicate the physical address andvarious results of the translation. If there is a page fault, enter “—” for the answerand all subsequent results. All answers should be given in hexadecimal.Parameter ValueVPN1VPN2PTE (level 1)Page Fault? (Y/N)PTE (level 2)Page Fault? (Y/N)PPNPhysical Address3. (6 points) For the virtual address 0x0507EE00, indicate the physical address andvarious results of the translation. If there is a page fault, enter “—” for the PPN andPhysical Address. All answers should be given in hexadecimal.Parameter ValueVPN1VPN2PTE (level 1)Page Fault? (Y/N)PTE (level 2)Page Fault? (Y/N)PPNPhysical Address63. Process Control (15 points)Consider the following C program. For space reasons, we do not check return codes, soassume that all functions return normally. Also assume that printf is unbuffered, andthat each process successfully runs to completion.int main() {int pid;pid = fork() && fork();if (!pid)printf("A\n");elseprintf("B\n");exit(0);}Mark each column that represents a valid possible output of this program with ‘Yes’and each column which is impossible with ‘No’.A A A A AA A A A AA B B AB B74. Signals (15 points)Consider the following code.int val = 1;void handler(int sig) {waitpid(-1, NULL, 0);val++;}int main() {int pid;signal(SIGCHLD, handler);pid = fork();if (pid == 0) {val = 0;exit(0);}printf("%d\n", val);exit(0);}Assume that all system calls succeed, and that all processes terminate normally. Listall possible outputs of this program.85. Garbage Collection (15 points)In this problem we consider code for a specialized mark-and-sweep garbage collector, askeleton of which was introduced in Problem 1. We first explain the data structures. Apolygon is implemented as a doubly linked list of vertices, where each vertex has a linkto its successor and predecessor vertices (the next and prev pointers, respectively). Inaddition the x and y position of each vertex are stored in pos[0] and pos[1].struct Node {float pos[2];int marked; /*only for GC*/struct Node*next;struct Node*prev;};typedef struct Node node;Finally, we have a mark (field marked) which is used exclusively by the garbage collectorand should not be touched by the user program. For simplicity, we store this as a wholeint instead of as a bit.There is a static array polygon of size N containing all vertices. There is
View Full Document
Unlocking...