COSC 3250 / COEN 4820 Operating Systems
Final Examination
Friday, May 11, 2012

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 (for Monday's and Friday's instance combined):

Range: [51.5, 94.5]; Median: 78; Mean: 77.5; Standard Deviation: 18.31

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

Problem 1 Acronyms and Definitions
Problem 2 Disk Scheduling
Problem 3 Internet Protocols
Problem 4 Xinu File Sharing (XFiSh) protocol
Problem 5 Tricky C - prioritize()
Problem 6 Problem Device Drivers

For each item,

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. FCB
2. RPC
3. SMP
4. TLB
5. INODE
6. SSTF
7. RAID
8. HTTPS
9. MAC (NOT an Apple computer)
10. DNS

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

1. FCB - File Control Block (p. 463): (an inode in most UNIX systems) contains information about a file.
2. RPC - Remote Procedure Call (p. 131): Abstract the procedure-call mechanism for use between systems with network connections.
3. SMP - Symmetric Multiprocessing (p. 202): Each processor is self-scheduling.
4. TLB - Translation Look-aside Buffer (p. 333): Special, small, fast hardware look-up table often used to store a page or segment table in a virtual memory system.
5. INODE - Trick question. Not an acronym. (p. 463) Traditional variable name in UNIX source code for the File Control Block.
6. SSTF - Shortest Seek Time First disk scheduling (p. 512): Service all requests close to the disk head before servicing requests far away.
7. RAID - Redundant Arrays of Independent/Inexpensive Disks (Section 12.7).
8. HTTPS - Hypertext Transfer Protocol (Secure). Protocol for in which web pages and responses requiring secure communications (e.g., login or personal information) are communicated.
9. MAC - Medium Access Control (p. 699): Unique byte number assigned to every Ethernet device for addressing on its Ethernet.
10. DNS - Domain Name System/Service (p. 448). Provides host-name-to-network-address translations.

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.

1. What are the criteria for selecting a good disk scheduling algorithm? What does each mean?
2. List and describe four disk scheduling algorithms
3. Which is best? Why?

Several students responded with CPU scheduling. Read The Fine Question.

1. The book does not address this explicitly. You must think for yourself.
   1. Response time (average, maximum, variance)
   2. Throughput (requests served per second)
   3. Waiting time (average, maximum, variance)
   4. No starvation
   5. Fair
   6. Simplicity
   A disk scheduling algorithm may adapt to drive latency times, but it does not get to control them.
2. See Section 12.4:
   1. First-Come, First-Served (12.4.1)
   2. Shortest Seek Time First (12.4.2)
   3. SCAN (12.4.3)
   4. C-SCAN (12.4.4)
   5. LOOK (12.4.5)
   6. C-LOOK (12.4.5)
3. Depends. See Section 12.4.6. Discuss advantages and disadvantages of each

Choose ONE of a or b:

1. Explain how User Datagram Protocol (UDP) works.
   Your explanation should cover UDP in general. Your explanation should include:
   • What is the purpose?
   • Draw an appropriate sketch illustrating the process.
   • What information do you start with (input)?
   • What is the end result (output)?
   • How is the output derived from the input?
   • How are changes in the world reflected?

   OR

    

2. Explain how routing works.
   Your explanation should cover routing in general. Your explanation should include:
   • What is the purpose?
   • Draw an appropriate sketch illustrating the process. Your sketch might include a source, a destination, and 2-3 intermediate gateways.
   • What information do you start with (input)?
   • What is the end result (output)?
   • What happens at each of the 4-5 machines in your sketch?

1. See User Datagram Protocol; tutorial from InetDaemon.Com

   From compnetworking.about.com/od/networkprotocolsip/g/udp-user-datagram-protocol.htm:
   UDP (User Datagram Protocol) is a simple OSI transport layer protocol for client/server network applications based on Internet Protocol (IP). UDP is the main alternative to TCP and one of the oldest network protocols in existence, introduced in 1980.

   UDP is often used in videoconferencing applications or computer games specially tuned for real-time performance. To achieve higher performance, the protocol allows individual packets to be dropped (with no retries) and UDP packets to be received in a different order than they were sent as dictated by the application.

   UDP network traffic is organized in the form of datagrams. A datagram comprises one message unit. The first eight (8) bytes of a datagram contain header information and the remaining bytes contain message data. A UDP datagram header consists of four (4) fields of two bytes each: source port number, destination port number, datagram size, checksum.

    

2. See Section 16.5.2 Routing Strategies or Lecture notes on Routing

