COSC 3250 / COEN 4820 Operating Systems
Final Examination
Wednesday, May 9, 2018, 10:30 - 12:30

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
• Read, understand, explain, and desk-check C programs
• 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

Section and page number references in old exams refer to the edition of the text in use when that exam was given. You may have to do a little looking to map to the edition currently in use. Also, which chapters were covered on each exam varies a little from year to year.

Questions may be similar to homework questions from the book. You will be given a choice of questions. I try to ask questions I think you might hear in a job interview. "I see you took a class on Operating Systems. What can you tell me about ...?"

Preparation hints:

Read the assigned chapters in the text. Chapter summaries are especially helpful. Chapters 1 and 2 include excellent summaries of each of the later chapters.

Read and consider Practice Exercises and Exercises at the end of each chapter.

Review authors' slides and study guides from the textbook web site

Review previous exams listed above.

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.

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

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.
• 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.
• 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.
• If I ask questions with parts

  1. . . .
  2. . . .

  your answer should show parts

  1. . . .
  2. . . .

• Someone should have explained to you several years ago that "X is when ..." or "Y is where ..." are not suitable definitions (possibly excepting the cases in which X is a time or Y is a location). "X is when ..." or "Y is where ..." earn -5 points.
• The instructors reserve the right to assign bonus points beyond the stated value of the problem for exceptionally insightful answers. Conversely, we reserve the right to assign negative scores to answers that show less understanding than a blank sheet of paper. Both of these are rare events.

The university suggests exam rules:

1. Silence all electronics (including cell phones, watches, and tablets) and place in your backpack.
2. No electronic devices of any kind are permitted.
3. No hoods, hats, or earbuds allowed.
4. Be sure to visit the rest room prior to the exam.

In addition, you will be asked to sign the honor pledge at the top of the exam:

"I recognize the importance of personal integrity in all aspects of life and work. I commit myself to truthfulness, honor and responsibility, by which I earn the respect of others. I support the development of good character and commit myself to uphold the highest standards of academic integrity as an important aspect of personal integrity. My commitment obliges me to conduct myself according to the Marquette University Honor Code."

Name ________________________   Date ____________

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

Problem 1 Internet protocols
Problem 2 User vs. kernel mode execution
Problem 3 Tricky C
Problem 4 Process creation and termination
Problem 5 Networking
Problem 6 Virtual machines

Here are acronyms for several protocols from the Internet protocol suite. For each protocol, give
i) What does the acronym stand for?
ii) What is the purpose of that protocol?

1. ARP
2. NDP
3. IP
4. ICMP
5. TCP
6. UDP
7. DCCP
8. RSVP
9. SFTP
10. TLS/SSL
11. DNS

Taken from the handout for the skits:

1. ARP - Address Resolution Protocol, RFC 826
   ARP is a "communication protocol used for discovering the link layer address, such as a MAC address, associated with a given network layer address, typically an IPv4 address." -- Address_Resolution_Protocol (Wikipedia)

    

2. NDP - Neighbor Discovery Protocol operates with IPv6 "at the Network Layer of the Internet model and is responsible for gathering various information required for internet communication, including the configuration of local connections and the domain name servers and gateways used to communicate with more distant systems." -- Neighbor Discovery Protocol (Wikipedia)

    

3. IP - Internet Protocol, RFC 791 (IPv4) and , RFC 2460 (IPv6)
   "IP is the principal communications protocol in the Internet protocol suite for relaying packets across network boundaries. Its routing function enables internetworking, and essentially establishes the Internet. IP has the task of delivering packets from the source host to the destination host solely based on the IP addresses in the packet headers. For this purpose, IP defines packet structures that encapsulate the data to be delivered. It also defines addressing methods that are used to label the datagram with source and destination information." -- Internet Protocol (Wikipedia)

    

4. ICMP - Internet Control Message Protocol, RFC 792 (v4) and RFC 4884 (v6)
   "ICMP is used by network devices, including routers, to send error messages and operational information indicating, for example, that a requested service is not available or that a host or router could not be reached." -- Internet Control Message Protocol (Wikipedia)

    

5. TCP - Transmission Control Protocol, RFC 793
   "TCP provides reliable, ordered, and error-checked delivery of a stream of octets (bytes) between applications running on hosts communicating via an IP network." -- Transmission Control Protocol (Wikipedia)

    

6. UDP - User Datagram Protocol, RFC 768
   "With UDP, computer applications can send messages, in this case referred to as datagrams, to other hosts on an Internet Protocol (IP) network. Prior communications are not required in order to set up communication channels or data paths. UDP uses a simple connectionless communication model with a minimum of protocol mechanism. UDP provides checksums for data integrity, and port numbers for addressing different functions at the source and destination of the datagram. It has no handshaking dialogues, and thus exposes the user's program to any unreliability of the underlying network; There is no guarantee of delivery, ordering, or duplicate protection. " -- User Datagram Protocol (Wikipedia)

    

