[OS] Operating System - CPU Scheduling

CPU Scheduling

 

스케줄링은 멀티프로그래밍을 위한 운영체제의 기본 개념이다.

• 멀티프로그래밍
  • 여러 프로세스가 같은 시간 내에 동시에 운용이 되는 것
  • CPU의 사용률을 최대로 사용하는 것이다.
• CPU 스케쥴러
  • 메모리에 존재하는 프로세스 중에 하나의 프로세스를 고르는 것
    • 이때 메모리에 존재하는 모든 프로세스가 선택의 조건을 만족하는 것이 아니다. 
    • 프로세스 중에서 준비-ready 상태에 있는 프로세스만 자원 할당의 대상이 될 수 있다.
  • 메모리에 존재하는 프로세스는 스케줄러에 의해 ready queue에서 선택되면 CPU에 할당이 된다.
• DIspatcher - 디스패처
  • CPU 스케줄링 과정의 일부, 다음 실행될 프로세스에게 CPU 제어권 전달의 역할
  • 문맥교환, 프로세스 전환, 스케줄링 정보 유지를 담당하고 있다.
  • 특징
    • 낮은 오버헤드
      • 디스패처는 빠른 동작을 요구
      • 디스패처 지연은 최소화되어야 하며, 프로세스가 실행 상태로 전환되기까지 걸리는 시간을 의미
    • 효율성
      • 시스템의 전반적인 성능과 반응성 향상
    • 자동화
  • 스케줄러의 경우 실행될 프로세스를 결정하는 역할이며, 디스패처의 경우 CPU에 실제로 할당하는 작업을 담당

디스패처 지연(Dispatcher latency)

• Scheduling Criteria
  • CPU 스케줄링 알고리즘의 성능을 평가하는 데 사용되는 지표
  • 기준
    • CPU Utilization : CPU가 활동적으로 작업을 수행하는 시간 비율
    • 처리랑 : 단위 시간당 시스템이 완료하는 작업의 수
    • 대기 시간 : 프로세스가 준비 큐에서 실행을 기다리는데 소요된 총 시간
    • 응답 시간 : 사용자나 프로세스가 요청을 한 후 첫 번째 응답을 받기까지의 시간
    • 턴 어라운드 시간 : 프로세스가 시작되어 완료될 때까지의 걸리는 총 시간

 

Preemptive vs Non-preemptive

 

Preemptive(선점형) vs Non-preemptive(비선점형)

 

스케줄링의 두 가지 주요 접근 방식이다. 각각의 특성은 아래 정리한 바와 같다.

 

• 선점형 스케줄링
  • 운영체제가 현재 실행중인 프로세스를 CPU에서 임시로 제거(선점)하고 다른 프로세스에 우선권 제공
  • 스케줄러는 현재 실행 중인 프로세스를 중단 및 일시 중지를 할 수 있다.
  • 중지된 프로세스는 ready queue로 이동하고 다른 프로세스가 CPU를 할당받는다
  • 특성
    • 프로세스 간의 전환이 더 활발하게 발생한다. 다만 자주 발생하기에 그만큼 문맥교환도 일어난다
    • 지나친 문맥교환으로 인해 오버헤드의 발생 가능성이 존재한다
    • 시간 공유 시스템 및 대화형 환경에 더 적합하다
  • 종류
    • 라운드 로빈, 우선순위 스케줄링, 다중 레벨 큐 스케줄링
• 비선점형 스케줄링
  • 프로세스가 CPU를 받으면, 해당 프로세스가 할당 해제하기 전까지 CPU를 유지
  • 프로세스가 종료하거나 대기상태로 전환되기까지 계속 실행이 된다
  • 특성
    • 프로세스가 CPU를 양보하지 않는 한, 문맥교환이 필요 없기에 구현의 간소화
    • 문맥 교환의 횟수가 더 적기에 선점형 스케줄링에 비해 오버헤드의 가능성이 낮다
    • 긴 작업을 수행하는 프로세스가 다른 프로세스를 차단하여 대화형 시스템에서는 성능이 저하될 수 있다
  • 종류
    • 선입선 처리(FCFS), 최단 작업 우선(SJF)

---

대화형 시스템

• 사용자와 컴퓨터 간의 양방향 통신을 가능하게 하는 컴퓨터 시스템
• 사용자의 입력에 반응 및 결과 제공이 가능

---

특징

• 즉시 반응
  • 사용자가 입력을 제공하면, 시스템은 거의 즉시 반응하여 결과 표시 및 피드백 제공
• 사용자 인터페이스
  • GUI 혹은 텍스트 기반 인터페이스를 포함해 사용자 친화적 인터페이스를 제공
• 다중 작업 처리
  • 사용자의 다양한 요구를 동시에 처리
  • 여러 프로그램 혹은 탭을 동시에 열고 작업 가능
• 사용자 중심 설계
  • 사용자의 편의성 및 효율성을 중심으로 설계
  • 사용자 경험(UX)에 큰 중점을 둠
• 대화형 프로세스
  • 사용자의 요구에 따라 실시간으로 처리과정을 변경하거나 조정 가능

---

예시

• 운영체제
• 웹 브라우저
• 모바일 앱

 

선점형 스케줄링

 

