[PINTOS] project4: File System

핀토스 마지막 프토젝트인 file system에서는 데이터를 저장하는 디스크를 운영체제가 어떻게 가상화하고 데이터를 저장하고 접근하는지에 대해 알아보았다.

I/O 장치

                              Prototypical System Architecture

일반적인 시스템의 고전적인 구조는 위 그림과 같다. CPU와 주메모리가 메모리 버스와 연결되어 있다. 그리고 그래픽이나 다른 고성능 I/O 장치들이 범용 I/O 버스(PCI: Peripheral Component Interconnect, 컴퓨터 내부에서 CPU와 주변 기기를 연결하는 local bus의 일종)에 연결 되어 있다. 마지막으로, 그 아래에는 SCSI, SATA 또는 USB와 같은 주변 장치용 버스가 있다. 이 버스들을 통해 디스크, 마우스, 키보드와 같은 느린 장치들이 연결된다.

이런 계층 구조가 필요한 이유는 물리적인 이유와 비용 때문이다. 버스가 고속화되려면 더 짧아져야 하는데, 그런 고속 메모리 버스에는 여러 장치들을 수용할 공간이 없다. 또한 제작 비용도 높기 때문에 계층 구조를 택하여 고성능 장치들을 CPU에 가깝게 배치하고 저성능 장치들은 멀리 배치하게 된 것이다. 또한 디스크처럼 느린 장치를 주변 장치 I/O 버스에 연결하여 여러 이득(많은 장치 연결 가능)을 얻을 수 있다.

file and file system

file: 하드디스크에 저장하는 단위, 이름을 통해서 접근하는 단위, a named collection of related information, 비휘발성의 보조기억장치에 저장, 운영체제는 다양한 저장 장치를 file이라는 동일한 논리적 단위로 관리한다.

메모리는 주소를 통해서 접근하는 장치

File attribute(파일의 metadata): 파일의 metadata를 메모리로 올리는 것을 open이라 한다. 파일은 파일을 관리하기 위한 정보가 있다.

• 파일 이름, 유형 저장된 위치, 파일 사이즈 등.
• 접근 권한(읽기/쓰기/실행), 시간(생성/변경/사용), 소유자 등

File system: 운영체제에서 파일을 관리하는 부분, 파일 자체와 메타데이터도 같이 저장. 디렉토리를 통해 계층적으로 관리

Directory: 디렉토리도 하나의 파일, 파일의 내용이 디렉토리 밑에 파일들이 무엇이 있는지(파일의 메타데이터)를 정보로하는 파일

Partition(=logical disk): 물리 디스크들을 용도에 맞게 논리적으로 나눈 것

open()

파일은 open하면 file의 metadata가 물리메모리로 올라온다.

1. 사용자 프로그램이 open(”/a/b”) 호출
2. root dir의 metadata를 먼저 메모리에 올린다.(root를 먼저 open한다.)
3. root dir의 metadata를 바탕으로 실제 content(dir내의 파일들의 data)에 접근하고 그 중에 a가 존재하고 그것을 메모리에 올린다.
4. a(dir file)의 metadata를 통해 content에 접근하고 a 내부에 있는 b의 metadata를 메모리에 올린다.
5. 각 프로세스마다 metadata pointer 배열이 정의되어 있는데(fd), 이 중 b file을 가르키고 있는 것을 process에 리턴한다.

read()를 할때는 위에서 얻은 fd(file discriptor)를 이용하여 파일을 읽는다.

read(fd): 커널 영역으로 넘어간 후 메모리에 있는 b의 metadata를 보고 b의 content의 접근하여 요청한 용량만큼 읽어서 운영체제가 커널 메모리 공간에 가져온다. 그 후 사용자 프로그램에 카피해서 전달한다. 즉, 동일한 파일에 동일한 데이터를 요청하면, 커널 메모리에 데이터가 존재하기 때문에 디스크에서 읽을 필요가 없어진다. —> buffer caching

현재 프로세스가 파일의 어떤 위치를 읽고 있는지(offset) 정보를 알고 있어야 한다. 이는 프로세스마다 별도로 가지고 있어야한다.

open file table은 프로세스 별도로 존재

File protection

메모리 protection은 접근 권한을 바탕으로 보호가 가능했다.

그러나 파일은 여러 사용자, 여러 프로그램이 같이 사용할 수 있으므로, 접근 권한이 누구한테 해당하느냐와 연산이 누가누가 가능한가를 같이 가지고 있어야 한다.

Access: control 방법

