file system

File System

1.   File concept

·       연속적인 논리주소 공간, 데이터를 담는 그릇.

·       사용 목적에 따라 다양한 구조를 가질 수 있다.

·       OS는 오직 메타데이터만 관리한다.(name, type, location, size, protection, time, date, user identification …)

·       모든 파일에 대한 정보는 디렉토리 내에 유지되며, 디렉토리는 하드디스크에 저장된다.

2.   File operation

·       Create, write, read, reposition(seek), delete, truncate(파일의 내용은 지우고, 파일의 속성은 그대로 남기는 연산. 파일을 삭제하는 것이 아니라 메타데이터를 살리고 데이터를 지운다, file size는 0이 된다.), open, close

·       Access methods

·       Sequential access : 순차적으로 접근

·       Direct access : block number로 접근

·       Directories

·       For user : 관련 파일을 묶어서 관리할 수 있다, for the file system : 파일의 메타데이터가 저장되는 별도의 공간.

·       Directory entry : 디렉토리를 표현하는데 쓰이는 자료구조.

·       디렉토리는 하드디스크에 저장되므로, file에 access가 일어날 때 Directory entry를 메모리에 올려서 접근한다. I/O 속도 개선을 위해 캐싱을 사용한다.(다만, inconsistency 문제에 대한 대책 필요. - 메모리에 반영된 메타데이터의 변화가 하드에 반영되지 않을 수 있음.)

·       결국은 file에 대한 정보를 가진 node들의 집합. 다양한 구조로 구현 할 수 있다.

Ex) UNIX의 경우 아이노드를 사용하여 디렉토리 엔트리는 파일 이름과 아이노드의 정보를 갖고, 파일의 속성,  소유자 정보 등의 메타데이터는 아이노드에 저장한다.

·       파일을 삭제하는 것은 디스크에서 해당 block을 지우는 것이 아니라 디렉토리 엔트리에서 메타데이터를 삭제하는 것임.

·       디렉토리의 구조

o   Single level directory

·       단일 레벨 디렉토리 사용시, 똑같은 이름을 사용할 수 없음.

o   Two level directory

·       사용자 별로 single level 디렉토리를 하나씩 만들어 준다. 다른 사용자간 동일한 파일 이름을 쓸 수 있다.

·       여전히 파일을 그룹으로 관리할 수 없다.

o   Tree- structure directories

·       최상위에 하나의 루트 디렉토리가 존재, 시스템 내의 모든 파일들은 고유한 경로명을 가진다.

·       디렉토리는 하위 디렉토리를 계속해서 가질 수 있고, 한 비트를 사용하여 해당 항목이 파일인지 디렉토리인지 구분한다.

·       Home directory, current directory, absolute path, relative path 등의 개념 등장.

·       Search path(명령어 해석기) : 명령어를 해석하기 위한 정보를 담는 path를 지정한다.

·       디렉토리 삭제 시 문제 발생 가능. Empty 시에만 허용 or 그냥 다 지우기.

o   Acyclic-graph directories(cycle x)

·       디렉토리들이 서브디렉토리들과 파일들을 공유할 수 있음.

·       같은 파일이 두 디렉토리간 공유되고 있다면, traverse 시 두 번 방문될 수 있고, delete시에도 문제 발생 가능

§  Kang이 x 파일 갖고 있는데(x의 메타데이터를 담은 디렉토리 entry), choi가 sharing 하고자 할 때,

UNIX는 링크라 불리는 새로운 디렉토리 엔트리를 choi의 디렉토리에 만든다.

·       Symbolic link - 실제 파일을 찾기 위한 경로명, 간접적인 포인터, path를 지정.

·       Hard link - 기존 kang이 갖고 있던 디렉토리 엔트리를 choi에게 복사해 준다.

·        update 시 consistency 문제 발생 가능.

·       Delete시 OS는 file에 할당되었던 block을 freeblock으로 assign 하는데, choi가 여전히 파일을 사용하고자 할 경우, 없는 파일에 접근하게 된다. 그래서 Count 값을 사용할 수 있다. Reference count를 사용하여 하드링크 시 마다 1씩 증가, 삭제 시 마다 1씩 감소하여, 0일때만 실제로 file을 지우는 방법을 사용한다.

o   General graph directory(cycle o)

·        directory traverse시 무한 루프 발생 가능, 쓰려면 cycle detect 필요.

