[PintOS, Project 4] Buffer Cache

 Modify the file system to keep a cache of file blocks. When a request is made to read or write a block, check to see if it is in the cache, and if so, use the cached data without going to disk. Otherwise, fetch the block from disk into the cache, evicting an older entry if necessary. You are limited to a cache no greater than 64 sectors in size.

 file block을 cache로 보존하기 위해 file system을 수정하라. block의 읽기/쓰기 요청이 들어왔을 때, 이 블록이 cache 안에 있는가부터 보고, 있다면 cache에 있는 data를 사용하라. cache에 없는 경우는 disk로부터 block을 읽고 cache에 추가한다 (자리가 없다면 다른 블록을 비워서 자리를 만든다.). cache는 64sector의 용량만 가진다.  

 

 You must implement a cache replacement algorithm that is at least as good as the "clock" algorithm. We encourage you to account for the generally greater value of metadata compared to data. Experiment to see what combination of accessed, dirty, and other information results in the best performance, as measured by the number of disk accesses.

 cache 교체 알고리즘은 최소한 clock 알고리즘만큼 효율이 나와야한다. data랑 비교해서 일반적으로 큰 값을 가지는 metadata의 값을 넣도록 하는 걸 추천한다. accessed, dirty 혹은 다른 정보들을 조합하여 disk access 횟수가 어떻게 나오는지 실험해보는 것이 최상의 결과를 가져다줄 것이다. 

 

 You can keep a cached copy of the free map permanently in memory if you like. It doesn't have to count against the cache size.

 원한다면 free map을 cache에 계속 올려놔도 되고, 이는 cache size에 포함하지 않아도 된다. 

 

 The provided inode code uses a "bounce buffer" allocated with malloc() to translate the disk's sector-by-sector interface into the system call interface's byte-by-byte interface. You should get rid of these bounce buffers. Instead, copy data into and out of sectors in the buffer cache directly.

 제공된 inode code는 "bounce buffer"를 사용하여 sector-size 단위로 disk에 넣는 것을, byte-size단위로 넣는다. "bounce buffer"를 제거하고 sector에 넣거나 뺄 data들은 buffer cache를 사용하여 다뤄라.

 

 Your cache should be write-behind, that is, keep dirty blocks in the cache, instead of immediately writing modified data to disk. Write dirty blocks to disk whenever they are evicted. Because write-behind makes your file system more fragile in the face of crashes, in addition you should periodically write all dirty, cached blocks back to disk. The cache should also be written back to disk in filesys_done(), so that halting Pintos flushes the cache.

 여기서 cache는 write-behind를 도입한다. block이 수정되었다면 그 즉시 disk로 반영하는 것이아니라 cache에 보존한 채로 가지고 있다가 해당 block이 cache에서 사라질 때, disk에 반영시킨다.  Write-behind를 도입했다면, file system은 crash에 취약하기 때문에 주기적으로 dirty cache를 disk에 옮겨야하고, filesys_done()이 실행됐을 때에도 cache를 disk에 옮김으로써 Pintos가 중지되었을 때 cache를 비울 수 있도록 한다. 

 

 If you have timer_sleep() from the first project working, write-behind is an excellent application. Otherwise, you may implement a less general facility, but make sure that it does not exhibit busy-waiting.

 첫번째 프로젝트에서 timer_sleep()을 만들었다면, write-behind는 훌륭하게 작동할 것이다. 만들지 않았다면 할 일은 줄어들겠지만 busy-waiting 문제는 반드시 해결해야한다. 

 

 You should also implement read-ahead, that is, automatically fetch the next block of a file into the cache when one block of a file is read, in case that block is about to be read. Read-ahead is only really useful when done asynchronously. That means, if a process requests disk block 1 from the file, it should block until disk block 1 is read in, but once that read is complete, control should return to the process immediately.

 한 file의 block을 읽었을 때, 그 다음 block도 cache에 가져오는 read-ahead도 구현해야한다. Read-ahead는 비동기적으로 구현했을 때만 유용해질 것이다. 다시 말하면, disk에서 한 file의 첫번째 블록을 요구했을 때, 그 block을 불러올 때까지 못쓰도록 막고, 쓰기 작업이 완료되는대로 processs에게 통제권을 반납한다. 

 

 The read-ahead request for disk block 2 should be handled asynchronously, in the background. To do so, you might need to create a dedicated thread for the IO. When the disk IO needs, the thread passes the request to the dedicated one.

 disk block 2에 대한 read-ahead 요청은 비동기적으로 이뤄져야한다. 이 때문에 IO를 전담할 thread를 만들어야한다. disk IO가 필요할 때, 이 thread가 요청을 받아서 수행할 것이다. 

 

Hint for implementation

You might implement this functionality through the virtual memory subsystem as Linux does. You can introduce new vm type (e.g. "pagecache") and manage the buffer cache through the swap_in, swap_out, and destroy interfaces. If you choose this design, you can manage the cache with a PAGE_SIZE granularity rather than SECTOR_SIZE granularity. For the synchronization issue for file backed page, you can use the mmaped area as a cache for them.

We recommend integrating the cache into your design early. In the past, many groups have tried to tack the cache onto a design late in the design process. This is very difficult. These groups have often turned in projects that failed most or all of the tests.

 linux처럼 vm 시스템을 구현했다면, 새로운 vm type (예를 들어 pagecache) 을 도입하고, 해당 type에 대해서 swap_in, swap_out, destroy 등으로 buffer cache 를 다룰 수 있다. 이 경우에는 cache를 sector size 단위 대신에 page size 단위로 다룰 수 있다. fiel backed page의 동기화 문제를 위해 mmaped area를 cache처럼 쓸 수 있다. cache를 빨리 구현하는 것을 추천한다. 여태까지 많은 팀들이 늦게나마 cache를 도입하려고 하지만, 거의 모든 테스트를 실패했다. 이는 매우 어렵다. (역주 : 이걸 왜 지금 알려줘)