디스크 관리 - Disk Scheduling, RAID Architecture

Disk Scheduling

• Disk access 요청들의 처리 순서를 결정
• Disk system의 성능을 향상
• 평가 기준
  • Throughput : 단위 시간당 처리량
  • Mean response time : 평균 응답 시간
  • Predictability
    • 응답 시간의 예측성
    • 요청이 무기한 연기(starvation)되지 않도록 방지

---

Data access time

1. Seek time
   • 디스크 head를 필요한 cylinder로 이동하는 시간
2. Rotational delay
   • 1) 이후에서 부터,
   • 필요한 sector가 head 위치로 도착하는 시간
3. Data transmission time
   • 2) 이후에서 부터,
   • 해당 sector를 읽어서 전송 (or 기록)하는 시간

---

• Optimizing seek time
  • FCFS (First Come First Service)
  • SSTF (Shortest Seek Time First)
  • Scan
  • C-Scan (Circular Scan)
  • Look
• Optimizing rotational delay
  • Sector queueing (SLTF, Shortest Latency Time Frist)
• SPTF (Shortest Positioning Time First)

 

First Come First Service (FCFS)

• 요청이 도착한 순서에 따라 처리
• 장점
  • Simple
  • Low scheduling overhead
  • 공평한 처리 기법 (무한 대기 방지)
• 단점
  • 최적 성능 달성에 대한 고려가 없음
• Disk access 부하가 적은 경우에 적합

 

Example

• 총 256개의 cylinder으로 구성
• Head의 시작 위치 : 100번 cylinder
• Access request queue

• 시작 위치 : 100
• Total seek distance : 690

 

Shortest Seek Time First (SSTF)

• 현재 head 위치에서 가장 가까운 요청 먼저 처리
• 장점
  • Throughput ↑ ( 이동거리↓ -> 단위시간당 처리할 수 있는 양↑)
  • 평균 응답 시간 ↓
• 단점
  • Predictability ↓
  • Starvation 현상 발생 가능
• 일괄처리 시스템에 적합

• Total seek distance : 300
• 20 위치의 요청은 오래 기다려야 하는 문제

 

Scan Scheduling

• 현재 head의 진행 방향에서, head와 가장 가까운 요청 먼저 처리
• (진행방향 기준) 마지막 cylinder 도착 후, 반대 방향으로 진행
• 장점
  • SSTF의 starvation 문제 해결
  • Throughput 및 평균 응답시간 우수
• 단점
  • 진행 방향 반대쪽 끝의 요청들의 응답시간 ↑

• Total seek distance : 300

 

C-Scan Scheduling

• SCAN과 유사
• Head가 미리 정해진 방향으로만 이동
  • 마지막 cylinder 도착 후, 시작 cylinder로 이동 후 재시작
• 장점
  • Scan대비 균등한 기회 제공
• 단점
  • 불필요한 head 이동

• Total seek distance : 490

 

Look Scheduling

• Elevator algorithm
• Scan (C-Scan)에서 현재 진행 방향에 요청이 없으면 방향 전환
  • 마지막 cylinder까지 이동하지 않음
  • Scan (C-Scan)의 실제 구현 방법
• 장점
  • Scan의 불필요한 head 이동 제거

• Total seek distance : 260

 

Shortest Latency Time First (SLTF)

• Fixed head disk 시스템에 사용
  • 각 track마다 head를 가진 disk
    • e.g., drum disk
  • Head의 이동이 없음
• Sector queuing algorithm
  • 각 sector별 queue 유지
  • Head 아래 도착한 sector의 queue에 있는 요청을 먼저 처리 함

• Moving head disk의 경우
• 같은 cylinder에 여러 개의 요청 처리를 위해 사용 가능
  • Head가 특정 cylinder에 도착하면, 고정 후
  • 해당 cylinder의 요청을 모두 처리

 

Shortest Positioning Time First (SPTF)

• Positioning time = Seek time + rotational delay
• Positioning time이 가장 작은 요청 먼저 처리
• 장점
  • Throughput ↑, 평균 응답 시간 ↓
• 단점
  • 가장 안쪽과 바깥쪽 cylinder의 요청에 대해 starvation 현상 발생 가능

Eschenbach scheduling

• Positioning time 최적화 시도
• Disk가 1회전 하는 동안 요청을 처리할 수 있도록 요청을 정렬
  • 한 cylinder내 track, sector들에 대한 다수의 요청이 있는 경우, 다음 회전에 처리 됨

---

RAID Architecture

• Redundant Array of Inexpensive Disks (RAID)
• 여러 개의 물리 disk를 하나의 논리 disk로 사용
  • OS support, RAID controller
• Disk system의 성능 향상을 위해 사용
  • Performance (access speed)
  • Reliability

 

RAID 0

• Disk striping
  • 논리전인 한 block을 일정한 크기로 나누어 각 disk에 나누어 저장
• 모든 disk에 입출력 부하 균등 분배
  • Parallel access
  • Performance 향상
• 한 Disk에서 장애 시, 데이터 손실 발생
  • Low reliability

 

 

RAID 1

• Disk mirroring
  • 동일한 데이터를 mirroring disk에 중복 저장
• 최소 2개의 disk로 구성
  • 입출력은 둘 중 어느 disk에서도 가능
• 한 disk에 장애가 생겨도 데이터 손실 X
  • High reliability
• 가용 disk 용량 = (전체 disk 용량/2 )

 

 

RAID 3

• RAID 0 + parity disk
  • Byte 단위 분할 저장
  • 모든 disk에 입출력 부하 균등 분배
    • Parallel access, Performance 향상
• 한 disk에 장애 발생 시, parity 정보를 이용하여 복구
• Write 시 parity 계산 필요
  • Overhead
  • Write가 몰릴 시, 병목현상 발생 가능

 

 

RAID 4

• RAID 3과 유사, 단 Block 단위로 분산 저장
  • 독립된 access 방법
  • Disk간 균등 분배가 안될 수도 있음
  • 한 disk에 장애 발생 시, parity 정보를 이용하여 복구
  • Write 시 parity 계산 필요
    • Overhead / Write가 몰릴 시 병목현상 발생 가능
• 병목 현상으로 성능 저하 가능
  • 한 disk에 입출력이 몰릴 때

 

 

RAID 5

• RAID 4와 유사
  • 독립된 access 방법
• Parity 정보를 각 disk들에 분산 저장
  • Parity disk의 병목현상 문제 해소
• 현재 가장 널리 사용 되는 RAID level 중 하나
  • High performance and reliability

 

 

RAID Architecture

• Other RAID levels are available
  • RAID 6, 0+1, Etc.
• Error Correction with Parity
  • https://en.wikipedia.org/wiki/Parity_bit
    • Redundant array of independent disks section 참조

 

---

강의

www.youtube.com/watch?v=xlKz4HteK0U&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=44

www.youtube.com/watch?v=omDkxSyol98&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=45