·       파일을 delete 했으나, reference count 가 0이 아니어서(self-reference or cycle...) 실제로는 남아있지만, 접근을 할 수 없게 되는 경우 발생 가능. -> garbage collection 필요.(access가 불가한 node들을 찾아서 free)

·       너무 느리므로 일반적으로 cycle 허용 않는다.

§  File sharing은 허용 하되, directory sharing은 허용하지 않으면 cycle이 절대 발생하지 않는다.

·       Protection

·       각 user들의 access를 어떻게 관리할 것인가?

o   각 파일 별로 어떤 유저가 어떤 권한(RWX)를 수행할 수 있는지 관리할 수 있지만, Table size가 너무 커진다.

·       각 파일의 디렉토리 엔트리에 권한을 넣어서 저장하자.

·       전체 user를 셋으로 나누어 관리한다.(USER : owner(root), GROUP : file에 접근할 가능성이 높은, OTHERS : 먼 사람)

o   Ex) chmod 761 game -> game 디렉토리 권한이 user는 RWX, groups는 RW-, others는 --X.

o   Ex) chmod others + R과 같이 사용도 가능.

·       File-System Structure

·       File system은 secondary storage(disk)에 존재.

·       Fopen이라는 시스템 라이브러리를 통해서, open 시스템 콜을 호출한다. Open 시스템 호출은 디스크로부터 파일의 메타데이터를 메모리로 가져온다. (이를 위해 디스크 탐색 필요), 또한, 현재 메모리에 있는(open 된) 파일들의 메타데이터를 저장하는 open file table을 유지한다. Open file table에서 해당 파일의 위치를 담고 있는 위치를 가리키는 포인터를 file descriptor라 한다. (만약 fd를 사용하지 않는다면, 해당 파일의 위치를 알기 위해 해당 디렉토리 엔트리에 접근해야 하고, 이를 위해서는 불필요한 disk I/O가 발생한다. 예를 들어, Fscanf( )의 인자로 파일이름을 넣는다면 매 호출마다 해당 파일의 위치를 알기 위해 disk I/O가 필요하다. Fd를 사용하면 open file table에 저장된 메타데이터를 통해 바로 알 수 있다.)

·       Mounting file system

·       Mounting은 각 디바이스들이 서로 다른 파일시스템을 사용한다고 해도, 같은 파일 시스템인 것처럼 사용할 수 있도록 해준다.

·       각 디바이스의 가장 위에 단순히 새로운 root를 만들면, 디바이스 별로 파일 시스템이 다를 경우 같은 operation을 적용할 수 없다.

·       Booting Drive의 root를 전체 root로 보고 각 디바이스의 디렉토리를 마운트 한다.

·       마운트가 되면, 지정된 마운트 포인트의 하위 디렉토리 인 것처럼 접근할 수 있다.(기존 파일시스템의 디렉토리 까지는 해당 파일 시스템에 맞게, 마운트 된 디바이스에는 그 파일 시스템에 맞게 동작한다.)

·       마운트를 사용하면 한 하드디스크 내에 파티션을 여러 개 만들고, 각 파티션에 다른 파일 시스템을 적용할 수 있다. 그리고 저장할 파일들의 특성에 맞게 포맷하여 사용하여 Performance를 향상 시킬 수 있다. 예를 들어 linux의 swap partition의 경우 프로세스가 통째로 swap될 때 발생하는 많은 양의 disk I/O를 줄이기 위해서는 연속적으로 DISK에 할당할 필요가 있다. 이 파티션의 경우 연속 할당 방식의 파일 시스템을 사용한다.

·       Allocation of file data in disk

