프로세스 스케줄링 방법

스케줄링이란 준비되어있는 프로세스에게 cpu를 할당하는것 

 

스케줄링을 만들때 고려해야할 사항들

1. 입출력 위주의 프로세스인가 == cpu적게 쓰고 채널을 통해서 입출력 자주함
2. 연산 위주의 프로세스인가 == cpu를 많이 필요한다
3. 프로세스가 일괄처리형인가 == cpu를 뺏기지 않고 지속적으로 사용
4. 긴급한 응답이 요구되는가(실시간인가)
5. 프로세스의 우선순위가 필요한가 == 어떤건 빨리 어떤건 늦게
6. 높은 우선순위를 지닌 프로세스에 의해서 얼마나 자주 뺏기는가
7. 실행시간은 얼마인가
8. 완전처리되는데 필요한 시간은 얼마나 요구되는가
9. 페이지 부재를 얼마나 자주 발생되는가

모두 만족 불가능 이중 하나를 선정하여 만듬

 

프로세스 스케줄링 단계별 분류(별로 안중요)

상 중 하 단계로 분류됨

하위 단계 스케줄링(3단계 스케줄링)

어떤 준비 상태의 프로세스에게 중앙처리장치를 항당할 것인가를 결정함

우리가 만드는 단계

상위 (1단계)

더블클릭->메모리에 올라감

작업이 시스템에 들어오는것을 승인함

중위 (2단계)

실행 -> 준비 혹은 대기 상태

실행하다가 다시 준비로 가는 단계

단계별 스케줄링

프로세스 스케줄링 방식별 분류

1. 선점 / 비선점 스케줄링

+선점이란 뺏어오는것

• 비선점 방식 = 일관처리 시스템에서 주로 사용

하나의 프로세스에 중앙처리 장치가 할당되면 그 프로세스의 수행이 끝날때까지

중앙처리 장치는 그 프로세스로 부터 빠져나올 수 없음

응답시간 예측이 가능함

짧은 작업의 프로세스가 긴작업의 프로세스를 기다리는 경우 종종 발생

• 선점방식

하나의 프로세스가 중앙처리장치를 차지하고 있을때 다른 프로세스가 현재 수행중인 프로세스를 중지시키고

중앙처리장치를 차지할 수 있음

우선순위가 높은 프로세스를 먼저 수행 할 수 있음

실시간 시스템 또는 시분할 시스템에서 사용

단 기존에 실행하던 정보(context)를 별도로 유지 관리해야함 -> 오버헤드(부담)가/이 발생

프로세스가 바껴서 실행되는걸 context switching(문맥 교환)이라고 함

 

2. 우선순위 스케줄링 방식

들어오는 순서대로 처리해 == 우선순위 없음

각 프로세스에게 우선순위를 부여하여 우선순위가 높은 순서대로 처리하는 방법

• 정적 우선순위 기법

한번 우선순위를 정한 후 바꾸지 않음

상대적으로 오버해드가 적으나, 주위여건의 변화에 적응 x

• 동적 우선순위

필요에따라 우선순위 재구성 ,복잡하고 오버해드 ㅇ

 

3. 기한부(deadline) 스케줄링 방식

명시된 기한 내에 완료되야함

실시간 시스템에 유효, 하지만 어려움(프로세스 여러개가 기한안에 끝내야함)

정확한 자원을 제시해야함, 다른 작업에 영향을 미치지 않아야함,배부 철저히 등등

우리는 그중 2가지를 배워보자

1. RM알고리즘 

대표적인 정적(시스템에 의해 실행되는 작업 시간이 미리 정의되어 있는 경우) 스케줄링 방식 작업주기가 짧을 수록 더 높은 우선수위가 부여

1. EDF알고리즘

동적(작업의 발생시산이나 특성을 미리 예측할 수 없을 경우에 유용) 스케줄링 방식 임계시간이 가장 근접한 태스크를 가장 먼저 수행하는 방식

 

4. 다중프로세서 스케줄링 방식

프로세스들의 형태가 동일한 동질 시스템 또는 서로다른 이질시스템이 존재

