파일구조 요약 (3~4장)

2017/10/30 - 파일구조 요약 (1~2장)
2017/10/30 - 파일구조 요약 (3~4장) (이 글)
2017/10/30 - 파일구조 요약 (5~6장)

3장. Secondary Storage

• Magnetic Tape과 Disk, CD-ROM에 대하여 이야기한다.
• Disk의 구성을 소개한다.
• Buffer를 사용하여 효율을 높이는 기술을 소개한다.

Disk

• Sector : 디스크에 접근하기 위한 가장 작은 단위
• Track
• Cylinder (vertical collection of tracks)

# of sectors per track. * bytes per sector. 와 같은 식으로 주어진 디스크 용량에서 몇 개의 실린더 혹은 섹터가 있는 지 계산하는 문제가 나올 가능성이 높다.

Interleaving

 어떤 계수값(interleaving factor)를 가지고 메모리를 병렬화하여 접근한다. 접근하는 대역폭을 증가시켜서 메모리 접근 속도를 가속화 시킬 수 있다.

Cluster

(섹터로 트랙을 구성했다면) 연속된 섹터로 구성되어 있다. 파일 할당의 가장 작은 기본 단위이다.

• 하나의 파일은 하나 이상의 cluster를 가질 수 있다.
• 한 cluster는 “특정 개수의” 연속된 섹터들이다.
• Cluster마다 연속된 섹터들의 정보를 관리하는 Mapping Table이 있다.
• 한 cluster 내에서는 추가적인 seek이 필요가 없다.
• FAT(File Allocation Table) : 파일에 속한 모든 cluster들의 실제 위치를 가지고 있다.

(inode 구조체에 FAT를 들고 있다.)

Extents

(가변길이의) 연속된 Cluster들이다. 

Fragmentation

Sector나 cluster 내에서 생기는 빈 공간들은 데이터를 저장하지 못하고 공간이 낭비될 것이다. 이를 Internal fragmentation이라 한다.

Block으로 Track을 구성하는 경우

사용자가 임의로 block의 크기를 설정한다. 보통 고정된 크기를 많이 사용한다.

• Sector간의 빈 공간이 없기 때문에, Internal fragmentation이 발생할 일이 없다.
• Block에 sub-block을 붙여서 부가적인 정보들을 함께 저장할 수 있다.
• Blocking factor: 한 block에 들어있을 수 있는 record의 개수

Problem) Block단위로 저장한 disk에서

• 20,000 bytes/track 을 담을 수 있다.
• Subblock, interblock gap은 300 bytes/block 정도이다.

하나의 파일이 100 bytes인 record들을 저장하고 싶을 때, blocking factor가 10 또는 60 인 경우에 몇 개의 record들을 저장할 수 있는가?

Solve)

Blocking factor가 10인 경우,

1 block의 크기 = 10개 * (100 bytes 짜리 record) + 300

20,000 bytes에는 20,000 / (10*100 + 300) = 15 blocks = 150 records 가 들어갈 수 있다.

Blocking factor가 60인 경우,

1 block의 크기 = 60개 * (100 bytes 짜리 record) + 300

20,000 bytes / (60*100 + 300) = 3 block = 180 records 가 들어갈 수 있다.

Disk Access Time

= Seek time + Rotational delay + Transfer time

= 디스크에서 위치(실린더)를 찾는 시간 + 섹터를 찾아 읽고/쓰는 시간 + 돌아오는 시간

Disk as Bottleneck

원하는 데이터를 읽고 싶으나, 공간이 크지 않아 읽는데 속도가 오래 걸려 기다리게 되는 상황.

• 해결1. Multiprogramming
  Disk I/O를 사용하지 않는 프로세스는 먼저 실행시킨다.
• 해결2. Striping - Parallel I/Os
  RAID 디스크 여러개를 구성하여 사용한다.
• 해결3. RAM이나 Cache를 써서 Disk 접근을 피한다.

Parity bit

데이터의 전달 과정 혹은 저장 과정에서 오류가 생겼는 지를 검사하기 위해서 추가된 비트

Disk vs. Tape

• Random Access vs. Sequential Access
• Expensive seek in sequential processing vs. No seek

CD-ROM; Compact disc Read-Only Memory

• 적당한 저장공간
• 준수한 속도를 갖지만, seek 비용이 너무 크다.

CLV & CAV

  

< CLV(좌), CAV(우) >

★ Constant Linear Velocity (CLV)

나선형으로 쓰니까 Disk를 가능한 꽉꽉 채워서 기록할 수 있다. 바깥을 돌 때 더 천천히 돌아야 모든 지름에서 같은 용량의 크기를 사용할 수 있다. 

CD에서 이 방식을 주로 사용한다.

★ Constant Angular Velocity (CAV)

일정한 속도로 회전한다. 위치를 빨리 찾을 수 있다. (데이터 접근 속도가 빠르다) 모든 지름에서 같은 용량의 크기를 사용해야 하다보니 바깥쪽 트랙일수록 데이터가 덜 조밀하게 저장된다.

HHD, FDD 등에서 이 방식을 주로 사용한다.

• Constant Linear Velocity
• Constant Angular Velocity

Problem) CAV와 CLV를 비교하고 그 장단점을 서술하시오.

Buffer Management

 Bottleneck을 해결하기 위한 하나의 방법으로 Buffer를 사용할 수 있다. Buffer란 하나의 I/O 실행 동안 대기중인 I/O를 미리 Buffer에 저장하여 대기시간을 줄이고 효율을 높일 수 있다.

 이를 사용하는 전략으로는 버퍼를 여러개 두는 Double buffering, LRU(List of Recently used)를 이용하여 공간을 마련하는 Buffer pooling 등이 있다.

4장. Fundamental FS Concepts

• 파일에 Record를 어떻게 저장하고 읽어들일 것인가를 이야기한다.
• 고정길이와 가변길이방식을 통한 record의 저장
• Buffer와 Record 사이에서 pack/unpack을 소개한다.
• C++의 순수가상클래스를 상속받아 추상화된 함수를 사용한다.
• 연산자 오버로딩을 사용한다.

Field를 구분하는 4가지 방법

• 고정된 길이
• 각 field의 시작마다 길이를 적어둔다.
• 구분자를 둔다.
• <key=value> 표현을 사용한다.

Problem) Person의 pack과 DelimTextBuffer의 pack을 비교하시오.

• Person은 각 항목을 Buffer에게 pack을 맡긴다. buffer.pack(this.name) 과 같은 방식.

Pack/Unpack

파일을 효율적으로 읽고 쓰기 위해 Buffer를 다음과 같이 인터페이스로 둔다.

Buffer의 성질에 맞게 메모리로부터 Pack한 후 파일에 Write한다. 반대로 Read 후 Unpack한다.