운영체제 스터디 (4) - CPU 스케줄링

Posted on | In

운영체제 스터디 도중 쉽게 배우는 운영체제를 읽고 요약한 내용입니다. 자세한 내용은 책을 구매하여 확인 부탁드립니다.

4. CPU 스케줄링

스케줄링

식당의 비유

  • 식당에서는, 주방에서는 홀의 상황을 알기 어려움
  • 이런 홀의 상황은 식당 관리자가 관리하고, 실제 요리는 요리사가 하도록 구분 되어 있음
  • CPU 스케줄러가 이 식당 관리자의 역할을 맡아 줌
  • 식당 관리자의 역할
    • 예약 손님이 온다면, 다른 손님보다 먼저 들이기도 함
    • 예약한 손님이 오지 않으면, 다른 손님을 앉히기도 함
    • 주문을 받기도 함
    • 손님이 아직 다 드시지 않았다면, 다른 손님 거 부터 주문을 받기도 함
    • 손님의 개별적인 요구에도 응함
  • 컴퓨터에서 발생하는 상황에 대입 해보면, 프로세스가 손님 역할이고 CPU가 요리사 역할, 위 역할들을 CPU 스케줄러가 한다고 생각하면 됨
  • 크게 보면, 식당 관리자는 좌석 관리, 조리 순서 관리를 진행 함

스케쥴링

고수준 스케줄링

  • 가장 큰 틀에서 이루어지는 CPU 스케줄링
  • 손님을 무조건 많이 받으면, CPU 과부하가 걸리는데, 이를 방지하기 위해 시스템 내의 전체 작업 수를 조절하는 작업
  • 작업 = 여러개의 프로세스 or 한개의 프로세스
  • 어떤 작업을 시스템이 받아 들일지, 거부 할 지 정한다
  • 전체 프로세스의 수 → 멀티 프로그래밍 정도
  • 전체 손님의 수를 조절하는 작업
  • 승인 스케줄링 이라고도 칭함

저수준 스케줄링

  • 가장 작은 틀에서 이루어지는 CPU 스케줄링
  • 어떤 프로세스에 CPU를 할당 할 지, 어떤 프로세스를 대기 상태로 보내는 지 등을 결정하는 스케줄링
  • 손님의 주문과, 요리 순서를 조절하는 작업
  • 저수준 스케줄링, 짧은 시간에 일어나므로 단기 스케줄링 이라고도 칭함

중간 수준 스케줄링

  • 고수준 스케줄링과 저수준 스케줄링 사이에서 일어나는 스케줄링
  • 손님의 주문을 다른 주문으로 바꾸도록 유도하거나, 주문을 천천히 받는 작업에 해당
  • suspend, active 작업으로, 전체 시스템의 활성화 된 프로세스 수를 조절하여 과부하를 막는 스케줄링
  • 보류된 프로세스는, 처리에 여유가 생기면 다시 활성화 됨
  • 일부 프로세스를 중지 상태로 옮김 ( 보류 상태로 옮김 )

스케줄링의 목적

  1. 공평성 : 모든 프로세스가 공평하게 작업하도록 하는 것
  2. 효율성 : 놀고있는 자원이 생기지 않도록 스케줄링 하는 것
  3. 안정성 : 중요 프로세스가 먼저 작동하도록 배정
  4. 확장성 : 프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치 해야함
  5. 반응 시간 보장 : 적절한 시간 내에 프로세스에 응답 해야 함
  6. 무한 연기 방지 : 작업이 무한히 연기 되는 것을 방지

