15일차 - Disk Management and Scheduling

지난 시간에는 디스크에 file이 어떻게 저장되는지에 대해 배웠다.

오늘은 디스크를 효율적으로 관리하는 법에 대해서 알아볼 수 있었고 디스크에 들어온 요청을 효율적으로 수행하기 위한 여러 알고리즘에 대해 배울 수 있었다.

 

 

 

1. 디스크 구조

우리는 이전 시간에 file을 디스크에 저장할 때 sector단위로 저장한다고 배웠다.

sector는 디스크를 관리하는 최소단위로 디스크 내부에서 관리하는 단위를 의미한다.

디스크 외부에서는 sector를 어떻게 볼까?

sector는 logical block단위로 외부에서 관리된다.

logical block는 디스크 외부에서 보는 디스크의 정보 저장 공간들을 뜻한다.

주소를 가진 1차원 배열처럼 취급하여 외부에서 logical block으로 요청을 하면 그 요청에 대해서는 디스크 내부에서 sector를 가리키게 된다.

 

다시 sector에 대한 설명으로 돌아와보면 sector는 logical block이 디스크에 매핑된 위치라고 이해할 수 있다.

sector 0번은 최외각 실린더의 첫 트랙에 있는 첫 번째 섹터를 의미한다.

sector 0은 모든 디스크가 공통적으로 boot block으로 지정되어 사용된다.

boot block은 컴퓨터가 처음 켜졌을 때 커널을 메모리에 올리기 위해 사용되는 block이다.

 

아래의 디스크 구조 이미지를 보면 하나의 디스크는 여러 개의 platter로 이루어져 있다.

하나의 platter는 여러 개의 sector를 가진 track으로 이루어져 있다.

cylinder는 각 platter의 수직적으로 같은 위치에 있는 track들을 의미한다.

디스크 구조 [출처: https://core.ewha.ac.kr/publicview/C0101020140523151255773807?vmode=f]

 

 

2. 디스크 관리

디스크는 여러 sector로 나뉘어져 있다고 하는데 이러한 sector로 나뉘어지는 것을 언제 이루어질까?

보통은 디스크가 제조될 때 이루어지고 이를 physical formatting(low-level formatting)이라고 한다.

pyhsical formatting은 디스크를 컨트롤러가 읽고 쓸 수 있도록 섹터들로 나누는 과정이다.

각 sector는 header와 실제 data가 들어가는 공간(보통은 512바이트로 둔다.)과 trailer로 구성된다.

header와 trailer는 sector number, ECC(Error-Correcting Code) 등의 정보가 저장되며 컨드롤러가 직접 접근하고 운영한다.

여기서 ECC란 우리가 sector에 저장된 data가 손상되었는지에 대해 알려주는 정보이다.

data의 전체 복사본을 가지고 있는 것이 아니라 오류를 인식할 수 있을만한 최소의 크기로 인코딩되어 저장된 정보이다.

 

이렇게 여러 섹터로 구성된 디스크는 partitioning과정을 거친다.

partitioning은 디스크를 하나 이상의 실린더 그룹으로 나누는 과정이다.

운영체제는 이렇게 partititoning되어 나뉘어진 각각의 partition을 독립적 disk로 취급하며 logical disk라고도 부른다.

 

다음으로 디스크에 담을 파일들을 관리하기 위한 파일시스템을 만드는 logical formatting이 이루어진다.

 

 

3. 디스크 스케쥴링

우리는 CPU 스케쥴링에 대해 배울 때 CPU가 더 효율적이고 CPU사용률을 높이기 위해 스케쥴링을 사용한다고 배웠다.

디스크에서도 여러 요청이 들어왔을 때 최대한 많은 요청을 처리하고 디스크의 접근시간(Access time)을 줄여 디스크가 효율적으로 동작되도록 하기 위해 스케쥴링을 사용한다.

여기서 접근시간(Access time)은 3가지로 구성된 디스크의 성능을 나타내는 지표이다.

3가지 요소는 다음과 같다.

- seek time: 헤드를 해당 실린더로 움직이는 데 걸리는 시간

- rotational latency: 헤드가 원하는 섹터에 도달하기까지 걸리는 회전지연시간

- trasfer time: 실제 데이터의 전송 시간

 

스케쥴링의 필요성에 대해 알았으니 여러 스케쥴링에 대해 알아보자.

1) FCFS (First Come First Service)

