Disk Structure

Logical block

디스크 외부(컴퓨터 호스트의 외부)에서 접근하는 단위

• 디스크의 외부에서 보는 디스크의 단위 정보 저장 공간들
• 주소를 가진 1차원 배열처럼 취급
• 정보를 전송하는 최소 단위

Sector

디스크를 구성하는 최소한의 단위
디스크 내부에서 관리하는 단위, sector의 데이터 read/write는 disk controller가 직접 관리

• logical block이 물리적인 디스크에 mapping된 위치
• sector 0은 최외곽 실린더의 첫 트랙의 첫 번째 sector이다.

Disk Management

physical formatting

• 디스크를 컨트롤러가 읽고 쓸 수 있도록 섹터들로 나누는 과정
• 각 섹터는 header + 실제 data(보통 512 byte) + trailer로 구성
  - logical block외의 부가적인 것 : header, trailer (잘 저장되었는지, 어디에 저장되었는지)
• header와 trailer는 sector number, ECC(Error-Correcting Code)등의 정보가 저장되며 controller가 직접 접근 및 운영
  - ECC : 데이터의 요약 (보통 hash 함수를 생각하면 된다. )
  • 저장되어있는 ECC와 실제 데이터에서 만든 ECC를 비교 -> 같으면 bad sector가 생기지 않았군 / 다르면 문제가 생겼음
  • 축약본이므로 모든 error를 잡지 못하지만 hash 함수를 잘 사용하면 error를 그래도 많이 잡아낼 수 있다.
  • error가 발생했을 때 ECC의 규모에 따라 검출만 하거나 수정까지 할 수도 있다.

Partitioning

• 디스크를 하나 이상의 실린더 그룹으로 나누는 과정
• OS는 이것을 독립적 disk로 취급 (logical disk)

Logical formatting

• 파일 시스템을 만드는 것 (설치하는 것)
• FAT, inode, free space등의 구조 포함

Booting

전원을 켜면 메모리는 비어있음, CPU는 메모리만 접근가능 / HDD는 접근 불가능
메모리 중 전원을 꺼도 남아있는 소량의 데이터 -> ROM
전원을 켜면 CPU 제어권이 ROM으로 감

• ROM에 있는 'small bootstrap loader'의 실행
• HDD의 sector0 (boot block)을 load(메모리에 올리고)하여 실행
• sector0은 'full Bootstrap loader program'
• OS를 디스크에서 load하여 실행

Disk Scheduling

Access Time

Seek time

디스크 헤드가 read/write 요청을 한 track으로 움직이는데 걸리는 시간
가장 시간이 오래걸린다.

Rotational latency

헤드가 원하는 sector에 도달하기까지 걸리는 회전 지연 시간
seek time의 1/10 정도이다.

Transfer time

실제 데이터의 전송시간 (읽고 쓰는 시간)
굉장히 작은 시간이다.

Disk bandwidth

단위 시간당 전송된 바이트 수

Disk Scheduling

• seek time을 최소화하는 것이 목표
  디스크 접근 시간이 seek time에 좌우
• seek time = seek distanc

요청을 순서대로 처리하면 비효율적이다.
안쪽->바깥쪽->안쪽 : 느리게 왔더라도 안쪽 -> 안쪽 -> 바깥쪽이 더 효율적이다.

Disk Scheduling Algorithm

FCFS (First Come First Service)

들어온 순서대로 처리
안쪽과 바깥쪽이 번갈아 나타나면 헤드의 이동거리가 길어짐 -> 굉장히 비효율적
엘리베이터를 1층 100층 2층 78층 을 왔다갔다하면 힘들다.

SSTF (Shortest Seek Time First)

현재 헤드에서 제일 가까운 요청(큐에 있는 것 중)을 가장 먼저 처리
이동거리가 줄어드는 것은 사실이나, starvation이 생길 수 있는 문제가 있다.

SCAN

엘리베이터 스케줄링
queue에 어떤 요청에 상관없이 항상 안쪽에서 바깥쪽으로 이동하면서 가는 길목에 있는 요청들을 처리하는 방식이다.

• disk arm이 디스크의 한쪽 끝에서 다른쪽 끝으로 이동하며 가는 길목에 있는 모든 요청을 처리한다.
• 다른 한쪽 끝에 도달하면 역방향으로 이동하며 오는 길목에 있는 모든 요청을 처리하며 다시 반대쪽 끝으로 이동한다.
• 문제점 : 실린더 위치에 따라 대기 시간이 다르다.
  - 가운데 부분은 예상 대기 시간이 짧다. -> 최악의 상황 : 반바퀴
  • 가장자리는 헤드를 놓치면 반대편으로 갔다 올 때 까지 기다려야함 -> 최악의 상황 : 한바퀴

C-SCAN

