Chapter 13 ~ 15. File Systems

Outline

---

① File concepts

② File System Implementation

③ Allocation Methods

④ Examples

 

① File concepts

---

● 정의

보조 기억장치에 기록된 관련 정보의 명명된 모음

(A named collection of related information that is recorded on secondary storage)

 

● 속성

1. 이름

2. 식별자 (inode)

3. 타입

4. 위치

5. 크기

6. protection

7. time, date, user identification

 

● 연산 (파일 접근을 위한 API)

1. create

2. write

3. read

4. reposition within file (fseek)

5. delete

6. truncate (파일 내용 삭제)

 

● Open files

파일에 대한 정보를 읽어서 table 형태로 관리

entry를 메모리에 불러오고 keep함

 

Open-file table

  -> 열려있는 모든 파일의 정보를 포함

  -> 파일의 위치, 속성 등을 메모리에 keep

                    

 

open()

  -> File Control Block을 Open-file table에 저장

  -> FCB를 메모리에 저장함으로써 read, write, seek를 효과적으로 수행

  -> FCB가 메모리에 없으면 FCB 읽기 위해 disk I/O 계속 수행

  -> open file table의 pointer를 반환 (file descriptor)

 

 

close()

  -> File Control Block을 Open-file table에서 제거

 

● File Control Block

해당 파일에 대한 모든 것 제어 가능

1. File pointer                  : 현재 파일의 offset (seek으로 변경가능)

2. File-open count            : 해당 파일을 open한 프로세스 수

3. Disk location of the file : 파일이 저장된 disk의 위치

4. Access right                 : 접근 권한

② File System Implementation

---

1. Information on disk

  1) Boot Control Block

    -> 시스템이 OS를 부팅하기 위해 필요한 정보를 저장

    -> 각 볼륨(파티션)의 첫 번째 block

 

  2) Volume Control Block

    -> 파일 시스템 자체에 대한 정보 

    -> 각파티션마다 별도의 파일 시스템 설치됨

 

  3) Directory structure

    -> directory file들의 meta-data (file name, inode number)

    ※ meta-data       : 파일을 관리하기 위한 정보

    ※ inode number  : File Control Block number

 

  4) FCB (File Control Block)

    -> 파일에 대한 자세한 정보 포함

• file permission
• file dates (create, access, write)
• file owner
• file size
• file location

 

2. Information in memory

  1) in-memory mount table

    -> mount된 각각의 volume 정보

    -> 현재 mount된 file system의 정보

    -> 파일 시스템 사용 위해 필수

    -> 부팅 시 자동으로 mount

 

  2) in-memory directory structure

    -> 최근에 접근한 directory structure를 메모리에 keep (빠른 접근 가능)

 

  3) system-wide open-file table

    -> 열려있는 파일들의 FCB 사본과 기타 정보 포함

 

  4) per-process open file table

    -> system-wide open-file table에 있는 entry에 대한 포인터와 기타 정보 포함

    -> 하나의 파일을 여러 프로세스가 별도로 open 가능

 

File Open

기존에 다른 프로세스가 해당 파일을 open 했는지 확인하기 위해서 system-wide open-file table 탐색.

다른 프로세스에서 해당 파일을 open했을 경우

  -> file control block을 디스크로부터 가져올 필요 없으므로

  -> per-process open-file table이 이미 존재하는 system-wide open-file table을 가리키고,  

  -> offset과 protection은 별도로 저장.

 

다른 프로세스에서 해당 파일을 open하지 않았을 경우,

  -> file control block을 디스크로부터 가져와서 system-wide open-file table에 추가 해야함.

  -> File control block을 가져오기 위해서 directory structure를 탐색.

  -> Directory structure에서 inode number를 찾고,

  -> inode table에서 해당 inode number에 해당하는 file control block 찾음.

  -> 해당 file control block을 system-wide open-file table에 복사함.

 

File R/W

  -> Per-process open-file table을 탐색해서 해당 파일의 offset, protection mode에 대한 정보 확인

  -> file의 위치 정보가 있는 file control block을 찾기 위해서 system-wide open-file table 탐색.

File Close

  -> per-process open-file table 제거

  -> system-wide open-file table의 open count 감소

 

3. Virtual file systems

여러 개의 file system 사용할 때 하나의 API로 여러 개의 file system 접근

R/W/Open 할 때 실제 file system API를 사용하지 않고, VFS interface 사용

file system에 맞춰 자동으로 변환됨

v node: virtual system에서 관리하는 inode

③ Allocation Methods

---

하나의 파일을 구성하고 있는 일련의 disk block들을 어떻게 저장/관리할 지

 

1. Contiguous allocation

하나의 파일을 구성하고 있는 block들을 연속적으로 저장

 

장점

  -> 구현이 간단함. 파일의 시작위치와 길이(블록 개수)만 알면 된다.

  -> 파일을 읽을 때 head movement가 필요 없다.

 

단점

  -> external fragmentation 발생

  -> file이 일정 크기 이상으로 커질 수 없음

 

구현

  -> Sequential access : 이전에 읽은 disk address에서부터 읽기

  -> Direct access       : 파일의 시작주소 + i에서 읽음

 

개선방안

  -> extent-based allocation

 

2. Linked allocation

이전 block의 끝에 다음 block의 주소 기록. 포인터 저장

 

장점

  -> 파일을 연속적으로 저장하지 않기 때문에 contiguous allocation의 문제점인 externam fragmentation 해결 가능

단점

  -> direct access 불가능.

  -> i번째 block을 찾기 위해서 파일의 시작지점부터 탐색해야함

  -> Pointer information을 저장하는 overhead

  -> 중간에 block이 사용 불가할 경우, 그 다음 block 접근 불가능.

 

해결책

  -> 단위를 block이 아닌 여러 개의 block으로 구성된 cluster 단위로 저장

 

개선 방안

  -> FAT(file allocation table)

 

3. Indexed allocation

각 파일마다 존재하는 Index block에 해당 파일을 구성하고 있는 block number 기록.

Index block 위치만 각 파일별로 가지고 있으면 그 파일을 구성하고 있는 block number들 확인 가능.

 

문제점

  -> 파일의 block 개수가 index block에 저장할 수 있는 block number 개수보다 많으면?

  1) Linked scheme

    -> 하나의 index block만 사용.

 

  2) Multilevel index

    -> index를 여러 level로 구성.

    -> Outer index에는 file  block number가 아닌 index block number 기록

    -> index block을 두 번 읽어야 하는 문제 발생(outer index, inner index)

    -> caching으로 해결 가능. Index block을 메모리에 keep

 

  3) Combined scheme

    -> 여러 개의 인덱스 기법을 혼합해서 사용.

    -> I-node에는 12개의 direct block과 3개의 indirect block 존재.

 

Direct block      : 파일을 구성하고 있는 block number를 저장(4KB x 12 = 48KB)

Single indirect   : linked scheme(4byte x 1024 = 4MB)

Double indirect : 2-level index(4mb  x 1024 = 4GB)

Triple indirect   : 3-level index(4gb x 1024 = 4TB)

 

④ Examples

---