1. CPU 스케줄링
스케줄링의 단계
고수준 스케줄링: 전체 시스템의 부하를 고려하여 작업을 시작할지 말지 결정
중간수준 스케줄링: 시스템에 과부하가 걸려서 프로세스 수를 조절해야 한다면 이미 활성화된 프로세스 중 일부를 보류 상태로 보냄
저수준 스케줄링: 실제 작업 수행
스케줄링의 목적
- 공평성: 모든 프로세스가 자원을 공평하게 배정받아야 함
- 효율성: 시스템 자원이 유휴 시간없이 사용되도록 해야하고, 유휴 자원을 사용하려는 프로세스에 우선권을 줘야함
- 안정성: 우선순위를 사용하여 중요 프로세스가 먼저 작동하도록 배정함으로써 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호해야함
- 확장성: 프로세스가 증가해도 안정적으로 작동하게 해야함
- 반응 시간 보장: 시스템은 적절한 시간안에 프로세스의 요구에 반응해야함
- 무한 연기 방지: 특정 프로세스의 작업이 무한히 연기되면 안됨
2-1. 선점형 스케줄링, 비선점형 스케줄링
선점형 스케줄링
- 운영체제의 판단하에 실행 상태에 있는 프로세스를 중단시키고 새로운 작업을 시작할 수 있는 방식
- 프로세스가 CPU를 독점할 수 없어 대화형 시스템, 시분할 시스템에 적합
- 대부분의 저수준 스케줄러는 선점형 사용
비선점형 스케줄링
- 프로세스가 실행 상태에 들어가면 프로세스가 종료되거나 자발적으로 대기 상태에 들어가기 전에는 계속 실행되는 방식
- 스케줄러의 작업량이 적고 문맥 교환 적음
- CPU 사용이 긴 프로세스가 있다면 사용시간이 짧은 프로세스가 기다리기 되어 전체 시스템의 처리율이 떨어짐
- 일괄 작업 방식 스케줄링에 사용
2-2. 프로세스 우선 순위
- 커널 프로세스 > 일반 프로세스
- 우선순위가 높은 프로세스가 CPU를 먼저, 오래 차지
2-3. CPU 집중 프로세스, 입출력 집중 프로세스
CPU 집중 프로세스
수학 연산같은 CPU를 많이 사용하는 프로세스, CPU 버스트가 많은 프로세스
입출력 집중 프로세스
저장장치에서 데이터를 복사하는 일 같이 입출력을 많이 사용하는 프로세스, I/O 버스트가 많음
우선 배정
- 스케줄링할 때, 입출력 집중 프로세스의 우선순위를 CPU 집중 프로세스보다 높이면 시스템 효율 향상
2-4. 전면 프로세스, 후면 프로세스
전면 프로세스
- GUI를 사용하는 OS에서 가장 앞에 있는 프로세스
- 현재 입출력을 사용하는 프로세스
- 사용자와 상호작용 가능한 프로세스
후면 프로세스
- 사용자와 상호작용이 없는 프로세스
- 사용자의 입력없이 동작하므로 일괄 작업 프로세스라고도 함
2-5. 정리
3-1. 준비 상태의 다중 큐
준비 상태의 다중 큐
- 프로세스는 준비 상태에 들어올 때마다 자신의 우선순위에 해당하는 큐의 마지막에 삽입
- CPU 스케줄러는 우선순위가 가장 높은 큐의 맨 앞에 있는 프로세스에 CPU 할당
- 0번큐, 1번큐, 2번큐에 각각 프로세스 (1, 2, 3) (4, 5, 6) (7, 8, 9)로 3개의 프로세스가 있다면 0번 큐의 1번 프로세스가 가장먼저 CPU에 할당됨
프로세스 우선순위 배정 방식
- 고정 우선순위 방식
- 운영체제가 우선순위를 부여하면 프로세스가 끝나기 전까지 변하지 않음
- 구현은 쉽지만, 작업 효율이 떨어짐
- 변동 우선순위 방식
- 생성시 부여받은 우선순위가 작업 중간에 변하는 방식
- 구현은 어렵지만, 작업 효율이 좋다
3-2. 대기 상태의 다중 큐
대기 상태의 다중 큐
- 효율을 위해 같은 입출력을 요구한 프로세스끼리 모아 놓음
- 준비 상태 큐는 한번에 하나의 프로세스를 CPU에 할당하지만, 대기 상태 큐는 여러 개의 PCB를 동시에 꺼내어 준비 상태로 옮김
- 대기 상태 큐에서 동시에 끝나는 인터럽트를 처리하기 위해 인터럽트 벡터라는 자료구조 사용
4. 스케줄링 알고리즘
스케줄링 알고리즘 평가 기준
대기 시간: 프로세스가 생성된 후 실행전까지 대기하는 시간
응답 시간: 첫 작업을 시작한 후 첫 번째 출력이 나오기까지의 시간
실행 시간: 프로세스 작업이 시작된 후 종료까지 걸리는 시간
반환 시간: 대기 시간을 포함해서 실행이 종료될 때까지의 시간
평균 대기 시간: 모든 프로세스 대기시간의 평균
FCFS 스케줄링
- 준비 큐에 도착한 순서대로 CPU에 할당하는 비선점형 방식
- 큐가 하나라 모든 프로세스 우선순위가 동일
FCFS 스케줄링 평가
- 처리시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들이 기다리는 시간 증가 → 효율 ↓
- 현재 작업중인 프로세스가 입출력을 요청하면 CPU가 쉬는 시간이 많아짐 → 효율 ↓
SJF 스케줄링(Shortest Job First)
- 준비 큐에 있는 프로세스 중 가장 실행시간이 짧은 것부터 CPU를 할당하는 비선점형 방식
- FCFS의 문제점 완화
SJF 스케줄링 평가
- OS가 프로세스의 종료시간을 정확하게 예측하기 어려움
- 작업시간이 길다는 이유로 뒤로 밀려 공평성이 떨어짐 → 아사(기아) 현상
- 에이징 → 아사 현상 완화, 양보할 수 있는 상한선을 정하는 방식, 양보할때마다 나이를 먹어 양보의 상한선에 다다르면 더 이상 양보 X
HRN 스케줄링(Highest Response Ratio Next)
- SJF의 아사 현상 해결하기 위한 비선점형 알고리즘
- 기다린 시간과 CPU 사용 시간을 고려해서 스케줄링
- 우선순위 = (대기시간 + CPU 사용 시간) / CPU 사용 시간
HRN 스케줄링 평가
- 실행시간이 짧은 프로세스를 우선으로 하면서도 대기 시간을 고려하여 아사현상 완화
- 그럼에도 공평성에 위배됨
라운드 로빈 스케줄링(Round Robin)
- 한 프로세스가 할당받은 시간(타임 슬라이스/타임 퀀텀)동안 작업을 하고 완료하지 못하면 준비 큐의 맨 뒤로 가서 대기하는 방식
- 선점형 알고리즘 중 가장 단순하고 대표적인 방식
- 모든 프로세스가 작업을 완료할 때까지 순환하며 실행
라운드 로빈 스케줄링 평가
- RR과 FCFS의 평균 대기시간이 같다면 RR이 더 비효율
- RR과 같은 선점형 방식에서는 문맥 교환 시간이 필요하기 때문
SRT 우선 스케줄링(Shortest Remaining Time)(First)
- 프로세스가 도착했을 때 실행중인 프로세스를 멈추고 스케줄링을 재실행
- 가장 남은 시간이 적은 프로세스를 실행함
- 선점형 방식
SRT 우선 스케줄링 평가
- 현재 프로세스와 큐에 남아있는 프로세스의 남은 시간을 계산하여 더 적은 프로세스와 문맥교환할 때 SJF에 없는 추가적인 계산이 들어감
- OS가 프로세스 종료 시간을 예측하기 어렵고 아사현상이 일어날 수 있어서 사용 잘 안함
우선 순위 스케줄링
- 미리 정해놓은 우선 순위에 따라 스케줄링
- 비선점형, 선점형 모두 적용 가능
- 고정 우선 순위 알고리즘: 한번 정한 우선 순위가 변동 X, 효율 떨어짐
- 변동 우선 순위 알고리즘: 일정 시간마다 우선 순위를 새로 계산해서 반영, 효율 증가
우선 순위 스케줄링 평가
- 아사현상 유발
- 준비 큐의 순서를 무시하고 우선 순위에 따라 바꿔야하기 때문에 오버헤드 발생, 효율 ↓
다단계 큐 스케줄링
- 우선 순위에 따른 큐를 여러 개 사용하는 방식
- OS로부터 부여받은 우선 순위에 따라 프로세스가 삽입
- 고정형 우선 순위 사용
- 상단 큐의 작업이 모두 끝나야 그 다음 큐의 작업 실행
다단계 피드백 큐 스케줄링(MLFQ; Multi-Level Feedback Queue)
- 프로세스가 CPU를 할당받을 때마다 프로세스 우선 순위를 낮춤
- 우선 순위에 따라 타임 슬라이스 크기가 다름
- 우선 순위가 낮은 큐는 타임 슬라이스가 큼
- 마지막 큐의 타임 슬라이스는 무한대 + FCFS 스케줄링 방식으로 동작
5. 인터럽트
폴링
입출력을 요청하면 OS가 주기적으로 입출력 장치를 직접 확인해서 처리하는 방식
인터럽트
입출력을 요청하고 입출력이 완료되면 이벤트를 발생시켜 알림
동기적 인터럽트
- 프로세스가 실행중인 명령어로 발생
비동기적 인터럽트
- 하드웨어적 오류로 발생
인터럽트 처리 과정
- 인터럽트가 발생하면 현재 실행중인 프로세스는 일시정지 상태, 재시작을 위한 정보 저장
- 인터럽트 컨트롤러가 인터럽트 실행 순서 결정
- 정해진 순서에 따라 인터럽트 벡터에 등록된 인터럽트 핸들러가 이를 실행
- 인터럽트 처리를 마치면 일시정지된 프로세스 재실행 or 종료
'Computer Science > 운영체제' 카테고리의 다른 글
5. 프로세스 동기화 (0) | 2024.08.01 |
---|---|
3. 프로세스와 스레드 (0) | 2023.10.16 |
2. 컴퓨터 구조와 성능 향상 (0) | 2023.10.16 |
1. 운영체제 개요 (0) | 2023.10.16 |