[운영체제] 프로세스 관리 - 프로세스 스케줄링, CPU 스케줄링

운영체제는 다수의 프로세스를 효율적으로 실행하기 위해 프로세스의 생명주기를 제어하는 프로세스 스케줄링 기능을 수행한다. 프로세스 스케줄링은 역할별로 단계를 나누어 new, ready, running, wait, suspend 상태로의 이전을 관리한다.

프로세스 스케줄링

프로세스 생명주기

장기 스케줄러(Long-term scheduling)

• 프로세스 생성(new) -> ready 로의 스케줄링을 담당한다.
• 활성화할 프로세스 수를 결정하는 역할
• Job 스케줄링이라고도 부름

중기 스케줄러(Middle-term scheduling)

• ready -> suspended, wait -> suspended
• 시스템의 과부하를 막기위해 활성화된 프로세스 수를 조정하는 역할

단기 스케줄러(Short-term scheduling)

• ready -> running -> waiting -> ready
• CPU 자원을 할당받을 프로세스를 교체하는 작업을 한다.
• 일반적으로 CPU 스케줄링이라고 부름

CPU 스케줄링

만약 한 프로세스가 CPU 자원을 독점한다면 무슨 일이 일어날까? 다른 프로세스들은 해당 프로세스가 종료될때까지 실행되지 못한채 무한대기 상태로 있을 것이다. 이러한 문제가 일어나지 않게 프로세스들에게 적절하게 CPU 자원을 할당하는 것이 CPU 스케줄링의 역할이다. 즉, CPU 스케줄링이란 시스템 성능 최적화를 위해 프로세스들에게 CPU 자원을 효율적으로 할당하기 위한 방법이다.

CPU 스케줄링의 목적

• 효율성 - 시스템 자원이 유휴 시간없이 사용
• 공평성 - 모든 프로세스에 자원을 공평하게 배분
• 확장성 - 프로세스 수가 증가해도 안정적이게 작동
• 안정성 - 자원 독점을 하는 프로세스로부터 자원을 보호

CPU 스케줄링 알고리즘의 선택기준(척도)

‘어떤 알고리즘이 좋은 알고리즘일까?’ 이 질문에 대한 대답을 내리기 위해선 평가기준이 필요하다. CPU 스케줄링을 위한 알고리즘을 선택할 때도 이러한 기준이 존재한다.

• CPU 사용률(CPU utilization)
  • 전체 시스템 동작시간 중 CPU가 사용된 시간
  • 클수록 좋음
• 처리량(throughput)
  • 단위 시간당 작업을 마친 프로세스 수
  • 클수록 좋음
• 대기 시간(waiting time)
  • 프로세스가 ready 상태에서 대기하는 시간
  • 짧을수록 좋음
• 응답 시간(response time)
  • 첫 프로세스 시작 후 첫 뻔재 출력이 나오기까지의 시간
  • 대기시간을 포함함
  • 짧을수록 좋음
• 반환 시간(turnaround time)
  • 대기시간과 실행시간의 합
  • 짧을수록 좋음

CPU 스케줄링 알고리즘

CPU 스케줄링은 프로세스 실행도중 CPU자원을 빼앗을 수 있느냐 없느냐를 기준으로 비선점형과 선점형방식으로 나뉜다.

구분	비선점형 (non-preemptive)	선점형(preemptive)
방식	👉 실행중인 프로세스로부터 CPU를 빼앗지 못함 👉 실행중인 프로세가 완료 또는 대기 상태가 될 때까지 계속 실행	👉 실행중인 프로세스로부터 CPU를 빼았음 👉 일정시간 이후 다른 프로세스 실행
장점	문맥교환이 적어 오버헤드가 적음	CPU 독점이 불가해 빠른 응답시간을 가짐
단점	전체적인 시스템 성능이 좋지않음	잦은 문맥교환으로 인한 오버헤드가 큼
알고리즘	FCFS, SJF, HRN	RR, SRT, MLQ, MLFQ

비선점형 스케줄링 기법

1. FCFS(First Come First Served)
   • 준비큐에 들어온 프로세스를 순서대로 실행
   • 프로세스별 우선순위 존재하지 않는다.
   • convoy effect 문제 발생
2. SJF(Shortest Job First)
   • 실행시간이 짧은 프로세스에게 우선순위 부여하여 먼저 실행
   • 실행시간을 정확하게 예측하긴 어려움
   • convoy effect를 완화
   • starvation 문제 발생
3. HRN(Highest Response Ratio Next)
   • 응답률( (대기시간 + 실행시간)/실행시간 )이 높은 프로세스를 먼저 실행
   • 실행시간을 정확하게 예측하긴 어려움
   • starvation 문제를 완화했지만 여전히 존재함

🤔 프로세스의 실행시간 예측이 어려운이유
외부 요인에 대한 영향(I/O 장치의 성능에 따라 달라짐), 하나의 프로세스가 여러 CPU 코어에서 실행 등으로 인하여 정확한 실행시간을 예측하긴 여렵다

💡 convoy effect
실행 시간이 긴 프로세스가 먼저 실행되어 실행시간이 짧은 프로세스는 실행이 계속 지연되는 문제로 전체적인 효율을 떨어뜨리는 현상

💡 starvation
우선순위가 높은 프로세스로 인해 운선순위가 낮은 프로세스의 실행이 계속 지연되는 문제로 특정 프로세스가 자원할당을 받지 못하는 현상

선점형 스케줄링 기법

선점형 스케줄링은 대부분 시분할 시스템으로 동작한다. 시분할 시스템이란 일정 시간(Time slice)동안만 CPU를 할당받는 것으로 시간이 지나면 다른 프로세스에게 CPU 사용권이 넘어간다.(선점형)

1. RR(Round Robin)
   • FCFS + 시분할시스템 - 먼저 도착한 프로세스 먼저실행
   • Time slice가 크면 FCFS와 비슷해지고 작으면 잦은 문맥교환으로 인한 오버헤드가 생김
2. SRT(Shortest Remaining Time)
   • SJF + 시분할시스템 - 남은 실행시간이 짧은 프로세스에게 우선순위를 줌
   • SJF의 문제점과 동일하게 Startvation 현상이 발생할 수 있음
3. MLQ(Multilevel Queue)
   • 우선순위에 따라 여러 큐를 사용
   • 우선순위가 높은 큐의 프로세스를 모두 실행완료해야 다음 큐의 프로세스 실행
     -> 우선순위가 높은 큐일수록 작은 time slice 사용
   • 고정 우선순위 방식
     -> 프로세스의 우선순위는 변하지 않음(다른 우선순위의 큐로 이동되지 않음)
     -> 프로세스 실행 후 완료되지 않았으면 기존 큐의 끝으로 이동
   • starvation 문제 발생
4. MLFQ(Multilevel Feedback Queue)
   • 우선순위에 따라 여러 큐를 사용
   • 우선순위가 높은 큐의 프로세스를 모두 실행완료해야 다음 큐의 프로세스 실행
   • 변동 우선순위 방식
     -> 프로세스 실행 후 실행완료되지 않으면 우선순위가 낮아짐
     -> 즉, 우선순위가 낮은 큐로 적재됨
   • 현재 운영체제들의 일반적인 스케줄링 방식