스케줄링 시 고려 사항

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

  • 선점형 스케줄링
    • 어떤 프로세스가 CPU를 할당 받아 실행 중이더라도, 운영 체제가 CPU를 강제로 뺏을 수 있는 스케줄링 방식
    • 인터럽트 처리가 가능함 ( 인터럽트 → 현재 작업 중단 → 커널을 깨워 인터럽트 처리 → 원래의 작업으로 복귀 )
    • Context switching이 발생 할 수 있는 것이 단점
    • 대부분 선점형 사용
  • 비선점형 스케줄링
    • 어떤 프로세스가 CPU를 할당 받아 실행 중이면, 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식
    • 종료 되기 전까지 계속 실행
    • Context switching이 발생하지 않아 낭비 적음, 스케줄러 일도 적음
    • 전체 시스템의 처리율이 떨어짐
    • 일괄 작업 시스템에서 사용하던 방식
  • 선점형 / 비선점형 혼합 하는 경우
    • 선점형 스케줄링 속에서도 시스템을 백업하는 프로세스는, 비선점형으로 작동 한다
    • 비선점형 프로세스의 중요도를 매우 낮게 설정하여 선점형 프로세스에 영향을 덜 미치도록 한다.

프로세스 우선순위

  • 프로세스의 우선순위가 없다 → 모든 프로세스의 중요도가 같다
  • 레스토랑이 꽉 차서 기다리는 손님을 상상하면 알맞음
  • 하지만, 일반적으로 프로세스별 중요도가 다르기 때문에 대부분 CPU 스케줄러는 우선순위를 사용
  • 예약 손님을 먼저 들이는 것과 비슷
  • 커널 프로세스가 일반 프로세스보다 우선순위가 높다
  • 우선순위가 높다 → 더 빨리 자주 실행된다
  • 일반 프로세스도 중요도가 서로 다를 수 있다.
    • 비디오 플레이어의 중요도가 낮다면, 끊기면서 실행 될 수 있음
    • 워드프로세서 같은 경우엔, 유저가 타이핑 하는 속도가 CPU 처리 속도보다 늦기 때문에 중요도가 낮아도 됨
    • 사용자가 직접 우선순위 설정 가능하기도 함

CPU 집중 프로세스와 입출력 집중 프로세스

  • CPU 버스트 : CPU를 할당 받아 실행하는 작업
  • 입출력 버스트 : 입출력 작업
  • CPU 집중 프로세스 : CPU 버스트가 많은 프로세스를 의미
  • 입출력 집중 프로세스 : 입출력 작업이 많은 프로세스를 의미
  • 일반적으로, CPU집중 프로세스와 입출력 집중 프로세스가 동시에 있다면, 입출력 집중 프로세스부터 실행 하는것이 나음
    • CPU집중 프로세스를 먼저 실행하면, CPU집중 프로세스가 작동하는 동안 입출력 집중 프로세스가 작동하지 못한다.
    • 하지만 입출력 집중 프로세스는 실행 되고, 대기 상태로 입출력 집중 프로세스를 보낸 뒤 남은 CPU를 CPU 집중 프로세스에 할당 가능하기 때문

전면 프로세스 / 후면 프로세스

  • 전면 프로세스
    • CPU를 사용하는 운영체제에서, 화면의 맨 앞에 놓인 프로세스를 의미
    • 현재 입력과 출력을 사용하는 프로세스
    • 사용자와 상호작용 가능
    • 사용자의 요구에 즉각 반응 해야 함 → 우선순위가 높다
  • 후면 프로세스
    • 사용자와 상호작용이 없는 프로세스
    • 사용자의 입력 없이 작동 하는 경우 다수

다중 큐

준비 상태의 다중 큐

  • 프로세스는 저마다 우선순위가 다르고, 이는 PCB에 표기 되어 있음
  • 스케줄러가 PCB를 모두 뒤져서 가장 높은 우선순위의 프로세스에 CPU를 할당
  • 하지만, 이렇게 매번 검색하는 작업은 번거로움
  • 우선순위에 따라 여러개의 큐를 만들어 놓으면 우선순위를 따로 검색하지 않아도 됨
  • 프로세스는 준비 상태에 들어올 때 마다 자신의 우선순위에 해당하는 큐의 마지막에 삽입
  • Ready queue를 몇개로 나눌 지, Ready queue 안에 있는 프로세스 중 어떤 프로세스에 CPU를 할당 할 지는 스케줄링 알고리즘에 따라 다름
  • 우선순위 배정 방식
    • 고정 우선순위
      • 프로세스에 우선순위를 부여하면, 프로세스가 끝날 때 까지 우선순위가 바뀌지 않는 방식
      • 시스템의 변화에 대응이 어려워 작업 효율이 떨어 질 수 있다.
    • 변동 우선순위
      • 우선순위가 프로세스 작업 중간에 변하는 방식
      • 구현하기 어렵지만 효율성을 높일 수 있음
    • 예제
      • 중요한 자원을 사용하고 있는 P1을 상정
      • P1의 우선순위가 낮다면, P1이 끝날 때 까지 중요한 자원을 독점
      • 변동 우선순위 방식이라면 P1의 우선순위를 높여 빨리 끝냄으로써 중요한 자원을 다른 프로세스에도 양도 할 수 있도록 해줄 수 있음

