Date: Mon, 11 Nov 1996 17:32:33 GMT Server: NCSA/1.5 Content-type: text/html Last-modified: Tue, 30 Jan 1996 23:07:28 GMT Content-length: 13558 CS 736 Project Suggestions (Spring 96)

CS 736 Project Suggestions (Spring 96)

Here are a list of suggested topics for your project. You are also welcome to come up with your own project. As you can see, most of the projects listed here are open-ended research questions, and we will definitely discover some interesting stuff at the end of the projects --- I will be just as excited about them as you will be!

For most of the projects, you need to read some additional papers. I will list the papers here if I have online copies, otherwise I will give out the references and you can either find them in library or ask me for copies.

File Systems: Cache Management

As the disk performance continues to lag behind microprocessor performance, file system is increasingly becoming a performance bottleneck in many systems. The file system performance is often determined by how effectively the file cache is used. Unfortunately, most operating systems today still use the LRU (or its approximation, two-hand clock) caching strategy to decide which file data are kept in cache and which are not. LRU algorithm, unfortunately, do not always perform well due to the following problems:
. flushing: a one-time scan on a large file can wipe out the entire content of the file cache, if the file is larger than the cache;
. loops: sometimes a group of files are always accessed in the same order; if the files are bigger than the cache, LRU would not perform well;

Research on this topic consists of three projects:

  1. Trace-Driven Simulation Study
    Write a trace-driven simulator, which takes the SPRITE file system traces and the DEC SRC Epoch file system traces as input, and study the hit ratio of the file cache under different replacement policies:
    . LRU replacement: baseline algorithm;
    . LBN replacement: for each file, replace the block with the largest logical block number first;
    . sequence detection: in the trace, detect the situations when file A is almost always read immediately before file B, in which case file B's blocks should be replaced before file A's blocks;
    . LRU-2 replacement: in deciding about replacement blocks, consider the times of the last two references to the file, instead of just the last reference (like is done in LRU); this is an algorithm suggested by database researchers, but it might have good application in file cache management as well.
    or any other policy you might discover along the way.

    Papers you might want to read for this project:

    1) ftp ftp.cs.princeton.edu; cd reports/1994; get 445.ps.Z
    
    2) @inproceedings{dewitt:buffer-policy-evaluation,
            author = "Hong-Tai Chou and David J. DeWitt",
            title = "An Evaluation of Buffer Management Strategies for Relational Da
    tabase Systems",
            booktitle = "Proceedings of the Eleventh International Conference on Ver
    y Large Databases",
            year = 1985,
            month = Aug,
            pages = "127--141"
    }
    
    3) @inproceedings{db:lru-k,
            author = "Elizabeth J. O'Neil and Patrick E. O'Neil and Gerhard Weikum",
            title = "The {LRU-K} Page Replacement Algorithm For Database Disk Buffer
    ing",
            booktitle = SIGMOD93,
            year = 1993,
            month = May,
            pages = "297--306"
            }
    

  2. File System Trace Replay
    If we have a good file caching algorithm, how could we prove that it performs better than existing ones? Sometimes we can use benchmark programs, but they are often too small to capture the long term effects in file caching. Traces, on the other hand, seems only good for simulations, unless we can replay it on a real system. The project investigates how to emulate trace events as actual file I/Os on a system, and how to simulate different caching policies for these traces by writing a special device driver that implements its own buffer cache. The result would be a comparison of the different buffer caching policies in terms of elapsed time on real systems (instead of file cache hit ratios).

    Papers you might want to read for this project:

    1) http://www.eecs.harvard.edu/~keith/papers/realloc.ps.gz
    
  3. Better File Caching in Solaris
    While the above two projects are above kernel level, this one digs down and tries to find out what needs to be done to change Solaris' file caching policy. In fact, you may need to change the VM paging algorithm as well. Pick any of the policies listed above (or policies that you come up with), and implement them in the Solaris kernel. Then we measure their performance by using some benchmark programs.

    Papers you might want to read for this project:

    1) ftp ftp.cs.princeton.edu; cd pub/people/pc/OSDI94; get paper.ps.Z
    

Virtual Memory: Page Replacement Algorithms

