Buffer Cache

Introduction

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.

파일 블록의 캐시를 사용하도록 파일 시스템을 수정한다. 블록을 읽거나 쓰는 요청을 받았을 때, 캐시에 저장되어 있는지 확인하고, 캐시에 존재하면 디스크에서 로드하지 않고 캐싱된 데이터를 사용한다. 캐시에 존재하지 않다면 디스크로부터 블록을 캐시로 가져오고, 필요한 경우 캐시 엔트리를 교체한다. 버퍼 캐시는 최대 64블록의 크기를 가진다.

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 코드는 디스크의 섹터 별 인터페이스를 시스템 콜의 바이트 별 인터페이스로 변환하기 위해 malloc()을 통해 할당된 바운스 버퍼를 사용한다. 바운스 버퍼를 제거하고 데이터를 버퍼 캐시 안에 존재하는 섹터로 직접 복사한다.

Buffer Cache 개요

• Buffer Cache: 버퍼 캐시는 디스크 블록을 캐싱하는 메모리 영역이다. 디스크 블록을 메모리 영역에 둠으로써 파일의 입출력 응답시간을 줄인다.

현재 PintOS는 버퍼 캐시가 존재하지 않으므로, 파일 입출력 시 바로 디스크 입출력 동작을 수행한다.

File System

• File System: 파일 시스템은 OS가 디렉토리나 파일을 생성, 접근 및 보관할 수 있도록 하는 계층이다.

파일 시스템은 블록 디바이스를 일정한 크기의 블록(sector)들로 관리한다.

파일 시스템은 블록의 사용 여부를 비트맵을 통해 관리한다.

File System Block Layout

PintOS의 8MB 파일 시스템은 총 16,384개(8MB/512 Byte)의 블록으로 구성되어 있다.

0번 블록은 bitmap on-disk inode, 1번 블록은 root dir on-disk inode, 2~5번 블록은 bitmap data, 6번 블록은 root dir entries, 나머지 블록들은 data blocks이다.

inode란 무엇인가?

inode란 Unix/Linux 파일 시스템에서 각 파일에 대한 정보를 포함하는 구조체로서, 각각의 파일을 관리하기 위해 사용되는 자료구조이다.

파일이 생성되면 하나 이상의 inode 번호가 할당되고 inode 블록이 생성된다. inode 블록을 기반으로 파일의 처리가 이루어진다.

파일명이 다르지만 inode 번호가 같은 경우 두 파일은 동일한 파일이다.

파일의 표현

• In-memory inode: struct inode

• sector: inode가 저장된 블록의 번호

• data: disk_inode 데이터

• removed: 파일의 삭제 여부

struct inode 구조체는 in-memory inode의 정보를 관리하는 자료구조로 sector, data, removed 필드를 가진다.

• On-disk inode: struct inode_disk

• start: 파일 데이터의 디스크 블록 시작 주소

• length: 파일의 크기

• unused[125]: 사용되지 않는 영역

struct inode-disk 구조체는 on-disk inode의 정보를 관리하는 자료구조로 start, length, unused[125] 필드를 가진다.

디렉토리

• struct dir: dir 구조체는 디렉터리의 정보를 관리하는 자료구조로 struct inode와 off_t pos를 멤버로 가진다.

• inode: 디렉터리의 in-memory inode를 포인팅

• pos: 디렉터리의 엔트리 오프셋

디렉터리 엔트리 자료구조

• struct dir_entry: dir_entry 구조체는 디렉터리 엔트리(파일 또는 디렉터리)의 정보를 관리하는 자료구조이다.

• inode_sector: inode의 디스크 블록번호를 저장

• in_use: dir_entry의 사용 여부

블록 비트맵

• struct free_map: free_map 구조체는 디스크 블록의 free/used를 표현하는 비트맵이다.

• free_map_file: 비트맵을 디스크에 파일 형태로 저장

• bit_cnt: 파일 시스템 전체의 디스크 블록 개수

사용 중인 파일의 표현

• struct file

• inode: 파일의 in-memory inode 포인터

• pos: 파일 오프셋

• deny_write: write 명령 가능 여부

디스크 블록 접근 순서

• off_t file_read(struct file file, void buffer, off_t size): file_read() 함수 호출 시

1. file 자료구조를 통해 메인 메모리의 inode에 접근한다.

2. inode를 통해 디스크에 접근한다.

Write

Writes SIZE bytes from BUFFER into FILE, starting at the file's current position. Returns the number of bytes actually written, which may be less than SIZE if end of file is reached.

• file_write(): inode_write_at()을 호출하여 디스크 블록에 데이터를 기록하고 기록한 크기 만큼 파일 오프셋을 변경한다.

Writes SIZE bytes from BUFFER into FILE, starting at offset FILE_OFS in the file. Returns the number of bytes actually written, which may be less than SIZE if end of file is reached.

• file_write_at(): 파일의 오프셋 FILE_OFS 인자 SIZE 만큼의 바이트를 버퍼로부터 파일에 쓴다. 실제로 쓰여진 바이트를 리턴한다.

file_write()와 file_write_at()은 쓰기를 시작하는 파일의 위치가 다르다.

• offt inode_write_at(struct inode inode, const void buffer, off_t size, off_t offset): buffer가 가리키는 영역의 데이터를 디스크에 기록한다.

• block_write(): 디스크 블록 단위로 loop을 돌며 디스크 블록에 기록한다.

• byte_to_sector(): 데이터를 기록할 디스크 블록 번호를 얻는다.

