Tiny Operating System

Useful links:

• Introduction to BSim
• Summary of Instruction Formats (PDF)
• Beta Documentation (PDF)

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 Assemble, or when a running simulation halts. If you received a message about unsaved changes when attempting to close the BSim window, just click Assemble 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. { "required_tests": ["36036"], "initial_state" : { "beta.uasm": "url:../exercises/beta.uasm", "TinyOS.uasm": "url:../exercises/tinyos/tinyos.uasm" }, "state":{"Tiny OS":"url:../exercises/tinyos/tinyos.uasm"} }

Instructions

1. Copy the code from TinyOS.uasm into the Tiny OS in the BSim window
2. Look through the code to figure out how it works.
3. Modify your copy of the code as described below and test your changes
4. 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).

TinyOS.uasm implements a simple timesharing system (or will after you complete Problem 1!). There is kernel code to deal with supervisor calls, illops, and keyboard interrupts, along utility functions for printing out console messages, etc. And initially there are two user-mode processes:

• 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.

There are three design problems that ask you to modify TinyOS. You must complete the first problem, but the last two are optional, providing additional points should they be completed successfully.

Memory Management Unit

BSim implements a very simple memory-management mechanism called base and bounds when ".options segmentation" is included in the program. The MMU contains two control registers, SEG_BASE and SEG_BOUNDS, which the Beta can access using LD and ST instructions. Here's how it works:

• When running in kernel mode (PC[31]=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[31]=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.

The net effect is that the user-mode virtual address space is mapped to a contiguous region of physical memory that starts at the location specified by the SEG_BASE control register. The size of the region (and hence the size of the virtual address space) is determined by the SEG_BOUNDS control register.

The appropriate base and bounds values for each process are kept in the process table, along with the saved register values. When getting ready to run a user-mode process, the kernel initializes the MMU SEG_BASE and SEG_BOUNDS control registers using ST instructions to two reserved memory addresses, which the Beta interprets as accesses to the MMU control registers.

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 register

Where 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 stack

When 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 OPCODE

Your 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 0x80000014 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:

0x80000000 reset
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

Recall that only user-mode programs can be interrupted. Interrupts signaled while in the Beta is running in kernel-mode (e.g., handling another interrupt or servicing a supervisor call) have no effect until the processor returns to user-mode.

The original TinyOS code prints out "Unexpected interrupt..." and then halts if a mouse interrupt is received. Change this behavior in your copy of the code by adding an interrupt handler that stores the click information in a new kernel memory location and then returns to the interrupted process. You might find the keyboard interrupt handler a good model to follow.

We've added a new Beta instruction your interrupt handler can use to retrieve information about the last mouse click:

     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=00000041

Each 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 succeeds

Add 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.