이질 시스템 : 자신의 프로세스를 위한 준비 큐가 각각있으며 자신만의 스케줄링 알고리즘을 가짐

동질 시스템 : 동질일 경우 로드 밸런싱을 수행해야함->일에대한 부담을 나눔

동질 시스템에서의 두가지 스케줄링방식

1. 각 프로세서가 스스로 스케줄링하며, 공동 준비 큐를 조사하여 실행할 프로세스를 선택함
2. 한 프로세서가 다른 프로세서를 위한 스케줄러로 지정되어 주종구조를 구성함

드디어 프로세스 스케줄링 알고리즘을 배워보자!!

FCFS(First Come First-Served) 스케줄링

먼저 들어온게 먼저 서비스 된다.

비선점 방식, 간단함, 도착순서에 따라cpu할당, 예측 용이,

단점 : 긴 작업이 들어오면 잛은 작업이 오래 기다림 == 호위 효과(convoy effect)

평균대기 & 반환 시간

FCFS

SJF(Shortest Job First)스케줄링

짧은것 부터 해결

비선점, fcfs보다 평균 대기시간 감소

단점 : 수행딜 프로세스의 길이를 정확히 알기 어려움

사용자가 제공하는 정보에 의존, 거짓정보의 위험 존재

SJF

SRT스케줄링

선점 방식!!!!

4개가 들어와있다. 그럼 짧은것 부터 진행한다. 그러던 중 새로운 프로세스가 등장하면

수행중이던 프로세스와 비교를 하여 실행한다.(실행중인 프로세스도 남은 처리시간과 비교)

단점:수행중인 작업들에 대한 실행시간을 추적보유 해야함(오버해드)

+++ SJF SRT를 비교해서 풀어보자

문제 :

SJF방식

SRT방식은 표를 그려서 해결하자

간츠파트

 

 

 

 

평균 반환시간(마지막으로끝난 시간만 계산하면됨)

끝난 시간에 도착시간 빼서 더하면 됨

우선순위 스케줄링

선점 비선점 둘다 가능

각 프로세스에다가 우선순위를 주고 외부적(사용부서의 중요도) 내부적(메모리 요구량,파일 수) 요인을 이용하여 우순위 할당 가능

문제점 : 무한대기(우선순위가 낮은것은 계속 지연됨), 기아현상(cpu를 못받은 프로세스가 죽음) 발생위험

->에이징 기법으로 해결

+에이징기법

오햇동안 시스템에 대기하는 프로새스들의 우선숭위를 시간이 지남에 따라 점진적으로 증가시킴

 

라운드 로빈 스케줄링

선점 방식, 시분할 시스템을 위해 고안됨 방식

각 프로세스들이 같은 크기를 할당 받으며 할당 시간내에 완료하지 못하면 뒤로 보내짐

항당시간이 길면:순서대로 진행됨 

짧으면: 오버해드가 발생 

 

다단계 큐

선점 방식, 큐가 여러개 프로세스의 요구에 따라 같은 유형의 큐에 할당함

각 큐별로 개별적인 스케줄 알고리즘을 가짐

다단계 큐

다단계 피드백 큐

선점 방식

일단 들어오면 제일 높은 큐에 특정 시간안에 못끝내면 다음 큐에 또 못끝내면 다음 큐에 못끝내면 다음큐에

짧은 작업 유리, 입출력 유리

새로운 프로세스는 큐잉 네트워크의 단계1큐에 추가되어, 그 프로세스는 FCFS에 의하여 CPU를 할당 받음(높은 우선순위 배정)

하위 단계 큐 일수록 cpu할당시간을 크게 설정함

다단계 피드백 큐

HRN스케줄링

비선점 방식 = 쭉~

SJF에 에이징 방식을 추가

우선순위 계산식에서 시스템 응답시간이 클수록 순위가 높아짐

우선순위 = 대기시간+버스트시간/버스트시간

짧은 작업이나 대기시간이 큰 작업일수록 우선순위가 높아짐

HRN 스케줄링