CSC468h TUTORIAL -- WEEK 5 For this week`s tutorial, please refer to the files in the include/documents directory. These give a good overview of the Minotaur OS. There are relevant files on: - Minotaur Virtual Machine - Minotaur External Documentation - Minotaur OS - Starting Minotaur These files are the main reference for this week's tutorial. Some notes on running Minotaur: Suggestion: Read these instructions over first before carrying them out. Minotaur demands quite a bit of computing power to run. In order to execute at a reasonable speed, you should run Minotaur on eddie using oot2. oot2 can be launched simply by typing oot2 at the command prompt. (oot should work fine and another server can be used, you'll just be running a lot slower. Try to avoid oot with Minotaur on cdf because it tends to hog resources.) 1. First, you want to get an xterm running on eddie and displaying on your local machine. This can be done by with an rlogin, an rcmd etc. 2. In order to run Minotaur, a file system must be generated for each disk that will be used in the system (you can use one disk for now). This file system contains all the system programs which Minotaur can run. These files are written in MiniTuring and must be compiled using the mturing compiler. Before making a file system, the sysprogs must be compiled and placed in the /sysprogs directory. mkfs can then be used to generate the file system you require which will include these sysprogs (see the StartingMinotaur file in the documents directory for more details). When you start working on the assignments, you may wish to write new sysprogs in order to test your work. This will require building a new file system. For now, however, a standard file system has already been built which you may use. It is called "stdfile" and is located in the /local/include/oot/Minotaur directory. Copy this file into a local directory where you have write permission. This could be your home directory, or another directory you wish to use as the base for running Minotaur. 3. Fire up oot2. 4. When the windows appear, go to the Directory Viewer, and under Chdir, select %oot. Double click on the Minotaur directory. Single click on the Minotaur file and then select Fix main in the Utilities menu in the Directory Viewer. Then select Home, or whichever directory you stored stdfile in, under Chdir. Finally, select Run main on the main Viewer window. OOT should generate a dependency graph and then "compile" all modules (the first time). It should generate a Minotaur dialog window with options, a Debug window, and a Report window. Saying g (for go) in the dialog window should cause Minotaur to put messages in the report window for booting up, and then an xterm window should pop up for Minotaur "programming" at the end of booting. You have unleashed the Minotaur. Now for the main course.... THE MINOTAUR VIRTUAL MACHINE - The virtual machine minotaur runs on is a homogenous multiprocessor system with a single shared memory. - One of the processors is responsible for some "master" work during boot up but other than that the processors are symmetric. - Other than the processors the machine contains disks, RAM, and Xterminal devices. The processors are connected to these devices via the Main Bus. The devices are connected to each other via the Local Bus. There is also an interrupt Controller device that is connected to both busses. THE PROCESSORS - The processors can be run in two modes: 1. The User Mode (less privileged) - can only use a subset of CPU instructions. - all memory accesses are through the Local Page table. 2. The Kernel Mode (more privileged) - cpu has access to all registers and instructions. - memory access is through the Local or the Global Page Table. - paging can be switched on and off - Main Bus can be used - There are two status registers: 1. status0 - this has a single bit flag indicating the current mode of execution 2. status1 - this has four single bit flags: PagingOn - used to turn on the paging mechanism CodePresent - indicates that the Code Prefetch Cache is loaded. Stack Present - indicates that the Stack Prefetch Cache is loaded. Shutdown - used to shutdown the processor - The CPU has two stack pointers: 1. sp - used in both execution modes 2. ksp - used only in kernel execution mode - The CPU switches context using two registers: 1. timeslice - the number of instructions to execute in each timeslice 2. counter - number of instructions executed so far. When this reaches timeslice the CPU traps and switches context. - Traps are used to switch a processor from executing a process into the kernel. A trap can be generated by a hardware interrupt, a timer interrupt, a user instruction, or an exception condition. Each type of trap has a unique trap number. This number is used to identify a handler for the trap in the Interrupt Descriptor Table (IDT). - When the paging bit in status1 is set, the processor supports single level paged virtual memory. There is a global page table which is pointed to by the GPT register. Each process also has it's own Local Page Table. An LPT register is provided to hold the location of the current process' page table. - A Page Fault is a special trap that is generated by an attempt to access an invalid page. - Each processor has two single-page prefetch caches. One is for code pages, and the other is for stack pages. The CodePresent and StackPresent bits in the status1 register are used to indicate if the caches contain code. The codePage register is used to indicate which page of code is in currently in the code prefetch cache. The stack prefetch page holds the stack page being used for stack operations involving the sp register. THE MAIN BUS The main bus is used by the processors to communicate with the various devices. A processor must acquire the bus and become the 'Bus Master' before it be used. The processor communicates with the devices by reading and writing to ports that are assigned to the various devices. Each port that is assigned to a device is used to access a particular register on that device. THE LOCAL BUS The local bus is used by the devices to access RAM, and the interrupt controller without tying up the main bus. The interrupt controller allows devices to interrupt or trap the processor. This bus is acquired in the same way as the main bus. RAM and DEVICES RAM and devices are accessed through the busses. Available devices are: Xterminal - fictitious terminal upon which Xterms can be displayed. Disk - random access block device. IMPLEMENTATION The files implementing the virtual machine are located in: /local/include/oot/Minotaur/Hardware Processors and User Processes - Each processor has a register set that is passed around in the Minotaur code to identify the CPU. - Each processor is implemented by a forked OOT process that is called a dispatcher. - Each running user process is implemented by a forked OOT process - The ProcMon monitor is used to pass control of a "CPU" between the dispatcher process for that CPU and the user processes. The Main Bus - This is implemented by a monitor that coordinates access to an array of Device objects that is indexed by port number. RAM - This is implemented by an array of nat4. All accesses to the RAM must be properly aligned. Disks - Each disk is implemented by a forked OOT process that runs a method of the Disk class. This class inherits the Device class so that a reference to it can be stored in the Main Bus. This class uses a monitor to allow the disk process to sleep until it receives a request via the Main Bus. Xterminals - Each xterm window opened on the virtual Xterminal is managed by a seperate OOT process that is created by the Xterm class. This class inherits the Device class for the same reasons as Disk. THE MINOTAUR OS PROCESS MANAGEMENT In Minotaur, programs execute as processes. A process consists of code and data ( in Minotaur code is referred to as "text"), which is what you produce when you compile a Mini Turing program, (the executable file), the virtual address space of the process, plus an internal Minotaur state that describes what the process is doing at the moment. The state includes -open files -scheduling and blocking information -family relationships, child and parent processes -current directory -CPU registers The state includes the exact contents of the CPU registers. If the process is currently running, this is stored implicitly in the registers themselves. If the process is blocked, then the register contents from when it was last running are saved. When the process is un-blocked, the registers of the CPU are reloaded with the saved data. This allows a Minotaur process to switch between any of the available CPUs, since the complete state of execution can be recreated on any CPU by loading its registers with the saved data from the process state. The current scheduling algorithm used in Minotaur takes adavantage of this fact by maintaining only a single queue of runnable processes, and assigning processes to CPUs as they become available. During a process' life, it moves between the states: NEW - just created or in the process of being created READY - runnable, but not running. This basically means it is sitting in the scheduler's queue because there are not enough CPUs to run all of the processes that would like to run. RUNNING - executing on a CPU. There can't be more processes RUNNING than CPUs - this sounds obvious, but the in a simulated OS such as Minotaur, there is no physical reason that this has to be so.... BLOCKED - waiting for an event. When the event happens, the process is woken up and moved to the RUNNING state. ZOMBIE - the process is dead, but it's parent hasn't picked up the exit code by calling WAIT. SLEEPING - a special state used only for daemons in between their invocations. Minotaur is a pre-emptive multiprocessing OS, which means that the process is forced to give up the CPU by the OS when a certain amount of time has expired (a time-slice). MEMORY MANAGEMENT Minotaur divides the physical memory into frames. The kernel and the processes each have their own address spaces which are also divided into frames. The frames of the virtual address spaces are dynamically assigned to physical frames. Extra frames of memory are kept in a swap file on disk. NOTE: Most OS variables are stored in OOT variables and not in the RAM as in a real machine. The Core Map - This is an OS data structure used to keep track of the physical memory allocated for user frames. There is one core map entry per frame. The Swap Map - This is an OS data structure that keeps track of the free swap pages. Text (Code) Pages - The text or code pages that are loaded into memory may be shared by many insantiations of the same program. This is done by the Text class. The Page Daemon - This is a seperate process that is periodically woken up by the dispatcher. This process is responsible that there are a minimum number of free frames available. If not, least recently used frames are swapped out. FILE MANAGEMENT Files in the Minotaur file system go through a couple levels of tables between the process and the disk. When a file is opened by a process, a User File Descriptor is returned. This represents an index into a list of files that the process has open, known as the File Descriptor Table (FDT). Each process will have a different FDT. The entries of the FDT point to a Global File Table (GFT) in the kernel. There is one entry in this table for every open file in the system. Thus multiple FDT entries from multiple FDTs can point to the same entry in the GFT. A reference count is maintained in the GFT of how many FDT entries point to each entry. The entries of the GFT point to an i-node table, which actually points to the physical location of the blocks on the disk. SYSTEM CALLS Processes FORK - creates a new process that is an exact copy of the calling process. - similar to UNIX fork. - NOT similar to OOT fork. - returns 0 to the child and child's pid to the parent. EXEC - runs a given executable file. - does not create a new process. - the normal way to simulate OOT fork is to call FORK followed by an EXEC of the desired program by the child and nothing by the parent. EXIT - terminates the calling process and returns an exit code to the parent. WAIT - retrieves the exit code of the given child process. - will block until the child calls EXIT Files CREATE - create a new file OPEN - opens an existing file - returns a file descriptor to use in subsequent calls. READ BYTEREAD WRITE BYTEWRITE - read and write data from/to the current position in an open file. SEEK - change the current position in a file. CLOSE - close an open file. UNLINK - delete a file. - if other processes still have the file open, it is not actually deleted until they all close it.