7. DCCP - Datagram Congestion Control Protocol, RFC 43366 and RFC 4340
   "DCCP implements reliable connection setup, teardown, Explicit Congestion Notification (ECN), congestion control, and feature negotiation." -- Datagram Congestion Control Protocol (Wikipedia)

    

8. RSVP - Resource Reservation Protocol, RFC 2205
   "RSVP is a transport layer protocol designed to reserve resources across a network for quality of service (QoS) using the integrated services model. RSVP operates over an IPv4 or IPv6 and provides receiver-initiated setup of resource reservations for multicast or unicast data flows. It does not transport application data but is similar to a control protocol, like Internet Control Message Protocol (ICMP) or Internet Group Management Protocol (IGMP). RSVP can be used by hosts and routers to request or deliver specific levels of QoS for application data streams or flows. RSVP defines how applications place reservations and how they can relinquish the reserved resources once no longer required. RSVP operation will generally result in resources being reserved in each node along a path. RSVP is not a routing protocol and was designed to interoperate with current and future routing protocols." -- Resource Reservation Protocol (Wikipedia)

    

9. SFTP - SSH File Transfer Protocol or Secure File Transfer Protocol
   "SFTP is a network protocol that provides file access, file transfer, and file management over any reliable data stream. It was designed by the Internet Engineering Task Force (IETF) as an extension of the Secure Shell protocol (SSH) version 2.0 to provide secure file transfer capabilities. This protocol assumes that it is run over a secure channel, such as SSH, that the server has already authenticated the client, and that the identity of the client user is available to the protocol." -- SSH File Transfer Protocol (Wikipedia)

    

10. TLS/SSL - Transport Layer Security / Secure Sockets Layer, RFC 6101 and RFC 5246
    "TLS is a cryptographic protocol that provides communications security over a computer network. Several versions of the protocols find widespread use in applications such as web browsing, mail, instant messaging, and voice over IP (VoIP). Websites are able to use TLS to secure all communications between their servers and web browsers. The TLS protocol aims primarily to provide privacy and data integrity between two communicating computer applications." -- Transport Layer Security (Wikipedia)

     

11. DNS - Domain Name System, RFC 1034 and RFC 1035
    "DNS is a hierarchical decentralized naming system for computers, services, or other resources connected to the Internet or a private network. It associates various information with domain names assigned to each of the participating entities. Most prominently, it translates more readily memorized domain names to the numerical IP addresses needed for locating and identifying computer services and devices with the underlying network protocols. By providing a worldwide, distributed directory service, the Domain Name System is an essential component of the functionality on the Internet, that has been in use since 1985. The Domain Name System delegates the responsibility of assigning domain names and mapping those names to Internet resources by designating authoritative name servers for each domain. Network administrators may delegate authority over sub-domains of their allocated name space to other name servers. This mechanism provides distributed and fault tolerant service and was designed to avoid a single large central database." -- Domain Name System (Wikipedia)

     

    Also might have asked about:

12. Ethernet
13. SCTP - Stream Control Transmission Protocol
14. FTP - File Transfer Protocol
15. FTPS - FTP Secure
16. SSH - Secure Shell
17. HTTP - Hypertext Transfer Protocol
18. HTTPS: HTTP over TLS
19. LDAP - Lightweight Directory Access Protocol
20. and several more

No, you are not expected to have memorized the RFC numbers.

1. What is user mode execution?
2. What is kernel mode execution?
3. Do you think the Raspberry Pi has kernel mode instructions? Why, or why not?
4. In your tiny file system assignment, you use operating system calls to retrieve contents of directories, retrieve statistics of files, open and close files, read and write files. Which are probably executed in user mode? Which are probably executed in kernel mode? Why?

See Section 1.5.1. The distinction is at the level of individual instructions, or blocks of instructions, not at the process or thread level. It is not the case that kernel processes run in kernel mode and user processes run in user mode. What users write is executed in user mode, but much of the code in many system calls is executed in user mode, too. Kernel mode is one means of enforcing certain types of mutual exclusion.

Alternative view: All system calls are executed in kernel mode.

Compromise: Most system calls that are made from user programs are high-level system calls which execute in user mode, except when they make low-level system calls to manipulate OS data structures or resources. The low level calls execute in kernel mode.

