프로세스 상태, CPU 스케줄러

프로세스 상태

running state : 현재 cpu에서 실행 상태

ready state : cpu에서 실행 가능한 상태(실행 대기 상태)

block state : 특정 이벤트 발생 대기 상태( ex : 프린팅 완료)

 

스케줄러란

스케줄러는 레디 큐에 존재하는 프로세스들을 특정한 우선순위 기반으로 CPU를 할당받게 해주는 역할을 함

링크드 리스트, 해쉬 리스트, 비트 맵, 레드 블랙 트리(리눅스)로 구현

 

스케줄링 목적

1. 처리량 최대화 - 스케줄링 규칙은 단위 시간당 가능하면 많은 프로세스가 서비스를 받을 수 있도록 해야 함
2. 자원 활용도 최대화 - 시스템 자원을 부지런히 사용 해야 함
3. 무기한 연기 회피 - 프로세스들이 서비스를 받으려고 한 없이 대기하면 안됨
4. 우선순위 강화 - 시스템이 프로세스에 우선순위를 부여할 경우 스케줄링 메커니즘은 우선순위가 더 높은 프로세스를 선호 해야 한다
5. 오버헤드(처리를 하기 위해 들어가는 간접적인 처리 시간, 메모리) 최소화 - 오버헤드는 자원 낭비
6. 예측 가능성 보장 - 프로세스 반응 시간에 대한 통계적인 변량을 최소화함으로써 시스템은 프로세스가 예측 가능한 수준으로 서비스함을 보장

 

스케줄링 수준

1. 고수준 스케줄링 : 어떤 작업이 시스템에 들어갈 것인지 결정
2. 중간 수준 스케줄링 : 어떤 프로세스가 프로세서를 얻으려고 경쟁할 수 있는지 결정
3. 저수준 스케줄링 : 정책은 활성화된 프로세스 중 어떤 프로세스에 프로세스를 할당할지 결정

 

선점형/비선점형 스케줄링

1. 비선점형 스케줄링 : 
   1. 시스템이 일단 프로세스를 어떤 프로세스에 할당한 경우 프로세스로부터 프로세서를 강제로 빼앗지 않는다
   2. 비선점형 스케줄링 규칙에서는 각 프로세스가 프로세서를 할당받으면 작업을 완료할 때까지 혹은 프로세스가 자발적으로 프로세서를 반납할때까지 프로세서에서 실행 할 수 있다
2. 선점형 스케줄링
   1. 프로세서에서 프로세스가 실행 중일 때 시스템이 해당 프로세서를 빼앗을 수 없다
   2. 문맥전환을 일으킬 수 있다

 

스케줄링 알고리즘

비선점 스케줄링

1. FCFS(First Come, First Served)
   1. CPU를 처음 요구한 프로세스가 CPU를 처음 사용
   2. FIFO(First in First Out) 큐 자료 구조 사용해 구현
   3. CPU를 사용하고 있는 프로세스 자기 자신이 CPU를 놓아줄 때까지 CPU를 다른 프로세스에게 양보하지 않음
   4. 콘보이 효과 불러 일으킬수 있음
      1. 콘보이 효과란 CPU를 매우 오래 사용하는 프로세스가 도착하게 되면 다른 프로세스가 CPU를 사용하는 시간이 매우 커지는 현상을 말함
      2. 비선점 스케줄링을 사용할 때만 발생
   5. 장점 : FCFS는 모든 프로세스가 공평한 조건으로 CPU를 사용할 수 있게 해주면 반응시간 예측 가능
   6. 단점 : 대기 시간이 매우 긴 스케줄링 알고리즘

 

선점 스케줄링

1. SJF(Shortest Job First)
   1. 가장 시간이 적게 걸리는 작업을 먼저 함
   2. CPU 업데이트 될 때 가장 시간이 적게 걸리는 프로세스가 선택되어 실행
   3. SJF는 비선점 스케줄링, 선점 스케줄링 2가지 종류가 있음
   4. 선점형 SJF는 SRTF(Shortest Remaining Time First)라고도 한다
   5. 장점 : 평균 대기시간을 가장 적게 가지는 스케줄링 알고리즘
   6. 단점 :
      1. 최소의 오버헤드로 최적의 성능 보장하도록 구현하는 것이 힘듬
      2. 선점형 SJF에서는 프로세스끼리 끼어들기 때문에 CPU가 점유 시간을 예측하는것이 힘듬
2. Priority Scheduling
   1. 높은 우선순위를 가진 프로세스가 항상 먼저 CPU를 사용할 수 있도록 구현
   2. 우선순위가 낮은 프로세스는 영원히 작동하지 않을 수 있음
   3. 해결책 : Aging-method(레디 큐에서 오랜 시간을 기다린 프로세스의 우선 순위를 높히는 방법)
3. Round Robin(RR)
   1. Round Robin 스케줄링은 각각의 프로세스가 공평하게 시간 간격 동안 CPU를 활용할 수 있도록 하는 알고리즘
   2. 정해진 시간 간격이 끝나면 CPU를 사용하고 있던 프로세스는 선점적으로 추방(레디 큐에 다시 들어가게 된다.)
   3. Round Robin은 SJF 스케줄링 보다 반응 시간 최적화에 있어서 탁월 하지만 대기 시간 최적화가 떨어짐