Computer Science 432 - Spring 2005

Operating Systems

Williams College

Final Projects

Brendan Dougherty '06, Ashok Pillai '05, Travis Vachon '06

Title:Card-based Logins -- making purple2 a thing of the past
Abstract: As our term project for Computer Science 432: Operating Systems during the Spring 2005 Semester at Williams College, we implemented an interface to the UHID driver which simplified the task of interacting with a MagTek magnetic stripe reader. Using this interface we were able to write an authentication module for FreeBSD 4, which allowed swipe card access to the system.

Mike Gnozzio '07, Arjun Sharma '07, Jan Zankowski '07

Title:Disk Butcher: Design Principles and Implementation Strategies for Developing a Dynamic Disk Partitioner
Abstract: We created a dynamic disk partitioner and called it Disk Butcher. While most of the available partitioning softwares provide poor usability or demand a substantial price, Disk Butcher provides a free and open source application that gets the job done with ease and e ectiveness. In this paper we discuss the design and implementation of the software, as well as general principles which we learned along the way. Specifically, we discuss the model-view-controller design paradigm, data retention on disk, filesystem equivalence and the details of the libparted library, which supports the underlying functionalities of Disk Butcher.

Rob Terchunian '06

Title:Semaphore Implementation in the Linux 2.6 Kernel
Abstract: Modern Operating Systems need to be able to manage resources that are in demand by a number of di erent processes. Their ability to do this is governed by their ability keep track of which resources are in use and which are available. Semaphores make this possible by giving programmers control over how many processes can execute a given section of code at once. By looking at an implementation of semaphores in a popular operating system, we can further our understanding of how these structures are made possible and how to best use them to our advantage. We can also better understand the di culties that semaphores face and why they might become obsolete in the future. The Linux 2.6 series kernel source code examined here is a particularly good example. It shows the evolution of the kernel to support preemption as well as the complexities that can develop as a result of the need to support a wide range of hardware. We can compare this to what would be required if we took full advantage of modern hardware support for synchronization.

Laura Effinger-Dean '06 and Brian Hirshman '06

Title:Modeling File Systems in Java
Abstract: Modeling a file system has several advantages over using a physical hard drive with logical data. Using a Java simulator allows us to analyze the benefits and drawbacks associated with different file systems without having to reformat the physical device. Furthermore, our simulator gives us more control over data and parameters, which results in more flexibility. As a further benefit, our simulation can model several different types of physical devices. Our abstract representation of a file system gives us a more nuanced understanding of the operations that a file system performs and the manner in which it stores data. Our simulation has the potential for many levels of complexity, from a simplistic model of a directory structure to a detailed analysis of caching and seek times.

Phil Enock '05

Title:Deadlock in Operating Systems and Databases: Real-world and Simulated
Abstract: The possibility for deadlock between processes is a concern that arises in operating systems and database systems. We will discuss deadlock in the context of file access locking, kernel data structure locking, and database record locking, as well as the various methods of dealing with deadlock issues used in the Linux and FreeBSD kernels and in database systems. I have implemented a resource request and allocation simulator, which generates local and remote resource requests made by processes in different locations. It detects deadlocks locally by using wait-for-graph detection and globally by using an edge-chasing distributed deadlock detection probe scheme. The simulator allows the user to input a set of locations, with processes in each location s having their own characteristic resource requests, then observe any simulated deadlocks that may occur in the system.

Oren Cass '05

Title: ODESA: Oren's Discrete Event Simulation Application. A Hardware Model in Software of a Single-Processor, Direct-Paging Computer
Abstract: This paper describes Oren s Discrete Event Simulation Application (ODESA), a software model designed to simulate a modern single-processor computer. Processes are executed via a sequence of requests to memory, and scheduled on the processor accounting for quantum expirations, I/O faults, and page faults. Main memory includes a level-one cache, a translation look-aside buffer, and a page table, which work together to simulate memory management and page fault frequency. The memory component also functions as an independent simulator in order to model expected access times for different page replacement algorithms under different reference strings. Both an optimal least-recently used algorithm and a standard clock algorithm are included.

Chris Douglas '05

Title: A Possible Implementation of a Cryptographic Filesystem
Abstract: At present, the methods for encrypting one s data are fairly ad-hoc. While the Internet is considered public and a worthy forum for protecting sensitive data, personal computers and servers are considered to be private. Any server administrator knows that the partition of public/private by ownership is a tenuous one; truly sensitive data ought to be protected by stronger means bound to the characteristics of the data and not to the fictitious analog of possession. Especially for those storing their data on or passing it through machines for which security is peripheral, misunderstood, or poorly implemented,1 reliable data protection ought to be implemented apart from the mechanisms that facilitate system administration. UNIX permissions, for example, provide inadequate protection against crackers. Should one gain access to the superuser account (using a rootkit or other exploit), then carefully crafted permissions schemes can be bypassed without ceremony. The goal of a cryptographic filesystem should be to obscure users data from all other users. Regrettably, absolute security is impossible, but one could conceive of a filesystem that- even given a compromise of a privileged account- could limit access to an attacker. We explore the mechanisms and guarantees that might mitigate access.