1. Normal or default level of privilege. The operating system enforces restrictions on operations and references. Rule of thumb: If the data structure being manipulated is stored in the address space of a single process, its manipulation is done in user mode.
2. Allows execution of privileged instructions which might interfere with other users. User processes are switched to kernel mode for critical operations, especially the manipulation of OS tables. Rule of thumb: If the data structure being manipulated is stored in the address space of the OS (or is shared by several processes), its manipulation is done in kernel mode.
3. Dennis: I'm certain it does, although we have not needed to make use of it thus far.
4. Dennis: Everything in the Embedded Xinu variant we use for class executes in kernel mode. Transitioning to user mode on most modern hardware requires at least setting up the MMU to provide memory protection -- at least to delineate what user mode can touch and what it cannot -- even if we aren't providing full-on virtual memory. To keep things simpler for the students, we just keep it all in kernel mode all the time.
   We've implemented user mode in full research versions of Embedded Xinu for the MIPS routers, including all of the API necessary for safe system calls into kernel mode for the key O/S services. We haven't bothered to port this part forward to the RasPi/ARM platform yet, but we set the Xinu kernel to boot in kernel mode on the Pis because you can't really do any of the device drivers if you don't.

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. What action or event causes a new process to be created?
2. List at least five actions the operating system must accomplish to create a new process.
   Hint: You might answer with high-level pseudo-code.
3. List at least four actions or events that cause an existing process to terminate.
4. List at least five actions the operating system must accomplish when it terminates an existing process.
   Hint: You might answer with high-level pseudo-code.

Does this sound like Assignment 4? It should.

1. (4 points) Call to fork()
2. (7 points) fork() must create a new process:
   • Assign space for a Process Control Block (PCB) in the memory space of the operating system;
   • Insert the PCB for the new process in the Ready list;
   • Assign appropriate values to fields in the PCB;
   • Allocate memory space for the process;
   • Copy contents of the memory space of the current process to the memory space allocated for the new process,
     OR
     Load the memory space for the new process with its executable (probably from disk);
   • Set the Program Counter in the PCB to the address to which fork() should return,
     OR
     Set the Program Counter in the PCB to the address at which execution of the new image should begin;
   • Return to executing the current process at the address to which fork() should return. In principle, fork() could call the scheduler() to pick the next process to run, but in practice, it returns control to the calling process just as any normal function does.
3. (7 points) Causes of termination include:
   1. The process terminates itself with a call to exit().
   2. The process terminates itself by finishing normally. A well-behaved process always calls exit(), but the operating system must clean up after non-well-behaved processes what finish normally without calling exit().
   3. The process terminates itself by finishing abnormally (crashing). The operating system must clean up after non-well-behaved processes what crash without calling exit().
   4. Another process kill()'s the process in question.
   5. Operating system kill()'s the process in question.
   6. Operating system shuts down or crashes.
4. (7 points) Essentially, reverse the actions of fork():
   • Close any open files;
   • Release memory allocated to this process;
   • Release any other resources allocated to this process;
   • Notify any processes that might be waiting to this process to do something (e.g., send a message, terminate);
   • Remove this PCB from Running, Waiting, or Ready lists;
   • Mark PCB memory space as available for re-use;
   • Which process executes next?

      

   • A terminating process does not return a value, nor does it report to a user. If it wanted to report, it should have done that before it terminated.

Do not exaggerate the presence of "the user." In many systems, there is no user.

What is this table about?

Application	HTTP, FTP, ...
Transport	UDP, TCP, ...
Network	IPv4gram, ARPgram, ...
Data/Physical	Ethergram, ...

Hint: You should give a 1-2 page discussion, similar to what you might say at a job interview. Points you might explain include:

• Collectively, what is the first column?
• What have those four/five terms to do with computer operating systems?
• What is the purpose of each of those four layers?
• Explain that the second column includes some examples (there may be many other examples) of what one might do at that layer.
• Which parts of Problem 1 fit into this table? Where?
• You might explain examples given here that are not already covered in Problem 1.
• Why should you (in your role as you) pay attention to this table?
• Anything else you'd like to add?

This table comes from Dennis's ping supplement lecture. It represents the TCP/IP protocol stack. See Fig. 17.8 and Section 17.6.

You might talk about why at least some of the protocols in column two belong to the layer in which they are placed.

Our book says: "With a virtual machine, guest operating systems and applications run in an environment that appears to them to be native hardware and that behaves to them as the native hardware would but that also protects, manages, and limits them." -- Text, p. 711

For each part
i) Explain what that means,
ii) Give an example, and
iii) Suggest how it might be implemented
[iv) What might be hard to achieve the ideal?]

1. "Run in an environment that appears to them to be native hardware"
2. "Behaves to them as the native hardware would [behave]"
3. "Protects them"
4. "Manages them"
5. "Limits them"

I expect a summary of the main points of Chapter 16.

1. "Run in an environment that appears to them to be native hardware"
2. "Behaves to them as the native hardware would [behave]"
   Hard parts include assembly instructions, interrupts, peripherals
3. "Protects them"
   Keep out intruders from host OS side
4. "Manages them"
   E.g., how does virtual memory work? Where is the guest's disk? Printer? Network?
5. "Limits them"
   Prevents guest OS & applications from interacting with host.

These pictures come from Dennis's ping supplement lecture.

Figure 4.1		Figure 4.2
Figure 4.3		Figure 4.4
Figure 4.5		Figure 4.6

Tell their story.