• sector_ofs: 데이터를 기록할 디스크 블록 내부의 오프셋

• partial_write(): 타겟 블록을 읽어 bounce buffer에 저장한다.

• memcpy()를 통해 bounce buffer에 partial write를 수행한다.

• block_write(): bounce buffer의 데이터를 디스크에 기록한다.

파일 오프셋을 통한 디스크 블록 주소 확인

byte_to_sector(): 파일의 시작 블록으로부터 오프셋 값을 더하여 디스크 블록 번호를 반환한다.

Read

• file_read(): inode_read_at()을 호출하여 디스크에서 버퍼로 데이터를 읽고 읽은 크기 만큼 파일 오프셋을 변경한다.

• inode_read_at()

• block_read(): 디스크 블록 단위로 loop을 돌며 디스크에서 데이터를 읽는다.

• byte_to_sector(): 데이터를 읽을 디스크 블록 번호를 얻는다.

• sector_ofs: 데이터를 읽을 디스크 블록 내의 오프셋

Buffer Cache 구현 세부 요구사항

버퍼 캐시를 관리하기 위한 인터페이스를 구현한다.

최대 64개(64 * 512 Byte = 32KB)의 블록으로 구성한다.

cache_search, patch, select_victim, flush 기능을 구현한다.

LRU, Clock 알고리즘 기반 교체 알고리즘을 구현한다.

write_behind(): 파일 시스템 종료 시, 모든 dirty 블록을 디스크로 flush하고, victim_entry 선정 시, dirty일 경우 블록을 디스크로 flush한다.

Buffer Cache 구조

buffer_head 자료구조 추가

• struct buffer_head: 버퍼 캐시의 각 엔트리를 관리한다.

해당 엔트리의 dirty 여부를 나타내는 flag

해당 엔트리의 사용 여부를 나타내는 flag

해당 엔트리의 disk_sector 주소

clock 알고리즘을 위한 clock bit

lock 변수 (struct lock)

버퍼 캐시 엔트리를 가리키기 위한 데이터 포인터

Buffer Cache를 추가한 Read

buffer_head를 검색하고 엔트리가 존재하는지를 확인한다.

엔트리가 존재하는 경우 버퍼 캐시의 데이터를 버퍼로 읽고 buffer_head를 업데이트 한다.

엔트리가 존재하지 않는 경우 캐시가 비었는지를 확인하여 victim entry를 선정한다.

buffer_head에서 empty entry를 선정하여 디스크에서 버퍼 캐시로 데이터를 block_read() 한다.

선정된 victim entry의 dirty 여부를 확인하여 디스크로 flush 한다.

• bc_read()

버퍼 캐시에서 데이터를 읽어 유저 버퍼에 저장하고 읽을 데이터가 버퍼 캐시에 없으면 디스크에서 읽어 버퍼 캐시에 캐싱한다.

memcpy()를 이용해 버퍼 캐시 데이터를 유저 버퍼에 복사하고 buffer_head()를 갱신한다.

파일 read 시, 버퍼 캐시에서 데이터를 읽어오도록 inode_read_at() 함수를 수정한다.

Buffer Cache를 추가한 Write

buffer_head를 검색하여 엔트리가 존재하는지 확인한다.

엔트리가 존재하는 경우 버퍼의 데이터를 버퍼 캐시로 기록하고 buffer_head를 업데이트 한다.

엔트리가 존재하지 않는 경우 캐시가 비었는지 확인하고 victim entry를 선정한다.

victim entry의 dirty 여부를 확인하여 victim entry를 디스크로 flush하고 victim entry를 buffer_head에서 해지한다.

Buffer Cache Write 함수 구현

• bc_write()

버퍼의 데이터를 버퍼 캐시에 기록한다.

버퍼 캐시에 빈 엔트리가 없으면 victim entry를 선정하여 디스크에 기록한다.

memcpy()를 이용해 버퍼의 데이터를 버퍼 캐시에 복사하고 buffer_head를 갱신한다.

파일 write 시, 디스크가 아닌 버퍼 캐시에 데이터를 쓰도록 inode_write_at() 함수를 수정한다.

Buffer Cache 초기화 함수 구현

• bc_init()

버퍼 캐시 영역 할당 및 buffer_head 자료구조를 초기화한다.

p_buffer_cache로 버퍼 캐시 영역을 포인팅한다.

buffer_head 자료구조를 초기화한다.

• bc_term()

버퍼 캐시에 캐싱 된 데이터를 디스크 블록으로 flush 한다.

버퍼 캐시 영역을 메모리에서 할당 해지한다.

Victim Selection 함수 구현

• bc_select_victim()

clock 알고리즘을 통해 버퍼 캐시에서 victim entry를 선택한다.

victim entry가 dirty일 경우 데이터를 디스크로 flush 한다.

• bc_lookup()

buffer_head를 순회하며 디스크 블록의 캐싱 여부를 검사한다.

디스크 블록이 캐싱되어 있다면, 버퍼 캐시 엔트리를 반환하고 그렇지 않으면 NULL 값을 반환한다.

인자 sector는 검색할 디스크 블록의 번호를 나타낸다.

Entry Flush 함수 구현

• bc_flush_entry()

block_write() 함수를 통해 버퍼 캐시 데이터를 디스크로 flush 한다.

모든 Entry Flush 함수 구현

• bc_flush_all_entries()

buffer_head를 순회하며 dirty인 엔트리의 데이터를 디스크로 flush 한다.