COSC 3250 / COEN 4820 Operating Systems
Final Examination, May 14, 2010

May we take the final exam early? No.

Your final examination will appear here.

It will be a two hour, closed book exam. It covers Chapters 1 - 12, 16, and 17. We have covered some material from Chapters 14, 15, and 19 that might illustrate points you want to make, but I will not explicitly ask questions from those chapters. It is a comprehensive exam, with at least half the questions coming from material since the second midterm 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?

On the final exam, any definition of the form "ZZZ is when ..." looses half the available points, unless ZZZ refers to a time.

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.
• 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 I can read what you write.
• Write only on one side of a sheet.
• Be sure your name is on each sheet of paper you hand in. [Or -5]

Score Distribution:

Problem 1 Acronyms and Definitions

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.

Problem 2 Caching

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.

Problem 3 Tricky C program

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

Problem 4 UltraTiny File System

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. Comment on tradeoffs 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.

Problem 5 Device Drivers

Recently, I received the following email from Uniblue <newsletter@unibluenews.com>:

...2...3... all PC drivers updated! Unless you update your drivers regularly the odds are that your PC will be slower and more likely to crash, or will have problems connecting with peripherals. Since a normal PC has about 100 drivers, updating them manually is a time consuming hassle you don't need. Luckily there is a quick 3 step solution called DriverScanner. Download DriverScanner and run a free scan. With only a few clicks you'll quickly be able to see the status of your drivers and know which need updating. Download all updates with one click and install them from the same screen. Um...? That's it! Now you'll be able to enjoy: Updated drivers and an optimized PC Continuous driver update management The power of a safe, simple and trusted driver update utility "DriverScanner is a "Must Have Application" and I'm awarding it the Tucows Editors Choice Award for Excellence. This is a program that is useful for every computer user. Give it a try, it has my highest recommendation." Dr File Finder, Tucows.com Identify your PC's outdated drivers Click here for a FREE diagnostic scan

Advise me. Is this legitimate? Is it a scam or a phishing scheme? Does it address a genuine operating system concern? What is it really offering? Should I try it? Should I buy it? Most importantly: Justify your advice.

Hint: Your answer should demonstrate an understanding of computer operating systems. This is not an opportunity for philosophical BS.

Advice: Probably OK. Probably legitimate. Probably little value.

What is a "device driver?" Some device drivers are provided by the operating system, and some are provided by special hardware, e.g., camera.

Yes, the operating system includes many device drivers to allow the operating system to talk to various devices and peripherals.

Yes, device drivers release updated drivers, sometimes to improve performance, sometimes to fix errors.

However, it is rare for device performance to deteriorate. If it worked before, it probably continues to work about as well. The exception must be device-device interference. That can happen, but it is rare. PC's may seem to run slower as time goes by, but it is not likely that device drivers are at fault.

Uniblue is a reputable vendor; I run some of their utilities. That is how I got on their mailing list.

Tucows is a highly respected authority, but I might check whether Tucows really said that about DriverScanner.

I expected a bit more insight about device drivers than I got. I got more advice about protection than I expected.

I did not bite on this offer, primarily because I don't think I need it.

 

In your answer, I did not care whether you said, "Yes," or "No." Did you demonstrate any understanding of operating systems?

Problem 6 Synchronization

Choose either column A or column B

The readers - writers problem is worth more than the dining philosophers because I suspect you are less likely to know the answers.

Readers - Writers		Dining Philosophers
See Section 6.6.2		See Section 6.6.3