COSC 3250 / COEN 4820 Operating Systems
Final Examination
Wednesday, May 11, 2016

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, 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:

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.

Results on exam 1 suggest you may wish to maintain a vocabulary list.

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.
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 university suggests exam rules:

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

On exam 1, we had an instance of at least one student using a prohibited aid, so for this exam, you will put all bags, coats, electronics, purses, bulky hoodies, and anything else we judge capable of concealing a prohibited aid across the front of the classroom when you enter. Sorry, but collectively, you earned this level of intrusion. I assume you have worked hard to prepare for this exam; you should not need to compete with students who cheat.

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 ____________

Score Distribution:

Histogram of scores

Median: 68; Mean: 70.4; Standard Deviation: 15.9

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

Problem 1 Definitions
Problem 2 Tricky C - Threads
Problem 3 Memory Management
Problem 4 Network Structure
Problem 5 Process Migration
Problem 6 Stream-based and Message-based Internet Communication Paradigms

Problem 1 Definitions

Give careful definitions for each term (in the context of computer operating systems):

Operating system
System boot
IPC
Monitor (in the context of cooperating processes)
Deadlock detection
Segmentation (in the context of memory management)
Copy-on-write (in the context of virtual memory)
NFS
Robustness (in the context of a distributed computer/operating system)
File naming (in the context of a distributed file system)

(2 points each) The first nine terms are section titles; these are not obscure.

Operating system (Section 1.1): An operating system is the program most intimately involved with the hardware. It manages resources including CPU time, memory, files, I/O devices, and communication. It manages the execution of user programs.

System boot (Section 2.10): Describe the sequence of events that precedes execution of user programs.

IPC (Section 3.4): Interprocess Communication - How can cooperating processes communicate? Shared memory or message passing.

Monitor (Section 5.8): An abstract data type that provides operations with mutual exclusion. Only one operation belonging to a monitor may be executing at once.

Deadlock detection (Section 7.6): We can determine that a set of processes is experiencing deadlock by examining the resource allocation graph. "Deadlock detection detects deadlocks" is circular (-2).

Segmentation (Section 8.4): A logical address space is a collection of segments, usually of varying sizes. That programmer specifies a memory address as a segment and an offset. Segments are copied from disk into working memory on demand. Segmentation is similar to paging, except that segments have varying sizes, making in-memory bookkeeping more difficult.

Copy-on-write (Section 9.3): When an in-memory page is modified, it is immediately written back to disk.

NFS (Section 12.8): Network File System - General term for apparent integration of files on one or more remote machines with the local host file system.

Robustness (Section 17.7): A distributed system may suffer from various types of hardware failure. A robust system must a) detect failures, b) reconfigure the system so that computation can continue, and c) recover when the failure is repaired.

File naming (in the context of a distributed file system) (Section 17.9.1): Naming is a mapping between logical and physical files, wherever they are located.

Problem 2 Tricky C - Threads

Consider this C program:

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

int value;
FILE *LOGFILE;

void *runner(void *param) {
    int a = 19;
    value = 3;

    printf("Line A: Value = %d; a = %d\n", value, a);
    fprintf(LOGFILE, "Line A: Value = %d; a = %d\n", value, a);
    value = value + value;
    printf("Line B: Value = %d; a = %d\n", value, a);
    fprintf(LOGFILE, "Line B: Value = %d; a = %d\n", value, a);

    pthread_exit(0);
}


int main(void) {
    int a = 17;
    value = 5;
    pthread_t tid;
    pthread_attr_t attr;
    
    LOGFILE = fopen("prob3_4.log", "w");  /* Open file for write */
    fprintf(LOGFILE, "Problem 3.4 log:\n\n");  /* Write to file  */
    
    pthread_attr_init(&attr);
    pthread_create(&tid, &attr, runner, NULL);   /* Creates and STARTS thread */
 
    printf("Line C: Value = %d; a = %d\n", value, a);
    fprintf(LOGFILE, "Line C: Value = %d; a = %d\n", value, a);
    pthread_join(tid, NULL);                     /* Waits for thread to finish */
    printf("Line D: Value = %d; a = %d\n", value, a);
    fprintf(LOGFILE, "Line D: Value = %d; a = %d\n", value, a);

    fclose(LOGFILE);  /* Close file */
    exit(0);
}

