close
프로필 배경
프로필 로고

석사한 백수의 공부 블로그

Study/운영체제 · 2023. 12. 10. fullscreen 넓게보기

운영체제 12. 입출력 시스템 & 디스크 관리 (2) - Disk Scheduling

728x90
반응형

출처 : https://www.youtube.com/watch?v=xlKz4HteK0U&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=44

 

 

 

Disk Scheduling

 

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

 

 

Data access time = seek time + rotational delay + data transmission time

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

Disk scheduling에서 성능을 높이려면 seek time과 rotational delay의 순서를 잘 결정을 해줘야한다.

 

 

Disk scheduling에서 고려해야할 것은 seek time과 rotational delay이다.

 

  • Optimizing seek time : seek time을 최적화하는 scheduling 기법
    • FCFS (First Come First Service)
    • SSTF (Shortest Seek Time First)
    • Scan
    • C-Scan (Circular Scan)
    • Look
  • Optimizing rotational delay : rotational delay를 최적화하는 scheduling 기법
    • Sector queuing (SLTF, Shortest Latency Time First)
  • SPTF (Shortest Positioning Time First)

 

 

First Come First Service (FCFS)

 

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

 

 

  • Example
    • 총 256개의 cylinder로 구성
    • Head의 시작 위치 : 100번 cylinder
    • Access request queue(들어오는 순서) : 160, 200, 90, 170, 20, 190, 120, 130 (head 번호들)

 

 

  1. 시작 위치는 100번 실린더에서 출발한다.
  2. 맨 처음 들어온 head 번호는 160번이므로 head가 160번 실린더로 이동한다. (이동거리는 60)
  3. 그 다음 200번 실린더로 이동한다. (이동거리 40)
  4. 90번 실린더로 이동한다. (이동거리 110)
  5. 170번 실린더로 이동한다. (이동거리 80)
  6. 20번 실린더로 이동한다. (이동거리 150)
  7. 190번 실린더로 이동한다. (이동거리 170)
  8. 120번 실린더로 이동한다. (이동거리 70)
  9. 130번 실린더로 이동한다. (이동거리 10)
  • Total seek distance = 60 + 40 + 110 + 80 + 150 + 170 + 70 + 10 = 690

 

 

Shortest Seek Time First (SSTF)

 

  • 현재 head 위치에서 가장 가까운 요청 먼저 처리 -> seek distance 감소
  • 장점
    • Throughput이 높음
    • Mean response time 낮음
  • 단점
    • Predictability 낮음. 거리가 먼 요청은 언제 처리될지 알 수 없음
    • 현재 head 근처에 요청이 계속 들어오면 Starvation 현상 발생 가능
  • 일괄처리 시스템에 적합함

 

 

  1. 시작 위치는 100번 실린더에서 출발한다.
  2. 현재 위치(100번)에서 가장 가까운 90번 실린더로 이동한다. (이동거리 10)
  3. 현재 위치(90번)에서 가장 가까운 120번 실린더로 이동한다. (이동거리 30)
  4. 현재 위치(120번)에서 가장 가까운 130번 실린더로 이동한다. (이동거리 10)
  5. 현재 위치(130번)에서 가장 가까운 160번 실린더로 이동한다. (이동거리 30)
  6. 현재 위치(160번)에서 가장 가까운 170번 실린더로 이동한다. (이동거리 10)
  7. 현재 위치(170번)에서 가장 가까운 190번 실린더로 이동한다. (이동거리 20)
  8. 현재 위치(190번)에서 가장 가까운 200번 실린더로 이동한다. (이동거리 10)
  9. 남은 20번 실린더로 이동한다. (이동거리 180)
  • Total seek distance = 10 + 30 + 10 + 30 + 10 + 20 + 10 + 180 = 300
  • FCFS 보다 적은 total seek distance를 가짐
  • 20번 실린더의 경우처럼 predictability가 낮고, starvation 문제가 발생할 수 있음

 

 

Scan Scheduling

 

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

 

 

  1. 시작 위치는 100번 실린더에서 출발한다. 초기 진행 방향은 낮은 쪽으로 이동한다고 해보자.
  2. 현재 위치(100번)에서 가장 가까운 90번 실린더로 이동한다. (이동거리 10)
  3. 현재 위치(90번)에서 가장 가까운 20번 실린더로 이동한다. (이동거리 70)
  4. 현재 위치(20번)에서 끝까지 가야하므로 0번 실린더로 이동한다. (이동거리 20)
  5. 진행 방향을 바꿔서 현재 위치(0번)에서 가장 가까운 120번 실린더로 이동한다. (이동거리 120)
  6. 현재 위치(120번)에서 가장 가까운 130번 실린더로 이동한다. (이동거리 10)
  7. 현재 위치(130번)에서 가장 가까운 160번 실린더로 이동한다. (이동거리 30)
  8. 현재 위치(160번)에서 가장 가까운 170번 실린더로 이동한다. (이동거리 10)
  9. 현재 위치(170번)에서 가장 가까운 190번 실린더로 이동한다. (이동거리 20)
  10. 현재 위치(190번)에서 가장 가까운 200번 실린더로 이동한다. (이동거리 10)
  • Total seek distance = 10 + 70 + 20 + 120 + 10 + 30 + 10 + 20 + 10 = 300
  • SSTF 스케줄링과 마찬가지로 낮은 total seek distance를 가짐
  • starvation 문제 해결

 

 

