📄 http:^^www.cs.wisc.edu^~cao^cs736^project-list.html
字号:
Date: Mon, 11 Nov 1996 17:32:33 GMTServer: NCSA/1.5Content-type: text/htmlLast-modified: Tue, 30 Jan 1996 23:07:28 GMTContent-length: 13558<html><head><title> CS 736 Project Suggestions (Spring 96)</title></head><BODY><h1> CS 736 Project Suggestions (Spring 96)</h1>Here are a list of suggested topics for your project. You are also welcometo come up with your own project. As you can see, most of the projects listedhere are open-ended research questions, and we will definitely discoversome interesting stuff at the end of the projects --- I will be just as excitedabout them as you will be!<p>For most of the projects, you need to read some additional papers. I willlist the papers here if I have online copies, otherwise I will give out thereferences and you can either find them in library or ask me for copies.<h2>File Systems: Cache Management</h2><p>As the disk performance continues to lag behind microprocessor performance,file system is increasingly becoming a performance bottleneck in manysystems. The file system performance is often determined by how effectivelythe file cache is used. Unfortunately, most operating systems todaystill use the LRU (or its approximation, two-hand clock) caching strategy todecide which file data are kept in cache and which are not. LRU algorithm, unfortunately, do not always perform well due to the following problems:<br>. 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;<br>. 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;<br><p>Research on this topic consists of three projects:<ol><li> <b>Trace-Driven Simulation Study</b><br>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:<br>. LRU replacement: baseline algorithm;<br>. LBN replacement: for each file, replace the block with the largest logical block number first; <br>. 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;<br>. 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.<br>or any other policy you might discover along the way.<p>Papers you might want to read for this project:<pre>1) ftp ftp.cs.princeton.edu; cd reports/1994; get 445.ps.Z2) @inproceedings{dewitt:buffer-policy-evaluation, author = "Hong-Tai Chou and David J. DeWitt", title = "An Evaluation of Buffer Management Strategies for Relational Database Systems", booktitle = "Proceedings of the Eleventh International Conference on Very 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 Buffering", booktitle = SIGMOD93, year = 1993, month = May, pages = "297--306" }</pre><p><li> <b>File System Trace Replay</b><br>If we have a good file caching algorithm, how could we prove that it performs better than existing ones? Sometimes we can use benchmarkprograms, but they are often too small to capture the long term effects infile 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 forthese traces by writing a special device driver that implements its ownbuffer 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).<p>Papers you might want to read for this project:<pre>1) http://www.eecs.harvard.edu/~keith/papers/realloc.ps.gz</pre><li> <b>Better File Caching in Solaris</b><br>While the above two projects are above kernel level, this one digs down andtries to find out what needs to be done to change Solaris' file cachingpolicy. 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.<p>Papers you might want to read for this project:<pre>1) ftp ftp.cs.princeton.edu; cd pub/people/pc/OSDI94; get paper.ps.Z</pre></ol><h2>Virtual Memory: Page Replacement Algorithms </h2>For the past few years, DRAM price has not dropped much. As a result, DRAM isstill 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 memoryvery well. Although most operating systems provide virtual memory, manyapplications 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 ispoor for many large-memory applications, and what techinques can be applied toimprove the situation. There are three projects.<ol><li><b>Memory Intensive Applications</b><br>Instrument the Solaris kernel to collect information related toVM system: page fault information (pid, memory address, time, etc.), cost ofpage 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 usuallyrequire too much memory to run on your workstation, run them anyway andcollect their paging information.<p>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 cachesimulator for this purpose.) <p><li><b>Multi-User Workload</b><br>Similar to the above study, but use multi-user workload instead of a singleapplication. SPEC95 server benchmarks, or desktop bench, are examplesof multi-user workload. Again, if the VM system performs poorly, findout why, and what we can do to improve the situation. In particular,pay attention to the interaction of virtual memory system and file buffermanagement when they compete for memory resource. Would it have been betterif 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.<p><li><b>Memory Intensive Applications</b><br>Finally, if you are really into kernel hacking, here is another oppurtunity.Messages from the project leader of Solaris VM at SUN:<p>"a) madvise usage: Solaris implements the madvise system calls but not many applicationsuse them. Project is to take utilities (tar, ar, ld, grep etc) and modify themto use madvise and see if they have performance differences.<br> Project can also see if the implementation of madvise (in seg_vn.c) can be improved or new madvise calls are needed....<p>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 thresholdsat which each kicks in appropriate? Is there a better implemenation?<p>h) Page coloring for various CPU cache types: There are 4 types of CPU caches (PIPT, VIPT, PIVT, VIVT). And withtwo levels of caches there can be even more combinations. In our physicalfreelist page management we try to do page coloring in various ways to improve cache utilizations as well as reduce cache flushes. Pick variousprocessors/machines and see if there are better page coloring algorithms."<p>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. </ol>Papers you might want to read for these projects:<pre>@inproceedings{anderson:oopsla, author = "Keith Krueger and David Loftesness and Amin Vahdat and Tom Anderson", title = "Tools for the Development of Application-Specific Virtual Memory 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 ExternalPage-Cache Management", booktitle = "The Fifth International Conference on ArchitecturalSupport for Programming Languages and Operating Systems", year = 1992, month = Oct, pages = "187--197" }</pre><h2>WWW Regional Cache Management</h2>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.<p>The project seeks to build such a regional information cache. We need acache management layer, which keep track of all documents cached on membermachines. Then we need to modify the client browser to intercept URLrequests, and make the request go through the cache management layer first.The cache management layer can return the document or request it from anotherworkstation if it knows that the document is cached in its region.Otherwise, the request is forward to the real server.<p>The cache actually does not sit on one machine; rather, it is the collectionof cached documents on member machines in the region. The cache managementmaintains a directory of documents cached in this region, and authenticatesthe cached copy of the document by keeping its fingerprints. In addition, thecache manager needs to coordinate with servers to maintain the consistency ofcached documents (i.e. keeping them up to date).Investigate, through implementation, the tradeoff of various cachemanagement policies and consistency protocols.<p>Papers you might want to read for these projects:<pre>http://excalibur.usc.eduhttp://www.das.harvard.edu/users/faculty/Margo_Seltzer/papers/hotos.95.ps.gzhttp://www.eecs.harvard.edu/~vino/web/usenix.196/</pre><h2>Databases on COW</h2>Can clusters of workstations (or clusters of SMP) support database systemseffectively and in a scalable fashion? This project is a small step ininvestigating this big question. The goal is to take the in-house databasestorage manager, shore, and port it onto the 4-node COW cluster. The projectinvolves 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. <p><h2>Kernel Documentation, Debugging and Binary Instrumentation</h2>Again, there are a few projects in this area.<ol><li><b> Kernel Documentation</b>Again, messages from Solaris VM project leader:<p>"e) Documentation: For some folks, it might be a good project to just look at the code anddocument 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.<br>h) Fork: Fork is typically a very heavy-weight operation. Why? Can this be speeded up?"<p><li><b> Kernel Reliability</b><br>"b) Kernel reliability:...<br> Another project would be to look for panics in the system and see ifthey can be handled gracefully. Note that many panics are there because theyare an invariant of the system (i.e. an ASSERT). We are more interested inthose that are truly errors that we should handle.<br> 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 memoryin the system. In many cases the caller just panics. A good test would be tohave kmem_alloc return random failures on kmem_alloc(NOSLEEP) and see if thesystem still works or how it can be fixed.<br> How do the file systems behave if some random disk error occurs?<br>"<p><li><b> Binary Instrumentation</b><br>Investigate whether binary rewriting techniques (e.g. EEL) can be appliedsuccessfully on kernel. There are probably a number of routines that shouldn'tbe instrumented by EEL --- find them out (usually, by instrumenting them andthen crashing the machine...).<p></ol><h2>Parallel I/O Systems and Applications</h2>How would one build a parallel I/O system? Partly, that depends on applicationneeds. Collect parallel applications that require large data sets, and charaterize their I/O demands. Port the applications to message-passingarchitecture, and observe their performance with a parallel file systemprototype.</body>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -