Poster Instructions
Your poster should include a title, names, and attributions.
Use a layout that allows you to separate topical concerns. Include motivation, approach,
and experimental methods used for evaluation. Include 1-2 architecture figures and
graphs, as appropriate. Limit the amount of text. Do not choose more than 2-3 font sizes
across the entire poster. The size is either 3'x4' (Portrait) or 4'x3' (Landscape).
Here's a sample PPT.
Open-Ended Project Instructions
By March 8, submit a two page description of your project idea, as PDF.
Please list the names of all team members. Below are some suggestions.
You should prove that you have already performed some initial discussions
about how to approach a particular project; do not merely copy and paste
from the ideas below. If you have an idea for a project not on the list
and want feedback, feel free to talk with me before submitting your idea.
Open-Ended Project Ideas
Your open-ended project should build on the Pintos platform (and your own solution)
and extend it in a meaningful and interesting way. Here are some ideas.
Ideally, each project should provide a sample implementation, with tests and a
specification. This way, the project could be added as an assignment to Pintos itself.
However, this is not a strict requirement. Your project may also just explore
additional features itself.
-
SMP/Multicore Support. As is, Pintos is a uniprocessor OS. Add support for multiple processors/cores.
This is a substantial, but potentially highly interesting project. It requires a number
of interconnected parts, including but possibly not limited to:
- Bootup code for each CPU, including ACPI support.
Studying the Linux code
may provide a suitable starting point.
-
Removing/changing all uniprocessor assumptions in the code.
Fortunately, the code is already written for a preemptive kernel; thus,
wherever interrupts are disabled to protect accesses from concurrent interrupt handlers,
spinlocks will need to be used.
- A spinlock implementation, including one that combines spinlock with disabling interrupts
depending on the synchronization need.
- Making the scheduler SMP-safe. Either use a shared ready queue, or use per-processor
ready queues along with simple load balancing.
- TLB shootdown. Should only be needed if multi-threading support is added.
-
Multi-threading Support. As is, Pintos supports only one thread per process. Add support
for multi-threading:
- Expand TCB/PCB as needed. Change context-switching code.
- Add API for user processes to create threads (thread_create, thread_join) - perhaps
similar to pthread_* API.
- Expose multi-threaded synchronization primitives to user level. Though expensive,
for simplicity, they could be mapped via system calls to their kernel equivalents.
A future extension could be the implementation of a futex-like primitive.
-
Implement a proportional-share scheduler. As we discussed in class, recent versions
of Linux have moved away from the traditional MLFQS-derived design and chosen
a WFQ-derived design, the "completely fair scheduler" (CFS). Implement a variant of
proportional share scheduling for Pintos. Different approaches are possible, including
but not limited to:
- Implement Lottery Scheduling. Lottery Scheduling is described here.
Unlike the BSD scheduler you implemented in project 1, strict proportional share
schedulers do not attempt to provide preference for I/O bound processes.
You may wish to read this paper to see how a scheme like lottery scheduling could be extended to
provide similar guarantees.
- Implement Stride Scheduling. Stride scheduling
is a deterministic variant of weighted-fair queing.
- Implement Linux's Completely Fair Scheduler, or CFS algorithm.
Descriptions can be found here and here.
See Li et al for a comparison
to other WFQ schemes.
- The current Pintos kernel uses sampling to estimate a process's past CPU usage.
Modern kernels exploit timestamp counters to more accurately measure a process's
CPU usage. For example, Windows Vista introduced this change for the MS Windows line of kernels.
In particular, the use of timestamp counters allows one to exclude
time spent handling interrupts, which should not count against the current process.
This change requires identifying and implementing the needed APIs. It could be
done in conjunction with one of the scheduler projects.
-
Implement Unix-Style Processes and File Descriptors, along with pipes.
Pintos uses a simplified process model that represents a mixture of Windows and Unix:
Like in Windows, exec() creates both a new process and loads a new program.
Like in Unix, there is a wait() facility to wait for terminating children.
In Pintos, file descriptors are currently not shared between processes and
are not inherited when a child process is created. As a result, it is not
possible to implement Unix-style redirection. Implement a Unix-style model
in Pintos! This would entail:
- Making file descriptors shareable (and reference counted) so that a given
file descriptor could be referred to from more than one process. Right now,
your file descriptors are probably embedded in the owning process's file
descriptor table. This needs to be replaced with dynamically allocated
data structures, which also must be protected against concurrent accesses.
- Add necessary system calls to allow sharing of file descriptors across
processes: fork(), a Unix-style
exec_in_process, dup(), dup2().
- Implement pipe()
- Implement a shell (could be simplified version of your CS3214 shell)
-
Implement user access control.
Define a user principal abstraction for Pintos, and implement access checks to
resources such as files. Extend your project 4 implementation to persistently
store access control information such as files, as well as information about
users (e.g., /etc/passwd). Design how principals map to processes. Implement
privilege escalation ('sudo') and authentication ('login').
-
Implement User Memory Allocation/sbrk(). (This is smaller than the other project ideas,
so suitable for single student or perhaps in combination with others).
Currently, Pintos does not support malloc() for user-level programs because it does not support
a growing heap. Implement sbrk() and adopt your CS 3214 memory allocator to provide malloc()
to user mode processes.
- Implement access to graphics or other hardware
Provide access to the frame buffer to applications (easy to do), and/or provide support
for low-resolution graphics, e.g. VESA. Port a graphical library for use by applications.
More advanced would be access to a recent generation graphics card.
- Implement shared memory
Implement some kind of shared memory facility, such as mmap() with MAP_SHARED.
Sharing should be supported throughout the VM system, including, for instance, sharing
of read-only code segment pages.
Your page eviction policy must take shared memory into account.
- Analyze VM Page Replacement Policies
Implement multiple different replacement policies and analyze their benefits for
different workloads.
- Implement a unified buffer cache/page cache
Currently, Pintos has separate buffer caches and VM caches. This means that shared mappings of
files aren't supported, and that separate eviction policies are in effect.
- Implement advanced file system features
Modern file systems have many advanced features that go far beyond the simple variant
we suggest for Project 4. Implement some of them.
-
Implement Networking .
This will require a Ethernet driver and a stack. You could investigate the porting
of existing drivers and/or stacks.
-
Implement Read-Copy-Update. See here.