가장 기본적인 스케쥴링으로 말 그대로 큐에 들어온 순서대로 처리를 하는 것이다.

이러한 방법은 디스크 요청이 안쪽 트랙과 바깥쪽 트랙을 번갈아 요구한다면 헤드가 움직여야할 시간이 많아지므로 효율적인 방법이 아니다.

 

2) SSTF (Shortest Seek Time First)

큐에 들어온 요청 중 현재 헤드위치에서 가장 가까운 요청을 처리하는 것이다.

예시를 본다면 이해하기 쉬울 것이다.

queue: 52 34 108 99 11 45 37

처음에는 52를 수행하고 헤더는 52에 위치해있으므로 큐에서 52와 가장 가까운 위치는 45이므로 45를 처리한다.

다음으로 37을 수행하고 34를 수행하는 순서로 되는 것이다.

이러한 방법의 문제는 starvation이다.

108은 3번째로 들어와 기다리고 있지만 계속해서 큐에 108보다 헤더의 위치와 가까운 요청이 들어온다면 계속해서 기다려야한다.

 

3) SCAN

디스크 스케쥴링에서 가장 간단하면서 획기적인 스케쥴링으로 disk arm이 디스크의 안쪽 끝에서 다른족 끝으로 이동하며 가는 길목에 있는 모든 요청을 처리하는 것이다.

다른 한쪽 끝에 도달하면 역방향으로 이동하며 오는 길목에 있는 모든 요청을 처리하며 다시 반대 쪽 끝으로 이동한다.

즉, 위와 같은 그림으로 disk arm이 움직이면서 해당 길목에 해당하는 요청이 큐에 있다면 수행하는 것이다.

이 방법의 문제점의 실린더의 위치에 따라 대기시간이 다르다는 것이다.

가장자리에 위치해 있는 실린더는 최악의 경우 한바퀴를 기다려야하고 가운데 위치에 있는 실린더는 최악의 경우 반바퀴만 기다리면 되어 실린더의 위치에 따라 대기시간의 편차가 생긴다.

 

4) C-SCAN (Circular SCAN)

SCAN의 문제점을 보완하기 위해 나온 방법으로 헤드가 한쪽 끝에서 다른 쪽 끝으로 이동하며 가는 길목에 있는 모든 요청을 처리한다.

다른 쪽 끝에 도달했으면 요청을 처리하지 않고 곧바로 출발점으로 다시 이동하게 된다.

위의 그림처럼 한쪽 끝에서 다른 쪽 끝까지 이동하고 역방향으로 이동하는 것이 아니라 다시 시작한 위치로 돌아오는 것이다.

이렇한 방법을 사용하면 모든 실린더에서 균일한 대기시간을 갖게 된다.

 

5) N-SCAN

SCAN의 변형 알고리즘으로 일단 arm이 한 방향으로 움직이기 시작하면 그 시점 이후에 도착한 job은 지나가는 길목에 있더라고 처리하지 않고 되돌아올 때 처리하는 것이다.

예시를 보면서 이해해 보자.

disk arm은 0~100(sector가 0번부터 100번까지 있다고 가정)번으로 이동을 시작하고 큐에는 10 20 30 40이 있다고 해보자.

arm이 이동을 시작하고나서 50 요청이 들어왔다면 기존은 SCAN은 처리하지만 N-SCAN은 처리하지 않고 다음에 되돌아 올 때 처리한다는 것이다.

 

6) Look and C-Look

Look과 C-Look 방식은 SCAN과 C-SCAN의 방식을 변형한 것이다.

SCAN과 C-SCAN은 무조건 끝에 요청이 없더라고 끝까지 간 후에 되돌아 온다.

즉, 디스크의 sector가 0~100까지 있고 큐에는 1 10 20 30 40이 존재하여 40 이후의 번호(40~100)에 대한 요청이 없더라도 0번부터 100번까지 disk arm이 움직인다는 것이다.

하지만, Look과 C-Look은 가는 방향에서 더 이상 요청이 없다면 그 지점에서 바로 방향을 바꾸는 것이다.

즉, 큐에 1 10 20 30 40이 있다면 굳이 100까지 가지않고 40에서 방향을 바꾼다는 것이다.