COSC 3250 / COEN 4820 Operating Systems
Final Examination
Wednesday, May 7, 2014

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 - 7, 10 - 12, 16, and 17 of our textbook, plus Internet protocols discussed in class. 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?

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:

Average: 67

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

Several of these questions ask you to apply what you know to unfamiliar problems.

Solution outlines are likely to be refined as the exams are graded.

Problem 1 Acronyms and Definitions
Problem 2 Tricky C
Problem 3 TCP/IP Stack
Problem 4 Caching
Problem 5 Virtual Machines
Problem 6 Process 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
   ("Definition" in this context means to describe what the protocol does, not how it does it. Your "definition" is a sentence or two, not a description of how the protocol works.)

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. SSH
2. SSL
3. FTP
4. DNS
5. UDP
6. TCP
7. IP
8. ARP
9. SMTP
10. RPC
11. RFC

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

1. SSH - Secure Shell (sect. 17.2.1.1). Facility to allow users to log into a system remotely and securely. Characters are transferred bidirectionally and securely.
2. SSL - Secure Socket Layer, RFC 6101. The primary goal of the SSL protocol is to provide privacy and reliability between two communicating applications. The SSL protocol provides connection security that has three basic properties:
   1. The connection is private. Encryption is used after an initial handshake to define a secret key.
   2. The peer's identity can be authenticated using asymmetric, or public key, cryptography.
   3. The connection is reliable.
3. FTP - File Transfer Protocol (sect. 17.2.1.2), RFC 959. The objectives of FTP are
   1. to promote sharing of files (computer programs and/or data),
   2. to encourage indirect or implicit (via programs) use of remote computers,
   3. to shield a user from variations in file storage systems among hosts, and
   4. to transfer data reliably and efficiently.
   FTP, though usable directly by a user at a terminal, is designed mainly for use by programs.
4. DNS - Domain Name Service (p. 751), RFC 1034 & 1035. DNS specifies the naming structure of the hosts and name-to-address resolution.
5. UDP - User Datagram Protocol (p. 758), RFC 768. Computer applications can send messages to other hosts on an Internet Protocol (IP) network without prior communications to set up special transmission channels or data paths. UDP uses a simple transmission model with a minimum of protocol mechanism. It has no handshaking dialogues, and thus exposes any unreliability of the underlying network protocol to the user's program. As this is normally IP over unreliable media, there is no guarantee of delivery, ordering, or duplicate protection. UDP provides check sums for data integrity, and port numbers for addressing different functions at the source and destination of the datagram.
6. TCP - Transmission Control Protocol (p. 758), RFC 761. The Transmission Control Protocol is intended for use as a highly reliable host-to-host protocol between hosts in packet-switched computer communication networks, and especially in interconnected systems of such networks.
7. IP - Internet Protocol, RFC 760. The Internet Protocol is designed for use in interconnected systems of packet-switched computer communication networks. The internet protocol provides for transmitting blocks of data called datagrams from sources to destinations, where sources and destinations are hosts identified by fixed length addresses. The internet protocol also provides for fragmentation and reassembly of long datagrams, if necessary, for transmission through "small packet" networks.
8. ARP - Address Resolution Protocol (p. 760), RFC 826. The Address Resolution Protocol is a method of Converting Protocol Addresses (e.g., IP addresses) to Local Network Addresses (e.g., Ethernet addresses).
9. SMTP - Simple Mail Transfer Protocol, RFC 2821. The objective of the Simple Mail Transfer Protocol is to transfer mail reliably and efficiently. SMTP is independent of the particular transmission subsystem and requires only a reliable ordered data stream channel. An important feature of SMTP is its capability to transport mail across networks, usually referred to as "SMTP mail relaying". A network consists of the mutually-TCP-accessible hosts on the public Internet, the mutually-TCP-accessible hosts on a firewall-isolated TCP/IP Intranet, or hosts in some other LAN or WAN environment utilizing a non-TCP transport-level protocol. Using SMTP, a process can transfer mail to another process on the same network or to some other network via a relay or gateway process accessible to both networks.
10. RPC - Remote Procedure Call (sect. 3.6.2-3), RFC 5531. RPC abstracts the procedure-call mechanism for use between systems with network connections.
11. RFC - Request for Comment. Name given to the suite of Internet and related standards and protocols.

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.

/**
* Function for sending FiSh packets.
* @param dst  MAC address of destination
* @param type FiSh protocal type (see fileshare.h)
* @param load FiSh protocal payload
* @param len  FiSh protocal payload length
* @return OK for success, SYSERR otherwise.
*/
static int fishSend(uchar *dst, char type, uchar *load, int len)
{
    uchar packet[PKTSZ];    // Local buffer to build packet.
    uchar *ppkt = packet;   // Pointer for working with packet.
    int i = 0;

    // Copy destination address to start of packet.
    ppkt = dst;
    // Source: Get my MAC address from the Ethernet device.
    control(ETH0, ETH_CTRL_GET_MAC, (long)ppkt, 0);
    ppkt += ETH_ADDR_LEN;
    // Convert "3250" packet protocol to big-endian.
    *ppkt++ = ETYPE_FISH >> 8;
    *ppkt++ = ETYPE_FISH >> 16;
    // Place FiSh packet type byte.	
    *ppkt++ = type;
    // Copy payload.
    for (i = 0; i < len; i++)
    {   ppkt = load;   }
    // Write to Ethernet device.
    write(ETH0, packet, ETHER_MINPAYLOAD);
    return OK;
}

