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:
Averages for Wednesday's version and Friday's version were both very close to 70.
This is really a battery of test questions from which two exams were taken.
Wednesday and Friday: Problem 1 Acronyms and Definitions
For each acronym,
- Give the phrase for which the acronym stands (in the context of computer operating systems)
- 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.
- PCB - Process Control Block (p. 103): Representation of a process in the operating system.
- FCB - File Control Block (p. 463): (an inode in most UNIX systems) contains information about a file.
- IPC - Interprocess Communication (Section 3.4)
- RPC - Remote Procedure Call (p. 131): Abstract the procedure-call mechanism for use between systems with network connections.
- SJF - Shortest Job First scheduling (p. 189): The next process assigned to the CPU is the one with the shortest expected execution time.
- LWP - Lightweight process (p. 199): Sometimes used as a synonym for a thread.
- SMP - Symmetric Multiprocessing (p. 202): Each processor is self-scheduling.
- 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.
- 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.
- 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.
- INODE - Trick question. Not an acronym. (p. 463) Traditional variable name in UNIX source code for the File Control Block.
- NFS - Network File System (p. 490): Both an implementation and a specification of a software system for accessing remote files across a network.
- SSTF - Shortest Seek Time First disk scheduling (p. 512): Service all requests close to the disk head before servicing requests far away.
- 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.
- RAID - Redundant Arrays of Independent/Inexpensive Disks (Section 12.7).
- FTP - File Transfer Protocol (p. 676)
- HTTPS - Hypertext Transfer Protocol (Secure). Programming language in which web pages are written
- SMTP - Secure Mail Transfer Protocol
- MAC - Medium Access Control (p. 699): Unique byte number assigned to every Ethernet device for addressing on its Ethernet.
- 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.
- 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.
Friday: Problem 2 CPU Scheduling
- What are the criteria for selecting a good CPU scheduling algorithm? What does each mean?
- List and describe three CPU scheduling algorithms
- Which is best? Why?
- See Section 5.2:
- Fairness
- CPU utilization - Percent of time CPU is doing useful work
- Throughput - Work completed per unit time
- Turnaround time - How long does it take to get my task done?
- Waiting time - How long to I wait to get started?
- Response time - How long is it before I know the CPU is working for me?
- See Sections 5.3 & 19.5:
- First-Come, First-Served (5.3.1)
- Shortest Job First (5.3.2)
- Priority (5.3.3)
- Round-Robin (5.3.4)
- Multi-level queue (5.3.5)
- Multi-level feedback queue (5.3.6)
- Rate-monotonic (19.5.1)
- Earliest Deadline First (19.5.2)
- Proportionate Share (19.5.3)
- Depends. Discuss advantages and disadvantages of each
Wednesday: Problem 2 Disk Scheduling
- What are the criteria for selecting a good disk scheduling algorithm? What does each mean?
- List and describe four disk scheduling algorithms
- Which is best? Why?
- The book does not address this explicitly. You must think for yourself.
- Response time (average, maximum, variance)
- Throughput (requests served per second)
- Waiting time (average, maximum, variance)
- No starvation
- Fair
- Simplicity
A disk scheduling algorithm may adapt to drive latency times, but it does not get to control them.
- See Section 12.4:
- First-Come, First-Served (12.4.1)
- Shortest Seek Time First (12.4.2)
- SCAN (12.4.3)
- C-SCAN (12.4.4)
- LOOK (12.4.5)
- C-LOOK (12.4.5)
- Depends. See Section 12.4.6. Discuss advantages and disadvantages of each
Not used: Problem Device Drivers
Recently, I received the following email 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.
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?
Friday: Problem 3 TCP/IP
Aaron explained that the TCP/IP "stack" consists of four layers:
- Application (or Process) Layer
- Transport (or Host-to-Host) Layer
- Network (or Internet) Layer
- 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
- API: What must send(...) pass in
- Transport layer does ...
- Network layer does ...
- Physical layer does ...
- Device driver does ...
Wednesday: Problem 3 TCP/IP
Aaron explained that the TCP/IP "stack" consists of four layers:
- Application (or Process) Layer
- Transport (or Host-to-Host) Layer
- Network (or Internet) Layer
- Physical (or Network Access) Layer
Assume that you are the programmer of an application that expects
receive a message from some application on another machine. Some message arrives at your machine as signals in the Ethernet cable.
Describe what the TCP/IP stack
does with the message from that point until it hands your program your message. How does it decide the message is for its machine? How does it decide the message is for your application? What else must it decide? What instructions must you have provided to the stack before it knows what to do with your message?
A good answer addresses
- What instructions must you have provided to the stack before it knows what to do with your message? Register to listen to a certain port.
- Device driver does ...
- Physical layer does ...
- Network layer does ...
- Transport layer does ...
- How does it decide the message is for its machine?
- How does it decide the message is for your application? Message specifies a port
Wednesday: Problem 4 File Allocation
Figure 11.7 from our textbook illustrates the file allocation table.
[Insert Figure 11.7 here]
Explain disk file management using a file allocation table.
Your answer might discuss the overall strategy, what constitutes a file, what constitutes a directory,
where file and directory is stored, how files and directories are accessed, how free disk space
is managed, and advantages and disadvantages.
If you don't know, make intelligent guesses based on the figure and your
understanding of file management.
See p. 475.
Your answer should discuss the overall strategy, what constitutes a file, what constitutes a directory,
where file and directory is stored, how files and directories are accessed, how free disk space
is managed, and advantages and disadvantages.
Several students gave answers that said nothing about FAT.
Friday: Problem 4 File Allocation
Figure 11.8 from our textbook illustrates indexed allocation of disk space.
[Insert Figure 11.8 here]
Explain disk file management using indexed allocation.
- Discuss the overall strategy of indexed allocation.
- What constitutes a file?
Where is a file stored?
How is a file accessed?
- What constitutes a directory?
Where is a directory stored?
How is a directory accessed?
- How is free disk space
is managed?
- 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. I expected to see
- An index is a disk block address, a kind of pointer.
- 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.
- Directory is like a file. It is a collection of data blocks plus plus one or more blocks of indices into the collection.
- 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.
- + 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.
Both: Problem 5 Tricky C Program
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));
}
What is wrong with this code?
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.
Wednesday: Problem 6 Real-Time Networking
You are designing a real-time control system that must monitor readings from multiple sensors (input), perform certain processing, and possibly trigger several activators (output). Examples include some medical systems, robotic control, air traffic control, building environment control, warehouse control, etc.
To communicate with the sensors and activators, you need a wired network. You have three choices:
- Standard Ethernet
- An industry standard network - widely used in your industry, but your team knows little about it
- Develop your own proprietary network
Your boss asks
- List advantages and disadvantages of each of the three choices
- Which would you recommend?
- Why?
Hint: I insist on an unambiguous recommendation. "It depends" gets you fired (and a zero on this question). Wish you had more information? Welcome to the world. You may wish that 10 times a day for the next 40 years. Do the best you can with the information you have.
- Advantages and disadvantages?
- Ethernet
+ Well understood, lots of hardware and software, lots of programmers
+ Probably lower development costs
- Latency is hard to predict, especially depending on traffic
- Relatively heavy-weight protocols
- Industry standard network
+ If everyone else is using it, probably well suited to the task
+ Lots of hardware and software, lots of programmers
+ [Probably] Highly predictable performance
- Learning curve, or they fire you and hire someone who knows it
- Does not inter-operate with the rest of the plant
- Develop your own proprietary network
+ Does exactly what you need, nothing more, nothing less
- Design costs, no existing hardware or software
- If performance is critical, almost surely choose the industry standard. Otherwise, Ethernet. Build your own is where the industry standard came from originally.
- Cost to achieve the required performance.
Does your answer recognize there is a difference between real-time and non-real-time systems?
Friday: Problem 6 Computer System Design
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
- Who are the customers/stakeholders in this design?
- List five customer requirements that are related to topics studied in this class.
- List five design questions/choices that are related to topics studied in this class.
Give the design question and at least two alternative concepts.
You do not have to make a choice.
An example of a design question: Where are users' files stored?
- Choices:
Give at least three alternative concepts for where users' files might be stored, including a couple sentence description of each.
For each alternative, list advantages and disadvantages.
- Choices: Which of your alternative concepts for where users' files might be stored
do you prefer?
Why? (Should cite at least some of the customer requirements in part b)
- Students, TA's, faculty, ITS staff, administration, cleaning staff
- 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
. . .
- Vendor of hardware
Operating system: Windows, Mac, Linux
Wired or wireless
Network topology
Application software
. . .
- Local hard disk
Central server
Distributed file system
Personal flash devices
- Depends. Important criteria include speed, back-up, access from various machines, cost, complexity of maintenance
| 