스케줄링의 개요
1. 스케줄링이란?
CPU 스케줄은 프로세서 스케줄러라고도 불리며 포르세스에 CPU와 시스템 얼마나 어
덯게 배정할지를 결정하는 작업이다.
1.1 고수준 스케줄링
가장 큰 단위의 CPU 스케줄링을 고수준 스케줄링이라고 한다.
시스템 전체 작업수를 조종하며 동시에 실행가능한 프로세스의 총개수가 정해진다.
스케줄링의 단계는 위 사진으로 정리해볼 수 있다.
고수준 스케줄링
전체 시스템의 부하를 고려하여 작업을 초기 시작을 관리한다. 고수준 방식이긴 하지만 스레드 방식으로 쪼개질 수 있다.
(규모가 큰 일괄 작업을 처리할 때 사용)
중간 수준 스케줄링
고수준 스케줄링 대신 프로세스의수를 조절해서 시스템의 부하를 최소화 시킨다.
저수준 스케줄링
저수준 스케줄링에서는 실제로 프로세스가 진행되며 필요 상태에 따라 준비 상태에 있는 프로세스를 싱행 상태나 대기 상태로 보내기도 한다.
고수준 스케줄링이 안된다면?
사실 일반 PC에서는 고수준 스케줄링이 없어도 충분히 프로세스가 실행된다.
하지만 특정 서버 관리면에서는 고수준 스케줄링이 필수적이다.
만약 고수준 스케줄링 지원되지 않는다면
대량의 이용자가 한 순간에 접속하는 대학교 수강신청 서버가 진작에 터질 것이다.
아직도 수강신청 서버가 말은 안들을때가 있지만
그래도 고수준 스케줄링으로 필터링을 하기 때문에 조금이나 오류를 줄일 수 있다.
1.1 스케줄링의 목표
공평성
효율성
안정성
확장성
반응 시간 보장
무한 연기 방지
위 목표들을
결국 OS 궁극적인 목표인
편리한 인터페이스 제공과 자원의 효율화로 묶어 정리할 수 있다.
스케줄링 시 고려 사항
1. 선전형 스케줄링과 비선점형 스케줄링
선점형 스케줄링 : CPU를 빼앗을 수 있는 방식
비선점형 스케줄링 : CPU를 빼앗을 수 없는 방식 (과거 일괄 작업 시스템에서 사용하던 방식)
대립의 개념은 아니다. 선점형이 문맥교환의 빈도가 더 높다.선점형 스케줄링와 비선점형 스케줄링
|
선점형 |
비선점형 |
|
|
개념 |
어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식 |
어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식 |
|
작업 방식 |
실행 상태에 있는 작업을 중단시키고 새로운 작업을 실행 가능 |
CPU 스케줄러의 작업량이 적고 문맥 교환의 오버헤드가 적다. |
|
장점 |
프로세스가 CPU를 독점할 수 없어 대화형이나 시분할 시스템에 적합 |
CPU 스케줄러의 작업량이 적고 문맥 교환의 오버헤드가 적다. |
|
단점 |
문맥 교환의 오버헤드가 많다. |
기다리는 프로세스가 많아 처리율이 떨어진다. |
|
사용 |
시분할 방식 스케줄러에 사용 |
일괄 작업 방식 스케줄러에 사용 |
|
중요도 |
높다 |
낮다 |
2. 프로세스 우선순위
여기서 우선순위 PCB할당하는 프로세스의 중요도를 의미한다.
즉 프로세스의 중요도가 다르다는것을 뜻한다.
프로세스의 우선순위를 교통에 비유해볼 수 있다.
우리가 정체가 심한 합류 구간에서
한 대 한 대 번갈아가면서 진입하는 암묵적인 규칙이 있는 것 처럼( 이게 맞는 규칙인지는 모르겠다)
일정한 규칙으로 도로 위를 지나간다.
이 도로위의 차를 스레드로 표현하고
신호등이나 표지판을 CPU라고 표현해볼 수 있겠다.
이렇게 일정 규칙이 있는 도로 위에서도
응급차가 지나가면
도로를 터준다.
우선순위가 높기 때문이다.
이처럼 프로세스 안에서도 우선순위가 존재한다.
프로세스는
커널 프로세스와 일반 프로세스로 나뉘며
커널 프로세스가가 우선순위가 더 높다.
결론 : 내부 작업(커널 프로세스) > 사용자
3. CPU 집중 프로세스와 입출력 집중 프로세스
프소세스는 CPU를 사용하여 작업을 하는 실행 상태 또는 입출력을 요청하여 완료되기까지 기다리는 대기 상태에 있는데 이때 CPU를 할당받아 실행하는 작업을
CPU 버스트,
입출력 작업을
입출력 버스트라고 불린다.
요약
CPU 버스트 - 사용자 프로그램이 CPU를 직접 가지고 빠른 명령을 수행하는 일련의 단계
입출력 버스트 - 요청이 발생해 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계
CPU 집중 프로세스 : CPU가 버스트가 많은 프레세스로 연산 기능을 주로 담당.
입출력 집중 프로세스 : 입출력 버스트가 많은 프로세스로 저장장치에서 데이터를 복사하는 기능을 주로 담당.
CPU 집중프로세스, 입출력 집중 프로세스 중 어떤 프로세스 먼저 우선 배정?
CPU 집중 프로세스보다 입출력 집중 프로세스를 먼저 처리하는 것이 효율적이다.
그 이유는 CPU는 처리 기간이 길기 때문에 먼저 처리하면 CPU의 대기 상태가 길어지기 때문이다.
입출력 프로세스는 잠깐 CPU를 사용한 후 대기 상태로 이동하기 때문에 다른 프로세스가 CPU를 사용할 수 있다.
4. 전면 프로세스와 후면 프로세스
전면 프로세스 : 현재 입력과 출력을 사용하는 프로세스로 GUI를 사용하는 운영체제에서 화면 맨 앞에 놓인 프로세스 (상호작용 가능)
EX : POWERPOINT
후면 프로세스 : 사용자의 상호작용이 없이 작동하기 때문에 일괄작업 프로세스라고 함 ( 우선순위는 후면 프로세스가 높음)
EX : 압축 프로그램
결론
- 높은 프로세스 : 커널, 전면, 대화형, 입출력 집중- 낮은 프로세스 : 일반, 후면, 일괄 작업, CPU 집중
다중 큐
1. 준비 상태의 다중 큐
PCB에 프로세스의 중요도 표시되지만
항상 PCB에 담겨져 있는 중요도를 읽기는 효율성이 떨어진다.
그렇기 때문에
중요도(우선순위)에 따라 PCB를 정렬 해놓으면 프로세스를 간결시킬 있다.
이렇게 우선순위별로 정리한 상태를 준비 상태의 큐라고 한다.
준비 상태의 다중 큐 : 프로세스를 할당 받아 실행하려고 기다리는 프로세서들의 대기
고정 우선순위 방식 : 운영체제가 프로세스에 우선순위를 부여하면 프로세스가 끝날 때까지 바뀌지 않음.
변동 우선순위 방식 : 프로세스가 작업 중간 변하는 방식 (시스템의 효율을 높임)
2. 대기 상태의 다중 큐
시스템 내에는 입출력장치가 있기 때문에 PCB 블록이 한 곳에서만 모아저 있으면
효율을 떨어트린다.
그렇기 때문이 대기중인 생태의 PCB연결들을 큐로 정리한다.
이때 같은 입출력을 요구한 프로세스들끼리 묶어논다.
하이패스와 다중 큐의 관계
하이패스 전용도로와 큐의 관계를 나타낼 볼 수 있겠다.
하이패스가 부착이 된 차량과 그렇지 않은 차량이
한 입구로 들어가게 된다면 교통이 정체될 수 있다.
그렇기 떄문에 하이패스 부착 유무에 따라
우선순위를 정하고
길을 정리한것을 프로세스의 PCB들을 큐로 묶은 것으로도 비유해볼 수 있겠다.
준비 상태와 다중 큐 대기 상틔태의 다중큐의 차이
준비큐는 한번의 하나의 프로세스를 꺼내어 cpu를 할당하지만 대기 큐는 여러 개의 PCB을 동시에 꺼내애 준비 상태로 옮긴다.
스케줄링 알고리즘
스케줄링은 크게 비선점형 알고리즘과 선점형 알고리즘으로 나누어진다.
스케줄링 알고리즘 선택 기준
- CPU 사용률 : 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법
- 처리량 : 단위 시간 당 작업을 마친 프로세스의 수
- 대기시간 : 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간
- 응답시간 : 프로세스 시작 후 첫번째 출력 또는 반응이 나올 때까지 걸리는 시간
- 반환 시간 : 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간
비선점형 알고리즘
1. FCFS 스케줄링
- 준비 큐에 도착한 순서대로 CPU를 할당하는 방식
- 프로세스가 큐에 도착한 순서대로 실행되며, 한 번 실행되면 그 프로세스가 끝나야만 다음 프로세스를 실행할 수 있다.
- 큐가 하나라 모든 프로세스는 우선순위가 동일하다.
- 콘보이(호위) 효과 : 단순하고 공평하지만, 처리시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들을 하염없이 기다려 시스템의 효율이 떨어지는 문제
- 현재 작업 중인 프로세스가 입출력 작업을 요청하는 경우 CPU가 작업하지 않고 쉬는 시간이 많아져 작업 효율이 떨어진다.
2. SJF 스케줄링
- 준비큐에 있는 프로세스 중에서 실행시간이 가장 짧은 작업부터 CPU를 할당하는 방식
- 프로세스에 CPU를 배정할 때 시간이 오래 걸리는 작업이 앞에 있고 간단한 작업이 뒤에 있으면 그 순서를 바꿔 실행
- 운영체제가 프로세스의 종료 시간을 정확히 에측하기가 어려워 사용하기가 힘들다.
- 실행시간이 긴 작업이 계속 연기되어 아사현상이 일어날 수 있다.
3. HRN 스케줄링
- SJF 스케줄링에서 발생할 수 있는 아사현상을 해결하기 위해 만들어진 비선점형 알고리즘
- 서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려해 스케줄링하는 방식
- 우선순위 = (대기 시간 + CPU 사용시간) / CPU 사용시간
선점형 알고리즘
1. 라운드 로빈 스케줄링
- 한 프로세스가 할당받은 시간(타임 슬라이스)동안 작업을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식
- 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행
- 평균 대기 시간이 같다면 문맥 교환 시간이 추가되어 비효율적
- 문맥 교환에 따른 추가 시간을 고려해 타임 슬라이스를 적절히 설정해야 한다.
- 타임 슬라이스가 너무 크면 하나의 작업이 끝난 뒤 다음 작업이 시작되는 것처럼 보인다.
- 타임 슬라이스가 작은 경우 사용자는 여러 프로스램이 동시에 실행되는 것처럼 느끼고, 문맥 교환에 많은 시간을 낭비해 실제 작업을 못하는 문제가 발생
2. SRT 스케줄링
- SJF 스케줄링과 라운드 로빈 스케줄링 방식을 혼합한 방식
- 기본적으로 라운드 로빈 스케줄링을 사용하지만, CPU를 할당박을 프로세스를 선택할 때 남아 있는 작업이 가장 적은 프로세스 선택
- 남은 시간이 적은 프로세스에 CPU 먼저 할당
- 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와 문맥 교환을 해야하므로 SJF에는 없는 작업이 추가
- 운영체제가 프로세스의 종료 시간을 정확히 에측하기가 어렵고, 아사현상이 일어날 수 있다.
3. 다단계 큐 스케줄링
- 고정형 우선순위에 따라 준비 큐를 여러 개 사용하는 방식
- 프로세스는 운영체제로 부터 부여받은 우선순위에 따라 해당 우선순위 큐에 삽입
- 우선순위에 따라 타임슬라이스를 조절 해 작업효율을 높일 수 있다.
4. 다단계 피드백 큐 스케줄링
- 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점 보완한 방식
- CPU를 사용하고 난 프로세스는 원래의 큐로 돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어간다.
- 우선순위가 낮은 큐의 타임슬라이스를 크게 설정
하이브리드 알고리즘
1. 우선순위 스케줄링
- 프로세스는 중요도에 따라 우선순위를 갖는데 이러한 우선순위를 반영한 스케줄링 알고리즘
- 어떤 기준으로 우선순위를 정하느냐에 따라 다양하게 구현
- 시스템의 효율성이 아닌 프로세스 중요도를 기준으로 결정
- 고정 우선순위 알고리즘 : 단순하게 구현할 수 있지만 시시각각 변하는 시스템의 상황을 반영하지 못해 효율성이 떨어진다.
- 변동 우선순위 알고리즘 : 일정 시간마다 우선순위를 새로 계산하고 이를 반영하기 때문에 시스템이 복잡하지만 시스템의 상황을 반영해 효율적인 운영이 가능하다.
연습문제
1. 고수준 스케줄링
2. 저수준 스케줄링
3. 선점형 스케줄링
4. 전면 프로세스
5. FCFS 스케줄링
6. SJF 스케줄링
7. 아사현상
8. aging
9. HRN 스케줄링
10. 라운드 로빈 스케줄링
11. 타임 슬라이스가 작을수록 프로세스 교체 빈도가 증가해 문맥 교환에 발생하는 오베헤드가 커지는 관계를 가지고 있다.
12. SRT 스케줄링
13. 다단계 큐 스케줄링
14. 다단계 피드백 큐 스케줄링
15. 무한대의 타임 슬라이스
16. 더 커진다.
17. FCFS
참고 웹사이트
"프로세스 스케줄링의 이해" SLIDEPLAYER. 2020년 7월 16일 접속,
https://slidesplayer.org/slide/16730305/
"CPU스케줄링" 즈오 티스뢰 블로그. 2020년 7월 16일 접속,
참고문헌
조성호.쉽게배우는 운영체제.2019발행.한빛아카데미
[별첨] 애플 인텔과 결별하고 멕에도 독자적인 CPU 적용?
2020년 6월 23일 애플의 WWDC 2020 행사에서
팀 쿡 CEO는
'오늘이 역사적인 날' 이라면서
자체 개발한 ARM 칩셋을 올해 말 맥북 및 아이맥 등에도 적용할 것이라고 밝혔습니다.
이렇게 자체개발 프로세스로 전홤함으로서
애플 더 높은 수준의 최적화된 스케줄 알고리즘과
훨씬 적은 전력 소비를 기대할 수 있게 되었으며
기존에는 애플과 PC에 적용되는 개발 아키텍쳐가 달랐지만
동일한 개발 방법으로 통합한데는 의의가 있다고 볼 수 있다.
이렇게 공식적으로
애플과 인텔의 결별로
인텔은 약 5%의 가량의 매출 및 상당한 브랜드 가치 상실이 예상된다고 한다.
하지만 애플도 CPU자체 개발에 있어서 특허 관련 부족으로 여러 난관이 있을것으로 예상되는데,
앞으로 애플의 행보가 기대가 된다.
출처 :https://www.youtube.com/watch?v=HXDKFhzI9k8
참고 웹사이트
"CPU 스케줄링 ."즈오블로그 2020년 7월 16일 접속,https://yunzuo.tistory.com/6
참고문헌
조성호.쉽게배우는 운영체제.2019발행.한빛아카데미