Scan 알고리즘

소개글

Scan 알고리즘에 대한 보고서 자료입니다.

목차

과제내용
해결방법
전체 프로그램 구조
각 함수의 기능
변수에 대한 구체적 설명
자료구조
실험결과
종합의견
결론
참고문헌

본문내용

정하여 고정된 값이나 한정된 값으로 할 경우 같은 수가 나온다던지 하는등의 실험이 실패할 변수를 줄입니다.
do while문을 사용할 때 최소 5회 이상 반복을 요구했으므로 num_run 값을 0으로 초기화시키고 4까지 돌게 해서 5번 돌게 합니다[while(num_run<5)]. for문을 사용하여 배열에 0 ~ 200을 차례로 넣고, swap함수를 사용하여 0 ~ 200까지 차례로 정리되어 있는 수를 랜덤하게 섞어 줍니다. 이렇게 섞여서 배열된 수에서 7번째 숫자까지 트랙 큐 배열에 넣습니다.
스캔 방향을 정하기 위해 랜덤 함수를 이용하여 0, 1을 임의로 정하게 한 뒤 100을 헤드 시작 위치인 현재 값으로 잡고 방향이 0일 땐 마이너스 방향으로, 1일 땐 플러스 방향으로 이동하게 합니다. 다시 for문을 사용하여 현재 포인트인 100에서 플러스 또는 마이너스 방향으로 1씩 증가 또는 감소시킵니다. 1씩 감소 또는 증가될 때 나온 값을 이전에 swap함수로 섞어서 트랙 큐에 배열된, 7개의 숫자와 대조합니다.
동일한 숫자를 출력시키고 움직인 총 거리를 구하기 위해 그 숫자를 num_mini또는 num_maxi로 지정합니다. 이 일치된 숫자는 0또는 200까지 도달한 후 다시 역으로 SCAN되어질 때 걸리지 않도록 999로 바꾸어 줍니다. 이때 역으로 SCAN 되는 시점인 0,200을 1,199로 지정해주어 중복 스캔하지 않도록 합니다. 또한 동일한 값을 대조하여 출력한 뒤 7개의 초과로 나오지 않도록 current_findnum값을 증가시킵니다. 나중에 이 값이 7개가되면 마이너스 또는 플러스 방향으로 1씩 이동하던 프로그램에서 빠져 나오게 됩니다.
움직인 총 거리를 구하기 위해 아까 지정해 두었던 num_mini를 (100-mini_num)하고 num_maxi를 (num_mini - num_maxi)하여 더해주고 마이너스가 나오지 않기 위해 절대값을 구해주는 함수인 abs()함수를 사용해서 총 이동거리를 구합니다.
이후 num_run값이 5가 되면서 전체 프로그램에서 빠져 나오게 됩니다.
그러면 임의로 정한 헤드시작 위치 100에서 요구 큐가 중복되지 않게 0부터 200사이의 값 중 7번의 임의의 트랙 숫자를 가져오게 되고 여러 번 실행시켜 평균 값 등을 구하여 결과에 대한 결론을 도출 해낼 수 있다.
[실험방법]
0 ~ 200의 숫자를 랜덤하게 섞고 나열된 숫자 중 7번째 숫자까지 요구 큐에 넣으면 조건 1을 만족하게 됩니다. 조건 2를 만족시키기 위해 프로그램을 돌리면 5번 돌리고 각 나온 값의 이동 경로와 총 이동 거리의 합이 시뮬레이션 되어 나옵니다. 이런 값들을 계산하여 의미를 찾아본다.
[실험결과]
결과 1
결과 2
결과 3
결과 4
결과 5
[종합의견]
결론의 도출과 종합적 의견을 위해 엑셀로 한번의 결과 그림 당 움직인 총 거리 합의 총합과 전체평균 , 각 합을 그래프 상으로 나타내 보았습니다. 그리고 의견.
다른 스케줄링 기법의 데이터나 저 말고 다른 학우들이 나타낸 데이터를 가지고 있지 않아서 비교분석은 곤란하고 자체 비교를 해야만 한다는게 아쉬웠습니다. 또한 스캔의 초기 위치를 지정하게 했으면 비교하기 좋았을 텐데 하는 생각도 들었습니다.
평균값이니 만큼 대체로 평균에 가까웠지만 많은 합들이 평균을 크게 벗어나는 값들이 많은걸로 보아 앞에서 살펴본거와 같이 SCAN Algorithm기법도 완벽하기보단 먼가 문제가 있다는 것을 알수 있었고, 크게 벗어난 값들이 눈을 치우자 마자 뒤에 눈이 쌓이는 현상과 같이 각 트랙에 대한 요청이 균등하다고 가정할 때 헤드가 한쪽 끝에 이르러 방향을 바꾸어야 할 시점에서 요청 밀도가 높은 쪽은 최초의 시작 부분이며 나중에 처리된 헤드 바로 뒷부분은 비교적 밀도가 낮고 이로 인해 밀도가 높은 쪽의 요청은 상당히 오래 기다림으로서 생겨나는 차이임을 유추할 수 있었습니다.
앞으로 다른 디스크 스케줄링 알고리즘의 결과나 같은 알고리즘의 다른 데이터가 주어진다면 스캔 시작 위치에 따른 평균의 차이와 다른 알고리즘과의 평균 값 차이의 계산으로 인한 효율성을 따질 수 있고, 좀더 다양한 생각을 할 수 있을 것 같습니다.
[결론]
제가 가진 데이터만으로는 SCAN Algorithm의 알아본 바와 같은 단점으로 인한 평균차가 심한 데이터가 발생되었음을 정확하진 않지만 유추할 수 있었습니다.
마지막으로 책에 나오는 다른 스케줄링 기법과의 차이점을 정리하는 것으로 결론을 마치겠습니다.
디스크 스케줄링의 형태
장 점
단 점
FCFS
(First Come First Served)
프로그램하기 쉬움.
공평성이 유지.
적은 부하에 적합.
탐색 패턴을 최적화 하려하는 패턴이 없음.
오버헤드가 커지면 응답 시간이 길어짐.
SSTF
(Shortest Seek Time First)
FCFS보다 처리량이 많고 평균 응답 시간이 짧음.
일괄처리 시스템에 유용.
실린더의 제일 안쪽과 바깥쪽 기아 현상 발생.
응답시간의 편차가 커서 대화형 시스템에 부적합.
SCAN Sheduling, LOOK
처리량, 평균응답시간 개선은 SSTF와 같지만, SSFT에서의 차별대우가 줄고 낮은 편차를 가짐.
진행 도중 도착한 요청도 서비스 받게 되므로 밖에 위치하는 트랙이 불리.
밀도가 높은 쪽의 요청은 상당히 오래 대기.
C - SCAN , C - LOOK
SCAN,LOOK에서의 대기 시간을 좀더 균등하게 적용
최근의 요청들이 높은 번호를 가지기 때문에 불공평한 할당
N - Step SCAN
SSTF나 SCAN방법보다 응답시간 편차가 적음.
많은 수의 요구가 있을 때 지연 발생 가능성 제거.
가장 최근의 요청들이 SCAN보다 오래 기다림
에션바흐 기법
(eschenbach scheme)
특징:C-SCAN처럼 움직이나 모든 실린더는 요청이 있으나 없으나 전체트랙이 한바퀴 돌 동안 서비스.
배우 부하가 큰 항공 예약 시스템을 위해 개발.
두 개의 요청이 실린더에서 같은 색터의 위치에 있으면 한 방향으로 진행시 한 개의 요청만을 서비스.
탐색시간, 회전지연시간을 동시에 최적화 하려고 했던 기법중 하나
[참고문헌]
운영체제의 커널 내부구조 / 장승주 저 / 2004

키워드

디스크,   스케줄링,   scan,   기법,   알고리즘,   디스크 스케줄링,   scan 알고리즘,   구현