Process State
Active status
- 프로세스의 상태를 정리해보자.
- 생성, 준비, 실행, 대기, 완료 -> 5가지 상태
Ready
- cpu 스케줄러의 호출을 기다리는 상태
Running
- cpu를 사용하고 있는 상태
- I/O 요청 시 cpu를 뺏김 -> I/O까지 wait
- timeslice를 모두 소모하면 뺏김
Waiting
- blocking status
- 입출력이 완료될 때까지 기다리는 상태이다.
- 입출력이 끝나면 인터럽트 발생
- 해당 프로세스 준비 상태로 이동
Zombie
- pcb만 남기고 다 지워짐
- 이후 부모에게 신호를 보낸다. ( 회수 요청 )
- 부모 프로세스는 wait 시스템 콜을 통해 자식 프로세스의 종료 상태를 읽어 들인다.
- 부모가 os에게 자식이 종료되었는지 확인함
- 이후 완전히 pcb까지 소멸된다.
고아 프로세스
부모가 wait 대신 그냥 종료되버림
init을 부모로 삼는다. init은 주기적은 wait 요청으로 고아를 거둠
특별한 상태
휴식 상태
- pause status
- 작업을 일시적으로 쉬고 있는 상태
보류 상태
- suspend status
- 메모리에서 잠시 쫓겨난 상태
- 메모리가 꽉차서 밀려남
- 오류 발생
- 바이러스, 악의적 행동
- 매우 긴 주기
- 입출력 계속 지연
- 메모리 밖인 swap area에 보관됨
- 이후 보류 준비 상태를 지나 준비 상태로 이동한다.
Process scheduler
- cpu 스케줄러는 프로세스의 모든 상태 변화를 조정한다.
- 목적은 찾아보자
스케줄링 단계
- 스케줄링은 3단계로 나뉜다.
- 고수준 스케줄링
- 저수준 스케줄링
- 중간 수준 스케줄링
High level scheduling
- 작업 스케줄링 ( job )이라고도 부른다. 전체 작업 수를 조절한다.
- 작업은 os의 가장 큰 일의 단위로 하나 혹은 여러 개의 프로세스로 이루어진다.
- 작업이 시작되면 자원이 소모되기에 기존 작업에 영향이 간다.
- 이에 작업을 승인할지 거부할지 결정한다.
- Admission scheduling 승인 스케줄링이라고도 부른다.
- 동시에 실행 가능한 프로세스의 총 개수가 정해진다.
Middle level scheduling
- suspend와 active로 활성화된 프로세스 수를 조절한다.
- 일부 프로세스를 suspend 상태로 돌려 나머지가 원활하게 만든다.
- 고수준과 저수준 스케줄링 사이의 버퍼 역할
Low level scheduling
- cpu에 프로세스를 배당하는 작업을 한다.
- 빠르게 작동하여 short-term scheduling 이라도 부른다.
Preemptive & Non preemptive scheduling
- 선점형 스케줄링
- 운영체제가 강제로 cpu를 뺏을 수 있다.
- 비 선점형 스케줄링
- 운영체제가 강제로 뺏을 수 없다.
Preemptive
- 선점형 스케줄링은 인터럽트처럼 cpu를 뺏을 수 있다.
- 문맥 교환 같은 낭비가 생긴다.
- 시분할 시스템에 사용된다.
- 사실상 대부분
Non preemptive
- 한 프로세스가 실행 상태에 들어가면 프로세스가 멈추지 않으면, cpu를 뺏을 수 없다.
- 스케줄링이나 문맥 교환의 오버헤드가 낮다.
- 다만 전체 시스템의 처리율이 떨어진다.
- 과거 일괄 작업 시스템에서 사용되었다.
Priority
- 프로세스는 큐로 관리된다.
- 이때 우선순위와 그 척도가 필요하다.
- 기본적으로 커널 프로세스가 일반 프로세스보다 우선순위가 높다.
- 임의로 사용자가 지정할 수 있다.
- 전면 프로세스가 후면 프로세스보다 우선순위가 보통 높다.
- 입출력 집중 프로세스가 cpu 집중 프로세스보다 보통 높다.
- 입출력 집중 프로세스는 cpu를 잠깐 쓰고 넘기기 때문이다.
Queue
cpu 사용하는 프로세스들
- pcb를 연결한 큐가 있다.
- 이때 우선순위에 따라 여러 큐를 만들어 multiple queue로 관리된다.
- 모두 검색하는 오버헤드를 줄임
- 이때 bitmap 배열을 이용해서 해당 우선순위의 큐가 pcb(task)를 가지고 있는지 확인한다.
- 만약 1이라면 해당 큐를 순회하며 cpu를 할당한다.
- 프로세스가 time slice를 모두 소모하면 expired array로 넘어간다.
- 해당 우선순위에 맞게
- active array가 사용이 다 되면 expired 에 time slice를 배정하고 active array로 바꾼다.
대기 상태의 프로세스들
위에서 설명한 큐는 실행 상태를 다룬다.
- 대기 상태의 프로세스도 큐를 가지고 있다.
대기 상태 다단계 큐는 같은 입출력 장치끼리 모아 놓는다.
- 입출력이 동시에 끝나면 여러 인터럽트가 한번에 처리된다.
- 이를 위해 인터럽트 벡터를 사용하며 입출력이 완료된 pcb 들은 준비 상태로 이동한다.
정리
Scheduling algorithm
- 스케줄링 알고리즘을 알아보자.
종류
| 구분 | 종류 |
|---|---|
| 비선점형 | FCFS, SJF, HRN |
| 선점형 | 라운드 로빈, SRT, 다단계 큐, 다단계 피드백 큐 |
| 둘 다 가능 | 우선순위 스케줄링 |
성능 기준
- 대기 시간 : 프로세스 생성 후 실행까지 걸린 시간
- 응답 시간 : 첫 작업을 시작한 후 첫 번째 반응까지 걸린 시간
- 실행 시간 : 프로세스 작업이 시작된 후 종료되기까지 시간
- 반환 시간 : 대기 시간을 포함하여 실행이 종료될 때까지의 시간
기준
- 보통 스케줄링 알고리즘 성능 비교에는 평균 대기 시간을 사용한다.
- 모든 프로세스들이 실행되기까지 걸린 대기 시간의 평균
- 다만 순서나 작업 패턴에 따라 역전되기도 한다.
FCFS
- 비선점형 방식
- first come first served
- 선입선출 스케줄링
- 큐가 하나라 모든 프로세스는 우선순위가 동일하다.
- 즉 하나씩 순서대로 실행된다.
- 일괄 작업 시스템
단점
- convoy effect
- 입출력 요청시 cpu가 놀게됨
SJF
- 비선점형 방식
- shortest job first
- shortest process first, 최단 프로세스 우선 스케줄링
- 실행 시간이 가장 짧은 작업부터 cpu를 할당
- convoy 효과를 완화함
단점
- 운영체제가 프로세스의 종료 시간을 정확히 예측하기 어렵다.
- 즉 프로세스의 작업 길이를 알아야 스케줄을 하는데 길이를 모른다.
- 현대 프로세스는 사용자와의 상호작용이 빈번하기 때문이다.
- 고로 적용하기 어렵다.
- 즉 프로세스의 작업 길이를 알아야 스케줄을 하는데 길이를 모른다.
- 공평하지 않다.
- starvation
- infinite blocking
- 이를 완화하기 위한 방법으로 aging이 있으나 기준 선정의 한계가 있다.
HRN
- 비선점형
- highest response ratio next
- SJF의 아사 현상을 해결하기 위한 알고리즘이다.
- HRN은 서비스를 받기 위해 기다린 시간과 cpu 사용 시간을 고려하여 스케줄링한다.
- 즉 대기 시간을 고려해 아사를 완화한다.
- 스케줄링에 에이징을 구현한 것
단점
- 여전히 공평성이 위배되어 많이 사용되지 않는다.
RR
- 선점형 알고리즘 중 가장 단순하고 대표적인 방식
- round robin
- 한 프로세스가 할당 받은 시간 동안만 작업하고 큐의 맨 뒤로 보내지는 알고리즘
- 완료 될 때까지 계속 순환
- FCFS와 차이점은 time slice가 있다는 것이다.
- 이는 convoy 효과를 완화한다.
유의점
- 문맥 교환에 대한 오버헤드를 생각해야 한다.
- 이에 타임 슬라이스의 크기가 중요하다.
- 타임 슬라이스가 너무 크면 FCFS와 다르지 않다.
- 타임 슬라이스가 너무 작으면 문맥 교환 오버헤드가 커진다.
SRT
- shortest remaining time
- 최소 잔류 시간 우선 스케줄링
- SJF와 RR을 혼합한 방법
- 기본적으로 RR 이다.
- 다만 작업 시간이 가장 적은 프로세스를 선택하여 cpu를 할당한다.
단점
- 실행중인 프로세스와 큐의 프로세스들의 시간을 주기적으로 계산해야한다.
- 문맥 교환 오버헤드
- 프로세스의 종료 시간 예측 어려움, 아사 현상
- 잘 안쓰임
Priority
- 중요도를 기준으로 우선 순위를 반영해 스케줄링한다.
단점
- 공평성 위배와 아사 현상
MLQ
MultiLevel Queue Scheduling 다단계 큐 스케줄링
우선 순위에 따라 준비 큐를 여러 개 사용하는 방식
고정형 우선순위를 사용한다.
- 프로세스가 시간을 소모하면 원래 큐로 돌아간다.
- 상단의 큐의 모든 프로세스의 작업이 끝나야 다음 큐의 작업이 실행된다.
- 선점형 방식으로 우선순위가 높은 프로세스가 먼저 작동한다.
- 만약 하위 큐의 프로세스 진행 중 상위 단계 큐에 프로세스가 도착하면 뺏어버림
각각의 큐에 대한 다른 스케줄링 알고리즘 적용가능하다.
큐의 우선순위에 따라 타임 슬라이스를 조절할 수 있다.
단점
- 우선 순위가 높은 큐가 완료되어야 다음 큐가 실행된다.
- 기아 현상
MFQ
- multilevel feedback queue
- 우선순위가 낮은 프로세스들의 문제를 보완한 방식
- cpu를 사용한 프로세스는 우선순위가 한 단계 낮아진다.
- 즉 다음 단계 큐로 들어간다.
- 우선순위에 따라 큐의 타임 슬라이스가 다르다.
- 낮은 순위는 cpu를 얻을 확률이 상대적으로 낮다.
- 그래서 오래 사용하도록 타임 슬라이스를 크게 만들어준다.
- 마지막 큐의 타임 슬라이스는 무한대의 타임 슬라이스를 가지며 이는 FCFS 로 동작하는 것과 같다.
- MFQ는 오늘날의 운영체제가 사용하는 방식이다. 변동 우선순위 알고리즘의 전형적인 예이다.
물론 커널 프로세스는 일반 프로세스의 큐로 삽입되지 않는다.
룰
- 짧은 작업에 우선권이 있다.
- 입출력 관련 프로세스에 우선권을 준다.
