* 참고 자료 : 운영체제론 한빛아카데미
스케줄링 알고리즘 1 :
https://cow-kite24.tistory.com/120
[운영체제론] 스케줄링 알고리즘 1 / 2021.12.06
* 참고 자료 : 운영체제론 한빛아카데미 스케줄링 알고리즘이란? 스케줄링 알고리즘이란 실행 시 어떤 프로세스가 언제, 얼마 동안 실행할지 결정하는 것이다. 이때 여러 요인을 고려해야 한다.
cow-kite24.tistory.com
7. 다수준 피드백 큐
프로세스가 행동 양식(입출력 요청 전 실행시간, 메모리 선호부분 등)을 확립할 기회를 얻지 못한 경우, 정확한 프로세서 사용 시간을 결정하지 못한다. 그리고 서로 다른 특징의 프로세스는 다른 스케줄링 방법을 요구한다. (일반적으로 짧은 프로세스, 입출력 중심 프로세스가 프로세서 중심 프로세스 이전에 실행되는 것을 선호함.) 이 때문에 프로세스의 성격을 파악하고 적절하게 스케줄링이 필요한데 다수준 피드백 큐는 이러한 목적을 달성하기 위한 장치이다.
7-1) 다수준 피드백 큐 동작
- n개의 레벨을 갖는 큐 운용 -> 상위 n-1 개의 큐 : FIFO, 마지막 큐 : 라운드 로빈
- 큐잉 네트워크에 진입하는 프로세스는 레벨 1 큐에 들어감
- 실행종료 또는 이벤트 대기이면, 큐잉 네트워크에서 나감
- 각 수준에서 허용된 퀀텀을 모두 소비하면, 한 수준 낮은 큐로 이동
- 낮은 수준으로 옮겨갈 때, 해당 프로세스의 퀀덤을 증가 -> 큐잉 네트워크에 오래 머물수록 큰 퀀텀을 받음
- 실행 중인 프로세스가 선점되면, 가장 높은 큐의 앞에 있는 프로세스를 디스패치
다수준 피드백 큐는 프로세스 성격에 맞게 스케줄링하는 좋은 방식이다. 프로세스들이 프로세서를 요구하는 정도에 따라 분류한다.
7-2) 다수준 피드백 큐에서 프로세스 동작
- 입출력 중심 프로세스와 짧은 프로세서 시간만 필요한 프로세스 선호 :
첫번째 큐에 충분히 큰 퀀텀을 지정해서, 대부분 입출력 중심 프로세스가 퀀텀 만료 전에 입출력을 요청할 수 있게함
입출력 중심 프로세스는 자주 큐잉 네트워크에서 나가고 들어오면서, 우선순위를 유지할 수 있음 (다시 들어오면, 나갔을 때의 우선순위 레벨로 진입)
- 프로세서 중심 프로세스는 결국 가장 낮은 레벨 큐에 도달하고 다른 프로세서 중심 프로세스와 라운드 로빈 방식으로 경쟁 :
프로세스가 큐잉 네트워크를 나갈 때 머물렀던 레벨을 식별번호로 스탬핑하여, 다시 들어올 때 스탬핑된 레벨로 진입 -> 프로세서 중심 프로세스의 높은 레벨 진입 방지
다수준 피드백 큐는 적응 메커니즘이다. 비적응 메커니즘보다 오버헤드가 많으나 시스템의 변화에 민감하게 적응해, 시스템의 방응성을 향상시킨다.
적응 메커니즘이 현대 스케줄러에 적합한 이유는 무엇인가?
답 : 현대 컴퓨터 시스템에서는 많은 응용 프로그램이 프로세서를 많이 사용하면서도 입출력 중심이다. 예를 들어, 스트리밍 비디오를 재생할 때 원격 서버에서 비디오 클립 데이터를 가져오려고 입출력을 수행함과 동시에 디코딩과 표시를 위해 프로세서도 많이 사용해야 한다. 이와 유사하게, 비행기 시뮬레이터와 같은 대화식 게임에서도 사용자 입력(조이스틱을 이동 등)에 빠르게 반응하면서도 복잡한 3D 화면을 계속 표시해야 한다. 적응 메커니즘은 이러한 프로세스들이 입출력 중심 기능과 프로세서 중심 기능 사이를 전환할 때 시스템도 이에 맞게 반응할 수 있게 해준다.
8. 공평 분배 스케줄링 (FSS)
8-1) 유닉스 시스템
시스템은 대체로 다양한 관련 프로세스 집합을 지원한다. 예를 들면, 유닉스 시스템은 각 사용자에게 속한 프로세스들을 그룹화한다. 유닉스 환경에서, FSS는 연관된 사용자 집합에 미리 지정된 비율의 시스템 자원을 주게 하려고 개발되었다.
다음 그림에서 n개의 사용자, p는 프로세스를 나타낸다.
표준 프로세스 스케줄러는 각 사용자 특성을 고려해서 전체 프로세스에 대해 스케줄링한다.
FSS는 처음엔 사용자 집합에 미리 지정된 비율의 시스템 자원을 주려는 목적에서 개발되었다. 이를 통해 사용자간 공평성을 유지할 수 있다.
8-2) FSS 적용 예
- 수석 연구원 그룹 : 연구원 수가 작고, 계산이 많은 시뮬레이션 같은 일을 주로 함
보조 연구원 그룹 : 연구원 수가 많고, 계산이 적은 데이터 수집, 입출력 같은 일을 주로함
- 업무 특성에 맞춰 수석, 보조 그룹에 차등화된 자원 할당
예) 수석 : 75% 보조 : 25%
8-3) 공평분배 스케줄링 (FSS)
- 비슷한 특성을 가지는 사용자들을 그룹화, 이들 각 그룹이 공평분배 그룹이다.
- 자원을 공평분배 그룹별로 할당한다. : 프로세스의 성능이 해당 프로세스가 속한 그룹 안에 있는 구성원에만 영향을 받고, 시스템 전체 사용자 수에는 영향을 받지 않음
- 각 공평분배 그룹에 우선순위를 부여할 때 최근 프로세스 사용비율을 고려해서. 명시한 자원 활용 목표에 가까운 정도를 기준으로 우선순위 부여 : 활용도가 떨어지는 그룹은 높은 우선순위를, 활용도가 높은 그룹은 낮은 우선순위를 가진다.
1. FSS에서 자원 활용도 목표를 달성하지 못한 그룹에 높은 우선순위를 부여하는 이유는 무엇인가 ?
답 : 명시한 자원 활용도 목표보다 적은 자원을 사용한 프로세스들은 낮은 수준의 서비스를 받았을 확률이 높다. 시스템은 이 프로세스들의 우선순위를 높여서 출분하 시간 동안 필요한 자원을 사용해 실행할 수 있게 한다.
2. FSS는 표준 프로세스 스케줄링 규칙과 어떻게 다른가?
답 : FSS는 자원을 프로세스 그룹별로 배분한다. 반변에 표준 프로세스 스케줄러는 모든 프로세스가 동일한 조건에서 모든 자원을 얻으려고 경쟁한다.
9. 데드라인 스케줄링
데드라인 스케줄링에서는 프로세스들이 특정 시간, 즉 데드라인 안에 마치도록 스케줄링한다. 데드라인 스케줄링은 복잡하다. 일단 사용자들은 정확한 자원 요구량을 미리 제시하는 것이 필요하다. 두 번째로, 시스템은 데드라인에 맞춰 프로세스를 실행하되 다른 사용자들에 대한 서비스에 심각한 악영향을 미치면 안된다. 또한 시스템은 데드라인이 될 때까지 자원 요구량을 철저하게 계획해야 한다.
데드라인 스케줄링이 요구하는 강도 높은 자원 관리는 상당한 오버헤드를 가져올 수도 있다.
사용자들이 필요한 자원을 미리 명시하는 것이 왜 중요한가?
답 : 스케줄러에서 프로세스들이 요구하는 자원을 확보해 데드라인 전에 작업을 완료할 수 있게 보장해야 하기 떄문이다.
10. 실시간 스케줄링
7번의 스케줄링 까지의 스케줄링 알고리즘의 주요 목적은 자원 활용도를 높이는 것이다. 주기적이거나 타이밍 제약을 가진 프로세스는 다른 알고리즘이 필요하다.
실시간 스케줄링은 타이밍 제약 요구를 충족하고 주기적인 실행 요구를 충족한다. 예를 들면 항공제어 시스템에서 비행기 위치를 갱신하는 기능이다.
- 소프트 실시간 스케줄링
소프트 실시간 스케줄링은 실시간 프로세스들이 해당 시스템의 다른 프로세스들보다 먼저 디스패치되게 하지만, 시간적 제약을 지킨다고 보장하지는 못한다. 예를 들어 멀티미디어를 부드럽게 재생한다.
- 하드 실시간 스케줄링
하드 실시간 스케줄링은 항상 프로세스의 시간적 제약을 충족함을 보장한다. 데드라인을 지키지 목할 경우 큰 재난을 초래할 수 있다. 예를 들어 항공 제어 시스템이 있다.
10-1) 정적 실시간 스케줄링
정적 실시간 스케줄링에서는 시스템 실행 전에 프로세스 우선순위는 결정되고 시간에 따라 변하지 않는다. 오버헤드가 적고 각 프로세스가 제한 시간 안에 완료함을 비교적 쉽게 증명할 수 있기 때문에 하드 실시간 시스템은 정적 스케줄링 알고리즘을 주로 사용한다.
- 비율 단조 알고리즘
비율 단조 알고리즘은 선점형, 우선순위 기반 라운드로빈 알고리즘으로, 프로세스가 실행해야 하는 빈도에 비례해 우선순위가 증가한다. -> 빈번하게 주기적으로 실행되는 프로세스를 선호한다.
- 데드라인 단조 알고리즘
데드라인 단조 알고리즘은 선점형 알고리즘으로 주기적인 프로세스들이 주기와 같지 않은 데드라인을 지정할 때 사용한다. -> 데드라인이 짧을수록 우선순위가 증가한다.
10-2) 동적 실시간 스케줄링 알고리즘
동적 실시간 스케줄링 알고리즘은 프로세스 실행 중에도 우선순위를 조절한다. 따라서 큰 오버헤드가 발생한다.
- 최단 데드라인 우선 (EDF)
데드라인이 가장 임박한 프로세스를 디스패치하는 선점형 스케줄링 알고리즘이다.
- 최소 여유 시간 우선 (MLF)
EDF와 유사하지만 프로세스의 여유 시간에 근거해 우선순위를 결정한다.
1. 대부분의 하드 실시간 스케줄링 알고리즘이 정적인 이유는 무엇인가?
답 : 하드 실시간 시스템은 프로세스가 데드라인을 철저히 지키도록 보장해야 한다. 정적 스케줄링 알고리즘은 특정 시스템에 이러한 속성을 부여함은 물론 구현 오버헤드를 줄여준다.
2. 최소 여유 시간 우선 알고리즘이 EDF 방식으로 변하는 경우는 어떤 때인가? 이와 같은 경우가 발생할 수 있는가 ?
답 : 앞에 나온 공식에서 C 값이 임의의 시점에 모든 프로세스에 대해 동일한 값을 가질 때 최소 여유 시간 알고리즘은 EDF 알고리즘으로 변한다. 가능성은 매우 적지만 그래도 발생 가능한 일이다.
'OS > 운영체제론' 카테고리의 다른 글
| [운영체제론] 고정 파티션 멀티프로그래밍 / 2021.12.07 (0) | 2021.12.07 |
|---|---|
| [운영체제론] 단일 사용자 연속 메모리 할당 / 2021.12.07 (0) | 2021.12.07 |
| [운영체제론] 스케줄링 알고리즘 1 / 2021.12.06 (0) | 2021.12.06 |
| [운영체제론] 프로세서 스케줄링 / 2021.12.06 (0) | 2021.12.06 |
| [운영체제론] 비동기식 병행 실행 요약 / 2021.10.28 (0) | 2021.10.28 |
