5장 디스크 스케줄링 200812120 이나현.

Presentation on theme: "5장 디스크 스케줄링 200812120 이나현."— Presentation transcript:

1 5장 디스크 스케줄링 이나현

2 자기 디스크의 소개 자기 디스크의 개요 얇고 둥근 금속 원판에 자성물질로 코팅되어 만들어진 것으로 그 평판 위에 헤드가 전도성 코일을 통해 표면을 자화시켜 데이터를 저장하는 원리이다. 자기 디스크의 구조

3 자기 디스크에서의 물리적 주소 자기 디스크 시스템에서 데이터의 전송 단위는 물리적으로 섹터 단위이다.
시스템에서 하나의 섹터를 정확히 지정하기 위해서 실린더 번호, 표면 번호, 섹터 번호가 필요하다.

4 자기 디스크의 액세스 시간 디스크 액세스 시간 = 탐색시간+회전지연시간+데이터전송시 ① 탐색시간(Seek Time)
⇒ 헤드를 해당 트랙으로 이동하는데 걸리는 시간 ② 회전 지연 시간(Latency Time)=서어치 시간(Search Time) ⇒ 해당 섹터가 헤드 아래로 회전 되어 올 때까지의 시간이다. ③ 데이터 전송 시간(Data Transfer Time) ⇒ 헤드를 통해 디스크의 특정 지역에 데이터를 저장하거나 읽는데 걸리는 시간이다.(디스크와 주기억장치 사이에 전송하는 시간) ♣ 위의 3가지 중 가장 큰 비중을 차지하는 것은 탐색시간이다. 속도는 10~30ms이다.

5 플로피 디스크의 소개 ■ 종류 ① 3.5인치(1inch=2.54cm) ② 5.25인치 ③ 8인치 ■ 디스크의 형태
5장 ■ 종류 ① 3.5인치(1inch=2.54cm) ② 5.25인치 ③ 8인치 ■ 디스크의 형태 ① 단면(Single) : 한쪽 면만 기록 ② 양면(Double) : 양면에 기록 ■ 밀도 단위 ① 2DD : 양면 배밀도 ⇒ Double side Double density ② 2HD : 양면 고밀도 ⇒ Double side High density 5.25인치 3.5인치 디스켓 레이블 (상표) 용량 섹터 (sector) 트랙 (track) 320KB 8 40 MD2D/DS,DD 360KB 9 MD2DD/DS,2DD 720KB 80 MD2HD/DS,HD 1.2MB 15 1.44MB 18

6 RAID RAID(Redundant Array of Inexpensive Disk; 복수 배열 독립 디스크) 정의
데이터를 분할해서 복수의 자기 디스크 장치에 대해 병렬로 데이터 를 읽는 장치 또는 읽는 방식이다. 즉, 여러 개의 하드디스크를 마치 1개의 하드디스크처럼 다룰 수 있는 기술이다. 다시 말하면 여러 개 의 하드디스크를 1개의 디스크처럼 사용함으로써 속도 향상을 가져 온다. ID의 목적 ① 데이터 전송 속도 향상 ② 대용량 디스크 확장 가능 ③ I/O 요구 처리율 향상 ④ 결함 허용도 향상 RAID의 Level 복수의 디스크를 병렬로 처리하여 컴퓨터와의 입출력을 제공하기 위한 디스크 관리 방법. 방법에 따라 RAID-0부터 RAID-5까지 있다. ⇒ PC에서 흔히 보이는 것이 RAID Level 0,1,0+1 이다.

7 RAID RAID-0 Disk Stripping을 이용하는 Disk 배열로 Redundancy는 포함하지 않음. 배열내의 모든 Disk들에 데이터를 분산 저장 배열 관리 소프트웨어(Array Management Software) 필요 장점: I/O요구의 병렬처리 및 Strip들의 병렬 Access로 I/O 전송시간 감소 단점: 디스크 데이터의 Parity를 계산하여 저장하는 디스크를 따로 배정하지 않았으므로 Disk Data Failure의  경우 복구 방법이 없음.  RAID-1 디스크반사(disk mirroring)방식 Disk Data Input에 있어서 2개 디스크에 Parallel Write가 가능 Disk Data Output에 있어서는 2개의 데이터 중 어느 하나의 데이터에 임의로 접근 할 수 있어 Access Time은 하나의 Disk일 경우 보다 오히려 줄일 수 있음. 두개의 디스크에 동일하게 데이터를 기록(Mirroring) 장점: 높은 신뢰도 단점: write 시 Overhead가 큼 RAID-2 : 비트-단위 인터리빙 및 검사 디스크 사용 Hamming Code를 이용한 오류검출과 정정 검사에 많은 Overhead발생으로 실제로는 사용하지 않음.