Errors include:

1. Packet buffer is not initialized (usually with bzero).
2. Destination address (6 bytes) cannot be copied with a single assignment -- requires a loop or helper function.
3. Assignment to ppkt overwrites pointer, rather than copying data to the contents.
4. Assignment to ppkt does not update pointer location.
5. ETYPE_FISH >> 16 does not correctly reverse byte order.
6. Copy loop does not copy payload, or increment either pointer.
7. Payload is not padded.
8. Size passed to write() is incorrect, and unrelated to true payload size.

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 wants to receive a message from some application on another machine.

Describe what the TCP/IP stack does with your message from the point at which you make the operating system call recv(...) until that function call returns control to your application.

A good answer addresses

1. API: What must recv(...) pass in?
2. Device driver does ...
3. Physical layer does ...
4. Network layer does ...
5. Transport layer does ...
6. Application layer does ...
7. API: What must recv(...) return?

A good answer surely includes a diagram of the stack.

Several students instead answered the question for send(), which appeared on a previous year's exam.

1. What is caching, in the context of computer operating systems?
2. List four different contexts in which caching is a possible solution
3. What are the advantages of caching?
4. What are the disadvantages of caching?

1. Keeping a local copy of remote information. Your solution should reflect in some way the "memory hierarchy." Cache storage is close, fast, small, and expensive. Remote storage is farther away, slower, larger, and more expensive.
2. Memory <--> disk, OS disk directories <--> on-disk disk directories, disk files, local disk files <--> remote disk files, domain name service, TLB <--> in-memory page table, browser or gateway can cache web pages
3. Speed, reduced bus/network traffic. Advantages means more than one.
4. Consistency, coherency, cost, complexity of hardware and OS, small size, slower on a miss than direct access. Disadvantages means more than one.

See chapters on memory, files, distributed systems. Chapter 1 has a summary.

-4 if all your examples are memory caching of disk, which I would consider one context.

Caching as an aspect of virtual memory or networking, but it is not the same. Caching does not provide a larger address space, for example, although it enables virtual memory to do so.

1. Describe the three types of traditional virtualization.
2. Describe four benefits of virtualization.
3. Give an example of an application for which virtualization is an attractive solution. Why is virtualization attractive for that application?
4. Describe four disadvantages of virtualization.
5. Give an example of an application for which virtualization is not an attractive solution. Why is virtualization not attractive for that application?

See problems 16.3 and 16.1, p. 738. See Sect. 16.1 - 3.

1. See p. 712:
   • Type 0: Hardware & firmware-based
   • Type 1: Operating-system-like software, e.g., VMware ESX, Citrix XenServer (see How it works)
   • Type 2: Run as applications on standard OS but provide VMM features to guest OS, e.g., VMware Workstation

    

2. Benefits include:
   • Host system is protected from the virtual machines
   • Virtual machines are protected from each other
   • Cost, performance
   • Single (few) powerful machines
   • Run whatever OS & application you need
   • Run old OS's
   • Lower system administration
   • Load balancing
   • VM's can be protected from known security holes
   • Developer can test on multiple platforms
   • Development vs. production
   • Especially OS development
3. ?
4. Disadvantages include:
   • Might prevent sharing
   • Cost, performance
5. Certainly real-time and embedded systems are poor candidates.

Background:

Suppose we have an atomic operation TestAndSet(), which works as if it were implemented by pseudocode such as (Figure 6.4 from our text)

     boolean TestAndSet(boolean *target) {
        boolean rv = *target;
        *target = TRUE;
        return rv;
     }

The function BoundedWaitingMutualExclusion (pseudocode adapted from Figure 6.8 from our text) claims to solve the critical-section problem:

  1: 
  2: 
  3: 
  4: 
  5: 
  6: 
  7: 
  8: 
  9: 
  
 10: 
 
 11: 
 12: 
 
 13: 
 
 14: 
 15: 

  void BoundedWaitingMutualExclusion(int i, int j, int n) {
     boolean key;
     while (TRUE) {
         waiting[i] = TRUE;
         key = TRUE;
         while (waiting[i] && key) { key = TestAndSet(&lock); }
         waiting[i] = FALSE;
         {
             // CRITICAL SECTION - ASSUME INTERRUPT
         }
         j = (i + 1) % n;
         while ( (j != i) && !waiting[j] ) { j = (j + 1) % n; }
         if (j == i) { lock = FALSE; }
         else {waiting[j] = FALSE; }
         {
             // REMAINDER SECTION
         }
     }
  }