C-Scan Scheduling

 

  • Scan과 유사
  • 하지만 Scan 스케줄링의 경우 진행 방향 반대쪽 끝의 요청들의 응답시간 높다는 문제점이 존재(ex. 200번 실린더)
  • Head가 미리 정해진 방향으로만 이동
    • 마지막 cylinder 도착 후, 시작 cylinder로 이동 후 재시작
  • 장점
    • Scan 대비 균등한 기회 제공

 

 

  1. 시작 위치는 100번 실린더에서 출발한다. 진행 방향은 낮은 쪽으로 이동한다고 해보자.
  2. 현재 위치(100번)에서 가장 가까운 90번 실린더로 이동한다. (이동거리 10)
  3. 현재 위치(90번)에서 가장 가까운 20번 실린더로 이동한다. (이동거리 70)
  4. 현재 위치(20번)에서 끝까지 가야하므로 0번 실린더로 이동한다. (이동거리 20)
  5. 현지 위치(0번)에서 반대편 끝 실린더 번호(255번)로 이동한다. (이동거리 255) 진행 방향은 이전과 동일하다.
  6. 현재 위치(255번)에서 가장 가까운 200번 실린더로 이동한다. (이동거리 55)
  7. 현재 위치(200번)에서 가장 가까운 190번 실린더로 이동한다. (이동거리 10)
  8. 현재 위치(190번)에서 가장 가까운 170번 실린더로 이동한다. (이동거리 20)
  9. 현재 위치(170번)에서 가장 가까운 160번 실린더로 이동한다. (이동거리 10)
  10. 현재 위치(160번)에서 가장 가까운 130번 실린더로 이동한다. (이동거리 30)
  11. 현재 위치(130번)에서 가장 가까운 120번 실린더로 이동한다. (이동거리 10)
  • Total seek distance = 10 + 70 + 20 + 255 + 55 + 10 + 20 + 10 + 30 + 10 = 490
  • Scan 스케줄링 대비 균등한 기회 제공
  • 실린더의 끝에 도달하면 반대쪽 끝으로 이동해야하는 비효율성이 존재

 

 

Look Scheduling

 

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

 

 

  1. 시작 위치는 100번 실린더에서 출발한다. 진행 방향은 낮은 쪽으로 이동한다고 해보자.
  2. 현재 위치(100번)에서 가장 가까운 90번 실린더로 이동한다. (이동거리 10)
  3. 현재 위치(90번)에서 가장 가까운 20번 실린더로 이동한다. (이동거리 70)
  4. 방향을 전환한 후, 현재 위치(20번)에서 가장 가까운 120번 실린더로 이동한다. (이동거리 100)
  5. 현재 위치(120번)에서 가장 가까운 130번 실린더로 이동한다. (이동거리 10)
  6. 현재 위치(130번)에서 가장 가까운 160번 실린더로 이동한다. (이동거리 30)
  7. 현재 위치(160번)에서 가장 가까운 170번 실린더로 이동한다. (이동거리 10)
  8. 현재 위치(170번)에서 가장 가까운 190번 실린더로 이동한다. (이동거리 20)
  9. 현재 위치(190번)에서 가장 가까운 200번 실린더로 이동한다. (이동거리 10)
  • Total seek distance = 10 + 70 + 100 + 10 + 30 + 10 + 20 + 10 = 260
  • 실린더 끝까지 이동하지 않기 때문에 낮은 total seek distance를 가짐

 

 

Optimizing Rotational Delay - Shortest Latency Time First (SLTF)

 

  • disk가 돌아가는 회전 수를 최대한 줄이면서 서비스를 제공하는 스케줄링 기법
  • Fixed head disk 시스템(head가 고정된 시스템)에 사용
    • 각 track 마다 head를 가진 disk
      • drum disk 등
    • Head의 이동이 없음
  • Sector queuing algorithm
    • 각 sector 별 queue 유지
    • Head 아래 도착한 sector의 queue에 있는 요청을 먼저 처리 함

 

 

  • 각 sector 마다 queue 존재 (Qn : Sn(n번 Sector)에 대한 Queue)
  • Queue에 몇 번째 track을 읽어야 하는지에 대한 요청을 넣음
  • 고정된 head가 특정 sector에 도착하면 해당 sector의 queue에 들어있는 요청을 모두 수행
  • 해당 queue에 있던 요청을 모두 수행하면 디스크 회전

 

 

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

 

 

Shortest Positioning Time First (SPTF)

 

  • Positioning time = Seek time + rotational delay
  • Positioning time이 가장 작은 요청 먼저 처리
  • 장점
    • Throughput 높음
    • mean response time 낮음
  • 단점
    • 가장 안쪽과 바깥쪽 cylinder의 요청에 대해 starvation 현상 발생 가능

 

 

  • Eschenbach scheduling
    • Positioning time 최적화 시도
    • Disk가 1회전하는 동안 요청을 처리할 수 있도록 요청을 정렬
      • 한 cylinder 내 track, sector들에 대한 다수의 요청이 있는 경우, 다음 회전에 처리됨 -> 요청이 특정 구역 내에 몰려있으면 낮은 성능을 보임

 

 

 

 

728x90
반응형

'Study > 운영체제' 카테고리의 다른 글

운영체제 12. 입출력 시스템 & 디스크 관리 (3) - RAID Architecture  (0) 2023.12.10
운영체제 12. 입출력 시스템 & 디스크 관리 (1) - I/O System  (1) 2023.12.10
운영체제 11. 파일 시스템 (5) - File System Implementation  (1) 2023.12.09
운영체제 11. 파일 시스템 (4) - File Protection  (0) 2023.12.09
운영체제 11. 파일 시스템 (3) - Directory Structure  (0) 2023.12.08
Study/운영체제 관련 글
더 보기

티스토리툴바