COSC 3250 / COEN 4820 Operating Systems
Final Examination
Wednesday, May 6, 2015

Your final examination will be a two hour, in-class examination. You are permitted to bring and use one 3x5 paper study card, which you will submit with your exam. It may be prepared in any manner you choose. The exam covers Chapters 1 - 12, 16, and 17 of our textbook, plus Internet protocols discussed in class. It is a comprehensive exam.

No electronic devices of any kind are permitted.

Expectations:

• See course goals and objectives
• See objectives at the beginning of each chapter
• See Summary at the end of each chapter
• See previous exams:

  midterm 2000 midterm #1 2005 midterm #2 2005 midterm #1 2007 midterm #2 2007 midterm #1 2008 midterm #2 2008 midterm #1 2009 midterm #2 2009 midterm #1 2010 midterm #2 2010 midterm #1 2011 midterm #2 2011 midterm #1 2012 midterm #2 2012

  midterm #1 2013 midterm #2 2013 midterm #1 2014 midterm #2 2014 midterm #1 2015 midterm #2 2015 midterm #1 2016 midterm #2 2016 midterm #1 2017 midterm #2 2017 midterm #1 2018 midterm #2 2018 midterm #1 2019 midterm #2 2019

  final A 2000 final B 2000 final 2005 final 2007 final 2008 A final 2008 B final 2008 C final 2009 Wed, Fri final 2009 solutions final 2010 final 2011 final 2012 Mon, Fri final 2013 final 2014 final 2015 final 2016 final 2017 final 2018 final 2019

See also Dr. Barnard's notes. He was using a different edition of our text, so chapter and section numbers do not match, but his chapter summaries are excellent.

In the Table of Contents or the Index to the text, can you define/explain each term?

Question: Could you send an email about what we REALLY should focus on as we prepare for the exam?

I ABSOLUTELY get it that the exam appears to you very differently from how it appears to me. You have 28 different exams to look at as examples of questions I might ask, so you are able to judge from what I DO, as well as from what I say. This year, since I am allowing you to bring a study card, there might be fewer questions taken directly from previous exams.

See what we claim as Course Goals and Objectives

Some questions are adapted from questions previous students have reported being asked about operating systems at an interview.

Of course, there will be a vocabulary question, in some form. You should AT LEAST know what each line in the Table of Contents means.

Of course, there will be a tricky C question.

I like to ask a question or two in which you apply knowledge you should know to a situation you may not have considered.

If I will ask 6 questions (you write on 5) from 12 chapters, a final examination is a random sampling process. I cannot possibly ask about everything. It may not look like it to you, but I think I try to ask primarily high level conceptual questions, not tricky, detailed questions (except for the tricky C question, which is, well, tricky).

I always am tempted to ask, "What are the five BIG CONCEPTS of operating systems? What concept would you rate as #6? Why is it not as important as the first 5?" I will NOT ask that because I do not know how to grade it fairly, but it is a question you should be able to answer.

Directions:

Read and follow the directions.

• Write on five of the six questions. Each question is worth 20 points. If you write more than five questions, only the first five will be graded. You do not get extra credit for doing extra problems.
• In the event this exam is interrupted (e.g., fire alarm or bomb threat), students will leave their papers on their desks and evacuate as instructed. The exam will not resume. Papers will be graded based on their current state.
• Read the entire exam. If there is anything you do not understand about a question, please ask at once.
• If you find a question ambiguous, begin your answer by stating clearly what interpretation of the question you intend to answer.
• Begin your answer to each question at the top of a fresh sheet of paper [or -5].
• Be sure your name is on each sheet of paper you hand in [or -5]. That is because I often separate your papers by problem number for grading and re-assemble to record and return.
• Write only on one side of a sheet [or -5]. That is because I scan your exam papers, and the backs do not get scanned.
• No electronic devices of any kind are permitted.
• Be sure I can read what you write.

Score Distribution: Median: 80; Mean: 72; N = 5

These shaded block are intended to suggest solutions; they are not intended to be complete solutions.

Problem 1 Acronyms and Definitions
Problem 2 Tricky C
Problem 3 Caching
Problem 4 UltraTiny File System
Problem 5 TCI/IP
Problem 6 Synchronization

For each acronym,

1. Give the phrase for which the acronym stands (in the context of computer operating systems)
2. Give a careful definition

If there is more than one correct answer (in the context of computer operating systems), I will accept any one correct answer.

Warning: A definition that starts "Z is when ...," or "Z is where ..." earns -5 points.

1. PCB
2. IPC
3. SJF
4. LWP
5. MUTEX
6. VFS
7. NFS
8. SCAN
9. FTP
10. TCP/IP

Worth 20 points total, 2 points per part, 0.5 - 1 for acronym, 1 - 1.5 for definition.

