Storage에 있는 데이터를 접근하는 방식에는 Sequential Access (순차 접근)과 Direct Access(직접 접근)이 있다.
매체에 따라서 tape 같은 것들은 순차 접근만이 되고, 하드 디스크나 플래시 메모리 같은 매체들은 직접 접근이 가능하다.
직접 접근이 가능한 매체라고 하더라도 데이터를 어떻게 관리하느냐에 따라 순차 접근만 허용하는 경우도 있고 직접 접근이 가능한 경우도 있다.
✓ Allocation of File Data in Disk
- 연속 할당 (Contiguous Allocation)
- 연결 할당 (Linked Allocation)
- 색인 할당 (Indexed Allocation)
파일 시스템은 디스크를 논리적인 디스크 블록들의 집합으로 보며, 디스크 블록은 0, 1, 2 등의 논리적인 번호를 하나씩 갖는다.
그리고 디스크 블록의 크기는 일반적으로 페이지 프레임의 크기와 같다.
일반적인 시스템에서는 페이지 프레임의 크기가 4KB이며, 따라서 디스크 블록의 크기도 4KB가 된다.
파일 시스템 성능의 최대 병목 요소는 디스크 I/O이기 때문에 최근 파일 시스템의 경우 디스크 블록의 크기를 더 크게 설정하는 경향이 있다.
디스크 블록의 크기가 클수록 한 번의 Disk I/O로 더 많은 데이터를 메모리로 읽어 들일 수 있기 때문이다.
그러나 디스크 블록의 크기와 속도 측면에서의 성능은 비례하지만 공간 효율성면에서의 성능은 반비례한다.
평균적으로 데이터 블록 중 마지막 블록의 절반은 낭비되기 때문이다.
연속 할당 (Contiguous Allocation)
연속 할당은 하나의 파일이 디스크 상에 연속해서 저장된다.
예를 들어, 두 개의 블록으로 구성되는 파일은 첫 번째 블록과 두 번째 블록이 인접해 있는 것이다.
만약 블록 6개로 구성되어 있는 파일이라면, 19번 블록부터 24번 블록까지 데이터를 연속적으로 할당하는 방식이다.
Directory File은 그 Directory 밑에 있는 파일들의 메타데이터를 내용으로 한다.
위 그림의 directory를 보면, 그 Directory에 다섯 개 파일의 메타데이터가 저장이 되어있다.
count라는 파일은 연속할당으로 저장하고 0번의 위치부터 길이가 2이므로 0,1번 블록에 할당이 된다.
연속할당은 각각 파일의 크기가 균일하지 않아서 free 블록이 생겨 외부 조각이 생길 수 있다.
새로운 파일이 만들어질 때, free 블록보다 크기가 크면 해당 블록에 할당하지 못하기 때문이다.
또한, 중간에 파일의 크기가 커지게 되면 제약을 받을 수 있다.
그래서 파일이 커질 것을 고려해서 미리 빈 공간을 어느 정도 확보해 놓는 방법이 있다.
미리 여유공간을 확보하더라도 해당 공간만큼만 커질 수 있으며, 미리 할당해 놓으면 지금 당장 사용되지 않는 공간(내부 조각)이 된다.
- 외부조각 : 아무도 사용하지 않기 때문에 누군가에게 할당될 수 있는 공간
- 내부조각 : 어떤 프로그램에 이미 할당되어 있는데 사용되지 않는 공간
디스크에서 데이터를 접근하는 데 걸리는 시간 구성 요소
- 탐색 시간 : Head를 요청한 데이터가 존재하는 트랙 위치까지 이동하는 데 걸리는 시간
- 회전 시간 : 요청한 섹터가 헤드 아래로 위치될 때까지 디스크 원판을 회전시키는 데 걸리는 시간
- 데이터 전송 시간 : 헤드가 섹터의 내용을 읽거나 기록하는 데 걸리는 시간
디스크에서 I/O 시 대부분의 시간은 디스크 헤드가 이동하는 시간이며, 실제로 데이터를 읽거나 쓰는 작업은 시간이 크게 소모되지 않는다.
연속할당에서 파일 전체를 읽고 싶다면 디스크 헤드가 한 번만 이동해서 많은 양의 데이터를 받아올 수 있다.
따라서, 디스크의 탐색 시간을 줄일 수 있기 때문에 I/O 작업이 빠르다.
연속 할당은 파일시스템 용도 말고 프로세스의 Swap Area 용도로도 사용한다.
파일 저장 용도가 아니라 프로세스의 주소 공간 일부를 물리적인 메모리에서 쫓아내고 나중에 필요할 때 올려놓는 용도로 사용한다.
Swap Area 영역은 프로세스가 끝나면 의미가 없는 정보들로, 대용량의 크기를 빠르게 디스크로 쫓아냈다가 필요하면 다시 메모리에 올려야 한다.
그래서 공간 효율성보다는 속도 효율성이 더 중요하기 때문에 연속 할당 방식을 사용한다.
또 하나의 장점으로는 직접 접근이 가능하다. 예를 들어, mail이라는 파일은 길이가 6이라고 다섯 번째 블록을 보고 싶다고 하면 앞의 네 개의 블록에 다 접근해야 볼 수 있는 것이 아니라 mail이라는 파일이 19번부터 연속 할당이 되어있기 때문에 19+4=23번 블록을 보면 해당 내용을 확인할 수 있다.
사용자는 이름을 통해 추상적인 자원인 '파일'에 접근하고 싶을 것이다.
따라서 파일 시스템은 처음 데이터를 기록할 때 실제 데이터뿐만 아니라 이 데이터를 추상적 자원인 '파일'로 제공해 주기 위해 부가적인 정보(파일 이름, 생성 시간, 실제 데이터 블록을 인덱싱 하기 위한 정보 등)를 기록해 두어야 한다.
이러한 부가적인 정보를 메타 데이터라고 한다.
✓ 단점
- External Fragmentaion
- File Grow가 어려움
- File 생성 시 얼마나 큰 Hole을 배당할 것인가?
- Grow 가능 vs 낭비 (Internal Fragmentation)
✓ 장점
- Fast I/O
- 한 번의 Seek/Rotation으로 많은 바이트 Transfer
- Realtime File용으로, 또는 이미 Run 중이던 Process의 Swapping 용
- Direct Access(=Random Access) 가능
연결 할당 (LInked Allocation)
네 번째 블록을 보기 위해서는 첫 번째 블록에 간 후에 두 번째 블록에 접근하고, 두 번째 블록에 접근 후 세 번째 블록에 접근해야 한다.
- 직접 접근이 되지 않는다.
- 중간에 Bad Sector가 발생하면 그 뒷 블록에 접근하지 못한다.
보통 디스크의 섹터는 512Byte로 구성되며, 디스크로 접근할 때, 디스크에 저장하라는 단위는 512의 배수를 디스크에 저장하라고 요청한다.
다음 블록을 가리키는 포인터를 위해서 하나의 섹터 512 Byte 중에서 4Byte가 소요되며, 실제 저장할 수 있는 데이터는 512-4=508 Byte가 된다.
때문에, 한 섹터에 들어갈 내용이 포인터 때문에 두 블록이 사용될 수도 있다.
FAT 파일 시스템은 Linked Allocation을 약간 변형하였다.
✓ 장점
- External Fragmentation 발생 안 함
✓ 단점
- No Random Access
- Reliability 문제 : 한 Sector가 고장 나 Pointer가 유실되면 많은 부분을 잃음
- Pointer를 위한 공간이 Block의 일부가 되어 공간 효율성을 떨어 뜨림 : 512 Bytes/Sector, 4 Bytes/Pointer
✓ 변형
- File-allocation Table (FAT) 파일 시스템 : 포인터를 별도의 위치에 보관하여 Reliability와 공간효율성 문제 해결
색인 할당 (Indexed Allocation)
직접 접근이 가능하게 하기 위한 방법이다. Linked Allocation에서는 중간에 있는 블록을 보려면 순차적으로 접근해야 했다.
이러한 문제를 해결하기 위해서 Directory File의 위치 정보를 바로 저장하는 게 아니라 Index를 가리키게 해 놓는다.
Index Block은 파일의 내용을 담고 있는 건 아니고 이 파일이 어디 어디에 저장이 되어있는지 블록 하나에 인덱스가 배열로 들어있다.
그렇기 때문에 앞에서부터 네 번째 블록을 보고 싶으면 Index를 통해 직접 접근이 가능하며, 비어있는 Hole을 활용할 수 있다.
단점은 아무리 작은 파일이라고 하더라도 Index 블록이 필요하고 굉장히 큰 파일의 경우에 하나의 Index 블록으로 다 표현하지 못할 수도 있다.
이걸 해결하려면 Linked Scheme이나 Multi-Level Index를 사용해야 한다.
Linked Scheme은 Index 블록에 실제 파일의 위치를 나열하다가 파일의 크기를 커버하지 못하면 마지막에 또 다른 Index 블록을 가리키게 해 놓는다.
Multi-Level Index는 하나의 Index블록이 직접 파일의 위치를 가리키는 게 아니라,
그게 또 다른 Index를 가리키게 해서 Index가 실제 데이터 위치를 바로 가리키는 게 아니라 두 번 거쳐야 가리키는 방식이다.
✓ 장점
- External fragmentation이 발생하지 않음
- Direct access 가능
✓ 단점
- Small File의 경우 공간 낭비 (실제로 많은 File들이 Small)
- Too Large File의 경우 하나의 Block으로 Index를 저장하기에 부족
- 해결 방안 : Linked Scheme, Multi-level index
