Chapter5 디스크 스케줄링 200512079 조은성.

Presentation on theme: "Chapter5 디스크 스케줄링 200512079 조은성."— Presentation transcript:

1 Chapter5 디스크 스케줄링 조은성

2 개요 디스크 스케줄링(disk scheduling)은 운영체제가 프로세스들이 디스크를 읽거나 쓰려는 요청을 받 았을 때, 우선순위를 정해주고 이를 관리하는 것을 말한다.

3 목적 입출력 스케줄러에는 입출력 스케줄러의 목표에 따라 수많은 목적이 있다. 일반적인 목표로는 다음 과 같다.
입출력 스케줄러에는 입출력 스케줄러의 목표에 따라 수많은 목적이 있다. 일반적인 목표로는 다음 과 같다. 하드 디스크 검색으로 낭비되는 시간을 최소화한다. 특정한 프로세스의 입출력 요청의 우선 순위를 정한다. 디스크 대역을 실행 중인 각 프로세스에 할당한다. 정해진 기한까지 요청을 보증한다.

4 스케줄링의 종류 FCFS (First-Come-First-Served) 스케줄링 가장 간단한 스케줄링
디스크 입출력 요청 대기 큐에 들어온 순서대로 서비스를 받음 장점 프로그래밍이 쉬움 대기 큐에 들어온 순서대로 서비스하기 때문에 더 높은 우선 순위의 요청이 입력되어도 순서가 바뀌지 않아 공평성이 보 장 단점 헤드 이동거리가 상당히 길어질 수 있음 디스크 오버헤드(서비스 요구 횟수)가 커지면 응답시간이 길 어짐

5 스케줄링의 종류 SSTF(Shortest Seek Time First) 스케줄링
탐색 시간이 가장 짧은 트랙으로 헤드를 이동시키는 방법 장점 FCFS보다 처리량이 많고, 평균 탐색시간이 짧음 단점 현재 서비스한 트랙에서 가장 가까운 트랙에 대한 서비스 요 청이 계속 발생하는 경우, 먼 거리의 트랙에 대한 서비스는 무한정 기다려야 하는 기아 상태가 발생할 수 있음

6 스케줄링의 종류 SCAN 스케줄링(엘리베이터 알고리즘) N 단계 SCAN 스케줄링
SSTF가 갖는 탐색시간의 편차를 해소하기 위한 방법 디스크 헤드가 맨 바깥쪽 트랙에서 가장 안쪽 트랙 쪽으로 이동 하면서 해당되는 트랙에 대한 요구를 차례대로 서비스해 주는 방식 디스크 오버헤드가 적어야 가장 좋은 효율을 가짐 대부분의 디스크 스케줄링에서 기본 전략으로 이용 밀도가 높 은 쪽의 요청은 상당히 오랜 시간 대기하게 됨 N 단계 SCAN 스케줄링 어떤 방향의 진행이 시작될 당시에 대기 중이던 요청들만 서비 스하고,진행 도중 도착한 요청들은 한데 모아서 다음 반대 방 향 진행 때 최적으로 서비스할 수 있도록 배열되는 디스크 스케 줄링 기법이다.

7 스케줄링의 종류 C-SCAN 스케줄링과 예션바흐 기법 에센바흐 기법(Eschenbach scheme) :
C-SAN(Circular SCAN) 헤드가 항상 바깥쪽 실린더에서 안쪽 실린더로 이동하면서 가장 짧은 탐색 시간을 갖는 요청을 서비스하는 방법 진행도중 도착한 요청은 다음 수행시 서비스 응답시간의 편차가 매우 적음 회전 시간의 최적화가 가능하며 부하 (Overhead)가 많이 걸리는 경우 효과적 에센바흐 기법(Eschenbach scheme) : 탐색 시간 최적화뿐만 아니라 회전 지연 시간도 최적화하 고자 하는 최초의 기법이다.(항공 예약시스템을 위해 개 발됨)

8 탐색(seek)시간과 회전시간 최적화 FCFS:대기 큐를 재배열하지 않고 들어 온 순서대로 처리한 다.
특징:오버헤드가 크다. SSTF:현재 헤드의 위치에서 가장 가까운 요청을 서비스한 다. 특징:응답 시간의 편차가 크므로 대화형 시스템에 부적합 하다.(탐 색시간 최적화) SCAN:헤드가 디스크표면을 앞으로 왔다 갔다 하면서 지나 는 길에 있는 요청을 서비스 한다. 헤드는 현재의 진행 방향 을 더 이상의 요청이 없을 때에만 방향을 바꾼다. 특징:SSTF가갖는 응답시간에 있어서의 차별 대우와 큰편차를 해 결한다.

9 탐색(seek)시간과 회전시간 최적화 N-Step:헤드는 SCAN에서와 같이 양 방향으로 움직이나 진 행중에 도착하는 모든 요청들은 한데 모아 처리한다. 특징:SCAN의 지연과 무한연기를 해결한다. 응답시간 편차가 적다. C-SCAN:헤드는 트랙의 안쪽으로, 한 방향으로만 움직인다. 안쪽에 더 이상 요청이 없으면 가장 바깥쪽에 있는 요청을 서비스하고 다시 안쪽으로 진행한다. 특징:SCAN의 가장 안쪽과 바깥쪽의 실린더에서 차별 대우를 해결 한다.(SCAN의 대기시간의 균등화) 예션바흐기법:헤드는 C-SAN처럼 움직이나 모든 실린더는 그 실린더에 요청이 있든지 없든지 전체 트랙이 한 바퀴 회 전할 동안의 서비스를 받는다. 특징:회전 시간 최적화를 처음으로 시도한 것

10 탐색(seek)시간과 회전시간 최적화 SLTF:일단 디스크 헤드가 특정 실린더에 도착 하면 도착 한 순서에 관계없이 대기 큐에 지정된 순서대로 서비스를 받는다. 특징:회전 시간 최적화 섹터큐잉:드럼과 같은 고정 헤드 장치를 스케줄링 할 때 사용하는 것으로써 탐색 시간 없이 없고 회전 지연 시간 만 존재 한다. 특징:고정 헤드장치 알고리즘