8 RAID RAID-3 : 패리티 디스크(parity disk)사용 각각의 Disk에 데이터를 Bit 단위로 Stripping하여 기록하며, 안전성 확보를 위해 별도 디스크에 Parity Disk를 저장함. 장점 : Overhead 낮음 단점 : Parity Disk가 성능상의 bottleneck이 됨. RAID-4 : 병렬 데이터 전송 채널 추가 Block 단위의 Interleaving 장점 : 동시 Access가능하며 병렬전송으로 전송률 향상 단점: 쓰기 동작 시에 4번의 Access(데이터와 Parity의 읽기와 쓰기)필요 RAID-5 : 회전 패리티(rotated parity) 방식 이용 회전 Parity Disk를 사용함 장점 : Parity Disk에 대한 병목현상 해소 RAID-6 : 2차원 패리티(2-dimensional parity)방식 2차원 디스크 배열로 열에 대한 패리티 외에 행에 대한 패리티 추가 장점 : 2개 이상의 디스크에 결함이 발생하여도 회복 가능 단점 : 한번의 쓰기 동작에 6번의 디스크 액세스 발생

9 디스크 스케줄링 기준 디스크 스케줄링은 디스크 입출력을 하기 위해 대기하고 있는 요청 (request)들 중에서 어느 요청을 먼저 처리할 것인가를 결정하는 것 이유 -큐(Queue)에 대기중인 요청들에 대해 서비스 순서를 어떻게 결정하는 지에 따라 디스크 시스템의 성능이 달라지므로 더 좋은 성능을 얻기 위한 것이다. 디스크 스케줄링에서는 데이터 액세스 시간 중에 데이터 전송시간은 제외 되므로 탐색시간, 회전 대기시간의 최적화 기법이 필요하다. 디스크 스케줄링의 평가 기준 ① 단위 시간당 처리량(Throughput)⇒ 극대화 ② 평균 응답 시간(Mean Response Time)⇒ 감소 ③ 응답 시간의 예측성(Predictability)

10 탐색 시간의 최적화 FCFS(first come first served scheduling) 스케줄링
가장먼저 입력된 요구가 우선적으로 서비스를 받는 방법 ① 구현 - 대기 큐에 입력된 요구 순서대로 서비스 진행 ② 특징 - 대기 큐의 순서대로 서비스하며 더 높은 우선 순위의 요청이 입력되어도 순서가 바뀌지 않아 공평성이 보장 됨 - 디스크 오버헤드(부하)가 커지면 응답시간이 길어지고 비효율적.

11 SCAN 스케줄링(엘리베이터 알고리즘) Denning이 개발, SSTF가 갖는 응답시간의 편차와 차별을 극복하기 위한 방법 오버헤드가 적은 경우에 사용 ① 구현 - 헤드진행 방향과 같은 방향의 가장 짧은 거리에 있는 요청을 먼저 서비스하고 진행 중 가장 바깥쪽까지 갔거나 더 이상 요구가 없으면 반대쪽으로 방향을 바꾸어 서비스한다. ② 특징 - 디스크 오버헤드가 적어야 가장 좋은 효율을 가짐 - 대부분의 디스크 스케줄링의 기본 전략 - 밀도가 높은 쪽의 요청은 상당히 오랜 시간 대기하게 됨 SSTF 스케줄링 - 탐색 거리가 가장 짧은 요청을 먼저 처리하는 방법  - 탐색 시간의 극소화, 극단적일 경우 기아상태 발생 가능 ① 구현 - 현재 위치에서 가장 가까운 거리에 있는 요청을 서비스한다. - 대기 큐의 우선순위에 관계없이 다음 최단 거리 요청을 서비스 ② 특징 - 실린더 지향 기법 - 가장 안쪽이나 바깥쪽의 트랙은 가운데 트랙보다 서비스를 받지 못하기 때문에 응답시간의 편차가 크다. - FCFS보다 처리량이 많고 평균 응답시간이 짧다. - 일괄처리 시스템에 유용하고 응답시간의 편차가 크므로 대화형 시스템에 부적합.