대기 상태의 다중 큐

  • 대기 상태에서도 다중 큐를 사용함
  • 같은 입출력을 요구한 프로세스끼리 동일한 큐에 모아 놓음
  • 대기 상테의 프로세스는, 동시에 여러 입출력 작업이 끝날 수 있기 때문에, 한번에 인터럽트를 모아서 보내기 위해 인터럽트 벡터라는 자료 구조 사용
  • 입출력이 너무 길면, 나중에 온 PCB가 먼저 준비상태로 옮겨 가기도 함

스케줄링 알고리즘

스케줄링 알고리즘의 선택 기준

  • CPU 사용률 : 전체 시스템의 동작 시간 중 CPU가 사용 된 시간을 측정하는 방법 ( 이상적인 수치 : 100 % )
  • 처리량 : 단위 시간 당 작업을 마친 프로세스의 수 ( 크면 좋음 )
  • 대기 시간 : 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간 ( 짧을수록 좋음 )
  • 응답 시간 : 사용자의 요구에 걸리는 시간, 프로세스 시작 후 첫번 째 출력까지 걸리는 시간 ( 짧을수록 좋음 )
  • 반환 시간 : 프로세스가 사용하던 자원을 모두 반환하는데 까지 걸리는 시간 ( 대기시간 + 응답시간 )
  • 실행 시간 : 프로세스의 작업이 시작 된 후 종료되기 까지의 시간
  • 이 중 주로 대기 시간, 응답 시간, 반환 시간을 성능의 지표로 쓴다. ( CPU 사용률, 처리량은 측정하기 어려움 )
  • 평균 대기 시간 = 총 대기 시간 / 총 프로세스의 갯수

pic1.png

FCFS 스케줄링 ( First Come First Served )

  • 특징
    • 비선점형 스케줄링 방식
    • 테이블이 하나만 있는 레스토랑과 유사
    • 손님이 도착한 순서대로 한번에 한 팀씩 요리를 제공
    • 큐가 하나라 모든 프로세스의 우선순위가 동일
    • 프로세스가 끝나야만 다음 프로세스가 실행 가능
  • 위 작업 조건에서의 성능
    • P1의 대기시간 : 0 / P2의 대기시간 : 30 - 3 / P3의 대기시간 : 48 - 6
    • 평균 대기시간 : 23
  • 위 작업 조건에서의 평가
    • 단순, 공평
    • Bottle neck 발생
    • 컨베이어 벨트 생각 하면 편함
    • 입출력 작업 시 CPU의 쉬는 시간이 많아져 비효율적

SJF 스케줄링 ( Shortest Job First )

  • 특징
    • 비선점형 스케줄링 방식
    • Ready queue에서 실행 시간이 가장 짧은 작업부터 CPU를 할당
    • 오래 걸리는 작업을 나중에 하고, 간단한 작업을 먼저 진행
  • 위 작업 조건에서의 성능
    • P1의 대기시간 : 0 / P2의 대기시간 : 39 - 3 / P3의 대기시간 : 30 - 6
    • 평균 대기시간 : 20
  • 위 작업 조건에서의 평가
    • 장점
      • 효율성이 좋아짐
      • 평균 대기시간이 줄어 듬
    • 단점
      • 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 힘들다.
        • 사용자와의 상호작용이 잦아 져 종료 시간 알기 힘듦
      • 공평하지 못하다
        • 공평성을 위배
        • P2보다 작업 시간이짧은 프로세스가 계속 들어오면, 해당 프로세스는 작업이 계속 밀림 → 아사 현상, 무한 봉쇄 현상이 발생
        • 에이징을 통해 해결 가능 ( 세번 이상 밀리면, 바로 실행하라 … 등 ) 하지만 에이징의 기준을 정해야 하는 문제가 있어 잘 사용하지 않음