We have two processes which share memory. Each calls BoundedWaitingMutualExclusion():

   #define N 2
   boolean waiting[N];  // Assume initialized all FALSE
   boolean lock = FALSE;

 1: 
 2: 
 3:  

 #define ME 0
 int j = 0;
 BoundedWaitingMutualExclusion(ME, j, N); 

 1: 
 2: 
 3:  

 #define ME 1
 int j = 1;
 BoundedWaitingMutualExclusion(ME, j, N); 

Questions:

1. A solution to the critical-section problem must satisfy what requirements? List them.
2. At BoundedWaitingMutualExclusion() line 6, what is the purpose of the while(...) loop?
3. At BoundedWaitingMutualExclusion() line 10, what is the purpose of the while(...) loop?
4. Assuming Process Alice runs first, step carefully through the execution until each process has completed one pass through its critical section. Show values at each step for all local and all shared variables. Assume a context swap occur in the middle of the CRITICAL SECTION and that any busy waiting eventually is interrupted for a context swap.

Hint: The answer to part d) might have the form:

Name _______________________

Worksheet for Problem 6

1. (4 points) See page 228 or 230. We must show that
   • Mutual exclusion is preserved;
   • The progress requirement is satisfied; and
   • The bounded waiting requirement is met.
   "No busy waiting" is NOT a requirement. Busy waiting is a concern for performance, not for correct functioning.

    

2. (3 points) Wait until no other process is in its critical section AND it is this process's turn among those waiting. Enforces Mutual Exclusion and Bounded Waiting.

    

3. (3 points) Cycle through waiting processes. The loop cycles through non-waiting processes, stopping at a waiting process. The result is to set the index to the next waiting process. The purpose is to prevent the same process from re-entering its critical section repeatedly, starving an unlucky process is waiting, but never gets the CPU when the way is clear. Enforces Bounded Waiting.

    

4. (10 points) Details of your answer depend on when you let context swaps occur. See the discussion on pages 233 - 234. In grading, I was more concerned with whether you followed what the code does than with whether you interrupted exactly when I intended. If you interrupted Process Alice during her CRITICAL SECTION and then ran Process Bob until he encountered a busy wait, you were more likely to discover what the loop at line 10 is doing.

   See this simulation app that lets you step through this code.

   One scenario is:

Process Alice				Shared		Process Bob
Code line	i	j	key	waiting	lock	Code line	i	j	key
A 2:		0		[F, F]	F
BWME(0, 0, 2)	0	0		[F, F]	F
BWME 3: (T)	0	0		[F, F]	F
BWME 4:	0	0		[T, F]	F
BWME 5:	0	0	T	[T, F]	F
BWME 6: (T & T) => T	0	0	F	[T, F]	T	Note: Line 6 is executed twice
BWME 6: (T & F) = > F	0	0	F	[T, F]	T
BWME 7:	0	0	F	[F, F]	T
BWME 8: CRITICAL	0	0	F	[F, F]	T
context swap
				[F, F]	T	B 2:		0
				[F, F]	T	BWME(1, 0, 2)	1	0
				[F, F]	T	BWME 3: (T)	1	0
				[F, T]	T	BWME 4:	1	0
				[F, T]	T	BWME 5:	1	0	T
				[F, T]	T	BWME 6: (T & T) => T	1	0	T
				[F, T]	T	BWME 6: (T & T) => T	BUSY WAIT until
context swap
BWME 8: CRITICAL	0	0	F	[F, T]	T
BWME 9:	0	1	F	[F, T]	T
BWME 10: (T & F) => F	0	1	F	[F, T]	T
BWME 11: (F)	0	1	F	[F, T]	T
BWME 12:	0	1	F	[F, F]	T
BWME 13: REMAINDER	0	1	F	[F, F]	T
BWME 3: (T)	0	1	F	[F, F]	T
BWME 4:	0	1	F	[T, F]	T
BWME 5:	0	1	T	[T, F]	T
BWME 6: (T & T) => T	0	1	T	[T, F]	T
BWME 6: (T & T) => T	Forced to take turns BUSY WAIT until			[T, F]	T
context swap
				[T, F]	T	BWME 6: (F & T) => F	1	0	T
				[T, F]	T	BWME 7:	1	0	T
				[T, F]	T	BWME 8: CRITICAL	1	0	T
context swap
BWME 6: (T & T) => T	Forced to take turns BUSY WAIT until			[T, F]	T
context swap
Your solution could end here after 1 complete CRITICAL SECTION in each process				[T, F]	T	BWME 9:	1	1	T
				[T, F]	T	BWME 10: (F & T) => F	1	1	T
				[T, F]	F	BWME 11: (T)	1	1	T
				[T, F]	F	BWME 13: REMAINDER	1	1	T
context swap
BWME 6: (T & T) => T	0	1	F	[T, F]	T
BWME 6: (T & F) => F	0	1	F	[T, F]	T
BWME 7:	0	1	F	[F, F]	T
BWME 8: CRITICAL	0	1	F	[F, F]	T
etc.

Thank you

We (Drs. Brylow and Corliss) have enjoyed this semester, and not for the stress we may have cause 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.