12 헤드가 안팎으로 움직이나 어떤 진행 방향의 진행이 시작될 당시 대기 중 이던 요청들만 서비스를 한다.
N-단계 SCAN 스케줄링 헤드가 안팎으로 움직이나 어떤 진행 방향의 진행이 시작될 당시 대기 중 이던 요청들만 서비스를 한다. 서비스가 한쪽 방향으로 진행될 때 대기 중이던 요구들만 서비스한다. ① 구현 - SCAN과 동일 - 진행 중 입력된 요청들은 한데 모아 반대방향 진행 때 서비스한다. ② 특징 - 처리량과 평균응답시간에 있어 효율적 - SSTF 나 SCAN 방법보다 응답시간의 편차가 적다. - 한 실린더에 많은 요청이 도착해도 대기중인 요청만 처리하므로 무한대기가 없다. C(Circular)-SCAN 스케줄링 SCAN 스케줄링 전략을 수정 한 것 헤드는 향상 같은 방향으로 헤드를 이동하면서 디스크 요청을 처리 하나 더 이상 그 방향으로 요청이 없을 때 반대 방향으로 헤드를 요청하는 것이 아니라 같은 방향의 처음부터 다시 처리 한다. ① 구현 - 바깥쪽 실린더에서 안쪽으 로 진행하면서 최단거리의 요구를 서비스 한다. - 더 이상 요구가 없으면 가장 바깥쪽에서 서비스하지 않은 요구로 이동하여 서비스 ② 특징 - 진행도중 도착한 요청은 다음 수행 시 서비스 - 응답시간의 편차가 매우 적다. - 회전 시간의 최적화가 가능하며 부하(overhead)가 많이 걸리는 경우 효과적이다.

13 예션바흐 기법(Eschenbach Scheme)
Look 스케줄링 헤드가 진행하다가 도중에 진행방향의 앞쪽으로 더 이상 요청이 없을 경우 양끝 실린더까지 진행하지 않고 그 자리 에서 방향을 바꾼다. 예션바흐 기법(Eschenbach Scheme) 이 기법은 매우 부하가 큰 항공 예약 시스템에 의 해 개발. - 탐색시간 뿐만 아니라 회전 지연시간도 최적화하려고 했던 최초의 기법들 중 하나이다.

14 회전 지연 시간의 최적화 일반적으로 회전 지연 시간의 최적화를 위해 섹터 큐잉(Sector Queuing) 기법을 사용한다. SLTF(Shortest Latency Time First) 기법 이라고도 한다. 이 기법은 각 섹터별로 별도의 규를 두어 관리하며 하나의 실린더에 대한 여러 입출력 요구가 도착할 때 이들을 각 섹터별로 설정된 큐에 삽입한다. 이런 상태에서 헤드의 탐색과정이 끝나고 헤드가 특정 실린더에 도착한 후 헤드 아래에 먼저 도착된 순서대로 각 섹터에 대한 서비스를 한다. ① 구현 - 디스크 헤드가 특정 실린더에 도착하면 여러 트랙을 가리 키게 된다.      - 이 여러 트랙에 대한 많은 요구들 중 가장 짧은 회전지연 시간을 갖는 요청에 대해 먼저 서비스 한다. ② 특징 - 구현하기 쉽다. 이론적 최적 값과 거의 일치    - 회전지연시간 최적화는 디스크 주변의 가장 가까운 섹터가 가장먼저 서비스되므로 섹터 큐잉(sector queuing)이라 불림     - 고정헤드 디스크를 위한 스케쥴링 기법

15 기타고려사항 1) 버퍼링(buffering) 2) 디스크 스트라이핑(disk striping)
버퍼링이란? 정보의 송수신을 원활하게 하기 위해서 정보를 일시적으로 저장하여 처리 속도의 차를 흡수하는 방법이다. 기법은 디스크에서 자주 참조되는 자료를 주기억장치 커널 공간의 버퍼 영역에 저장하여 관리 한다. 디스크의 입출력 횟수가 적어지므로 시스템 성능이 향상된다. 2) 디스크 스트라이핑(disk striping) 2~32개의 개별 디스크에 하나의 가상적 스트라이프를 작성하여 이들 디스크를 컴퓨터의 운영체제가 단일의 디스크 구동 장치로 인식하도록 하여, 이들 디스크상에 존재하는 똑같은 크기의 디스크 분할의 집합을 단일 디스크 볼륨으로 종합하는 방법. 같은 볼륨 내에서의 다중 입출력 동작이 동시에 진행될 수 있게 되어 성능이 크게 향상된다. 디스크 스트라이핑은 윈도즈 NT에서 지원되고 있으며, 성능은 뛰어나지만 장애 허용성은 없다. 고성능과 대용량을 중요시 하는 시스템에서 일반적으로 사용한다. 여기서 스트라이프란 입출력 단위가 되는 블럭을 의미 한다.