Final Exam

CS354  Spring 2009

May 4, 2009

Name: ______________________________________________________________________

1. True/False Questions (write F or  T) (10 points, 1 point each)

__ Swap space is the backing store for the heap.

__ Third-level page tables (in a 3-level paging system) are allocated when needed by a process

__ The access bit is set by the MMU

__ The LRU page replacement policy is fully implemented by current hardware

__ It's generally better to replace a dirty page than a referenced page

__ Using 4 MB memory pages instead of 4 KB ones means that second-level tables are not needed (in a 32-bit architecture)

__ Calling "unlink" on a symbolic link will decrease the reference count of the inode for the file specified by the path in the link

__ The “rootsquash” mount option prevents files on a mounted file system from executing with superuser privileges.

__ The page table base register remains unchanged whenever execution switches to a different thread in the same process.

__ Using fchmod(int fildes, mode_t mode) is a better idea than using chmod(const char * path, mode_t mode)

Short Questions

2.  Virtual memory and mmap.

a) Replace the following code sample by a single function call (hint: there are 2 correct answers, but you need only one of the two):

fd = open("/dev/zero", O_RDONLY);

ptr = mmap(0, desired_size, PROT_READ|PROT_WRITE, MAP_PRIVATE, fd, 0);

close(fd);

_________________________________________________________________________________

b) What would happen in the virtual memory system if you were to call malloc followed by memset instead of the single function call?  (hint: consider the case where a large number of pages would be initialized).  Explain why  the above call is preferable.  

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

3. Explain mark-and-sweep garbage collection.

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

4. Fragmentation.

a) Calculate the external fragmentation level of a free list that has 6 blocks of the following sizes:  1, 20, 2, 2, 15, 10

_________________________________________________________________________________

_________________________________________________________________________________

b) Calculate the total internal fragmentation % if the following requests for memory blocks of size (20, 24, 8) were satisfied respectively with blocks of size (32, 32, 16).  

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

5. Give a definition and an example for:

a) A wild free

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

b)  A double free _________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

6. In Lab 6, why should we put a fence post at the beginning and at the end of the free chunk returned by OS?

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

7. Malloc implementations.

a) Why does the following program crash with a bus error?

int main()
{
int p=34;
int *pp= (int *) ((char *)&p+1);
cout<<*pp<<"\n";
return 0;
}
_________________________________________________________________________________

_________________________________________________________________________________

b) Imagine that a friend implemented of memory-efficient version of malloc that returns exactly the number of usable bytes requested by the call.  Explain why programs using the new library often crash (with bus errors) even though they seem correct and run fine with the normal version of malloc.

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

8. When implementing the spin locks in lab4, you have seen and explained that the spin locks that call thr_yield use less user time than the ones that don't. How can you explain that on the other hand the version that calls thr_yield uses more system time ?

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

9. In the malloc project, there is a line of code that looks like:

size_t y = (x + 7) & ~7;

What does this line do ?

_________________________________________________________________________________

What is the purpose of the code where this line is embedded? (If you remember it, the name of the function suffices, otherwise describe the purpose)

_________________________________________________________________________________

Explain how this line works.

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

10. Is it possible to enforce memory protection at a granularity finer than the size of a page?

If yes, explain how; if no, explain why.

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

11. Given 3 pages frames in main memory initially empty and a program that requests 5 pages in this order:

a  b  a  c  e  b  d  b  a  c  d

a) using the optimal replacement algorithm, show which pages will be loaded into which frame after each request, and indicate page faults by a “*”. (4 points)

b) Using the FIFO replacement algorithm, show which pages will be loaded into which frame after each request, and indicate page faults by a “*”. (4 points)

c) Using the clock (2nd chance) replacement algorithm, show which pages will be loaded into which frame after each request, and indicate page faults by a “*”.(4 points)

12. Assuming a 4 KB page size and given the 2-level page tables below, find the physical memory addresses for the following address references (6 points total):

a) 0xCD023A8A

b) 0x330998F3

c) 0x620A393F

Level 1 ("*" means multiply)

Level 2

Your Answers (2 points each):

a) ___________________

b) ___________________

c) ___________________

13. The code below is from a solution to one of your labs.

a) What is that lab about (1 point)?_______________________________

b) What is the purpose of the code below (1 point)?

__________________________________________________________________________________

c) This code is missing 4 synchronization statements for the program to operate correctly.  Write them below (4 points) and show where you would insert them by writing the number (i or ii, ...) with an arrow between two lines of code (4 points):

i. ___________________________________________________________

ii. ___________________________________________________________

iii. ___________________________________________________________

iv. ___________________________________________________________

AThread* myThread;

int i = 0;

sema_wait(&_shared->_sem_available_threads);

_shared->_currentSimultaneousCalls += 1;

_shared->_totalCalls += 1;

while (_shared->_AThread[i]._in_use) i++;

AThread *myThread = &(_shared->_AThread[i]);

myThread->_in_use = true;

strcpy(myThread->_AName, AName);

memcpy(myThread->_argument, argument, AMaxArgumentsOrResults);

sema_post(&myThread->_sem_request);

sema_wait(&myThread->_sem_result);

memcpy(result, myThread->_result, AMaxArgumentsOrResults);

_shared->_currentSimultaneousCalls -= 1;

myThread->_in_use = false;

sema_post(&_shared->_sem_available_threads);

14. Assuming 4 KB disk block sizes and inodes that have 8 direct pointers, 4 single-indirect block pointers and one double-indirect block pointer, and a 32-bit architecture,

a) What is the number of bytes reachable from the double-indirect pointer (2 points)?

b) A seek operation to location 0x0000D15E is requested.  Draw a graph representing how the correct block on disk would be found, clearly indicating which pointers are used with the appropriate indexes and numbers.  Start with a representation of the inode (you don't need to show other fields in the inode besides the block pointers). (8 points)

15. Given the following structure:

struct my_data {

  char c;

  int i;

}

Write functions to serialize or deserialize this data structure into a file:

int serialize( char *filename, struct my_data *data);

int *deserialize( char* filename, struct my_data *data);

To simplify the code, we are considering to store (and load) only one data structure per file.  Return zero if successful, -1 if an error happens. To simplify the problem for the purposes of this exam, you can fully trust the provided parameters (i.e., you don't need to validate them, unlike a real program with robustness requirements).

a) Write these functions using file operations to load and store the data.  (8 points)

b) Write these functions using memory mappings to store and load the data. (8 points)

 Hint: consider how data structures were handled in the RPC lab (as in the elfinfo lab).