• RR - 라운드 로빈
  • 각 프로세스에게 동일한 크기의 시간 할당량 부여, 할당 시간이 끝나면 현재 진행하는 프로세스는 준비 큐의 끝으로 이동하고 다음 프로세스에게 CPU 할당
  • 장점 
    • 모든 프로세스에게 동등한 기회 제공
  • 단점
    • 시간의 할당량이 중요하다. 크기에 따라 문맥교환에 따른 오버헤드 발생의 정도가 틀려지기 때문
• Priority Scheduling - 우선순위 기반 스케줄링
  • 각 프로세스에 우선순위 부여, 높은 순서대로 프로세스에 세 먼저 CPU를 할당, 순위가 같을 경우 RR의 방식을 적용
  • 장점
    • 중요한 작업의 빠른 처리
  • 단점
    • 낮은 순위의 프로세스는 기아상태(Starvation)에 빠질 수 있음
• Multilevel Queue - 다단계 큐
  • 프로세스를 여러 큐에 우선순위에 따라 분류, 각 큐에 다른 스케줄링 알고리즘을 적용
  • 장점
    • 다양한 프로세스 유형(시스템 프로세스, 사용자 프로세스 등)을 효과적으로 관리
  • 단점
    • 큐 간의 밸런스를 맞추는 것이 어려울 수 있다.

 

 

비선점형 스케줄링

 

• FCFS - First Come First Served - 선입선 처리
  • 준비 큐에 도착한 순서대로 CPU를 할당
  • 장점
    • 공정성 : 도착 순서대로 처리되기에 공정한 방식으로 프로세스 처리가 가능
    • 구현 용이성 : 구현이 매우 간단하여 추가적인 오버헤드가 거의 없음
  • 단점
    • 컨보이 효과
• SJF - Short Job First - 최단 작업 우선
  • 프로세스 실행 시간을 고려하여 스케줄링 진행, 실행시간이 가장 짧은 프로세스에게 CPU 할당
  • 장점
    • 효율성 : 평균 대기 시간을 최소화할 수 있으며, 전반적인 효율성이 높음
  • 단점
    • 복잡성 : 프로세스의 실행 시간을 예측하거나 알아내야 하므로, 구현의 복잡도 증가
    • 기아 상태 

컨보이 효과(convoy effect) vs 기아 상태(starvation)

• 컨보이 효과
  • 주로 선입 선처리 스케줄링에서 자주 발생
  • 긴 작업이 먼저 처리되는 상황이면 그 뒤의 짧은 작업들이 프로세스가 완료될 때까지 기다려야하는 상황
  • 많은 프로세스들이 이를 대기해야하며, 시스템의 전체적인 처리량 감소 및 평균 대기 시간이 증가
• 기아 상태
  • 우선 순위 기반의 스케줄링 방식에서 자주 발생
  • 우선 순위가 낮은 프로세스가 계속해서 순위가 높은 프로세스에게 밀려 CPU 점유를 하지 못하는 상태
  • 낮은 우선순위의 프로세스는 무한정 대기 및 CPU를 할당받지 못할 가능성 존재
• 영향
  • 컨보이 효과는 시스템 전체의 성능 저하
  • 기아 상태는 특정 프로세스가 서비스를 받지 못하는 현상 발생

 

thread Scheduling

 

운영 체제에서 멀티스레딩 환경을 관리하는 방식

 

• 스레드
  
  • 프로세스 내에서 실행되는 실행 단뒤
  • 프로세스의 자원을 공유하며, 독립적인 실행 흐름을 ㄱ짐
• 스레드 스케줄링
  • 스레드들 사이에서 CPU 시간을 어떻게 할당하고 관리할지 결정
  • 특징
    • 경량화된 문맥 교환
      • 같은 프로세스 내에서 실행되므로, 프로세스 간의 문맥교환보단 자원과 시간의 소모가 적다
    • 자원 공유
      • 프로세스 내의 메모리와 자원 공유
      • 효율적인 자원 사용이 가능하지만, 동시성 제어가 필요
    • 병렬 처리 및 응답성 향상
      • 멀티스레딩은 병렬 처리를 통해 응용 프로그램의 응답성 향상 및 자원의 사용률을 최적화
  • 종류
    • 사용자 수준
      • 스레드의 생성 및 관리가 사용자 수준의 라이브러리에서 발생
      • OS의 경우 해당 스레드를 인식하지 못함 ->  유연성 향상
        • 하나의 스레드가 차단(Block)되면 동일 프로세스의 모든 스레드가 영향을 받음
    • 커널 수준
      • 스레드의 생성 및 관리가 운영체제 커널에서 발생
      • 커널은 모든 스레드를 인식하고 개별적으로 스케줄링 가능
      • 운영체제의 지원이 필요하며, 문맥교환 시 비용이 증가
    • 하이브리드
      • 사용자와 커널 수준의 특징 결합 -> 유연성 및 효율성을 균형 있게 제공
  • 성능 최적화 :  시스템의 성능과 자원 활용도를 최적화
  • 동시성 관리 : 스레드들이 자원을 공유하므로, 동시성 제어 및 동기화는 스케줄링의 중요 요소
  • 응답 시간 개선 : 멀티스레딩은 응용 프로그램의 응답 시간을 개선하여 사용자 경험 향상