Minimal Acceptable System

Requirements for the Course Project

Recall the constraints there are to create the kernel in the first place.

Things with ❗ are minimum requirements.

Things with ➕ are extras/secret sauce/good to haves.

Kernel (running on top of hardware) ❗

This could be a microkernel, monolithic kernel, exokernel, etc.

Needs to express concurrency in some way, create threads, coroutines, events, fibers, (whatever you may want to call concurrency).

The kernel should always get out of the way quickly. Looking for the shortest critical path for the kernel to do a task and getting out of the way.

Maximize Parallelism ❗

Need to extract the maximum available parallelism from the system (e.g. the number of cores in the system). If you have $n$ cores and $n$ activities in the system, we should be able to run all $n$ of those activities in parallel.

Direct Memory Access (DMA) ❗

Extracts a lot of extra parallelism without needing to do any extra computation. You need to be able to ask I/O to write directly to a DMA buffer.

GPU (Secret Sauce) ➕

GPUs ensure thousands of parallel streams, and this will be something that expands the requirement. They run different tasks, so you should try to use GPU as much as possible but not necessary to do CPU tasks (etc.).

Abstraction ❗

Some kernel applications will jump up from kernel code and run into userspace, and will need to be a user abstraction.

(e.g. a pThread that is exposed to the user as a wrapped format that can be used for concurrency)

Error Handling ❗

The kernel, in its final state, should never panic. User processes should not be able to cause the system to reach a state where user processes can make the system unstable.

What about hardware issues?

The kernel is not guaranteed to not panic if there are issues with things like hardware, power, etc. It can panic in those cases, but user programs should not be able to cause a panic.

No Spin-Locks* ❗

Spinning means the kernel has to be blocking because it takes work away from the system. We should not use kernel constructs that require spin locks. In some cases, spinning is necessary (idle loops if there really is nothing to do).

*Sometimes spin locks are necessary for protecting access to some resource or data structure. Doing so should be very very brief. The critical section should be $O(1)$.

No Disabling Interrupts* ❗

*Similar logic with the spin locks. There needs to be some constant amount of instructions that are run if disabling interrupts is necessary.

Disabling preemption is allowed for only kernel space processes, if the kernel needs to ensure interrupt-like safety. User space processes should not be able to do this.

Key Decision: (Non) Preemptible Kernel ❗

A non-preemptible kernel is conceivable. It can be difficult, and requires making design decisions that affect how user programs are written and run. This also can affect how the system will run code.

A non-preemptible kernel requires for highly-cooperative processes in the kernel space that yield for other processes at the end of their cycles, instead of waiting for the scheduler to preempt.

Virtual Memory ❗

Need a very strong notion of address spaces, establish grouping between threads and address spaces.

Demand Paging ❗

User space applications should be able to get more memory if they need it. They should be able to demand more data if required.

Page Swapping and Caching ❗

Need to be able to swap pages to disk or file system if physical memory is full to ensure that other processes can continue to see their illusion of “unlimited” memory.

Page cache is necessary for making sure that popular pages stay in memory, especially for things like dynamically linked libraries.

Processes ❗

Process needs its own context

• User ID
• Group ID
• Current Working Directory (cwd)
• Environment
• Open file descriptors
• Sockets
• Network connections
  • Mapped files
• Virtual address space (similar to any other OS)
• $n$-threads
  • Open-ended, but threads should allow sharing address spaces

Need to be able to create new processes. Things like fork/exec or follow your own convention.

Need to also be able to create new threads. ❗

Blocking Constructs ❗

Do not force user processes to spin (e.g. give them constructs so that they can receive signals or interrupts).

This means you need to solve race conditions that could occur between process resource contention. There are creative ways to approach this; things like futex in Linux (“very ugly abstraction but it works”).

Detect Spin Locking ➕

Detect when a process is spinning and make it yield.

Copy-on-Write ❗

We need to be able to copy-on-write because doing things like forking can be very expensive. May as well share memory until we need to change anything. Then, we incrementally copy our memory.

This shows up in executables (you’re usually not changing executable code), forks, dynamic linking/loading.

Signals ❗

Need a way to be able to handle and send signals to programs that are running on the machine. Usually very easy — essentially an interrupt but instead of hardware to kernel, it is kernel to user space.

UNIX systems have a (not-so-great) legacy system of handling signals.

Dynamic Linking ❗

Need to have dynamic linking for shared libraries. Need them to work efficiently.

This happens at link time. As such, it exists in the final executable as a reference or stub to the dynamically linked library.

➕ Preferably find a way to make sure that the shared libraries get mapped to the same addresses so the TLB doesn’t need to be fully flushed.

Additionally, we need to ensure that each process using a dynamically linked library has its own copy of the variables and stack and heap of the library. This ensure the processes are not able to modify other system memory.

This is a place you want to use copy on write.

Dynamic Loading ❗

User program should itself decide to load in a library during runtime, using an API from the OS similar to UNIX’s dlopen.

Hierarchical File System ❗

Something like the ext filesystems are a good starting point/example.

Need to have some mechanism for ensuring recovery in crashes. ❗

• Minimum requirement is no surprises
  • Machine should be able to do some sanity check and report whether or not the filesystem has been corrupted. Never give users incorrect data. Refuse to mount devices if the filesystem is corrupted.

Recoverable File System ➕

Something like a log filesystem that is able to ensure consistency even when recovering from a crashed state.

Snapshots ➕

Being able to take an atomic snapshot of the state of a filesystem. (never see things in the middle of an update, only before or after).

You could do something like copy-on-write for this as well, so that you preserve the state of the file system when taking a snapshot.

Examples: VideoFS, ZFS, NILFS, BTRFS

Users/Groups/Access Control ❗

Need a way of handling user IDs and group IDs like UNIX does at a minimum. Need to have access control bits for making sure only certain groups can access like read/write to the file system in spots.

Structures ❗

Needs to represents files, directories, sockets, special files for devices, symbolic links.

Ref Link ➕

Copy-on-write in the file system itself. Allows copying large files very efficiently and cheaply.

Deduplication ➕

Being able to deduplicate files if there are multiple copies of the same file on the filesystem.

Additional Requirements ❗

• Login/Logout System ❗
• Shells ❗
• GUI ❗
• Networking ❗
• Music ❗
• Graphics ❗