For the past few years, DRAM price has not dropped much. As a result, DRAM is still fairly expensive, and people spend half of the cost of a computer on its memory. On the other hand, operating systems have not managed the memory very well. Although most operating systems provide virtual memory, many applications cannot run on machines with relatively small memory because the paging performance is too poor. Research on this topic tries to find out why the demand-paging performance is poor for many large-memory applications, and what techinques can be applied to improve the situation. There are three projects.
  1. Memory Intensive Applications
    Instrument the Solaris kernel to collect information related to VM system: page fault information (pid, memory address, time, etc.), cost of page faults (how long the disk operation take), cleaning of dirty pages (how often it is done, cost of the disk writes), and other information. Then, collect a set of applications that you think is important and usually require too much memory to run on your workstation, run them anyway and collect their paging information.

    From these traces, figure out exactly what were the cause of paging or thrashing. Is there simply not enough memory? (definition of "not enough": if the memory is less than 10% of the working set of the application.) Does the VM system's prefetching policy hurt, rather than help, the performance? what about the writeback policy? Is two-hand clock policy a particularly bad page replacement policy for this application? (You might want to feed the page fault traces to a cache simulator for this purpose.)

  2. Multi-User Workload
    Similar to the above study, but use multi-user workload instead of a single application. SPEC95 server benchmarks, or desktop bench, are examples of multi-user workload. Again, if the VM system performs poorly, find out why, and what we can do to improve the situation. In particular, pay attention to the interaction of virtual memory system and file buffer management when they compete for memory resource. Would it have been better if Solaris used a fixed partition of memory among the VM and file cache? Also, see the messages from the project leader of Solaris VM system.

  3. Memory Intensive Applications
    Finally, if you are really into kernel hacking, here is another oppurtunity. Messages from the project leader of Solaris VM at SUN:

    "a) madvise usage: Solaris implements the madvise system calls but not many applications use them. Project is to take utilities (tar, ar, ld, grep etc) and modify them to use madvise and see if they have performance differences.
    Project can also see if the implementation of madvise (in seg_vn.c) can be improved or new madvise calls are needed. ...

    g) Paging algorithm: Solaris uses the global clock algorithm. Is there a better one? Are the thresholds used for paging better tuned? What is the interaction between swapping and paging? Are the thresholds at which each kicks in appropriate? Is there a better implemenation?

    h) Page coloring for various CPU cache types: There are 4 types of CPU caches (PIPT, VIPT, PIVT, VIVT). And with two levels of caches there can be even more combinations. In our physical freelist page management we try to do page coloring in various ways to improve cache utilizations as well as reduce cache flushes. Pick various processors/machines and see if there are better page coloring algorithms. "

    While the above two projects try to study these questions from trace analysis, in this project you will actually change the kernel and experiment with all these issues.

Papers you might want to read for these projects:
@inproceedings{anderson:oopsla,
        author = "Keith Krueger and David Loftesness and Amin Vahdat and Tom And
erson",
        title = "Tools for the Development of Application-Specific Virtual Memor
y Management",
        booktitle = OOPSLA93,
        year = 1993,
        month = Oct,
        pages = "48--64"
        }

@inproceedings{harty:appcontrol,
        author = "Kieran Harty and David R. Cheriton",
        title = "Application-Controlled Physical Memory using External
Page-Cache Management",
        booktitle = "The Fifth International Conference on Architectural
Support for Programming Languages and Operating Systems",
        year = 1992,
        month = Oct,
        pages = "187--197"
        }

WWW Regional Cache Management

As the Web grows and expands, the traffic on network backbones are quickly approaching the capacity limit of the network. One attractive method for reducing network traffic is through regional caching, i.e. a department-wise or campus-wisc shared information resource.

The project seeks to build such a regional information cache. We need a cache management layer, which keep track of all documents cached on member machines. Then we need to modify the client browser to intercept URL requests, and make the request go through the cache management layer first. The cache management layer can return the document or request it from another workstation if it knows that the document is cached in its region. Otherwise, the request is forward to the real server.

The cache actually does not sit on one machine; rather, it is the collection of cached documents on member machines in the region. The cache management maintains a directory of documents cached in this region, and authenticates the cached copy of the document by keeping its fingerprints. In addition, the cache manager needs to coordinate with servers to maintain the consistency of cached documents (i.e. keeping them up to date). Investigate, through implementation, the tradeoff of various cache management policies and consistency protocols.

Papers you might want to read for these projects:

http://excalibur.usc.edu
http://www.das.harvard.edu/users/faculty/Margo_Seltzer/papers/hotos.95.ps.gz
http://www.eecs.harvard.edu/~vino/web/usenix.196/

Databases on COW

Can clusters of workstations (or clusters of SMP) support database systems effectively and in a scalable fashion? This project is a small step in investigating this big question. The goal is to take the in-house database storage manager, shore, and port it onto the 4-node COW cluster. The project involves making shore a true SMP program, and then applying the fine-grained software DSM technique to its binary and running it on a 4-node COW cluster.

Kernel Documentation, Debugging and Binary Instrumentation

Again, there are a few projects in this area.
  1. Kernel Documentation Again, messages from Solaris VM project leader:

    "e) Documentation: For some folks, it might be a good project to just look at the code and document how it works. For example, the VM system, the hat layer, the scheduler,the I/O system or even portions of it. This is not easy.
    h) Fork: Fork is typically a very heavy-weight operation. Why? Can this be speeded up? "

  2. Kernel Reliability
    "b) Kernel reliability:...
    Another project would be to look for panics in the system and see if they can be handled gracefully. Note that many panics are there because they are an invariant of the system (i.e. an ASSERT). We are more interested in those that are truly errors that we should handle.
    One of the interesting one is kmem_alloc(NOSLEEP). The caller is supposed to be able to handle a return of NULL if there is no free memory in the system. In many cases the caller just panics. A good test would be to have kmem_alloc return random failures on kmem_alloc(NOSLEEP) and see if the system still works or how it can be fixed.
    How do the file systems behave if some random disk error occurs?
    "

  3. Binary Instrumentation
    Investigate whether binary rewriting techniques (e.g. EEL) can be applied successfully on kernel. There are probably a number of routines that shouldn't be instrumented by EEL --- find them out (usually, by instrumenting them and then crashing the machine...).

Parallel I/O Systems and Applications

How would one build a parallel I/O system? Partly, that depends on application needs. Collect parallel applications that require large data sets, and charaterize their I/O demands. Port the applications to message-passing architecture, and observe their performance with a parallel file system prototype.