1. access control matrix: 각각의 사용자와 파일에 대한 접근권한을 matrix로 표시, 그러나 행렬의 칸을 전부 만드는 방식은 비효율적이다 → linked-list 방식 사용: 파일별로 누구에게 어떤 접근 권한이 있는지 표시(access control list) or 사용자 별로 자신이 접근 권한을 가진 파일 및 해당 권한 표시(capability list)
2. Grouping: 모든 사용자에 대해서 다루는 것이 아니라 사용자 그룹을 3가지로 나눈다.
   1. onwer : group :public = rwx : r - - : r - -
   2. 각 파일에 대해 세 그룹의 접근 권한(rwx)을 3비트씩으로 표시
3. Password: 파일마다 password를 두는 방법(디렉토리 파일에 두는 방법도 가능), 모든 접근 권한에 대해 하나의 password, 접근 권한별 password

Access methods

파일의 접근하는 방식

1. 순차 접근(sequential access): 카세트 테이프를 사용하는 방식처럼 접근, 읽거나 쓰면 offest은 자동적으로 증가
2. 직접 접근(direct access, random access): LP 레코드 판과 같이 접근하도록 함, 파일을 구성하는 레코드를 임의의 순서로 접근할 수 있음

Allocation of file data in Disk

1. contiguous allocation: 연속 할당, 디스크 상에 데이터가 연속해서 할당된다.
   • 단점: 외부단편화, file grow가 어려움, 파일의 크기가 균일하지 않기때문에 내부에 hole이 생긴다.
   • 장점: 빠른 I/O가 가능하다. 한번의 seek/rotation으로 많은 바이트 transfer, process의 swapping 용, 직접 접근이 가능하다.
2. linked allocation: 연결 할당, 파일의 데이터를 디스크에 아무데나 배치한 후에 linked list처럼 연결 시킨다.
   • 장점: 외부단편화가 일어나지 않는다.
   • 단점: 직접 접근 불가능, Reliability = 중간에 한 sector가 고장나면 그 뒤에 있는 데이터들은 유실된다. 포인터를 위한 공간이 block의 일부가 되어 공간 효율성을 떨어트린다.
   • 변형- File-allocation table(FAT) 파일 시스템: 포인터를 별도의 위치에 보관하여 문제 해결
3. indexed allocation: 인덱스 할당
   • 직접 접근을 하기 위해서 파일의 위치정보를 저장하는 index block을 사용한다.
   • 장점: 외부단편화가 없다, 직접 접근 가능
   • 단점: small file의 경우 공간 낭비(실제로 많은 file들이 small), 혹은 너무 클 경우 하나의 index block으로 표시를 할 수가 없다. → linked scheme, multi-level index 사용

UNIX 파일시스템의 구조

• Boot block: 부팅에 필요한 정보(bootstrap loader) 항상 가장 맨 앞에 존재한다.
• Super block: 파일 시스템에 관한 총제적인 정보를 담고 있다. 어디가 빈 block이고 어디가 사용 중인 block인지를 관리, 어디까지 inode list인지 어디까지 data block인지 관리,
• Inode list: index_node, 파일의 metadata는 별도의 위치(Inode list)에 빼서 보관한다. inode는 파일의 metadata를 가지고 있는 것이다. 하지만 파일 이름의 경우는 directory가 가지고 있다. inode는 크기가 고정되어 있다. 그러므로 unix는 4가지로 파일의 위치정보를 구성한다.
• Data block: directory file은 file 이름과 inode 번호를 가지고 있다.

FAT file system

• metadata의 위치정보를 FAT에 저장
• directory가 file의 나머지 metadata를 가지고 있다.
• FAT의 크기는 할당된 data block만큼의 크기이다.
• 특정 위치에 있는 data가 소실되더라도 FAT에 위치정보가 저장되어 있으므로 다음 데이터에 접근할 수 있다.

Free-space Management

비어있는 block은 어떻게 관리할 것인가?

bit-map or bit-vector

비트맵의 크기 = data block의 크기

연속적인 n개의 free block을 찾는데 효과적

