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).

Memory Hierarchy (Text Section 6.1 - 6.3)

Practice Problem 6.2
Practice Problem 6.3
Practice Problem 6.4
Practice Problem 6.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
What is meant by the terms "spatial locality" and "temporal locality". How might these concepts affect your code?
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
Draw appropriate diagrams that show how one byte of memory is retrieved from a 64-Mbit 8 x 8 DRAM chip.
Define the following terms related to the "memory hierarchy"
1. cache
2. cache miss
3. cache hit
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?"

Virtual Memory (Text Section 10.1 - 10.5)

Practice Problem 10.1
Practice Problem 10.2
Practice Problem 10.6
Homework Problem 10.19
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
Describe the primary benefits of virtual memory?
What is the role of the page table in implementing virtual memory?
What actions are taken when a page fault ocurrs?
How does virtual memory act as a tool for memory protection?
Breifly describe the basic technique for translating a virtual memory address to a physical memory address.
Why is the concept of locality important in making virtual memory feasible?
How does virtual memory make sharing of code and data possible?

Dynamic Memory (Text Section 10.9* - 10.13 and Project 6)

Homework Problem 10.15
Homework Problem 10.16
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.
What is "internal fragmentation"? How does it occur?
What is "external fragmentation"? How does it occur?
Much of the code in the text and in project 6 uses void *. What is void * and why is it used?

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 the heap in the left column, 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

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.
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?
Describe the major implementation choices for organizing free blocks in the heap. Be sure to discuss the advanatages and disadvantages of each.
Describe the major implementations choice for coalescing free blocks in the heap. Be sure to discuss the advanatages and disadvantages of each.
Describe the major implementation choices for splitting free blocks in the heap. Be sure to discuss the advanatages and disadvantages of each.
Find the programming bugs in the code found in the text section 10.11.1 - 10.11.10 and explain how to fix them.

Processes and Control Flow (Text 8.1 - 8.8)

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( )
Define the following terms
1. signal
2. signal handler
3. pending signal
4. blocked signal
5. defunct process
6. reaping a child process
7. PID
Briefly decsribe the basic Unix signal handling methodology.
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 counterevery 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.
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?

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

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.

Linking

Practice Problem 7.1
Practice Problem 7.2
Practice Problem 7.3
Practice Problem 7.4
Practice Problem 7.5
Homework Problem 7.6
Homework Problem 7.7
What are the two primary functions of the linker when combining .o files together?
Describe the four (4) steps necessary to create an executable file (e.g. a.out) from a C source file (e.g. Bob.c. Specify the names of each translator used in the steps, the type of file input to each translator, the function of each translator and the type of file output from each translator.
What is the difference between a "symbol definition" and a "symbol reference"?
Consider the following three C source files.
File polygon.h:
```
struct Node {
    float pos[2];
    int marked;      /* only for Garbage Collector */
    struct Node* next;
    struct Node* prev;
};

typedef struct Node node;
node* alloc();            /* allocate a new node */
void init();              /* initialize  */
void gc();                /* call garbage collector */
```
File main.c (with portions of the function elided)
```
#include "polygon.h"

node* root_ptr;       /* root pointer, for Garbage Collector */


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 Garbage Collector */

void mark(node* v) {...}
void sweep () {...}
void gc () {...}
void init () {...}
node* alloc () {...}
```
Recall that a line #include "file" will literally be replaced by the contents of "file" by the C preprocessor. We compile the files to obtain an executable object file polygon with gcc -o polygon main.c gc.c. Questions related to symbols and linking therefore refer to the expanded versions of the files.
1. Fill in the following tables by stating for each name whether it is local or global, and whether it is strong or weak. Cross out any box in the table that does not apply. For example, cross out the first box in a line if the symbol is not in the symbol table, or cross out the second box in a line if the symbol is not global (and therefore neither weak nor strong).
  main.c
  Symbol Global / Local Strong / Weak
  
  root_ptr
  
  init
  
  main
  
  gcc.c
  Symbol Global / Local Strong / Weak
  
  N
  
  root_ptr
  
  init
  
  main
2. Explain why linking succeeds to create an executable despite the fact that some symbols are declared in both files.
3. Explain why the executable fails to be correct despite the fact that it compiles and links without warning. Propose how to fix the bug(s). Be clear in your suggestion correction (for example, replace the line . . . with . . .).
What are the rules the linker follows when resolving external symbol references?
List the three major types of object files.
Describe the contents of the following sections of an object file in ELF format.
1. .text
2. .data
3. .bss
4. .symtab

main.c
Symbol	Global / Local	Strong / Weak
root_ptr
init
main

gcc.c
Symbol	Global / Local	Strong / Weak
N
root_ptr
init
main