The Xinu File Sharing (XFiSh) protocol implemented in Project 10 included many simplifying design decisions to keep the assignment tractable. For example, all XFiSh exchanges were "best effort," in the sense that a client would not detect if a file it had requested was lost, altered, or corrupted in transit.

Extend the XFiSh protocol to allow a client to ensure that a requested file is received intact (i.e., has the same name, length and contents as the original) without resorting to higher-level protocols such as the TCP/IP suite.

Hint: Be specific. At least demonstrate that you remember the assignment.

There are two main requirements to adding this kind of reliability. First, the FISH_HAVEFILE packet type should be altered to include two more fields: 1) A file length field, missing from the base design, would specify the destination file size, as well as indicate how many bytes of the payload should be copied to disk; 2) A checksum, error correcting code, or other equivalent field is a simple technique for detecting corruption in the file name and content portions of the payload.

A file length field is not the only solution, as it is also possible to use a sentinel value (like EOF) to mark the end of the file. However, without describing a corresponding system of escape codes, this naive solution will perform badly if files happen to contain the EOF value. Similarly, alternatives to a checksum exist, including sending multiple copies or setting up a system of acknowledgement packets.

Second, there has to be a mechanism for tracking "state" on the XFiSh client. This can take many different forms, but in essence the client needs to know if a file has been requested to detect if it has not arrived in some predetermined time allowance. Moreover, if the file does not arrive, or does not arrive intact, the client should re-request the file, probably several times before gracefully timing out. This can be done even without adding a new packet type to the server design. Ample facilities for this exist even in the stripped-down version of Embedded Xinu you have implemented for this course. However, hopefully you can appreciate how much simpler the "stateless" XFiSh protocol is to implement, and why we did not include such reliability requirements for the project.

Consider the implementation of prioritize() below:

/**
* Prioritize a process into a queue in descending key order.
* @param pid    process id to prioritize
* @param q      queue in which process should be prioritized
* @param key    sorting key (priority, for example)
*/
void prioritize(short pid, queue q, ulong key)
{
       short head, prev, next, tail;
       head = queuehead(q);
       tail = queuetail(q);

       while ( (queuetab[next].key > key) && (next != tail) )
       { next = queuetab[next]->next; }

       queuetab[pid].next  = next;     // Set next and prev fields of new node
       prev = queuetab[next].prev;
       queuetab[pid].prev  = prev;
       queuetab[prev].next = next;     // Finish linking list
       queuetab[next].prev = prev;
}

Does this code correctly insert a process in priority order? If so, state the conditions under which it works correctly. If not, point out what is wrong.

Yes, this is repeated from Exam 2. No one got it then, so we thought we'd offer a second chance.

If you thought we'd put correct code in a tricky C question, you don't know your instructors very well. If you expected only one error, you don't know your instructors very well. On the other hand, it might be really tricky of us to give you correct code?

There are several major errors in this code.

1. The "->" operator in the body of the while-loop is a syntax error for a statically allocated array like queuetab, so this will not even compile;
2. Index variable "next" needs to start out one element past the head node before the while-loop, or else we potentially are considering inserting in front of the head node;
3. The key comparison within the while-loop needs to be ">=", or else processes with the same priority will not exhibit round-robin behavior;
4. The key value is never assigned into the new node;
5. The last two assignments statements do not correctly finish linking the new node into the list.

On some papers, I made notations such as "#2", or "#5" to indicate I credited you for identifying error #2 or error #5 from the list above. If you wish to argue that what you have written on your exam paper shows you recognized an error for which I did not give you credit, you are welcome to talk to me - Corliss.

Once these errors are all fixed, the assumptions under which it works correctly are:

1. Pid is a valid process ID, and it is not already in a process queue;
2. Queue 'q' is a valid process queue representation;
3. The key field in the queue struct is large enough to store an unsigned int.

You earned full credit if you identified 3 of these 5 errors and did not say anything false. Identifying 2 of the 5 errors earned 18 points. Identifying 1 of the 5 errors earned about 10 points, provided you did not say anything else false.

One student pointed out this code (if it otherwise worked) was not thread-safe. After some reflection, I like that answer. Of course, it does not work, but I really like that this student made a connection with the theoretical discussions of critical sections. Well done.

My favorite answer: "You would be very lucky if this code works." No extra credit, though.

Recently, I received the following e-mail 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.

Yes, the operating system includes many device drivers to allow the operating system to talk to various devices and peripherals, such as printers, cameras, smart phones, etc.

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 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?