운영체제의 기억장치 관리전략 및 스케줄링 정책

목차

운영체제의 기억장치 관리전략 및 스케줄링 정책



1. 기억장치 관리 전략
Ⓐ. 반입 전략(fetch strategy)
Ⓑ. 배치 전략(placement strategy)
Ⓒ. 교체 전략(replacement strategy)

2. 스케줄링 정책
①. 스케줄링의 개념
②. 스케줄링의 목적
③. 스케줄링의 성능 평가 기준
④. 스케줄링 알고리즘
④-1. 비선점형 방식
④-2. 선점형 방식

본문내용

다.
◎ 짧은 작업이나 중요한 작업을 오랫동안 기다리게 할 수 있다.
ex) FIFO 기법을 적용하여 작업 스케줄링 하였을 때, 다음 작업들의 평균 대기 시간과 평 균 반환 시간을 구하여라.
작업
도착시간
연산시간
A
0
24
B
1
6
C
2
3
A(24초)
B(6초)
C(3초)
0 24 30 33
B 작업의 경우 A의 작업이 모두 끝날 때 까지 기다렸으므로 24초-1초 = 23초
C 작업의 경우 A, B의 작업이 모두 끝날 때 까지 기렸으므로 30초-2초 = 28초
평균 대기 시간 : A=0초, B=(24-1)=23초, C=(30-2)=28초 이므로, 평균 대기 시간은 17초
평균 반환 시간 : A=(0+24)=24초, B=(23+6)=29초, C=(28+3)=31초 이므로,
평균 반환 시간은 28초
㉡. SJF(Shortest Job First) 스케줄링
◎ 작업이 끝나기까지의 실행 시간 추정치가 가장 작은 작업을 먼저 실행시키는 방식.
◎ FIFO 스케줄링을 개선한 비선점형 방식이다.
◎ 평균 대기 시간을 최소화한다.
◎ FIFO 스케줄링보다 평균 대기 시간이 짧지만 긴 작업의 경우 FIFO 스케줄링보다 더 크 고 예측이 더욱 어렵다.
◎ 실행 시간이 긴 작업일 경우에 무한 연기 현상이 발생될 수 있다.
◎ 무한 연기 현상을 방지하기 위해 에이징(Aging) 기법을 사용하여 해결한다.
※ 에이징(Aging) 기법 이란?
자원이 할당되기를 오랜 시간 동안 기다린 프로세스에 대하여 기다린 시간에 비례하는 높은 우선순위를 부여하여 가까운 시간 안에 자원이 할당되도록 하는 기법.
ex) SJF 기법을 적용하여 작업 스케줄링 하였을 때, 다음 작업들의 평균 대기 시간과 평 균 반환 시간을 구하여라.
C(3초)
B(6초)
A(24초)
작업
연산시간
A
24
B
6
C
3
0 3 9 33
평균 대기 시간 : A=9초, B=3초, C=0초 이므로, 평균 대기 시간은 4초
평균 반환 시간 : A=(9+24)=33초, B=(3+6)=9초, C=(0+3)=3초 이므로,
평균 반환 시간은 15초
㉢. HRN(Highest Response-ratio Next) 스케줄링
◎ SJF 스케줄링의 단점을 개선 하기위해 개발된 방식이다.
◎ 우선순위 계산 공식을 이용한다.
◎ 계산된 값이 가장 큰 작업이 우선순위가 높다.
◎ 공식 : (대기시간+서비스 시간) / 서비스 시간
ex) 다음 작업 중에서 우선순위가 높은 순서대로 나열하시오.
작업
서비스 시간
대기 시간
A
24초
4초
B
6초
2초
C
3초
3초
A=(24+4) / 24 = 1.16, B=(6+2) / 6 = 1.33, C=(3+3) / 3 = 2.00 이므로,
C → B → A 순으로 우선순위가 높다.
㉣. 우선순위 스케줄링
◎ 우선순위가 높은 작업을 먼저 처리하는 방식.
◎ 중요한 작업을 먼저 할 수 있는 장점이 있다.
㉤. 기한부(Deadline) 스케줄링
◎ 작업이 주어진 특별한 시간이나 만료 시간 안에 완료 되도록 하는 방식.
◎ 프로세스들이 마감 시간 내에 처리되지 않으면 폐기되거나 처음부터 다시 실행해야 한다
◎ 기한부 스케줄링에 필요한 집약적 자원 관리는 많은 오버헤드를 일으킬 수 있다.
◎ 동시에 다수의 기한부 작업이 수행되면 스케줄링은 매우 어려워진다.
◎ 사용자는 그 작업에 필요한 자원에 관한 정확한 정보를 시스템에 제시하여야 한다.
④-2. 선점형 방식
㉠. RR(Round-Robin) 스케줄링
◎ FIFO 스케줄링을 선점형으로 변환한 방식.
◎ 시간 할당량이 크면 비선점의 FIFO 스케줄링과 동일하다.
◎ 적절한 응답 시간을 보장해 주는 대화식 사용자에게 효과적이다.
◎ 동일한 시간을 사용하는 시분할 시스템에 효과적이다(시스템 측면).
◎ 시간 할당량이 작을 경우 문맥 교환에 따른 오버헤드가 커진다.
ex) RR 기법을 적용하여 작업 스케줄링 하였을 때, 다음 작업들의 평균 대기 시간과 평균 반환 시간을 구하여라. (시간 할당량 : 10초)
작업
연산시간
A
12초
B
25초
C
15초
D
8초
E
10초
A(10초)
B(10초)
C(10초)
D(8초)
E(10초)
A(2초)
B(10초)
C(5초)
B(5초)
0 10 20 30 38 48 50 60 65 70
평균 대기 시간 : A=(48-10)=38초, B=10+(50-20)+(65-60)=45초, C=20+(60-30)=50초
D=30초, E=38초 이므로, 평균 대기 시간은 40.2초
평균 반환 시간 : A=50초, B=70초, C=65초, D=38초, E=48초 이므로,
평균 반환 시간은 54.2초
㉡. SRT(Shortest Remaining Time) 스케줄링
◎ 작업이 끝나기까지 “남아 있는” 실행 시간 추정치가 가장 작은 프로세스를 먼저 실행하 는 방식으로 새로 입력되는 작업까지도 포함한다.
◎ 서비스 받은 시간을 기록해야 하기 때문에 오버헤드가 늘어난다.
◎ 평균 대기 시간과 대기 시간의 분산(편차의 제곱)도 크다.
◎ 실행 시간을 추적해야 하므로 오버헤드가 증가한다.
㉢. MFQ(Multi level Feedback Queue) 스케줄링
◎ 짧은 작업이나 입출력 위주의 작업에 우선순위를 부여하기 위해 개발된 방식이다.
◎ 큐(대기 리스트)가 여러 개이며 우선순위가 있다.
◎ 각 큐마다 시간 할당량(Quantum)이 존재하며 낮은 큐일수록 시간 할당량은 커진다.
◎ 각각의 큐들은 종속적으로 연결되어 있다.
◎ CPU를 시간 할당량만큼 사용한 프로세스는 낮은 큐로 이동된다.
◎ 맨 마지막 단계의 큐는 RR 스케줄링을 사용한다.
참고 문헌 : 최희준, 조홍만, 영진정보연구소, 『이기적IN 정보처리기사 필기기본서(2011)』, 영진닷컴, 2010
한금희, 함미옥, 『IT CookBook 컴퓨터 과학 개론』, 한빛미디어, 2004
참고 자료 출처 : 구역성(Locality) http://jmh3658.blog.me/150007507490
오버헤드(Overhead) http://terms.co.kr/
타임 스탬프(Time Stamp) http://blog.naver.com/yzasd?Redirect=Log&logNo=40124449332

키워드

운영체제,   기억장치,   스케줄링정책,   스케줄링