What is printed on the screen?
Explain your answer to a)
What is in the log file?
Explain your answer to part c)

Hint: The purpose of this question is to examine your understanding. I guarantee that I have run this code, but it may not illustrate the best coding practices. Do not let me trick you.

The issues you must address are:

What is shared?

What is not shared?

In what order do events happen?

Note well: I warned you this is a trick question. The fundamentally correct answer is, "I don't know exactly, but here is what I do know ..."

Line A (3, 19) prints before Line B (6, 19)
Line C (5, 17) prints before Line D (6, 17)
Line D prints after runner completes
You can make no assumptions about which thread runs first.
You can make no assumptions about when each thread may be interrupted.

int a is local to each thread
value is shared, so change in runner is reflected in main

Probably same as screen

You can make no assumptions about when each thread may be interrupted.
Threads SHARE global variables, which include file control block information.

When I ran this program on my Mac, here is what I happened to get. It represents a correct answer, but I do NOT consider this the correct answer.

Output:
make asThread
gcc -o prob3_4asThread prob3_4asThread.c
./prob3_4asThread 7
Line C: Value = 5; a = 17
Line A: Value = 3; a = 19
Line B: Value = 6; a = 19
Line D: Value = 6; a = 17
     
prob3_4.log:
Problem 3.4 log:
 
Line C: Value = 5; a = 17
Line A: Value = 3; a = 19
Line B: Value = 6; a = 19
Line D: Value = 6; a = 17

Problem 3 Memory Management

Suppose you are managing one Mb of contiguous storage. For the purposes of this problem, you may assume 1 Kb means 2¹⁰, and 1 Mb means 2²⁰. Your memory manager begins in the state with Block 0 holding 400 Kb and Block 1 holding 100 Kb at the locations shown in the table below. Your memory manager receives the following sequence of pseudo code malloc and free requests:

Block 2 = malloc (200 Kb);
Block 3 = malloc (100 Kb);
free (Block 2);
free (Block 0);
Block 4 = malloc (200 Kb);
Block 5 = malloc (200 Kb);
Block 6 = malloc (400 Kb);
free (Block 1);
free (Block 4);
Block 7 = malloc (100 Kb);
free (Block 5);
free (Block 3);
Block 8 = malloc (100 Kb);
free (Block 6);
Block 9 = malloc (500 Kb);

a) Assume that you are using a WORST FIT algorithm, with ties broken in favor of LOWER memory addresses. Assume we do no memory defragmentation/compaction.

Complete the following table for requests 4 - 15, showing where each block is placed in memory using WORST FIT:

Complete your work in this table and hand in this exam paper.

Start

100Kb

200Kb

300Kb

Block 0

400Kb

500Kb

600Kb

700Kb

800Kb

900Kb

1 Mb

Block 1

List any other assumptions you make.

b) Assume that you are using a BEST FIT algorithm, with ties broken in favor of LOWER memory addresses. Assume we do no memory defragmentation/compaction.

Complete the following table for requests 4 - 15, showing where each block is placed in memory using BEST FIT:

Hint: Think about why these two tables do not start out the same.

Complete your work in this table and hand in this exam paper.

Start

100Kb

200Kb

300Kb

Block 0

400Kb

500Kb

600Kb

700Kb

800Kb

900Kb

nbsp;

1 Mb

Block 1

List any other assumptions you make.

c) What do you conclude from this exercise?

a) Assume adjacent free blocks are collected into one.
Assume we do not do defragmentation (move blocks around to combine small free blocks).
Here is what I get:

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

100Kb B3 B3 B3 B3 B3 B3 B3 B3 B3 B3

200Kb B4 B4 B4 B4 B7 B7 B7 B7 B7 B7

300Kb Block 0 B0 B0 B0 B8 B8 B8

400Kb B5 B5 B5 B5 B5 B9

500Kb

600Kb B6 B6 B6 B6 B6 B6 B6

700Kb B2 B2

800Kb

900Kb

1 Mb Block 1 B1 B1 B1 B1 B1 B1 B1

This problem can become a mess if you make a mistake early.

b) At step 1, the WORST fit for Block 2 is at 700 Kb, while the BEST fit is at 100 Kb.

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