• 헤드가 한쪽 끝에서 다른쪽 끝으로 이동하며 가는 길목에 있는 모든 요청을 처리
• 다른쪽 끝에 도달했으면 요청을 처리하지 않고 곧바로 출발점으로 다시 이동
• 이동거리는 다소 길어질 수 있다. (반대쪽으로는 요청 처리 안하고 이동만 하므로)
• SCAN 보다 균일한 대기시간을 제공한다.

보통 SCAN을 사용한다.

Other Algorithm

N-SCAN

• SCAN의 변형 알고리즘
• 일단 arm이 한 방향으로 움직이기 시작하면 그 시점 이후에 도착한 job은 되돌아 올때 service
• 가는 도중에 도착한 요청은 처리하지 않음 => 기다리는 시간의 분포가 균일

LOOK and C-LOOK

• SCAN이나 C-SCAN은 헤드가 디스크 끝에서 끝으로 이동
• LOOK 과 C-Look은 헤드가 진행중이다가 그 방향에 더이상 기다리는 요청이 없으면 헤드의 이동방향을 즉시반대로 이동한다.
• SCAN과 C-SCAN은 요청이 있든 없든 끝과 끝까지 이동했다. 하지만 맨 끝에 요청이 없다면 끝까지 갈 필요가 없다. 따라서 이 알고리즘은 이러한 문제점을 해결했다.

Disk Scheduling Algorithm의 결정

SCAN, C-SCAN 및 그 응용 알고리즘은 LOOK, C-LOOK등이 일반적으로 디스크 입출력이 많은 시스템에서 효율적인 것으로 알려져 있음
merge를 통해 한번에 요청하는 방법도 있음

• File 할당 방법에 따라 디스크 요청이 영향을 받음
• 디스크 스케줄링 알고리즘은 필요할 경우 다른 알고리즘으로 쉽게 교체할 수 있도록 OS와 별도의 모듈로 작성되는 것이 바람직하다.

Swap-Space Management

Disk 사용 이유

• memory의 volatile한 특성 -> file system
  - 컴퓨터를 끄면 사라지는 특성 때문
• 프로그램 실행을 위한 memory 공간 부족 -> swap sapce(swap area)
  - 메모리의 연장 공간으로 사용

Swap space

물리적인 디스크를 파티션으로 나눠 논리적인 디스크로 만들어 각각의 logical disk는 운영체제가 독립적인 디스크로 인식한다. 이러한 각각의 디스크엔 file system을 설치할 수도 있고, swap area 용도로도 사용할 수 있다. file system은 기본적으로 512 byte sector단위로 데이터를 저장하고, 연속 할당, Linked allocation, indexed allocation등의 방법으로 데이터를 넣는다. UNIX의 file system이나, FAT file system 에서는 이러한 방식을 활용해 공간 효율성을 높이고 있다.
하지만 swap area는 프로그램이 실행되는 동안에 swap area 에 머물러 있던 프로세스의 주소공간(프로그램이 끝나면 사라짐)이 쫓겨날 때도 최대한 빨리 디스크에 써져야하고, 다시 memory로 돌아갈때도 굉장히 빨리 돌아가야한다. seek time을 줄여 공간 효율성 보다 속도 효율성을 중시한다. 왜냐 ? 어차피 조금 있으면 사라져버릴 내용이기 때문이다. 그래서 보통 512KB 단위로 swap area에 데이터를 올리고 내리고 한다. 즉, file system보다 굉장히 큰 단위로 데이터를 관리한다.

• virtual memory system에서는 디스크를 memory의 연장공간으로 사용
• 파일 시스템 내부에 둘 수도 있으나 별도 partition 사용이 일반적이다.
  - 공간 효율성보다 속도 효율성이 우선
  • 일반 파일보다 훨씬 짧은 시간만 존재하고 자주 참조됨

RAID(Redundant Array of Independent Disks)

디스크를 여러개(특히, 저렴한 디스크)를 묶어서 같이 사용하는 것이다.

여러 방식이 있다.

• 여러 디스크에 데이터를 어느정도로 중복 저장할 것인가.
• 중복 저장 vs 분산 저장

사용 목적

디스크 처리 속도 향상

여러 디스크에 block 내용을 분산 저장해 병렬적으로 읽어와 빠르게 처리할 수 있는 것이다. 이러한 기법을 interleaving, striping이라한다.

신뢰성

중복 저장을 하다보면, 하나의 디스크에서 failure가 나더라도 다른 디스크에서 읽어오면 되기 때문에 신뢰성이 향상된다. 단순히 하나의 디스크 내용을 다른 디스크 내용에서 똑같이 저장하는 단순한 중복 저장도 있으나, 일부 디스크에 parity(중복 저장의 정도를 대단히 낮게 해서 오류가 생겼는지를 알아내고 복구할 수 있는 정도의 중복 저장)을 저장하여 공간의 효율성을 높일 수 있다.

예로 A의 내용을 hash 함수를 사용해 B에 저장하는 등.

출처

Operating System Concepts 10th
KOCW 강의 - [운영체제] 이화여자대학교 반효경 교수