Tiny Operating SystemUseful links:
Problem 1. Design Problem: Tiny OS
See below for instructions.
Use the Bsim instance below to enter your code. Your buffer is autosaved to the server every few characters, when you click , or when a running simulation halts. If you received a message about unsaved changes when attempting to close the BSim window, just click and your changes will be saved.
To complete this design problem, please follow the instructions
below, which will ask you to modify the TinyOS code to add some
new functionality. There is no automated test for the lab, so
you'll need to run the tests described in the instructions to see
if you've meet the design criteria.
- Copy the code from TinyOS.uasm into the Tiny OS in the BSim window
- Look through the code to figure out how it works.
- Modify your copy of the code as described below and test your changes
- There is no automated check-in for the lab. When you are ready for checkoff, complete a check-off meeting during staffed lab hours (preferably during the less hectic times early in the week).
Process 0: reads characters from the keyboard,
echoing them to the console. When the return key is entered,
the sentence is translated into pig latin and the result also
printed to the console. Then the process repeats.
Process 1: Each time this process runs, it
increments a counter and then uses the Yield() supervisor call
to give up the rest of its timesharing slot. Every 4096
iterations, the process prints the count to the console.
When running in kernel mode (PC=1), there is no
address translation, i.e., the kernel virtual address is used
directly the physical address for main memory. On startup, the
Beta is running in kernel mode.
When running in user mode (PC=0), address
translation is enabled, which allows each user-mode process to
run in its own virtual address space. Each user-mode address is
translated to a physical address as follows:
the user-mode address is compared against the value
in the MMU SEG_BOUNDS control register. If the address is greater
than or equal to the SEG_BOUNDS value, a segmentation fault
occurs: PC+4 is saved in the XP register and the PC is set to
0x80000008. Note that the value saved in XP is a user-mode
virtual address. If the bounds check succeeds, proceed to the next step.
the user-mode address is added to the value in the
built-in MMU SEG_BASE control register to form the physical
address used to access main memory.
LD(CurProc, r0) // pointer to current process table entry LD(r0, 31*4, r2) // load base value from proc table ST(r2, SEG_BASE) // store into MMU SEG_BASE control register LD(r0, 32*4, r2) // load bounds value from proc table ST(r2, SEG_BOUNDS) // store into MMU SEG_BOUNDS control registerWhere do the appropriate base and bound values come from? They are determined at assembly time. To enter code and data for a user-mode process, use the .segment XXX directive to tell the assembler to start a new user-mode segment called XXX. Each user-mode segment has its own symbol table and is assumed to start at virtual address 0. Here's a very simple user-mode process that initializes a stack, then enters an infinite loop incrementing a counter in main memory:
.segment Example . = 0 // just a reminder that we start at 0 CMOVE(stack, SP) // initialize the stack pointer loop: LD(counter, r0) // load counter value ADDC(r0, 1, r0) // increment... ST(r0, counter) // store back into main memory BR(loop) // repeat counter: LONG(0) // storage for counter, initialized to 0 stack: STORAGE(100) // reserve 100 words for the stackWhen assembled, two new symbols are defined the kernel's symbol table: Example_base with the address of the physical memory location occupied by the first word of the segment (in this case the physical address of the CMOVE instruction), and Example_bounds with a value equal to the size of the segment in bytes, including both instructions and data. Note that since execution of this user-mode process will begin at location 0, that location should contain an instruction! The initial process table entry for this user-mode process would look like
STORAGE(30) // storage for registers 0-29 LONG(0) // storage for XP (initial PC is 0) LONG(Example_base) // process table copy of SEG_BASE LONG(Example_bounds) // process table copy of SEG_BOUNDS
Design Problem 1: MapUserAddress There are times when given a user-mode address, the kernel needs to read the contents of that location. For example, when processing an ILLOP exception, the kernel reads the offending instruction from memory and checks the opcode field to see if it's a SVC. The kernel code to do this looks like
SUBC(XP, 4, r0) // u-mode address of illegal instruction CALL(MapUserAddress) // convert to k-mode address LD(r0, 0, r0) // Fetch the illegal instruction SHRC(r0, 26, r0) // Extract the 6-bit OPCODEYour task is to write the code for the MapUserAddress procedure (search for "[Design Problem 1]" in the TinyOS code. This procedure emulates in software what the MMU does in hardware: converting a user-mode virtual address to the corresponding physical address. Once MapUserAddress is functioning correctly, the pre-defined process 0 and process 1 code should run correctly. So if you start the simulation of the assembled code, select the console at the bottom of the simulation pane with a single click, then type "hello there" followed by RETURN, process 0 should type "ELLOHAY ERETHAY". Meanwhile Process 1 will print out the value of its counter every now and then.
Design Problem 2: Add support for Mouse clicks Step 1: Add mouse interrupt handler When you click the mouse over the console pane, BSim generates an interrupt, forcing the PC to 0x800000014 and saving PC+4 of the interrupted instruction in the XP register. Note that BSim implements a "vectored interrupt" scheme where different types of interrupts force the PC to different addresses (rather than having all interrupts for the PC to one location). The following table shows how different exceptions are mapped to PC values:
0x80000004 illegal opcode
0x80000008 segmentation fault
0x8000000C clock interrupt*
0x80000010 keyboard interrupt**
0x80000014 mouse interrupt**
* must specify .options clk to enable
** must specify .options tty to enable
CLICK()This instruction can only be executed when in kernel mode (e.g., from inside an interrupt handler). It returns a value in R0: -1 if there hasn't been a mouse click since the last time CLICK() was executed, or a 32-bit integer with the X coordinate of the click in the high-order 16 bits of the word, and the Y coordinate of the click in the low-order 16 bits. The coordinates are non-negative and relative to the upper left hand corner of the console pane. In our scenario, CLICK() is only called after a mouse click, so we should never see -1 as a return value. Testing your implementation: insert a .breakpoint before the JMP(XP) at the end of your interrupt handler, run the program and click the mouse over the console pane. If things are working correctly the simulation should stop at the breakpoint and you can examine the kernel memory location where the mouse info was stored to verify that it's correct. Continuing execution (click the "Run" button in the toolbar at the top of the window) should return to the interrupted program. When you're done remember to remove the breakpoint. Step 2: Add Mouse() supervisor call Implement a Mouse() supervisor call that returns the coordinate information from the most recent mouse click (i.e., the information stored by the mouse interrupt handler). Like the GetKey() supervisor call, a user-mode call to Mouse() should consume the available click information. If no mouse click has occurred since the previous call to Mouse(), the supervisor call should "hang" until new click information is available. "Hang" means that the supervisor call should back up the saved PC so that the next user-mode instruction to be executed is the Mouse() call and then branch to the scheduler to run some other user-mode program. Thus when the calling program is rescheduled for execution at some later point, the Mouse() call is re-executed and the whole process repeated. From the user's point of view, the Mouse() call completes execution only when there is new click information to be returned. The GetKey() supervisor call is a good model to follow. Notes: Supervisor calls are actually unimplemented instructions that cause the expected trap when executed. The illegal instruction trap handler looks for illegal instructions it knows to be supervisor calls and calls the appropriate handler -- look at SVC_UUO for details. To define a new supervisor call, add the following definition just after the definition for Yield():
.macro Mouse() SVC(8)This is the ninth supervisor call and the current code at SVC_UUO was tailored for processing exactly eight supervisor calls, so you'll need to make the appropriate modifications. Step 3: Add third user-mode process that reports mouse clicks Modify the process table in the kernel to add the appropriate entry for a third user-mode process P2. You should then define a new segment called P2 and add user-mode code for the new process that calls Mouse() and then prints out a message of the form:
Click at x=000000EE, y=00000041Each click message should appear on its own line (i.e., it should be preceded and followed by a newline character). You can use WrMsg() and HexPrt() to send the message; see the code for Process 0 for an example of how this is done. Testing your implementation: If all three steps are working correctly the appropriate message should be printed out whenever you click the mouse over the console pane. You may find it necessary to use .breakpoint commands to debug your user-mode code.
Design Problem 3: Add Signal() and Wait() SVCs After Problem 2, there are now three user-mode processes that want to print messages to the console. Depending on timing of user input and the scheduling of processes, the printouts may interleave in a way that's very hard to read. We'll use a semaphore to ensure that each process' printout is completed without interference from the other processes. In other words, think of the console as a shared resource, which should only be accessed by one process at a time. Your first task is to implement the handlers for the Signal() and Wait() SVCs. TinyOS supports a fixed number N of integer semaphores numbered 0 through N-1 (N = 4 in the current code). The semaphore number for the SVCs is passed in the user's R0. If the value in the user's R0 is not between 0 and N-1 inclusive, the SVCs should simply resume user-mode execution after the SVC. The Signal() SVC increments the value of the specified semaphore, then resumes user-mode execution after the SVC. For example,
CMOVE(1, r0) // signal semaphore #1 Signal()The Wait() SVC tests the value of the specified semaphore. If the value is greater than 0, it's decremented, then user-mode execution resumes after the SVC. If the value equals 0, the WAIT operation cannot be completed as this time, so the kernel handler should arrange to re-execute the SVC when execution resumes, then run the next process. The next time the WAITing process runs, it will once again test the value of the specified semaphore. For example,
CMOVE(1, r0) // wait on semaphore #1 Wait() // execution resumes here only after the WAIT succeedsAdd the appropriate Signal() and Wait() SVC calls to processes 0, 1, and 2 so that once a process starts to print on the console, all the other processes must wait until the printout is complete.