COSC 3250 / COEN 4820 Operating Systems
Final Examination
Monday, May 7, 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]

Problem 1 Acronyms and Definitions
Problem 2 CPU Scheduling
Problem 3 TCP/IP
Problem 4 File Allocation
Problem 5 Tricky C Program - Memory Management
Problem 6 Computer System Design

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.

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.

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

1. See Section 5.2:
   For full credit, I expected at least five criteria.
   1. Fairness
   2. CPU utilization - Percent of time CPU is doing useful work
   3. Throughput - Work completed per unit time
   4. Turnaround time - How long does it take to get my task done?
   5. Waiting time - How long to I wait to get started?
   6. Response time - How long is it before I know the CPU is working for me?
   7. Prevent starvation
   8. Minimize both context swaps and busy waiting
   9. Obey priorities
   10. Meet deadlines
2. See Sections 5.3 & 19.5:
   1. First-Come, First-Served (5.3.1)
   2. Shortest Job First (5.3.2). Provably optimal, in some sense, but generally impossible to know.
   3. Priority (5.3.3)
   4. Round-Robin (5.3.4)
   5. Multi-level queue (5.3.5)
   6. Multi-level feedback queue (5.3.6)
   7. Rate-monotonic (19.5.1)
   8. Earliest Deadline First (19.5.2)
   9. Proportionate Share (19.5.3)
3. Depends. Discuss advantages and disadvantages of each

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 send a message to some application on another machine whose IP address you know.

Describe what the TCP/IP stack does with your message from the point at which you make the operating system call send(...) until the message becomes signals in the Ethernet cable.

A good answer addresses

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

A good answer surely includes a diagram of the stack.

Figure 11.8 from our textbook illustrates indexed allocation of disk space.

[Insert Figure 11.8 here]

Explain disk file management using indexed allocation.

1. Discuss the overall strategy of indexed allocation. What is an "index?"
2. Using indexed allocation, what constitutes a file?
   Where is a file stored?
   How is a file accessed?
3. Using indexed allocation, what constitutes a directory?
   Where is a directory stored?
   How is a directory accessed?
4. Using indexed allocation, how is free disk space managed?
5. What are the advantages and disadvantages of indexed allocation?

If you don't know, make intelligent guesses based on the figure and your understanding of file management.

See Section 11.4.3. The question asked about disk space, managed by indices. The question is not about memory management. I expected to see

1. An index is a disk block address, a kind of pointer.
2. Collection of data blocks plus one or more blocks of indices into the collection. If a file is large, we may need multiple index blocks.
3. Directory is like a file. It is a collection of data blocks plus plus one or more blocks of indices into the collection.
4. Free space is like a very large file, all of whose data blocks are not used. Free space management is a set (probably linked list) of index blocks, each of which contains indices pointing to free blocks.
5. + Fast direct access
   - Multiple accesses for first access
   - Danger of corruption

If your answers, especially to parts b, c, or d were general and not about the specifics of indexing, you were penalized.

Here is a tricky C function that might appear in the context of XINU memory management:

     struct memblock
     {
             struct memblock *next;  // pointer to next memory block
             ulong           length; // size of memory block (incl. struct)
     };                     

     // Allocates space using getmem(), and automatically hides accounting
     //  info in the two words below the memory region.  This allows a
     //  corresponding call to free() not to require a request size parameter.
     void *malloc(ulong nbytes)
     {
             struct memblock *block;

             // Round request size to multiple of struct memblock.
             nbytes = (nbytes + 7) % sizeof(struct memblock);
             block  = getmem(nbytes);
             if (block = SYSERR ) return SYSERR;
             // Back point up one slot.
             block  = block - sizeof(struct memblock);
             // Store accounting info.
             block.next   = block;
             block.length = nbytes;
             // Return pointer to useful part of memory block.
             return (block + sizeof(struct memblock));
     }

Hint: The errors are many and varied. identify as many as you can.

There is something wrong with almost every line in the function.

The local variable is not initialized.

The rounding operation is incorrect, returning the remainder rather than a rounded quantity. Also, it does not add in space for the accounting info.

The call to getmem() requires a typecast to be assigned to block.

The if-statement assigns block rather than comparing it, and is thus always true.

The subtraction operation moves the pointer into the previous free block, rather than preparing space within the new region for accounting info.

Also, pointer scaling will multiply the offset by 8, grossly overshooting the target.

The field assignments must use "->" instead of ".", and again, are in the wrong memory location.

The return statement suffers from additional unintended pointer arithmetic and overshoots by a factor of 8.

Design a computer system for an open computer laboratory such as Haggerty 482 or Cudahy 101.

You have a room with electrical power and furniture. You get one high-speed ethernet line to an ITS router. Everything else, you must specify, including computers, servers, operating systems, [application software], network, network protocol, file storage, printers, etc. Tell what you will specify, why, and give an approximate budget.

Hint: As in any design activity, you should begin by formulating requirements.

Yes, that question is far too large for this exam. What I really want you to do is

1. Students, TA's, faculty, ITS staff, administration, cleaning staff
2. Runs the software I need
   Is available
   Fast
   Secure
   Recruiting, cooler than what "they" have to use
   Installed in time
   Complexity to install, configure, maintain
   Cost of purchase, installation, operation, and disposal
   . . .
3. Vendor of hardware
   Operating system: Windows, Mac, Linux
   Wired or wireless
   Network topology
   Application software
   . . .
   Don't confuse requirements with solutions. For example, user authentication is a response to a requirement for protection against certain threats. If you had a guard checking IDs at the door, there might be no need to log in.
   Design choices explore the space of possible solutions.
    
4. Local hard disk
   Central server
   Distributed file system
   Personal flash devices
   Cloud-based systems
   . . .
   
5. Depends. Important criteria include speed, back-up, access from various machines, cost, complexity of maintenance. Most students made the mistake of reflecting their requirements, ignoring the university's requirement of low total cost of ownership.