✅ Disk 공간 할당

프로그램 파일, 데이터 파일, 디렉토리 파일 모두 파일이며, 파일은 저장장치에 블록 단위 로 저장됨. 이를 최대한 효율적으로 배치해야 파일 입출력의 속도를 높일 수 있음.

• 연속 할당: 임의의 한 파일을 위해 디스크 내에 선형적으로 연속된 블럭을 할당하는 방법
• 불연속 할당: 임의의 한 파일을 위해 디스크 내에 흩어져서 저장된 블럭을 연결해서 할당, 블럭이 어디에 저장되어 있어도 액세스 가능

✅ Disk Speed

• Random Access Time
  - Rotational latency (회전지연시간) : 특정 트랙의 특정 섹터를 찾아가기 위해 돌아가는데 걸리는 시간, 하드웨어 성능에 따라 다름
  - Seek Time (탐색시간) : 원하는 실린더로 가기 위해 걸리는 시간, 스케줄링 성능에 따라 다름
• Transmission time (전송시간) : 드라이브와 컴퓨터 간의 데이터 흐름 전송 속도에 따라 다름, 하드웨어 성능에 따라 다름

따라서 디스크에서 읽기 혹은 쓰기의 작업을 하기 위해서는 3가지 시간 지연 요소를 고려해야 함 =Rotational latency + Seek time + Transmission time

Disk Scheduling

✔️ 목적 : seek time을 최소화하기 위해서

일반적으로 한 파일의 블록들에 해당되는 섹터는 순차적으로 저장되지 ❌
동시에 수행 중인 프로세스들에 의해 발생되는 요청이 수시로 디스크의 입출력 요청 큐에 도착하기 때문에 순서화할 필요가 있음

요청을 순서화하는 데 가장 중요한 것은 처리율의 극대화
= 평균 반응시간과 반응 시간의 분산을 줄여야 함

• 평균 반응 시간 🔽 : 각 요청이 디스크 구동기에 전달되어진 순간 ~ 결과가 나올 때까지 걸리는 시간의 평균값을 최소화
• 반응 시간의 분산 🔽 : 어느 곳에 위치한 섹터이든 각 섹터에 대한 반응시간에 편차를 최소화하여 반응의 예측성을 높이도록 하는 것

1. FCFS

✔️ 가장 간단한 스케줄링 방법
✔️ 먼저 도착한 요청을 우선적으로 서비스하게 하는 기법으로 실질적으로 순서를 재배열하지 않아서 NOOP(No operation) 스케줄러라고도 함

• 특징 : 대기 큐를 재배열하지않고, 탐색 패턴을 최적화하려는 시도가 없다. 더 높은 우선순위를 가진 요청이 뒤늦게 도착해도 요청의 순서가 유지된다.
• 장점 : 구현하기 쉽다. 근본적인 형평성 유지 가능(먼저 오면 먼저 ㄱ)
• 단점 : 요청이 적은 경우에는 괜찮지만 요청이 많아지면 평균 응답 시간이 길어짐. 일반적으로 효율이 ❌

2. SSTF

✔️ 트랙을 찾아가는 거리가 짧은 요청부터 먼저 서비스하는 기법
✔️ 처리량이 주요 목표인 일괄 처리 시스템에 유용하고 응답시간이 중요한 대화형 시스템에서는 부적합함

• 특징 : 현재 헤드위치에서 최소 탐색 시간을 요하는 요청을 골라 먼저 처리한다.
• 장점 : FCFS보다 처리량이 많고(head movement가 작아지기 때문에) 평균 응답시간이 짧다.
• 단점 : 안쪽과 바깥쪽 트랙이 가운데 트랙에 비해 훨씬 서비스를 덜 받아 응답시간에 편차가 생길 수 있다. + starvation 까지 발생 가능

3. SCAN

+) LOCK 스케줄링

✔️ 두 방법 모두 기본적인 건 SSTF와 같음 하지만 헤드 진행 방향상의 가장 짧은 거리에 있는 요청을 먼저 서비스하는 기법
✔️ SCAN 방법은 엘리베이터 알고리즘이라고도 불린다.
헤드가 53번 트랙에서 0번 트랙방향을 향하고 있었다면 더 가까운 65번 트랙이 있어도 방향을 유지하도록 하는 37번으로 이동한다. 그렇게 더 이상의 요청이 없어도 이동방향의 끝인 0번 트랙까지 간다. 그 후 반대 방향에 대해 서비스를 한다.

