Exam 3 Review Questions

Picture ID is REQUIRED for all exams

Use the list of questions below as a guide when studying for Exam 3. It is by no means a comprehensive list of questions.

You are responsible for all material presented in lecture. You are also responsible for all associated reading assignments and material covered by practice and homework problems in the text.

Note the exam 3 covers only the material since Exam 2. Students are permitted to bring one 8 1/2 x 11 piece of paper to the exam.

DO NOT EXPECT to see these specific questions on your exam (but you might).

Please note that code examples in the text are available from the textbook student site for you to copy, compile, edit, and experiment.



    Memory Hierarchy (Text Section 6.1 - 6.3)
  1. Practice Problem 6.2 - calculating disk capacity
  2. Practice Problem 6.3 - calculating disk access time
  3. Practice Problem 6.4 - permuting loops to increase locality
  4. Practice Problem 6.5 - ranking functions in increasing degree of locality
  5. Define the following terms related to disk storage
    1. access time
    2. cylinder
    3. rotational latency
    4. read head
    5. sector
    6. seek time
    7. track
    8. transfer time
  6. What is meant by the terms "spatial locality" and "temporal locality". How might these concepts affect your code?
  7. Define the following terms related to random access memory (RAM)
    1. static RAM
    2. dynamic RAM
    3. memory module
    4. DIMM
    5. SIMM
    6. volatile memory
  8. Draw appropriate diagrams that show how one byte of memory is retrieved from a 64-Mbit 8 x 8 DRAM chip.
  9. Define the following terms related to the "memory hierarchy"
    1. cache
    2. cache miss
    3. cache hit
  10. What is meant by the statement "In the memory hierarchy for each k, the faster and smaller storage dveice at level k serves as a cache for the larger and slower storage device at level k + 1?"

  11. Virtual Memory (Text Section 10.1 - 10.5)
  12. Practice Problem 10.1 - calculating the size of address space
  13. Practice Problem 10.2 - calculating number of PTEs
  14. Practice Problem 10.6 - practice with malloc( )
  15. Practice Problem 10.7 - min block sizes
  16. Homework Problem 10.19 (part 1 and 2)
  17. Define the following terms related to virtual memory
    1. physical memory
    2. address space
    3. page
    4. page table
    5. page fault
    6. page hit
    7. thrashing
  18. Describe the primary benefits of virtual memory?
  19. What is the role of the page table in implementing virtual memory?
  20. What actions are taken when a page fault ocurrs?
  21. How does virtual memory act as a tool for memory protection?
  22. Breifly describe the basic technique for translating a virtual memory address to a physical memory address.
  23. Why is the concept of locality important in making virtual memory feasible?
  24. How does virtual memory make sharing of code and data possible?

  25. Dynamic Memory (Text Section 10.9* - 10.13 and Project 6)
  26. Homework Problem 10.15 - practice with malloc and block sizes
  27. Homework Problem 10.16 - similar to practice problem 10.7
  28. Find the programming bugs in the code found in the text section 10.11.1 - 10.11.10 and explain how to fix them.
  29. Describe each of the three major techinques for orgranizing free blocks discussed in class (implicit free list, explicit free list, segregated free list). Be sure to discuss the advantages and disadvantages of each technique.
  30. What are the two major goals of a memory allocator (like malloc/free/realloc) and how are they measured? Are these goals conflicting? If so how?
  31. What is "internal fragmentation"? How does it occur?
  32. What is "external fragmentation"? How does it occur?
  33. Much of the code in the text and in project 6 uses void *. What is void * and why is it used?
  34. The following problem concerns dynamic storage allocation. Consider an allocator that uses an implicit free list. The layout of each allocated and free memory block is as follows:
             31                          2 1 0
             __________________________________
    Header  | Block Size (bytes)        | | | | 
            |___________________________|_|_|_|
            |                                 |
            |                                 |
            |                                 |
            |                                 |
            |_________________________________|
    Footer  | Block Size (bytes)        | | | | 
            |___________________________|_|_|_|
    
    
    Each memory block, either allocated or free, has a size that is a multiple of eight bytes. Thus, only the 29 higher order bits in the header and footer are needed to record block size, which includes the header and footer. The usage of the remaining 3 lower order bits is as follows: -- bit 0 indicates the use of the current block: 1 for allocated, 0 for free. -- bit 1 indicates the use of the previous adjacent block: 1 for allocated, 0 for free. -- bit 2 is unused and is always set to be 0.

    Given the address of a word (4 bytes) in the heap in the left column, and the original contents of the heap in the middle column, show the new contents of the heap in the right column after a call to free(0x400b010) is executed. Your answers should be given as hex values. Note that the address grows from bottom up. Assume that the allocator uses immediate coalescing, that is, adjacent free blocks are merged immediately each time a block is freed.

    Address Current Value New Value
    0x400b028 0x00000012  
    0x400b024 0x400b611c 0x400b611c
    0x400b020 0x400b512c 0x400b512c
    0x400b01c 0x00000012  
    0x400b018 0x00000013  
    0x400b014 0x400b511c 0x400b511c
    0x400b010 0x400b601c 0x400b601c
    0x400b00c 0x00000013  
    0x400b008 0x00000013  
    0x400b004 0x400b601c 0x400b601c
    0x400b000 0x400b511c 0x400b511c
    0x400affc 0x00000013  

  35. Below you are given a series of memory requests as they might appear in a user's program. The heap is represented as a row of boxes, where each box is a single block on the heap, and the bottom of the heap is the left-most box. Simulate the calls to malloc( ) or free( ) on the left by marking each block in the corresponding row. In each block, you should write the total size (including headers and footers) of the block in bytes and either f or a to mark it as free or allocated, respectively, For example, the following heap contains an allocated block of size 16, followed by a free block of size 32.
                              |--------|--------|--------|--------|--------|
                              | 16a    |  32f   |        |        |        |
                              |--------|--------|--------|--------|--------|
    
    The calls to malloc( ) and free( ) are cumulative, so each call starts from the row above except the first which starts with and empty heap.

    A. Perform the series of calls to malloc and free using first fit to choose a free block for malloc() and immediate coalescing to merge blocks after free().
    B. Perform the series of calls to malloc() and free() using best fit to choose a free block for malloc() and immediate coalescing to merge blocks after free().

    ptr1 = malloc( 32 )
    |--------|--------|--------|--------|--------|
    |        |        |        |        |        |
    |--------|--------|--------|--------|--------|
    
    ptr2 = malloc(16); 
    |--------|--------|--------|--------|--------|
    |        |        |        |        |        |
    |--------|--------|--------|--------|--------|
    
    ptr3 = malloc(16);
    |--------|--------|--------|--------|--------|
    |        |        |        |        |        |
    |--------|--------|--------|--------|--------|
    
    ptr4 = malloc(40);
    |--------|--------|--------|--------|--------|
    |        |        |        |        |        |
    |--------|--------|--------|--------|--------|
    
    free(ptr3); 
    |--------|--------|--------|--------|--------|
    |        |        |        |        |        |
    |--------|--------|--------|--------|--------|
    
    free(ptr1);
    |--------|--------|--------|--------|--------|
    |        |        |        |        |        |
    |--------|--------|--------|--------|--------|
    
    ptr5 = malloc(16);
    |--------|--------|--------|--------|--------|
    |        |        |        |        |        |
    |--------|--------|--------|--------|--------|
    
    free(ptr4); 
    |--------|--------|--------|--------|--------|
    |        |        |        |        |        |
    |--------|--------|--------|--------|--------|
    
    ptr6 = malloc(48); 
    |--------|--------|--------|--------|--------|
    |        |        |        |        |        |
    |--------|--------|--------|--------|--------|
    
    free(ptr2);
    |--------|--------|--------|--------|--------|
    |        |        |        |        |        |
    |--------|--------|--------|--------|--------|
    
  36. This problem tests your understanding of pointer arithmetic, pointer dereferencing, and malloc implementation. Mr. Frey's friend Bob has decided to exercise his creativity and has created the most exotic dynamic memory allocator that the CMS 313 staff has ever seen. The following is a description of Bob’s block structure:
    ________________________
    |      |          |     |
    | KEY  | PAYLOAD  | FTR |
    |______|__________|_____|
    
    	• KEY - Key of the block (4 bytes).
    	• PAYLOAD - Payload of the block (arbitrary size).
    	• FTR - Footer of the block (4 bytes).
    
    Bob has decided to store a key in the beginning of each block instead of a header; Bob has a secret way of computing the size of the block’s payload from the key. The size of the KEY field is 4 bytes. Bob has also decided to store the size of a block’s payload in the footer of the block. Since there is an 8-byte alignment requirement, the least significant of the 3 unused bits is used to indicate whether the block is free (0) or allocated (1). Note that Bob is working on a 32-bit machine. You can assume the following:
    • sizeof(int) == 4 bytes
    • sizeof(char) == 1 byte
    • sizeof(short) == 2 bytes
    • sizeof(long) == 4 bytes
    • the size of any pointer (e.g., char *) is 4 bytes
    Your task is to help Bob by writing the code for the function getKey(void *bp). The function getKey() returns the key of a block, where bp is pointing to the first byte of a block returned from Bob's malloc() function.

    Write your code for getKey( void * bp ) below.

  37. Processes and Control Flow (Text 8.1 - 8.8)
  38. What is the purpose of each of the following system calls?
    1. fork( )
    2. wait( )
    3. waitpid( )
    4. execl( )
    5. signal( )
    6. kill( )
    7. getpid( )
    8. getppid( )
  39. Define the following terms
    1. signal
    2. signal handler
    3. pending signal
    4. blocked signal
    5. defunct process
    6. zombie process
    7. reaping a child process
    8. PID
  40. Practice Problems 8.1 - 8.4 ask you to determine the output from code using fork( )
  41. Homework Problems 8.9 - 8.14 are similar to the practice problems
  42. Briefly decsribe the basic Unix signal handling methodology.
  43. This problem tests your understanding of exceptional control flow in C programs. Assume the code is running on a Unix machine. The following problem concerns the value of the variable counter.
    int counter = 0;
    
    
    
    void handler( int signal ) 
    {
         counter ++;
    }
    
    
    int main( )
    {
    	int i;
    	signal( SIGCHLD, handler );
    	for (i = 0; i < 5; i ++) {
    		if (fork( ) == 0) {
    			exit(0);
    		}		
    	}
        
    	/* wait for a child to die */
    	while (wait(NULL) != -1);
        
    	printf("counter = %d\n", counter);
    	return 0;
    }
    
    1. Does the program output the same value of counter every time we run it?
    2. If the answer to A is Yes, indicate the value of the counter variable. Otherwise, list all possible values of the counter variable.
  44. Consider the following C program
        void handler1(int sig) {
            printf("Phantom\n");
            exit(0);
        }
    
        int main()
        {
            pid_t pid1;
            signal(SIGUSR1, handler1);
            if((pid1 = fork()) == 0) {
                printf("Ghost\n");
                exit(0);
            }
    
            kill(pid1, SIGUSR1);
            printf("Ninja\n");
            return 0;
        }
    
    Use the following assumptions to answer the questions:
    
    • All processes run to completion and no system calls will fail.
    • printf() immediately prints to the screen before returning.
    Mark the top of each each column that represents a valid possible output of this program with "YES" and each column which is impossible with "NO"
         
    PhantomNinjaGhostNinjaNinja
    NinjaPhantomNinjaGhostPhantom
     GhostPhantom Ninja
  45. This problem tests your understanding of exceptional control flow in C programs. Assume the code is running on a Unix machine. The following problem concerns the value of the variable counter.
    int counter = 0;
    int main()
    {
        int i;
        
        for (i = 0; i < 2; i ++){
            fork();
            counter ++;
            printf("counter = %d\n", counter);
        }
        
        printf("counter = %d\n", counter);
        return 0;
    }
    
    1. "How many times would the value of counter be printed?
    2. What is the value of counter printed in the first line?
    3. What is the value of counter printed in the last line?
  46. Consider the following C program. For space reasons, return codes are not checked, so assume that all functions return normally. Also assume that each process successfully runs to completion.
    
    int main() {
        int pid;
        pid = fork() && fork();
    
        if (!pid)
            printf("A\n");
        else
            printf("B\n");
        exit(0);
    }
    

    Mark the top of each column that represents a valid possible output of this program with "Yes" and each column which is impossible with "No".

    Mark the top of each column as "YES" or "NO"
             
    A
    A
    A
    A
    A
    A
    A
    A
    A
    A
    A
    B
    B
    A
    B
    B

     

  47. 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. List all possible outputs of this program.