---

Nachos Compound List

Here are the classes, structs, unions and interfaces with brief descriptions:

 
• AddrSpace (Data structures to keep track of executing user programs (address spaces))
• Alarm (The following class defines a software alarm clock)
• aouthdr (Data structure that describe the MIPS COFF format)
• Bitmap (The following class defines a "bitmap" -- an array of bits, each of which can be independently set, cleared, and tested. Most useful for managing the allocation of the elements of an array -- for instance, disk sectors, or main memory pages. Each bit represents whether the corresponding sector or page is in use or free)
• CallBackObj (Abstract base class for objects that register callbacks)
• Condition (The following class defines a "condition variable". A condition variable does not have a value, but threads may be queued, waiting on the variable. These are only operations on a condition variable: Wait() -- release the lock, relinquish the CPU until signaled, then re-acquire the lock Signal() -- wake up a thread, if there are any waiting on the condition Broadcast() -- wake up all threads waiting on the condition All operations on a condition variable must be made while the current thread has acquired a lock. Indeed, all accesses to a given condition variable must be protected by the same lock. In other words, mutual exclusion must be enforced among threads calling the condition variable operations. In Nachos, condition variables are assumed to obey *Mesa*-style semantics. When a Signal or Broadcast wakes up another thread, it simply puts the thread on the ready list, and it is the responsibility of the woken thread to re-acquire the lock (this re-acquire is taken care of within Wait()). By contrast, some define condition variables according to *Hoare*-style semantics -- where the signalling thread gives up control over the lock and the CPU to the woken thread, which runs immediately and gives back control over the lock to the signaller when the woken thread leaves the critical section. The consequence of using Mesa-style semantics is that some other thread can acquire the lock, and change data structures, before the woken thread gets a chance to run. The advantage to Mesa-style semantics is that it is a lot easier to implement than Hoare-style)
• ConsoleInput (The following class defines the input side of a hardware console device. Input to the device is simulated by reading to the UNIX file "readFile". Since input to the device is asynchronous, the interrupt handler "callWhenAvail" is called when a character has arrived to be read in.In practice, usually a single hardware thing that does serial input)
• ConsoleOutput (The following class defines the output side of a hardware console device. Output to the device is simulated by writing to the UNIX file "writeFile". Since output to the device is asynchronous, the interrupt handler "callWhenDone" is called when an output character has been "put" so that the next character can be written.In practice, usually a single hardware thing that does serial input. use two objects)
• Debug (Data structure for debugging routines)
• Directory (The following class defines a UNIX-like "directory". Each entry in the directory describes a file, and where to find it on disk. The directory data structure can be stored in memory, or on disk. When it is on disk, it is stored as a regular Nachos file. The constructor initializes a directory structure in memory; the FetchFrom/WriteBack operations shuffle the directory information from/to disk)
• DirectoryEntry (The following class defines a "directory entry", representing a file in the directory. Each entry gives the name of the file, and where the file's header is to be found on disk. Internal data structures kept public so that Directory operations can access them directly)
• Disk (The following class defines a physical disk I/O device. The disk has a single surface, split up into "tracks", and each track split up into "sectors" (the same number of sectors on each track, and each sector has the same number of bytes of storage). Addressing is by sector number -- each sector on the disk is given a unique number: track * SectorsPerTrack + offset within a track. As with other I/O devices, the raw physical disk is an asynchronous device -- requests to read or write portions of the disk return immediately, and an interrupt is invoked later to signal that the operation completed. The physical disk is in fact simulated via operations on a UNIX file. To make life a little more realistic, the simulated time for each operation reflects a "track buffer" -- RAM to store the contents of the current track as the disk head passes by. The idea is that the disk always transfers to the track buffer, in case that data is requested later on. This has the benefit of eliminating the need for "skip-sector" scheduling -- a read request which comes in shortly after the head has passed the beginning of the sector can be satisfied more quickly, because its contents are in the track buffer. Most disks these days now come with a track buffer. The track buffer simulation can be disabled by compiling with -DNOTRACKBUF)
• ElevatorBank (The following class defines a bank of elevators)
• ElevatorInfo (Data structure to represent the state of the physical elevator class is private to this module)
• ElevatorInspector (Data structures to control elevator device self test. Definition private to this module)
• filehdr (Data structure that describe the MIPS COFF format)
• FileHeader (The following class defines the Nachos "file header" (in UNIX terms, the "i-node"), describing where on disk to find all of the data in the file. The file header is organized as a simple table of pointers to data blocks. The file header data structure can be stored in memory or on disk. When it is on disk, it is stored in a single sector -- this means that we assume the size of this data structure to be the same as one disk sector. Without indirect addressing, this limits the maximum file length to just under 4K bytes. There is no constructor; rather the file header can be initialized by allocating blocks for the file (if it is a new file), or by reading it from disk)
• FileSystem (< Temporarily implement file system calls as < FILESYS)
• HashIterator (The following class can be used to step through a hash table -- same interface as ListIterator. Example code: HashIterator<Key, T> iter(table); for (; !iter->IsDone(); iter->Next()) { Operation on iter->Item() })
• HashTable (The following class defines a "hash table" -- allowing quick lookup according to the hash function defined for the items being put into the table)
• Instruction (The following class defines an instruction, represented in both undecoded binary form decoded to identify operation to do registers to act on any immediate operand value)
• Interrupt (The following class defines the data structures for the simulation of hardware interrupts. We record whether interrupts are enabled or disabled, and any hardware interrupts that are scheduled to occur in the future)
• List (The following class defines a "list" -- a singly linked list of list elements, each of which points to a single item on the list. The class has been tested only for primitive types (ints, pointers); no guarantees it will work in general. For instance, all types to be inserted into a list must have a "==" operator defined)
• ListElement (The following class defines a "list element" -- which is used to keep track of one item on a list. It is equivalent to a LISP cell, with a "car" ("next") pointing to the next element on the list, and a "cdr" ("item") pointing to the item on the list. This class is private to this module (and classes that inherit from this module). Made public for notational convenience)
• ListIterator (The following class can be used to step through a list. Example code: ListIterator<T> *iter(list); for (; !iter->IsDone(); iter->Next()) { Operation on iter->Item() })
• Lock (The following class defines a "lock". A lock can be BUSY or FREE. There are only two operations allowed on a lock: Acquire -- wait until the lock is FREE, then set it to BUSY Release -- set lock to be FREE, waking up a thread waiting in Acquire if necessary In addition, by convention, only the thread that acquired the lock may release it. As with semaphores, you can't read the lock value (because the value might change immediately after you read it))
• Machine (The following class defines the simulated host workstation hardware, as seen by user programs -- the CPU registers, main memory, etc. User programs shouldn't be able to tell that they are running on our simulator or on the real hardware, except we don't support floating point instructions the system call interface to Nachos is not the same as UNIX (10 system calls in Nachos vs. 200 in UNIX!) If we were to implement more of the UNIX system calls, we ought to be able to run Nachos on top of Nachos! The procedures in this class are defined in machine.cc, mipssim.cc, and translate.cc)
• Mail (The following class defines the format of an incoming/outgoing "Mail" message. The message format is layered: network header (PacketHeader) post office header (MailHeader) data)
• MailBox (The following class defines a single mailbox, or temporary storage for messages. Incoming messages are put by the PostOffice into the appropriate mailbox, and these messages can then be retrieved by threads on this machine)
• MailHeader (The following class defines part of the message header. This is prepended to the message by the PostOffice, before the message is sent to the Network)
• NetKernel (The class implementing the Net Kernel, for the assignmenton distributed systems)
• NetworkInput (The following class defines a physical network device. The network is capable of delivering fixed sized packets, in order but unreliably, to other machines connected to the network. The "reliability" of the network can be specified to the constructor. This number, between 0 and 1, is the chance that the network will lose a packet. Note that you can change the seed for the random number generator, by changing the arguments to RandomInit() in Initialize(). The random number generator is used to choose which packets to drop)
• NetworkOutput (The following class defines a physical network device. The network is capable of delivering fixed sized packets, in order but unreliably, to other machines connected to the network. The "reliability" of the network can be specified to the constructor. This number, between 0 and 1, is the chance that the network will lose a packet. Note that you can change the seed for the random number generator, by changing the arguments to RandomInit() in Initialize(). The random number generator is used to choose which packets to drop)
• noffHeader (Data structure defining the Nachos Object Code Format)
• OpenFile (Manages the details of accessing the contents of a specific file)
• OpInfo (Internal data structures for simulating the MIPS instruction set)
• OpString (Stuff to help print out each instruction, for debugging)
• PacketHeader (The following class defines the network packet header. The packet header is prepended to the data payload by the Network driver, before the packet is sent over the wire. The format on the wire is: packet header (PacketHeader) data (containing MailHeader from the PostOffice!))
• PendingElevatorEvent (Information about an elevator event that affects riders or controllers. Class is private to this module)
• PendingInterrupt (The following class defines an interrupt that is scheduled to occur in the future. The internal data structures are left public to make it simpler to manipulate)
• PersistBitMap (The following class defines a persistent bitmap. It inherits all the behavior of a bitmap (see bitmap.h), adding the ability to be read from and stored to the disk)
• PostOfficeInput (The class defines a "Post Office", or a collection of mailboxes. Receive -- wait until a message is in the mailbox, then remove and return it. Incoming messages are put by the PostOffice into the appropriate mailbox, waking up any threads waiting on Receive)
• PostOfficeOutput (The class defines a "Post Office", or a collection of mailboxes. Send -- send a message to a mailbox on a remote machine)
• Scheduler (The following class defines the scheduler/dispatcher abstraction -- the data structures and operations needed to keep track of which thread is running, and which threads are ready but not running)
• scnhdr (Data structure that describe the MIPS COFF format)
• segment (Data structure defining the Nachos Object Code Format)
• Semaphore (The following class defines a "semaphore" whose value is a non-negative integer. The semaphore has only two operations P() and V(): P() -- waits until value > 0, then decrement V() -- increment, waking up a thread waiting in P() if necessary Note that the interface does *not* allow a thread to read the value of the semaphore directly -- even if you did read the value, the only thing you would know is what the value used to be. You don't know what the value is now, because by the time you get the value into a register, a context switch might have occurred, and some other thread might have called P or V, so the true value might now be different)
• SortedList (The following class defines a "sorted list" -- a singly linked list of list elements, arranged so that "Remove" always returns the smallest element. All types to be inserted onto a sorted list must have a "Compare" function defined: int Compare(T x, T y) returns -1 if x < y returns 0 if x == y returns 1 if x > y)
• Statistics (The following class defines the statistics that are to be kept about Nachos behavior -- how much time (ticks) elapsed, how many user instructions executed, etc. The fields in this class are public to make it easier to update)
• SynchConsoleInput (The following class defines synchronized input to a console device)
• SynchConsoleOutput (The following class defines synchronized output to a console device)
• SynchDisk (The following class defines a "synchronous" disk abstraction. As with other I/O devices, the raw physical disk is an asynchronous device -- requests to read or write portions of the disk return immediately, and an interrupt occurs later to signal that the operation completed. (Also, the physical characteristics of the disk device assume that only one operation can be requested at a time). This class provides the abstraction that for any individual thread making a request, it waits around until the operation finishes before returning)
• SynchList (The following class defines a "synchronized list" -- a list for which these constraints hold: 1. Threads trying to remove an item from a list will wait until the list has an element on it. 2. One thread at a time can access list data structures)
• Thread (The following class defines a "thread control block" -- which represents a single thread of execution. Every thread has: an execution stack for activation records ("stackTop" and "stack") space to save CPU registers while not running ("machineState") a "status" (running/ready/blocked) Some threads also belong to a user address space; threads that only run in the kernel have a NULL address space)
• ThreadedKernel (The class implementing threaded kernel)
• Timer (The following class defines a hardware timer)
• TranslationEntry (The following class defines an entry in a translation table -- either in a page table or a TLB. Each entry defines a mapping from one virtual page to one physical page. In addition, there are some extra bits for access control (valid and read-only) and some bits for usage information (use and dirty))
• UserProgKernel (The class implementing the user prog kernel)

---