1. PCB - Process Control Block (p. 103): Representation of a process in the operating system.
2. IPC - Interprocess Communication (Section 3.4)
3. SJF - Shortest Job First scheduling (p. 189): The next process assigned to the CPU is the one with the shortest expected execution time.
4. LWP - Lightweight process (p. 199): Sometimes used as a synonym for a thread.
5. MUTEX - Mutual Exclusion (Chapter 6): When one process is executing in its critical section, no other process is allowed to execute in its critical section.
6. VFS - Virtual File System (p. 468): A layer in the file system interface . It separates file-system-generic operations from their implementations, and it provides a mechanism for uniquely representing a file throughout the network.
7. NFS - Network File System (p. 490): Both an implementation and a specification of a software system for accessing remote files across a network.
8. SCAN - Trick question. Not an acronym. (p. 513) The disk arm starts at one end of the disk and moves toward the other end, servicing requests as it reaches each cylinder, until it gets to the other end of the disk.
9. FTP - File Transfer Protocol (p. 676)
10. TCP/IP - Transmission Control Protocol/Internet Protocol (p. 693): Combination of a reliable, connection-oriented Transport Layer and the protocol responsible for routing IP datagrams through the Internet.

Our field is full of TLA's (Three Letter Abbreviations) that are convenient short-hand for insiders, but barriers to understanding by outsiders. We had a bad reputation in many quarters for over-use of jargon, sometimes with the intent to confuse. Don't be like that. Speak English with your stakeholders.

Consider the following code:

 1	#include <stdio.h>
 2	#include <stdlib.h>
 3	
 4	struct listnode
 5	{
 6	  int payload;
 7	  struct listnode *next;
 8	  struct listnode *prev;
 9	};
10
11	/* function prototypes */
12	int enqueue(int, struct listnode*);
13	void findpid(int, struct listnode*);
14	
15	int main() 
16	{
17	  struct listnode *head;
18	  head = (struct listnode*)malloc(sizeof(struct listnode));
19	  if (head == NULL) 
20	  { 
21	    fprintf(stderr, "Not Enough Memory!\n");
22	    exit(EXIT_FAILURE);
23	  }
24	  head->prev = NULL;
25	  head->payload = -1;
26	  head->next = NULL;
27	
28	  int pid;
29	  for (pid = 0; pid < 5; pid++)
30	    enqueue(pid, head);
31	
32	  findpid(5, head);
33	
34	  return EXIT_SUCCESS;
35	}
36	
37	int enqueue(int pid, struct listnode *head)
38	{
39	  struct listnode *current;
40	  struct listnode *newnode;
41	
42	  if (head->payload == -1) 
43	  {
44	    head->payload = pid;
45	  }
46	  else
47	  {
48	    current = head;
49	    while (current->next != NULL)
50	      current = current->next;
51	
52	    newnode = (struct listnode*)malloc(sizeof(struct listnode));
53	    if (newnode == NULL) 
54	    {
55	      fprintf(stderr, "Not Enough Memory!\n");
56	      exit(EXIT_FAILURE);
57	    }
58	    current->next = newnode;
59	    newnode->prev = current;
60	    newnode->payload = pid;
61	    newnode->next = NULL;
62	  }
63	  return pid;
64	}
65	
66	void findpid(int pid, struct listnode *head)
67	{
68	  struct listnode* current = head;
69	  while (current->payload != pid) {
70	    printf("Looking at process %d.\n", current->payload);
71	    current = current->next;
72	  }
73	  
74	  if (current->payload == pid)
75	    printf("Found process %d!\n", pid);
76	  else
77	    printf("Process %d not found.\n", pid);
78	}

1. Draw a picture of the data structure pointed to by the "head" pointer.
2. What does the program output when run as-is?
3. If working properly, the last line of output should read "Process 5 not found." Modify the source code accordingly.
   Hint: correct answers should maintain functionality for other process IDs and processes that actually are found, and not just hack it for this particular run.
4. The struct members in this code are accessed via pointers (ex. current, newnode) because the nodes are allocated dynamically with malloc. In your Xinu operating system, the queues are statically allocated.
   What is the major difference between the way struct members are accessed in these two approaches?
   Hint: What operator needs to change? To what should it be changed?

1. A sketch of a doubly linked list with 5 nodes, where head points to the first node, and the tail points to NULL.

2. Looking at process 0.
   Looking at process 1.
   Looking at process 2.
   Looking at process 3.
   Looking at process 4.
   Segmentation fault

