Skip to content
We're building a kernel yo
C Assembly Makefile Other
Branch: master
Clone or download

Latest commit

Fetching latest commit…
Cannot retrieve the latest commit at this time.

Files

Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
410kern
410user
kern
spec
user
vq_challenge
.gitignore
Makefile
README.STARTING_P3
README.dox
config.mk
doxygen.conf
update.sh

README.dox

/**

@mainpage 15-410 Project 3

@author William Ganucheau (wganuche)
@author Scott Krulcik (skrulcik)

# Stones

Stones is the hottest new OS on the market. Its many features include:

- Multiple threads running "simultaneously"
- Virtual Memory (whoa!)
- Console drivers
- Keyboard drivers
- All the system calls you could ever want ([full specification](https://www.cs.cmu.edu/~410/p2/kspec.pdf))
- Freedom (unlike the UC Stones)

Stones was written, developed, broken, fixed, hated and loved
by William Ganucheau (`wganuche`) and Scott Krulcik (`skrulcik`)

## Design & Implementation

### Scheduler

_Relevant files:_ scheduler.h scheduler.c

Stones uses a round robin scheduler. The timer generates an interrupt every 5ms, and, except under extraordinary circumstances, each interrupt causes a context switch to the next thread. To determine the next thread, the scheduler maintains a double-sided queue of runnable threads. When scheduled, threads can have one of two priorities: `PR_IMMEDIATE` or `PR_DEFAULT`. `PR_IMMEDIATE` threads are added to the front of the queue while `PR_DEFAULT` threads are added to the end of the queue. This allows threads that were waiting on a certain event, like a keyboard interrupt, to resume quickly while threads that were simply descheduled because their time was up wait their turn.

_Relevant bugs:_ #1, #2

### Task Managment

_Relevant files:_ task.c task.h thread.c thread.h reaper.c reaper.h

From the kernel spec:
>The “Pebbles” kernel supports multiple independent tasks, each of which serves as a protection domain. A task’s resources include various memory regions and “invisible” kernel resources (such as a queue of task-exit notifications). Some Pebbles kernels support file I/O, in which case file descriptors are task resources as well.
Execution proceeds by the kernel scheduling threads. Each thread represents an independently schedulable register set; all memory references and all system calls issued by a thread represent accesses to resources defined and owned by the thread’s enclosing task. A task may contain multiple threads, in which case all have equal access to all task resources. A carefully designed set of cooperating library routines can leverage this feature to provide a simplified version of POSIX “Pthreads.”

The lifecycle of a task can be summed up in three basic stages:
1. Birth: Initialization, work
2. Reaping (optional): Reap child tasks that may have been spawned by tasks that wanted big families
3. Death: Cleanup and freeing (of the UC Stones)

#### Birth

This is honestly a pretty boring time in a task's life. In general the following fields are initialized:
- ID
- Parent pointer
- ID of original thread
- Status
- Exited children list
- Running children list
- Virtual memory instance
- Other stuff that I promise is super boring

The underlying thread is immediately runnable and free to do work.
The one interesting thing that happens during birth is that a task informs its parent of its existence by adding a node to the parent's running children list.

#### Reaping

Finally something interesting. When reaping children, the first thing the task does is ensure that it _has_ children (How awkward would it be if it waited forever?). Once this check is made, it checks if any of its children have died already (via its list of exited children). If so, it picks one and notifiers the interested party of the child's id and exit status. Otherwise, it waits until a child dies. This leads us nicely to...

#### Death

When a task dies, it starts by removing itself from the hashmap of active tasks and frees as much as it can. Finally it signals *both* the Reaper and its parent task to let them know that a task has exited.

Note that tasks are only terminated after the last of their threads is destroyed.

#### Threads

That was a lot of talk about tasks, but the truth is threads are pretty boring in comparison. Threads generally have the following state:
- ID
- Task
- Kernel stack
- Software exception handler

They live, they die, and they're reaped just like tasks. 

#### Reaper
The Reaper is a thread dedicated to doing the dirty work. Certain things, like a thread's kernel stack, can't be freed by their owners. This is the job of the Reaper.

### Virtual Memory

Stones maintains one page-directory per task. Additionally, each
task is supplied with a list of user regions which correspond to virtual memory addresses the task has access to. 

#### Sharing Read-Only Regions
To conserve memory/physical frames, Stones shares read only regions between tasks that are forks of other tasks. The implementation of this is somewhat complex:

Each region itself maintains a list of regions (`shared_list`). Initially, when a new region is created, this list contains only the region itself. (So when Region A is created, Region A's `shared_list` contains only Region A). When a read-only region is copied, it first creates the desintation region B (importantly, region B's shared list is initially empty). A then adds B to A's shared-list. If, later on, we need a copy of B, we add that element after B in the list.

Eventually, a region will be freed. If that region is the only region on the list, then we know it is the last region to be using those frames, so we can remove it. Otherwise, we simply remove the element from the list. Note that if we're removing the region that contains the list that all the elements are on, we need to move all the elements to the next region's list.


Perhaps this is most easily shown with an example:

##### Example

Denote a region as a capital letter. A region's shared list is shown in brackets. For example:
```
A [A B C]
```
Denotes a region A whose shared list contains A, B, and C. Let's start with creating a new region:
```
A [A]
```
Now suppose we want a new region B that is a copy of A. Then we have
```
A [A B]
B []
```
If we make a copy of B and another copy of A we get:
```
A [A B C D]
B []
C []
D []
```
This makes one invariant of this method clear: All the regions sharing the same frams should be on the same list, and all but one of those regions' shared lists should be empty.

Now suppose we free region D. Then we get
```
A [A B C]
B []
C []
```
If we free A, we get
```
B [B C]
C []
```
Freeing C:
```
B [B]
```
Finally, if we free B here, we know to free the underlying frames because B is the only region on the list and therefore the last region using those frames.

### Drivers

Stones includes drivers for a keyboard and console. User code may utilize these hardware devices via functions provided by the kernel.


#### Console Driver

_Relevant files_: console.h console_driver.c console_colors.c

The console driver provides support for drawing all the best characters onto your console. Multiple colors are supported! (*oooh ahhh*)

Our main design decision regarding the console was involved balancing synchronization with responsiveness. Both the position of the cursor and the console output _should_ be consistent from a user's perspective. Due to the nature of the hardware interface, proper thread safety would require mutual exclusion across multiple operations (i.e. locks not CAS). Unfortunately, we also need to support writing to the console from interrupt handlers. Interrupt handlers cannot acquire locks, because they may interrupt threads that are holding the same locks.

With these two ideas in mind we decided to implement the core functions of the console driver without any synchronization, but make it easy for other kernel code to syncrhonize certain console operations (see "Readline and Print" below).

The thread-dangerous console driver functions are not careless; they make some attempts to perform well (or at least reliably) under racy conditions. For example, when writing a character using `putbyte`, we cannot ensure that retrieving a cursor position to write (or delete) a character, and drawing at that position will occur atomically. Despite this, we ensure that the software cursor stays consistent, so a rapid sequences of backspaces mixed with new characters cannot bring the software cursor into an invalid state.

Coarse syncrhonization of console output may be achieved with the `console_execute` function, which blocks until it has exclusive access to the console, but only relative to other operations executed in the same manner. This means that we can ensure that no two `readline` or `print` calls are executing simultaneously, without locking in the console functions themselves.


#### Keyboard Driver

_Relevant files:_ keyboard_driver.h keyboard_driver.c

Stones provides *both* `readline` and `getchar` system calls. (You read that right, wonderful TA or professor who is grading us!) Readline, as required by the official spec, echos characters immediately as they are typed. It also ensures that output is not interleaved with calls to `print`, ensuring wysiwyg. `getchar` is less restrictive. It does not echo to the console, and therefore does not synchronize with print (so both may be active at the same time). The thread dangerous calls to putbyte that cause readline echoes all occur within the uninterruptable keystroke handler, so they cannot be interleaved.

#### Readline and Print

Our `readline` and `print` implementations both write output to the console. Our kernel ensures that the echoes from print will not interleave with calls to print, and calls to print will not interleave with eachother.

_Relevant bugs:_ #3



## Bugs

_We prefer the term "undocumented features"._

1. Among runnable threads with the `PR_IMMEDIATE` priority, the scheduler actually reverses their order. So if I perform the following scheduling sequence:
    ```
    make_runnable(A, PR_IMMEDIATE)
    make_runnable(B, PR_DEFAULT)
    make_runnable(C, PR_IMMEDIATE)
    make_runnable(D, PR_DEFAULT)
    ```
    The order that the threads will run in is `(C, A, B, D)` whereas the more correct order is `(A, C, B, D)`. This can be solved with maintaining two queues, one per priority, or keeping a pointer to the most recently inserted high-priority thread and inserting later high priority threads after that one

2. The two priority levels do introduce the possibility of starvation, but it is unlikely to occur indefinitely. Priority levels can only be manipulated in our kernel code, not by user code. Knowing overuse of `PR_IMMEDIATE` could cause startvation (and reduces its immediacy), we restrict `PR_IMMEDIATE` to keyboard and timer events.

3. Since the keyboard driver waits to acquire exclusive access to the console, it's possible that this blocks for a while. If the user is impatient and starts typing immediately, we might drop the beginning of the input.

*/



You can’t perform that action at this time.