CSC468h 971017 Tutorial Notes: Week 6 This document contains all of "wk6" but it also contains a few code examples that were discussed in Andria's tutorial section. Topics: ====== - Setting up your own copy of Minotaur - Creating a new system program in your minotaur/sysprogs directory - Hints for Assignment 2 - Notes on Assignment 2 - Adding A New System Call - Processes - Timeslices - Daemons - Tasks for Assignment 2 Announcements: ============= - Midterm test will take place in next week's tutorial Setting up your own copy of Minotaur: ==================================== The scripts in include/mutil can be used to set up links to the minotaur source code and make local copies as appropriate. The scripts are: mtsetup -- This is used to create a "minotaur" directory in YOUR own directory that contains symbolic links to the real minotaur files in /local/include/oot/Minotaur. To call this script just type: % cd % mtsetup mtcopy -- Since the files in your minotaur directory are links, you can't change these files so you need to create your own copy of any file you want to change. To do this, go to your own minotaur directory and call mtcopy with the name of the file you want a copy of. For example, if you wanted your own copy of the "System" file, you would type: % cd ~/minotaur % mtcopy System NOTE: If you need local copies of files in a linked directory, you will first need to create a local directory and then relink to the files in that directory. See the file include/mutil/mutil.README for more details. Once you have set up your own minotaur directory, you should run OOT (oot2) in your own directory instead of in /local/include/oot/Minotaur. Changes to System The System file defines a bunch of constants including the system path. This should be changed from %oot/Minotaur to your own path (/homes/u2/csc468h/a468xxxx/minotaur) in order to run mkfs. Creating a new system program in your minotaur/sysprogs directory: ================================================================= You will need to write a system program that uses YIELD in order to test A2. System programs are written in the mini turing language. See /local/include/oot/Minotaur/sysprogs/*.mt for some examples. You will need to create your system program file in the minotaur/sysprogs directory in your own copy of Minotaur. First, you'll need to make sure that you can write to that directory (by removing the symbolic link for sysprogs, recreating the directory, and then relinking the other files). % cd ~/minotaur % \rm sysprogs % mkdir sysprogs % cd sysprogs % ln -s /local/include/oot/Minotaur/sysprogs ORIG % ln -s ORIG/* ORIG/.[A-z]* . Then create your system program in your minotaur/sysprogs directory. % cp sysprogs/testfork.mt sysprogs/test.mt And compile it using the mini turing program. % cd sysprogs % toot /local/include/oot/mtunis/mturing/mturing test.mt This creates a "test" executable that can be included in the Minotaur file system. Now we need to create a new Minotaur file system (stdfile) that includes the "test" system program. You do this by starting up oot2. Click on mkfs/mkfs in your copy of minotaur in your home directory. Click on Run." It will ask you for the name of the file system to create, and it will go through each program in your sysprogs directory, asking you one at a time if you would like to include them in the file system. The next time you start up Minotaur from your home directory, you'll be able to see this new program when you type 'ls' from the minotaur '%' prompt. At the minotaur prompt, type 'test' to run your program. Hints for Assignment 2: ====================== 1) Try to understand minotaur well before writing code. This will likely save you time in the long run. 2) Read the documentation and all the code that seems relevant. This will help you achieve #1. You should at least be familiar with the following files: Kernel/Schedule - process scheduler monitor to maintain ready queue of processes & decide which process to execute next. Kernel/Dispatch.b - takes processes off the ready queue and sets them up for execution. Kernel/Daemons - fires up daemons every once in a while, based on clock tick counter. Hardware/CPU - the CPU module which defines the virtual processor. Hardware/CPU_x.b - Contains the Execute routine to execute user code. Kernel/Process - In charge of creating, destroying, Kernel/Process.b and maintaining processes. Kernel/ProcMon - Switch control between CPU's dispatch process and the user process it wants to run. Notes on Assignment 2: ===================== For this assignment you will have to change Minotaur's scheduling policy to use a two-level feedback queue. Part of this new policy involves implementing a new system call, "YIELD". This system call allows a process to be nice and give up its use of the CPU so that another process can run. Currently Minotaur's process scheduler simpy implements a round- robin policy, with a single global queue of ready processes. Kernel processes are inserted at the head of this queue, and user processes are inserted at the tail. Processes are removed from the head of the queue. Your task is to design and implement a two-level (foreground and background) feedback queue for processor scheduling in Minotaur. Processes in the foreground queue have higher priority than those in the background queue; within a queue level, processes are served round-robin. The following types of processes are naturally found on the foreground queue: - kernel processes (ProcStruct.Priority in Kernel/Process) - user processes newly initiated (NewProcess in Kernel/Process.b) - user processes that have just YIELDed the processor Kernel processes are inserted at the head of the foreground queue; user processes are inserted at the tail. The background queue contains ready user processes not found on the foreground queue; insertion here occurs at the tail. Periodically, the background queue is scanned and each process that satisfies Condition A is moved to the foreground queue for its next burst. Condition A is defined by: A process with an average CPU time used per dispatching assignment that is less than the system-wide average, where the system-wide average is taken over all currently active ready user processes. The periodic interval for initiating a scan of the background queue is timeSlice/2. The foreground time slice (foregTS) is equal to the current timeSlice, and the backgound time slice (backgTS) is equal to 2*foregTS. - user processes - kernel processes Still Ready - YIELD --------------<-------------------<----------- | | | Foreground | New | ___________ | Finished ----|---> __|_|_|_|_|-------------> ----|--------> | | | | | | | Background | Pool of | | ___________ | Processors | |---> __|_|_|_|_|-------- | | | | | Not Ready | | Not Finished | | (Blocked on | | event) | ----------------- | ------<-------| Condition |-----<--------| | Gets Resolved | ----------------- Adding A New System Call: ======================== To add a new system call you will need to write new minotaur code in OOT. The test programs that minotaur runs are written in MiniTuring. MiniTuring programs will not be aware of the new system call you have implemented in OOT without further work on your part. To save you trouble, a generic SysCall facility has been implemented which MiniTuring will recognize. This SYSCALL can be used in your MiniTuring test programs to call the new minotaur system call you have written. The call is identified by the trap number you have associated with the new system call. There are more details on the generic syscall facility in the documentation. See Minotaur External Documentation - Section 11. Processes: ========= There are two main structures associated with a process: the UserStruct and the ProcStruct structures. UserStruct is used to store information about the cpu state for the given process. It also contains a pointer to the process struct, the fileTable and system call parameters. This structure may be easily obtained for the process which is currently on the CPU. A pointer to the user struct is stored at the same address of virtual address space for each process. The ProcStruct contains information about the process such as its ID and its family relationships. It is also used to store scheduling information and process statistics such as the number of CPU cycles used and the amount of CPU time used in milliseconds. These structures are kept in the kernel's process table (in Kernel/Process). % (Kernel/Process) % ProcStructs are kept in a kernel process table. They contain all % process scheduling and management information for a process, % type ProcStruct : record % Process state information pID : nat1 % Process ID LPT : nat4 % Location of process' LPT textClass : nat1 % Index of text class fileName : string % File name of text file state : nat1 % Process state stateNext : ^ProcStruct % Next process in state list statePrev : ^ProcStruct % Previous process in state list statusCode : nat4 % Exit code / Event proc is blocked on stats : Stats % Process execution statistics % Scheduling information schedNext : ^ProcStruct % Next process in scheduling queue schedPrev : ^ProcStruct % Prev process in scheduling queue Priority : nat1 % Process priority % Family relationships parent : ^ProcStruct % Parent process olderSibling : ^ProcStruct % Older sibling process youngerSibling : ^ProcStruct % Younger sibling process youngestChild : ^ProcStruct % Youngest child process % Memory management maxStackPage : nat1 % Maximum allowable stack page numTextPages : nat1 % Number of text pages maxAlloc : nat1 % The highest allocated user page # end record % (Hardware/CPU) % The state of a CPU is completely defined by the contents of a Regs % structure. In a multiprocessor system, there is a one to one % correspondence between "physical" processors and Regs structures. % type Regs : record processorID : nat1 % Read only register containing processor ID status0 : nat4 % Status dwords of processor status1 : nat4 % LPT : nat4 % Location of local page table in OS virtual memory LPTE : nat4 % Physical address of local page table GPT : nat4 % Location of global page table in physical memory faultAddress : nat4 % Address which caused page fault faultInfo : nat4 % Bit field describing the type of page fault pc : nat4 % Program Counter: pointer to next code byte sp : nat4 % Pointer to one dword past the top of the stack ksp : nat4 % Kernel stack pointer - used when in kernel mode st : array 1 .. NumStrings of ^StrReg % String registers ns : nat4 % Used to find a free string register % 'fs' contains an pool of pre-allocated strings that can % be rapidly moved to and from the string registers. fs : array 1 .. NumStrings of ^StrReg % Pool of free strings poolSize : nat4 % Number of free strings in the pool % The set of registers used to hold pointers to stack frames. % A "stack frame" (also called a "display") is an area on the % stack set aside for the local variables of a MiniTuring % procedure. display : array 0 .. DisplaySize - 1 of nat4 % The processor traps when counter reaches timeSlice (counter % increments after each instruction). If timeSlice = 0, the % processor will never trap. counter : nat4 timeSlice : nat4 codePrefetch : Page codePage : nat1 stackPrefetch : Page stackPage : nat1 trapNum : nat1 % Contains the value of the last trap end record There is a Dispatch OOT process (running the code in Kernel/Dispatch.b) associated with each CPU that picks the next ready process and executes it. % (Kernel/Dispatch.b) % This is the dispatch routine. It goes into an endless loop % picking processes off the ready queue and setting them up for % execution. When there are no ready processes it services % interrupts until another process appears on the ready queue. % After each "tick" it makes a call to Daemons.Tick, which will % periodically schedule daemons to run. body procedure Dispatch (var cpu : ^CPU.Regs) var p : ^ProcStruct % process to activate var u : pUser % user structure of process to activate var t1, t2 : int % used to determine CPUtime cpu -> timeSlice := TimeSlice % Set CPU's time slice to default loop p := Schedule.GetReadyProcess % Removes 1st process on queue ... % Update the counter and call Daemons.Tick % if it reaches TimeSlice. cpu -> counter += 1 if cpu -> counter = TimeSlice then cpu -> counter := 0 Daemons.Tick end if ... % Restart the process ... Daemons.Tick end loop end Dispatch There is an OOT process associated with each minotaur process. The ProcMon monitor (see Kernel/ProcMon) is used to switch control between the CPU's dispatch process and the user process it wants to run. This ensures that the CPU can run only one process at a time. % (Kernel/ProcMon) % S U S P E N D % A process calls this routine to give back control of the CPU % and go to sleep until one of the dispatchers wakes it up again. % When this happens, the new CPU on which the process should be % run is retrieved from processCPU (pID). procedure Suspend (var cpu : ^CPU.Regs, pID : nat1) signal CPUreleased (cpu -> processorID) if not resumed (pID) then wait resume (pID) end if resumed (pID) := false cpu := processCPU (pID) end Suspend The Schedule monitor (see Kernel/Schedule) implements the round-robin ready process queue. The CPU's Dispatch process takes ready processes from this queue and runs them. The processes get put back onto the queue when their timeslice expires, or if they become ready after being blocked on some event. Kernel processes (processes with ProcStruct.Priority = KernelPriority) are placed at the front of the queue. All other processes are placed at the end of the queue. % (Kernel/Schedule) % This is the process scheduler monitor. It is in charge of % maintaining the ready queue of processes and deciding which % process to execute next. It simply implements a round-robin % policy for user processes, keeping the ready processes in a % doubly linked list. Kernel processes are given higher priority % by placing them at the *head* of the list. % % The routines Lock and Unlock are provided to prevent a process % from being scheduled while one of its pages is being swapped out. monitor Schedule ... % Places the process at the end of the ready queue, unless % the priority is KernelPriority in which case the process % is placed at the start of the ready queue. procedure PlaceOnReadyQueue (p : ^Process.ProcStruct) if first = nil then first := p last := p p -> schedNext := nil p -> schedPrev := nil else if p -> Priority = Process.KernelPriority then p -> schedPrev := nil p -> schedNext := first first -> schedPrev := p first := p else p -> schedNext := nil p -> schedPrev := last last -> schedNext := p last := p end if end if end PlaceOnReadyQueue Timeslices: ========== As a process' instructions are being executed, they are counted in a counter variable. When the counter reaches the max number of instructions that can be executed in one timeslice, a TRAP is generated. This switches the CPU back into execution of kernel code. The function "Process.Tick" is called to accomplish this. This function also places the process back onto the ready queue. % (Kernel/Process.b) % T I C K % When a time slice expires, this procedure is called to % force the current process to relinquish the CPU. body procedure Tick (var cpu : ^CPU.Regs) var p : ^ProcStruct var b : boolean % required for Memory.LockPage CPU.FlushStackPage (cpu) p := GetCurrentProcStruct (cpu) Memory.UnlockPage (cpu, BufferPage) State.ChangeState (p, READY) % Now in READY state Schedule.PlaceOnReadyQueue (p) ProcMon.Suspend (cpu, p -> pID) b := Memory.LockPage (cpu, BufferPage) CPU.iRet (cpu) end Tick Daemons: ======= A daemon process is a "helper" process for the kernel. Daemon processes are run periodically to do some work for the kernel. The module Kernel/Daemons is responsible for managing the minotaur daemons. After each context switch, the procedure "Daemons.Tick" is called. This procedure wakes up a daemon every couple of times it is called. For example, the only daemon currently used by Minotaur is the Page Daemon which is run every 12 (4 * numProcessors) times Daemons.Tick is called. When a daemon is woken up it is placed on the process ready queue. Since they are kernel processes they are placed at the front of the queue. Each time that Daemons.Tick is called, a counter is updated. When the value of the counter is such that a daemon should run, then that daemon is woken up. % (Kernel/Daemons) % T I C K % Update counter and run any daemons if necessary procedure Tick var counter : nat4 counter := DaemonMon.UpdateCounter if (counter mod PageDaemonPeriod) = 0 then Memory.WakeUpPageDaemon end if end Tick Tasks for Assignment 2: ====================== -- Implement the YIELD system call. -- Change the scheduling from using a global round-robin ready queue to using two queues. A foreground queue for Kernel processes, new processes, and yielded processes; and a background queue for the rest of the processes. -- Setup minotaur so that the background queue is periodically scanned. Processes that are using less CPU time than the system wide average are moved into the foreground queue. (Daemon)