3. See commented section of line 69. (Remove for provided code)

   69		  while (current->payload != pid && current->next != NULL) {

4. Change arrow operator (->) to (.).

1. (5 points) What is "caching?"
2. (5 points) List four different contexts in which modern computer operating systems implement caching. For each, tell what is cached and where it is cached.
3. (10 points) In what ways is caching performed in a Distributed File System similar to segmentation or to paging for memory management? In what ways is it different? Explain in detail.
   Hint: You do not know the answer. This question asks you to make a case from what you do know. I expect a detailed, technical answer, although it may be speculative.

1. Caching replicates information from a relatively distant, relatively large, relatively slow, relatively inexpensive data store in a relatively close, relatively small, relatively fast, relatively expensive data store. Caching is not the same as buffering.
2. 1. Virtual memory caches disk blocks in main memory
   2. Translation Look aside Buffer caches page table entries in a hardware TLB
   3. Hardware level 1, level 2, and sometimes level 3 caches cache information from lower levels in the memory hierarchy, level 2, level 3, and main memory, respectively.
   4. Distributed File System caches files from a remote server in a local machine's memory or disk
   5. Web browser caches files from a remote server on a local machine's disk
   6. Domain Name Service server caches (name, IP address) pairs from a remote server in a local table
3. Some thoughts:

   The point was to take what you should understand about caching in the context of memory management and apply it to the context of DFS. Can you apply what you know in a strange context?

   If locally cached files are kept on a local disk, the cache size is the free space on the local disk, so cache size probably is not a constraint. Hence, strategies for selecting a victim to be removed from the cache probably is not important.

   If locally cached files are kept in local memory, cache size may be important. Then, strategies for selecting a victim to be removed from the cache including Optimal, First In First Out, Least Recently Used, and Approximate LRU are all candidates.

   The biggest difference between segmentation and paging is that segments are different sizes (leading to external fragmentation), while each page is the same size (leading to internal fragmentation). Files are different sizes, so if we cache entire files, DFS is more like segmentation. Instead, if we cache disk blocks from remote files, each disk block (probably) is the same size, and DFS is more like paging.

   If DFS caches entire files on a local disk, the external fragmentation is handled by the local file system.

   DFS must handle writing to a cached file, just as both segmentation and paging must handle writing to a segment or a page in main memory by Write Through, Write Back, or some variant.

   DFS must maintain a table of files cached locally, which may be different from the table of open files, just as segmentation or paging systems must maintain segment tables or page tables. However, the number of open files probably is much fewer than the number of segments or pages, so the cached files table is small. File access is much less frequent than memory access, to the speed of access to cached files table is not as critical as the speed of access to the segment or page table.

The UltraTiny File System (UTFS) implemented for Project 9 could only store files containing no more than 256 bytes.

1. Explain why the UTFS design was limited to 256 byte files.
2. Extend the UTFS design to allow arbitrarily long files, provided sufficient disk space is available. Comment on trade-offs made by your design, and other limitations that would still remain.

1. File data was contained in a single block, and a disk block was 256 bytes.
2. Several possibilities. Mark off the first four bytes of each file block to be a metadata linked-list pointer to the next block of file content. This is the easiest extension to the current design, but is very inefficient for file traversal. Or, build some kind of inode-like metadata block with one-level or multi-level pointers to file data blocks. This definitely requires breaking file metadata out of the single, top-level directory block, and introduces another level of indirection for reading a file, but provides quite a bit more flexibility.

The TCP/IP "stack" consists of four layers:

1. Application (or Process) Layer
2. Transport (or Host-to-Host) Layer
3. Network (or Internet) Layer
4. Physical (or Network Access) Layer

Assume that you are the programmer of an application that expects to receive a message from some application on another machine. Some message arrives at your machine as signals in the Ethernet cable.

Describe what the TCP/IP stack does with the message from that point until it hands your program your message. How does it decide the message is for its machine? How does it decide the message is for your application? What else must it decide? What instructions must you have provided to the stack before it knows what to do with your message?

See pp. 758 - 761. Would a diagram/cartoon help?

Questions your response should answer include:

• Which level decides an incoming message is for your machine? How?
• Which level decides an incoming message should go to your application? How?
• What instructions must you have provided to the stack before it knows what to do with your message?
• What errors in the message are handled by each layer?
• "Message" is likely to consist of several ethernet packets. How are they reassembled?

Choose either column A or column B

The readers - writers problem is worth more than the dining philosophers because it received less attention in class.

Readers - Writers		Dining Philosophers
See Section 6.6.2		See Section 6.6.3 Critical sections are the manipulation of chopsticks, not eating.

 

One student asked why the entire <pick up chopsticks>, <eat>, <replace chopsticks> is not the critical section

The shared resources that must be protected by mutual exclusion are not the chopsticks. What must be protected are the global flags that tell whether a fork is available. What must be indivisible is the picking up of two chopsticks. Once a philosopher HAS his two chopsticks, he needs no protection.

What we want to prevent is the possibility of each philosophy executing exactly simultaneously:

if ( isAvailable(chopsticks[myLeft]) && (isAvailable(chopsticks[myRight]) ) {
  acquire(chopsticks[myLeft]);
  // If everyone is here simultaneously, we have deadlock
  acquire(chopsticks[myRight]);
}

THAT is the critical section.

There is no danger of a race condition when the chopsticks are returned.

If eating were considered a critical section, only one philosopher could be eating at once, a valid, but an overly restrictive design.

Hope that helps. Synchronization IS subtle in its implications.

Thank you

We (Drs. Brylow and Corliss) have enjoyed this semester, and not for the stress we may have caused you. We find operating systems exciting and useful, objects of beauty (in a strange way). We hope we have communicated some of our knowledge and excitement.

If you are graduating, congratulations! Look for us at graduation, and we hope you will keep in touch, wherever life takes you.

If you are not graduating yet, we hope to see you next year, perhaps in other classes or just in the halls of Cudahy and Haggerty.