100Kb B2 B2 B5 B5 B5 B5 B5 B9

200Kb

300Kb Block 0 B0 B0 B0 B6 B6 B6 B6 B6 B6 B6

400Kb

500Kb

600Kb

700Kb B3 B3 B3 B3 B3 B3 B3 B3 B3 B3 B8 B8 B8

800Kb B4 B4 B4 B4 B7 B7 B7 B7 B7 B7

900Kb

1 Mb Block 1 B1 B1 B1 B1 B1 B1 B1

In contrast, FIRST FIT looks like:

Start 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ...

100Kb B2 B2 B4 B4 B4 B4 B7 B7 B7 B7 B7 B7 B7 B7 B7 B7 B7

200Kb B6 B6 B6 B6 B6 B6 B6

300Kb Block 0 B0 B0 B0 B5 B5 B5 B5 B5

400Kb

500Kb

600Kb B8 B8 B8 B8 B8 B8 B8 B8

700Kb B3 B3 B3 B3 B3 B3 B3 B3 B3 B3

800Kb

900Kb

1 Mb Block 1 B1 B1 B1 B1 B1 B1 B1

At step 7, we do not have a 400 Kb contiguous block as requested, so we make that request wait until step 11, when we have a large enough free space. Then, we do NOT free Block 6 at step 14; we allow it to run for 7 steps, and free it at step 18.

At step 15, we do not have a 500 Kb contiguous block as requested, so we must make the request to allocate Block 9 wait. Even after Block 6 is freed at step 18 and we have 8 free blocks, we do not have a 500 Kb contiguous block as requested, so the request for Block 9 must wait.

In the scenario given here, the request for Block 9 is starved until either Block 7 or Block 8 are freed.

c) At least in this scenario, there is little to choose between Worst Fit and Best fit.

However, Worst Fit works better than FIRST Fit.

Biasing ties toward low addresses may not be a good strategy.

Sometimes, we really benefit from memory defragmentation/compaction.

Problem 4 Network Structure

What is meant by a "local-area-network" (LAN)?
What is meant by a "wide-area-network" (WAN)
If you are programming at the application layer (e.g., HTTP, DNS, SMTP, FTP, or secure versions there-of), how does it matter whether the another machine with which you are communicating is on your LAN or your WAN? Explain.
If you are programming at the Internet layer (e.g., IP), how does it matter whether the another machine with which you are communicating is on your LAN or your WAN? Explain.
If you are programming at the physical or network access layer (e.g., Ethernet), how does it matter whether the another machine with which you are communicating is on your LAN or your WAN? Explain.

This question explores whether you really grasp the concept of the layer networking protocols. Many answers were rather vague.

In a local area network, hosts are distributed over a small area, such as a building. Communication links tend to have a higher speed and a lower error rate. Machines on a LAN typically can send messages directly to other machines on their LAN. Ethernet and various wireless protocols connect machines on a LAN.

In a wide area network, hosts are widely distributed and communication links tend to be slower and more error-prone. Messages pass through multiple routers along their way. Computers on a WAN may be connected by Ethernet, but not directly to each other. WAN is really a network of networks.

This question asks whether the programmer of an HTTP or FTP client or server cares whether the communication is via LAN or WAN. The answer to that is "No." If you are programming a browser to load a web page (HTTP or HTTPS), you know nothing of LAN vs. WAN. The differences are indirect, including latency (speed), reliability, and security (or -1). Those concerns affect performance, but they have little effect on the code you write, with the possible exception of error handling. Other differences are hidden by lower level protocols.

By definition, you are concerned primarily with WAN communication.

By definition, you are programming for LAN communication, not WAN. You may be transmitting WAN packets, but you do not know it.

Problem 5 Process Migration

Suppose we have a homogeneous network of 16 identical machines, running identical software, including some form of a distributed operating system. Describe a method for process migration. That is, Process P begins to run on machine i. Later, the distributed operating system decides that machine i is too busy, but a different machine k is idle. Machine k has no previous knowledge of Process P. Describe what the distributed operating system must do to move Process P to machine k with no loss of work. State any assumptions you make.
Now suppose that the network is heterogenous. That is, it consists of machines with different architectures and different operating systems. Describe a method for process migration. State any assumptions you make.

