프로세서 알고리즘

목차

1. 프로세서 알고리즘별 분류
2. 페이지 교체 알고리즘
3. 디스크 스케쥴링 알고리즘
4. 참고문헌

본문내용

에서 가장 가까운 거리인 트랙 65로 이동 후 다시 65에서 가장 가까운 거리인 67로 이동한다.
② 트랙 67에서 트랙 37까지는 거리가 30이고 트랙 98까지는 31이므로 트랙 37로 먼저 이동 한다.
③ 이후 헤드는 트랙 14, 98, 122, 124, 183 위치로 차례차례 이동한다.
④ SSTF 스케줄링은 현재 헤드 위치에 가까운 곳에서 계속 요청이 들어오는 경우 기아 (starvation) 현상이 일어날 수 있다.
장점 : FCFS 방법보다 처리시간이 개선되었다.
단점 : 트랙의 안쪽이나 바깥쪽이 가운데보다 더 적은 서비스를 받아 응답시간의 편차가 커 서 대화형 시스템에 부적합하고 안쪽이나 바깥쪽 요청은 기아현상이 일어날 수 있다.
그림SSTF 스케줄링
■ SCAN
SCAN 방법은 한 방향으로 요청에 대해 먼저 SSTF 방법으로 서비스를 하고 계속 진행한다. 한 방향으로의 모든 서비스가 끝나면 방향을 바꾸어 반대 방향으로 서비스를 계속하여 나간다.
① SCAN 스케줄링은 SSTF의 응답시간 차별대우와 편차를 극복하였다.
② 현재 헤드가 트랙 53에 있고 트랙 0방향으로 움직인다면 먼저 트랙 0방향으로 가정 가까 운 트랙 37로 이동 후 다시 14로 이동할 것이다.
③ 트랙 0에 이르러서는 방향을 바꾸어 그림 10.5와 같이 서비스 할 것이다. 이 알고리즘
은 엘리베이터 움직임과 흠사하여 엘리베이터 알고리즘 (elevator algorithm)이라고도
한다.
④ SCAN 방법은 트랙의 가운데보다 바깥쪽은 더 적은 서비스를 받을 수 있는 문제점이
있다.
장점 : SSTF의 응답시간 편차를 극복하였다.
단점 : 바깥쪽 트랙이 가운데의 트랙보다 더 적은 서비스를 받는다.
그림SCAN 스케줄링
■ C-SCAN(circular scan)
C-SCAN 방법은 SCAN과 비슷한 방식으로 안쪽 트랙에서 바깥쪽 트랙으로 이동하면서 탐색시간이 가장 짧은 것부터 서비스 한다.
① C-SCAN 방법은 한쪽 방향으로의 서비스가 모두 끝났으면 디스크 헤드를 다시 가장 안쪽 의 요청이 있는 곳으로 옮겨 서비스를 계속하는 방법이다.
②처음 트랙과 마지막 트랙은 서로 연결한 것과 같은 환형 (circular) 처리와 유사하다.
장점 : 안과 밖 트랙의 차별적인 서비스를 제거하였다.
단점 : 헤드가 바깥쪽 트랙에 도달하여 안쪽 트랙으로 이동시 탐색시간 낭비가 있다.
그림CSAN 스케줄링
■ LOOK 와 C-LOOK
LOOK와 C-LOOK 스케줄링은 SCAN 이나 C-SCAN 스케줄링을 개선한 스케줄링이다.
① SCAN 이나 C-SCAN 스케줄링은 더 이상 ㅅ비스 요청이 없어도 디스크 헤드가 안쪽이나 바깥쪽 끝에 도달한 후 다시 반대 방향으로 서비스를 계속하거나 또는 반대 방향으로 되돌 아 서비스를 계속했다.
이 경우 디스크 헤드의 이동은 시간 낭비로 효율의 저하를 가져올 뿐이며 따라서 오늘 날에 는 이러한 방법의 스케줄링 보다는 좀 더 개선된 방법을 사용한다.
그림C-LOOK 스케줄링
② LOOK 스케줄링은 현재 서비스 진행 방향에 더 이상 요청이 없으면 바로 반대 방향으로
서비스를 하고 C-LOOK 스케줄링은 더 이상 요청이 없는 경우 반대쪽 끝의 요청한 곳으 로 헤드를 옮겨 서비스를 계속한다.
장점 : 불필요한 헤드의 이동을 제거 하였다.
■ 디스크 스케줄링 알고리즘 의 선택
앞에서 언급한 여러 가지 디스크 스케줄링 알고리즘 중 시스템에 어떤 방법을 적용할 것인지를 결정하기 위해선은 다음을 고려해야 한다.
(1) 시스템의 디스크 서비스 요구량
디스크의 접근 요구가 서비스 큐를 넘지 않으면 스케줄링 기법간에 효과과 같다.
따라서 간단한 스케줄링 기법을 사용한다.
(2) 디스크 상의 데이터를 저장하기 위한 파일할당 방식
연속적으로 할당된 파일에 접근하는 프로세스는 디스크 상의 특정주소 부근에 대한 접근 요구가 많아 디스크 헤드의 이동거리는 적을 것이고 프로세스가 접근하려는 파일이 링크 파일(linked file) 이나 색인 파일)(indexed file)인 경우 디스크 상의 분산된 블록을 할당 받아 사용함으로 디스크의 사용효율은 좋겠지만 디스크 헤드의 이동거리는 많을 것이다.
이 경우 헤드 이동거리에 효율 좋은 스케줄링 기법을 사용하여야 할 것이다.
(3) 디스크 운용을 위한 정보들의 관리방식
디렉토리와 색인 블록의 위치도 매우 중요하다. 이는 모든 파일은 일당 개방 (open) 되어야 사용할 수 있고 파일을 개방하기 위해서는 디렉토리 테이블이 탐색되어 해당 디렉토리 정보 를 사용하여야 하기 때문이다.
따라서 디렉토리 테이블은 디스크의 끝 부분에 두는 것보다 중간 부분에 두는 것이 디스크 헤드의 이동을 상당히 감소시킬 수 있다.이상과 같은 여러 가지 이유로 디스크 스케줄링 알로리즘은 운영체제에서 별개의 한 모듈로 작성하여 필요에 따라 지금까지 사용해 온 스케줄링 알고리즘을 제거하고 다른 알고리즘으로 교체 할 수 있도록 한다.
처음에는 SSTF나 FCFS 방법을 사용하는 것이 적절하다고 추천된다. Thorey와 Pin-kerton(1972)은 시뮬레이션을 통해 여러 가지 알고리즘을 비교해서 SCAN과 C-SCAN의 사용을 추천했다.
최근에는 디스크 헤드의 스케줄링 기능을 디스크 컨트롤러 (disk controller) 가 자체적으로 할 수 있는 것도 있다. 이 경우 운영체제의 모듈을 줄이는 이점도 있으나 운영체제와 디스크 컨트롤러 사이의 복잡한 제어 상황이 생겨 성능이 감소하는 경우가 생기기도 한다.
참고문헌
http://terms.naver.com/entry.nhn?docId=15454
http://ko.wikipedia.org/wiki/%EC%84%A0%EC%9E%85_%EC%84%A0%EC%B6%9C
http://www.google.co.kr/search?q=SCAN+%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81&hl=ko&newwindow=1&prmd=ivnsul&source=lnms&tbm=isch&ei=tvP9TbbdG4jevwOcp5y3Aw&sa=X&oi=mode_link&ct=mode&cd=2&ved=0CCUQ_AUoAQ&biw=880&bih=647

키워드

프로세서알고리즘,   프로세서,   알고리즘,   페이지 교체 알고리즘,   디스크 스케쥴링 알고리즘