Efficiency in NACHOS code for CPS110

When writing code for the labs in this course, the grading criteria include correctness, code clarity, documentation, AND a peculiar form of “efficiency”. Recall that one of the reasons for designing an OS is to provide programs with easy-to-use methods which make I/O devices perform efficiently. This criterion is part of the grading criteria for labs.

I/O efficiency simply means that the OS tries to keep each I/O device busy doing useful work for as much of the time as is possible. For example, disk devices are very slow – maybe 10msec for a seek to another track, and 16msec or so to wait for the requested data to rotate around under the read/write head. This means:

· Each disk operation takes several msec to perform

· Scheduling disk operations to minimize seek and rotation delays is helpful

One possibility is to reduce the NUMBER of disk operations needed. A disk record typically holds about 4096 characters of data. However, each line a program writes to disk (say, using printf()) is usually far shorter – maybe 50 characters. This suggests that the program which writes to disk should collect several “printf()” results into a single long record, before writing anything to disk. This process is termed “buffering”, and is very useful in reducing useless disk delays.

Disk “scheduling” accumulates several requests for the disk in a “pending request list”. It then tries to satisfy these requests in an order different from the order they were produced, but one which the OS determines minimizes “seek time”, and “rotational delay”. The exact characteristics of the disk being used are taken into account when the OS calculates the new order, as is the order of requests that are “related” (one request writes a record that a later request asks to read, say).

Efficiency of the C++ code written is usually not weighted heavily in the grading. However, if possible, your code should avoid searching arrays and lists, in favor of creating lists which contain just the items needed. For example, the OS CPU scheduler needs to determine the next process (parallel thread of execution) to start up, when the running process is stopped. The OS COULD do this by searching a list of ALL processes for one that is not “blocked”, and is “ready” in main memory to be run. However, this is time consuming, and causes the OS itself to consume CPU cycles that application programs could use. Instead, most OS schedulers maintan a list of “unblocked” and “in memory” processes. When a new process is to be found, the scheduler simply selects the first one on this list – no search is used. This list can be maintained (added to) quickly, without search, also – when a process is “blocked”, the process is kept on a list of “blocked” processes (the list might be associated with a more specific reason for the blockage, like “processes waiting for disk I/O”). When the condition for which the process was waiting occurs, the record of that process is moved from the “waiting for..” list to the “ready” list. You should look for opportunities to build such data structures in the new code you create.