🔒 여기서 LOCK과 SCAN의 차이점
LOCK의 경우에는 움직이는 방향으로 더 이상 요청이 없으면 끝까지 가지 않고 반대 방향으로 서비스함

• 특징 : 두 방법 모두 처리량과 평균 응답시간을 개선하면서도 아울러 SSTF에서 발생하는 반응시간의 편차를 많이 개선했음
  그러나 응답시간 편차는 여전히 존재한다. (헤드 진행 도중 도착한 요청도 함께 서비스를 받게 되므로, 밖에 위치하는 트랙은 가운데 트랙보다 더 적은 서비스를 받을 수도 있다. 각 트랙의 요청 분포가 균일하다고 해도, 헤드가 한 쪽 끝에 이르러 방향을 바꾸는 시점을 생각해보면 요청 밀도가 높은 쪽은 반대편이 되며, 현재 헤드 근처 부분은 밀도가 낮아진다. 따라서 요청 밀도가 높은 양 끝의 요청은 상당히 오랜 시간을 대기할 수밖에 없게 된다. 반면 중간 지점의 트랙은 오가며 처리되니 처리율이 높다.)
  그럼에도 SSTF 방법에서처럼 높은 편차를 갖고 움직이는 경우는 없어지기 때문에 실제로 구현되는 대부분의 디스크 스케줄링의 기본 전략이 되었다.

• 장점: bounded waiting (starvation ❌)

• 단점: 처음과 마지막의 실린더가 짧은 시간 내에 두번 제공된다는 점

4. C-SCAN

✔️ SCAN 스케줄링 기법을 살짝 수정한 것

• SCAN : Elevator algorithm
• C-SCAN : Circular Elevator Algorithm

🔒 여기서 SCAN과 C- SCAN의 차이점
SCAN은 한 쪽 끝까지 가서 방향을 바꾸지만 C-SCAN은 한번 가고 나면 다시 한 쪽 끝으로 점프해서 다시 진행한다는 것이 차이점
SCAN C-SCAN
     ↘️           ↘️
     ↙️          ↘️
     ↘️          ↘️
     ↙️          ↘️

✔️ C-SCAN 방식은 양끝과 가운데 부분의 요청밀도에 편차를 줄일 수 있어, 대기시간을 좀 더 균등하게 제공할 수 있다. 복귀시간이 필요하지만 처리시간이 훨씬 공평해진다.

Rotational latency 최적화

초창기에는 seek time의 최적화가 훨씬 중요했음.
Rotational latency보다 arm을 구동하는 시간이 훨씬 컸기에 트랙을 찾아가는 시간인 seek time의 최적화를 주로 다뤘지만
최근에는 Rotational latency 최적화도 중요해졌음.
특히, 한 트랙 내 여러 곳에 분산된 섹터중 일부만 요구하는 요청이 많을 경우 회전지연시간을 최적화하여 성능을 개선해야한다.

SLTF 스케줄링

(Shortest-Latency-Time-First)
회전하는 방향 상 가까운 순서로 서비스해준다. 트랙상 서비스할 섹터들이 도열되어 있다는 의미에서 섹터큐잉(Sector Queueing)이라고도 불린다. 이론적으로 회전지연시간을 최소화한다는 측면에서 최적전략에 근접하고, 구현하기 쉽다.

SPTF 스케줄링

(Shortest-Positioning-Time-First)
탐색시간과 회전지연시간의 합인 '위치 결정시간(Positioning time)'이 가장 짧은 요청을 다음 서비스 대상으로 선택한다. 처리량이 많고 평균 반응시간도 짧지만, SSTF와 같이 가장 안쪽과 바깥쪽 실린더가 기아상태에 빠질 위험이 있다.

SATF 스케줄링

(Shortest-Access-Time-First)
위치결정시간과 전송시간의 합인 '접근 시간(Access time)'이 가장 짧은 요청을 다음 서비스 대상으로 선택한다. 3가지 시간지연요소를 모두 고려한다는 점과 SPTF보다 처리량이 많다는 장점이 있지만, 작은 크기의 요청이 연속으로 요청될 때는 큰 크기의 요청이 기아 상태에 빠질 위험이 있다.