·       Contiguous allocation : 디스크에 연속적으로 파일을 저장한다. Starting location(block #) + length(# of blocks) 필요.

·       External fragmentation 발생 -> hole이 많이 생긴다.

·       Fire grow가 어렵다. 처음부터 여유있게 할당할 경우 internal fragmentation이 발생한다.

·       Fast I/O 가 가능하다. 한번의 Seek으로 많은 바이트를 전송한다.(real time, process swapping에 사용한다. -entire R/W)

·       순차접근, random access가 모두 가능하다.

·       Linked allocation

·       파일이 디스크 블록의 연결리스트로 구현. 각 블록들은 디스크 곳곳에 산재되어 있다.

·       각 블록은 file content + pointer로 구성.

·       공간 낭비가 발생하지 않는다.

·       But, random access 불가(start block 부터 하나씩 따라 가야 한다.)

·       disk I/O가 비효율적이다, reliability가 낮다. ( 한 sector가 고장나 pointer가 유실되면 이후 부분을 전부 잃게 된다.)

·       pointer를 각 블록마다 저장해야 한다.

·       -> 변형하여 사용한다.(FAT : file allocation table)

·       File allocation table

·       각 디렉토리 엔트리에 해당 파일의 start block #가 저장되어 있고, 디스크 블록의 연결리스트 정보가 메모리에 저장된다.(FAT)

·       FAT의 각 항목은 다음 블록의 주소를 저장하고 있다. FAT를 통해 모든 파일의 모든 블록 위치를 알 수 있다. 역시 하나씩 따라가 보아야 하지만, 메모리 접근이므로 상대적으로 빠르다.

·       FAT가 손상되는 것을 방지하기 위해 하드디스크에 백업하며, 주기적으로 변경된 값을 반영한다.

·       Indexed allocation

·       각 파일들은 자신만의 index block을 가지고, index block의 i번째 항목은 해당 파일의 i번째 디스크 블록을 가리킨다.

·       Direct access가 가능하다.

·       But, 이 index block이 손상되면 파일 전체를 잃어버린다는 점, file 크기에 한도가 존재한다는 점, 파일의 크기가 아주 작아서 한 두개의 블록만 사용한다면, 해당 블록의 나머지 공간이 낭비된다는 점 등의 단점이 존재한다.

·       파일의 크기가 클 경우 1) linked list로 구현(크기 제한 x, but random access 불가) 2) two -level index(tree) 3) combined(unix) 사용.

·       Combined scheme

·       Unix의 경우 각 파일 별로 존재하는 아이 노드의 색인블록 중 첫 12개는 직접 데이터 블록을 가리키고, 이보다 파일이 크면 단일 간접을 통하여, 이보다 크면 이중 , 삼중 간접을 통해 디스크 블록의 위치를 가리킨다.

·       크기가 작은 파일들에 더 빨리 접근 할 수 있다.

·       Management of free space

·       Bit map(bit vector)

o   각 블록을 1비트로 표현, 비어있으면 1, 사용 중이면 0.

o   연산 속도를 높이기 위해 word단위로 search.

o  

o   추가 공간 필요.

·       Linked list

o   각 free block은 그 다음 free block을 가리킨다.

o   리스트 순회를 위해서는 disk I/O 필요.

o   연속된 공간 할당 힘듬.

o   공간 낭비 X.

·       Grouping(indexed block)

o   한 자유블록 내에 다른 자유블록들의 리스트를 저장한다.

o   이 자유블록의 마지막에는 역시 리스트를 저장하는 다른 자유블록을 가리키는 포인터를 저장한다.(연결리스트)

·       Counting

o   프로세스들은 매우 자주 연속된 블록을 동시에 할당, 반환 하므로, 각 자유블록의 시작 위치와 연결된 블록의 개수를 가지고 관리한다.

·       Directory implementation

·       Linear list : 탐색시간이 오래 걸림.

·       Hash table : file name -> meta data. Linear list 보다는 빠름.

·       Efficiency and performance

·       디스크 캐시 : 주메모리의 일부를 자주 사용되는 블록을 위한 캐시로 사용.

·       Free behind and read ahead(순차적 접근을 위해)

o   Free behind : 읽어온 블록을 공간이 없을 때 버리자. Next block 요청 할 때 현 block을 free.

o   Read-ahead : 하나 읽어 올 때 뒤이은 페이지들을 같이 가져와서 캐싱하자.

·       Virtual disk(RAM disk) : 주메모리의 일부를 디스크처럼 사용한다.(사용자가 관리 가능, 디스크 캐시는  사용자가 관리 불가)

·       Recovery

·       Consistency checking : 디렉토리의 일부분은 성능을 향상시키기 위해 주 메모리에 저장된다. 이 정보의 갱신이 디스크에 곧바로 반영되지는 않는다. 이 상황에서 비정상 종료될 경우 파일의 실제 상태가 디렉토리 엔트리 정보와 다른 inconsistency 가 발생 할 수 있다. 부팅시, consistency checker는 하드디스크를 scan하면서 메타데이터와 사용자 데이터의 불일치를 찾아서 메타데이터를 기준으로 복구한다.

-> file system은 결국 하드디스크에 존재하는 하나의 자료구조.