1. linked-list: 비어있는 block을 linked-list로 관리 첫번째 위치만 가지고 있고, 그 다음 위치는 block 마지막에 적어논다. 공간의 낭비가 없다.연속적인 가용공간을 찾기는 어렵다.
2. Grouping: 비어있는 block이 index 역할을해서 첫번째 free block이 n개의 pointer를 가진다.
3. Counting: 연속적인 빈 block을 표시하기 위해서 사용, 프로그램들이 종종 여러 개의 연속적이 block을 할당하고 반납한다. (free block, # of contigous free blocks)을 유지

Directory implementation

directory file의 구조

1. linear list: file name, metadata를 리스트 형식으로 저장

2. hash table: 파일의 이름을 해시 함수에 적용해서 그 결과 값을 index로 하는 table

3. metadata 보관 위치: 직접 보관, inode , fat 등에 보관

4. long file name: dir entry는 고정되어 있으므로 long file name을 지원해야 한다.

   how? 앞부분은 평소대로 저장을 하다가 마지막을 pointer 위치 정보를 저장하고, 파일 이름을 다른 공간에 저장한다.

VFS and NFS

Virtual File System(VFS): 사용자가 파일 시스템에 접근할 때에는 system call을 해야한다. 서로 다른 다양한 file system에 대해 사용자가 동일한 시스템 콜 인터페이스를 통해 접근할 수 있게 해주는 OS의 layer

Network File System(NFS): 분산 시스템에서는 네트워크를 통해 파일이 공유될 수 있음, NFS는 분산 환경에서의 대표적인 파일 공유 방법

Page Cache and Buffer Cache

1. page cache: virtual memory의 paging system에서 사용하는 page frame을 caching의 관점에서 설명하는 용어 → 운영체제한테 주어지는 정보가 지극히 제한적
2. Memory-mapped I/O: 파일을 접근할 때, file의 일부를 virtual memory에 mapping 시킴
3. Buffer cache: 파일 시스템을 통한 I/O 연산은 메모리의 특정 영역인 buffer cache 사용 → 파일 데이터가 어디에 있던지 file에 접근할 때는 system call을 해야하기 때문에 운영체제가 여러 정보를 가지고 있다. LRU, LFU 사용 가능
4. Unified Buffer cache: buffer cache와 page cache를 통합

Disk management and scheduling

Disk structure

디스크를 관리하는 최소 단위는 sector, sector는 내부에서 관리하는 단위. 외부에서 접근하는 단위는 logical block 단위로 디스크에 접근한다. logical block은 1차원 배열처럼 취급 정보를 전송하는 최소 단위

• Physical formatting: 디스크를 컨트롤러가 읽고 쓸 수 있도록 섹터들로 나누는 과정 각 sector는 header + 실제 data(512 byte) + trailer로 구성, header와 trailer는 sector num, ECC(error-correcting code)등의 정보가 저장되며 controller가 직접 접근 및 운영
• Partitioning: 디스크를 하나 이상의 실린더 그룹으로 나누는 과정, OS는 이것을 독립적 disk로 취급
• Logical formatting: 파일 시스템을 만드는 것, FAT, inode, free space 등의 구조 포함
• Booting: ROM에 있는 “small bootstrap loader” 실행, sector 0(boot block)을 load하여 실행, sector 0은 “full Bootstrap loader program”, OS를 디스크에서 load하여 실행

Disk scheduling

Access time:

• Seek time: 헤드를 해당 실린더로 움직이는데 걸리는 시간
• Rotational latency: 헤드가 원하는 섹터에 도달하기까지 걸리는 회전지연시간
• Transfer time: 실제 데이터의 전송시간

대부분 걸리는 시간은 seek time

Disk bandwidth: 단위 시간 당 전송된 바이트의 수

disk scheduling: seek time을 최소화하는 것이 목표, seek time ~ seek distance

Disk scheduling algorithm

1. FCFS(first come first service)

   들어온 순서대로 처리하겠다.

2. SSTF(Shortest Seek Time First)
   현재 head와 가장 가까이 있는 요청을 처리한다. → starvation 문제

3. SCAN(엘리베이터랑 비슷)
   disk arm이 디스크의 한쪽 끝에서 다른쪽 끝으로 이동하며 가는 길목에 있는 모든 요청을 처리한다.
   실린더 위치에 따라 대기 시간이 다르다.

4. C-SCAN
   헤드가 한쪽 끝에서 다른쪽 끝으로 이동하며 가는 길목에 있는 모든 요청을 처리, scan과 다른 점은 C-SCAN은 다른쪽 끝에 도달했으면 요청을 처리하지 않고 곧바로 출발점으로 다시 이동

5. N-SCAN
   디스크 헤드가 이동하면서 지나가는 도중에 들어오는 요청은 다음번에 처리한다.

6. LOOK and C-LOOK
   헤드가 진행 중이다가 그 방향에 더 이상 기다리는 요청이 없으면 헤드의 이동 방향을 돌린다.

Swap-space management

physical disk를 logical disk로 나누어서 사용

ex) 1 physical disk → file system + swap area

swap-space: virtual memory system에서는 디스크를 memory의 연장 공간으로 사용, 공간 효율성보다는 속도 효율성이 우선(금방 사라질 가능성이 높은 데이터이기 때문에), block의 크기 및 저장 방식이 일반 파일시스템과 다름

RAID(Redundant Array of Independent Disks): 여러 개의 디스크를 묶어서 사용

사용 목적

1. 디스크 처리 속도 향상: 여러 디스크에 block의 내용을 분산 저장, 병렬적으로 읽어 옴
2. 선뢰성 향상