HRN 스케줄링 ( Highest Response Ratio Next )

  • 특징
    • 비선점형 스케줄링 방식
    • 서비스를 받기 위해 프로세스가 기다린 시간과, CPU 사용 시간을 고려하여 스케줄링 우선순위를 정하는 방식
    • 우선순위 = ( 대기시간 + CPU 사용 시간 ) / CPU 사용 시간
    • HRN 스케줄링 에서는 우선순위 값이 높을 수록 먼저 처리됨
    • 위 작업 조건에서는, P3의 우선순위 값이 P2 보다 높음 → P3가 먼저 처리
    • 에이징이 알고리즘에 포함 된 방식
  • 위 작업 조건에서의 성능
    • P1의 대기시간 : 0 / P2의 대기시간 : 24 / P3의 대기시간 : 36
    • 평균 대기시간 : 20
  • 위 작업 조건에서의 평가
    • 공평성이 위배 되어 많이 사용되지는 않음

라운드 로빈 스케줄링 ( Round Robin, RR )

  • 특징
    • 선점형 스케줄링 방식
    • 한 프로세스가, 할당받은 타임 슬라이스 동안 작업을 하다가 작업을 완료하지 못하면 Ready queue의 tail로 보내는 방식
    • FCFS와 유사하지만, 타임 슬라이스가 차이점
    • 우선순위가 적용되지 않은 단순한 선점형 스케줄링
    • 앞의 긴 작업을 무제한으로 기다려야 하는 현상은 없음
  • 위 작업 조건에서의 성능
    • P1의 대기시간 : 0 + 19 + 8 / P2의 대기시간 : 7 + 19 / P3의 대기시간 : 14
    • 평균 대기시간 : 22.33
  • 위 작업 조건에서의 평가
    • FCFS 스케줄링과 평균 대기 시간이 같다면, RR 방식은 Context switching이 자주 발생하기 때문에 좋지 못함
    • 타임 슬라이스
      • 타임 슬라이스가 큰 경우
        • 너무 크면, 하나의 작업이 끝난 뒤 다음 작업이 시작되는 것 처럼 보임 → FCFS 방식과 다르지 않아 보임 ( 실제로, 타임 슬라이스가 무한대라면, FCFS 방식과 동일 )
      • 타임 슬라이스가 작은 경우
        • 너무 작다면, 동시에 실행되는 것 처럼 느끼지만 Context switching이 매우 빈번하게 발생 할 것
      • 타임 슬라이스를 되도록 작게 설정하되, Context switching에 걸리는 시간을 고려하여 적당한 크기로 설정 하는것이 중요

SRT 우선 스케줄링 ( Shortest Remaining Time )

  • 특징
    • 선점형 스케줄링 방식
    • SJF 스케줄링과, RR 스케줄링의 혼합형
    • 기본적으로 RR스케줄링 이지만, CPU를 할당받을 프로세스를 정할 때 작업 시간이 가장 짧은 프로세스로 정함
  • 위 작업 조건에서의 성능
    • P1의 대기시간 : 0 + 27 / P2의 대기시간 : 10 + 6 / P3의 대기시간 : 4
    • 평균 대기시간 : 15.66 밀리초
  • 위 작업 조건에서의 평가
    • 남은 시간을 주기적으로 계산 하는 작업, Context switching이 부담
    • 프로세스의 종료 시간이 예측하기 어렵고, 아사 현상이 일어 날 수 있음

