Final Presentation Schedule

• CS 4284 Peer Eval: PintosGrind
• CS 4284 Peer Eval: Multiprocessor
• CS 4284 Peer Eval: Unix Processes
• CS 4284 Peer Eval: Networking
• CS 4284 Peer Eval: Security

Meeting Schedule

Apr 6+13+20, Mo
3:45pm  Andrei, Nathan, Nathan
4:30pm  Audrey, Chris, Richard, Patrick 

Apr 8+15+22, We
3:00pm  David, Alan, Kelsey     
3:45pm  Scott, Marc, Brianna        
4:30pm  Antoine, Sam, Thomas        

Poster Instructions

• Your poster should include a title, names, and attributions. Please list me as faculty advisor for the VTURCS competition.
• Use a layout that allows you to separate topical concerns. Include motivation, approach, and experimental methods used for evaluation.
• Read John Wilkes Creating an effective poster
• Include 1-2 architecture figures and graphs, as appropriate.
• Limit the amount of text. Prefer graphs and charts to text. Do not choose more than 2-3 font sizes across the entire poster.
• Be generous with white space
• Use high-resolution images or scalable image formats
• The size is either 3'x4' (Portrait) or 4'x3' (Landscape).
• Properly document any outside sources used
• Here are two examples sample PPT 1, sample PPT 2 you may draw from
• The printer will accept pptx and pdf files

Open-Ended Project Instructions

By March 6, 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.

I would like Patrick to join one of the existing groups for this, forming a group of 4.

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 by itself.

I expect that some projects will be more implementation-heavy, and involve less experiments. Others may involve less implementation and more experiments.

I would very much favor the projects that explore new directions, including multiprocessor support, multithreading support, networking, and security.

• SMP/Multicore Support. As is, Pintos is a uniprocessor OS. Most general-purpose OS are not. Add support for multiple processors/cores. 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. Alternatively, I would look at MIT's xv6 kernel and/or MIT's JOS system.
  • 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-capable. 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 also.
• 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.
  Multiprocessor and multithreading support could also be combined into one project for twice the impact.

• Make Pintos Secure/implement security/user access control. As is, Pintos has no notion of security whatsoever. Adding security is a cross-cutting concern, affecting all parts of an operating system, from process management to the filesystem implementation. It also requires support for authentication as well as privilege escalation. If you have ever wondered how 'setuid root', 'sudo', and similar commands work, this project is for you.

  Define a user principal abstraction for Pintos, and implement access checks to resources such as files. Extend the file system implementation to persistently store access control information for files, as well as information about users (e.g., /etc/passwd). Design how principals map to processes. Implement privilege escalation ('sudo') and authentication ('login'). The idea here would be to mimic what Unix does, but you could, if interested, implement more sophisticated access control models, such as SELinux. Mimicking Unix would give you a deeper understanding of the vulnerabilities faced by currently deployed versions of Unix.

  I believe this project can be built with or without a working project 4, it only requires a working project 2.

  A potential alternative may be to implement a system similar to AppArmor

• Implement Networking . As is, Pintos does not provide support for networking. However, our version does have support for PCI. This project involves writing an Ethernet driver and hooking it up to a networking stack. A possible approach may be:
  • A minimum functionality device driver, for the E1000 card. This is used in the network lab in MIT's JOS project. The E1000 is a complex card, but only a subset of features is needed to get a working stack. We would rely on the card's emulation in qemu. This means you can debug it with a custom build of qemu.
  • Adapt the lwIP stack, provided here. This is a generic IP stack targeted for embeddability.
  • Implement the minimum required functionality to provide support for sockets. Achieve the ability to log into Pintos via telnet!
  This would be a project for anyone wanting to learn more about device drivers as well as how a kernel implements networking.
• 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 User Memory Allocation/sbrk(). 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. This will be necessary for your porting your shell.
  • Implement a shell (could be simplified version of your CS3214 shell)

• Analyze VM Page Replacement Policies Implement multiple different replacement policies and analyze their benefits for different workloads. In project 3, most of you will probably just implement some version of a 1-bit or 2-bit clock.

  This project would involve implementing a variety of cache-replacement policies and analyzing their performance.

  I think this would be interesting academically - can you reproduce the research done by Belady and others on real workloads?

  For it to be very realistic, you would have to 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. Real OS merge the two, after all, physical memory could be used either for file caching, file ahead, or program's data or code.

  This could double as your project 3 implementation, (even though the buffer cache is the first part of project 4).

  If a unified buffer cache is implemented, could look at the performance of algorithms like the one used in Linux, or more modern algorithms such as ARC.

• 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 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, such as.
  • A scalable directory implementation, perhaps using B-trees.
  • Recovery after a crash. Either traditional fsck, or some version of physical logging.
  This could double as your project 4 implementation (if your advanced filesystem passes project 4 tests).
• Various other ideas I haven't thought much about.
  • 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.
  • Implement Read-Copy-Update. See here.