See p. 747 and Problem 17.5, p. 775. This question should distinguish "A" students from "B" students.

The question asks about moving running processes. Of course, you must interrupt it, but you cannot count on allowing it to reach a convenient stopping point.

Assume the machines are PC-like computers, running Windows, Linux, Mac OSX, or a similar OS, except that the OS includes features for load-balancing across the network.
On machine i, we need to

Interrupt Process P

Marshal process state (including all registers and Process Control Block), memory image, disk image, any open files, any open ports, and any OS resources held for Process P.
You should appreciate that marshalling OS resources (e.g., semaphores) or open files is very challenging.

Transmit the marshalled information to machine k
On machine k:

Un-marshal it. The un-marshalling must recreate on machine k everything machine i knew about Process P. Un-marshalling must consider that memory addresses will have changed. Hopefully, patching the page table might handle that. Un-marshalling dynamic data structures is hard, but RPC machinery already handles that.
You should appreciate that marshalling and un-marshalling OS resources (e.g., semaphores) or open files is very challenging.

Insert Process P into the list of processes ready to run on machine k

You must be careful to distinguish work on machine i from work on machine k.
You must include some indication that you understand the implications of "process state." If we really are moving from one PC-like machine to another, a window (or windows) open on the screen is part of the process state. How do we move a window, including information that has been written (and forgotten P? If we have sent an HTTP request with the address of machine i, and we move to k, how will we know when our request returns?

To receive full credit, you must give evidence that you understand that process migration is not hard for simple processes, but process migration may be essentially impossible for sufficiently complicated processes.

The concept is the same, but there are many complications. Fundamentally, instructions, data representations, resorces, and even operating systems calls may be different:

A different architecture may not run the same executable. Possible remedies: Java should run in a different JVM; Initially cross-compile for several architectures; Recompile on machine k.

Memory addresses may have different formats. Possible remedy: RPC machinery already handles heterogenous memory formats.

Different operating systems have different system calls. Possible remedy: Use POSIX calls.

Machine k may not have the same peripherals/resources. Possible remedy: Distributed OS should know which machines have which peripherals, so it should not send Process P to an inappropriate machine. Impossible to anticipate if P has not yet requested those resources.

One approach is to run on machine k a virtual machine copy of machine i and run Process P in that VM.
To receive full credit, you must give evidence that you understand that process migration in a heterogenous network may work for simple processes, but process migration may be essentially impossible for sufficiently complicated processes.

Problem 6 Stream-based and Message-based Internet Communication Paradigms

In class, Dr. Brylow described the two basic Internet communication paradigms, stream-based and message- or datagram-based.

Which Internet protocol characterizes stream-based communication? Give acronym and full name of the protocol.
Outline important properties of the stream-based protocol.
What is the major advantage of the stream-based protocol? Explain.
Which Internet protocol characterizes message-based communication? Give acronym and full name of the protocol.
Outline important properties of the message-based protocol.
What is the major advantage of the message-based protocol? Explain.
Give an application for which the stream-based protocol should be preferred. Why?
Give an application for which the message-based protocol should be preferred. Why?

Pictures from Dr. Brylow's 5/2/2016 lecture:

TCP - Transmission Control Protocol. See en.wikipedia.org/wiki/Transmission_Control_Protocol

Connection-oriented, 1-to-1, stream of individual bytes, arbitrary length transfers, used by most applications

Reliable - receipt of packets is guaranteed

UDP - User Datagram Protocol. See en.wikipedia.org/wiki/User_Datagram_Protocol

Message-oriented, connection-less, many-to-many: unicast (1-1), broadcast (1-everyone), multicast (1-many)

Simplicity, speed

Most: e.g., HTTP

Numerous key Internet applications use UDP, including: the Domain Name System (DNS), where queries must be fast and only consist of a single request followed by a single reply packet, the Simple Network Management Protocol (SNMP), the Routing Information Protocol (RIP), and the Dynamic Host Configuration Protocol (DHCP). - en.wikipedia.org/wiki/User_Datagram_Protocol

Thank you

We (Dennis and George) 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.

Marquette University. Be The Difference.

Marquette | Corliss |

COSC 3250 / COEN 4820 Operating Systems Final Examination Wednesday, May 11, 2016