우선 순위 스케줄링

  • 특징
    • 선점형, 비선점형 방식에 모두 사용 가능
    • 어떤 기준으로 우선순위를 정하느냐에 따라 다양하게 구현 할 수 있음
      • SJF → ( 비선점형 ) 작업 시간이 짧은 프로세스에 높은 우선순위 부여
      • HRN → ( 비선점형 ) 작업 시간이 짧거나, 대기 시간이 긴 프로세스에 높은 우선순위를 부여
      • SRT → ( 선점형 ) 남은 시간이 짧은 프로세스에 높은 우선순위 부여
    • 우선순위 알고리즘
      • 고정 순위 알고리즘 : 우선순위를 한번 부여받으면, 종료 될 때 까지 우선순위가 고정
      • 변동 순위 알고리즘 : 우선순위가 일정 시간마다 변화시켜 시스템이 복잡하지만, 시스템의 상황을 잘 반영 할 수 있기 때문에 효율적인 운영 가능
  • 우선순위 스케줄링 평가
    • 공평성을 위배하고, 아사 현상을 일으킬 수 있음
    • 우선순위를 매번 바꿔야 하기 때문에 오버헤드 발생 가능
    • 프로세스의 효율성 보다 중요도 기준으로 결정 → 커널 프로세스가 제 역할을 수행하기 편해짐

다단계 큐 스케줄링

  • 특징
    • 선점형 스케줄링 방식
    • 우선 순위에 따라 큐를 여러 개 사용하는 방식, 각 단계의 큐에 RR방식 사용
    • 프로세스는 운영체제로 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입
    • 우선순위는 고정형 우선순위 방식 사용
    • 상단의 큐 ( 우선순위가 높은 큐 )에 있는 모든 프로세스가 모두 끝나야 다음 우선순위 큐의 작업이 시작 됨
    • 우선순위가 높은 프로세스가 먼저 실행 될 수 있고, 타임 슬라이스를 조절 하여 작업 효율을 조절 할 수 도 있음
      • 전면 프로세스는 타임 슬라이스를 작게 하고, 후면 프로세스는 FCFS 방식으로 처리
    • 우선순위가 높은 프로세스 때문에 우선순위가 낮은 프로세스의 작업이 연기 → 이를 해결하기 위해 다단계 피드백 큐 스케쥴링 방식이 도입 됨

다단계 큐 스케줄링

  • 특징
    • 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 방식의 단점을 보완한 방식
      • CPU를 사용 하고 난 프로세스의 우선 순위가 한단계 낮아짐 → CPU 사용을 한 프로세스는, 원래의 queue가 아닌, 우선순위가 한단계 낮은 queue에 삽입 됨
      • 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화
      • 커널 프로세스가 일반 프로세스의 큐에 삽입 되지는 않음
    • 우선순위에 따라 타임 슬라이스의 크기가 다름
      • 우선순위가 낮아 질 수록 해당 큐의 타임 슬라이스가 커짐
      • 어렵게 얻은 CPU를 좀 더 오랫동안 사용 할 수 있도록 해줌
      • 가장 마지막 큐에 있는 프로세스는 무한대의 타임 슬라이스를 얻음 → FCFS 방식과 동일
      • 변동 우선순위 알고리즘의 전형적인 예

"Operation System" 카테고리의 최근 포스팅

카테고리 모든 글 보기
운영체제 스터디 (13) - 네트워크와 분산 시스템 2021. 03. 14
운영체제 스터디 (12) - 파일 시스템 2021. 03. 14
운영체제 스터디 (11) - 입출력 시스템과 저장 장치 2021. 03. 11
운영체제 스터디 (10) - 가상 메모리 관리 2021. 03. 10
운영체제 스터디 (9) - 가상 메모리의 기초 2021. 03. 08
운영체제 스터디 (8) - 물리 메모리 관리 2021. 03. 07
운영체제 스터디 (7) - 교착상태 2020. 12. 04
운영체제 스터디 (6) - 프로세스 동기화 2020. 11. 10
운영체제 스터디 (5) - interrupt 2020. 10. 20
운영체제 스터디 (4) - CPU 스케줄링 2020. 10. 19