cpu 스케줄링

searchortype·2022년 3월 20일
OS
0
post-thumbnail

스케줄링의 개요

CPU스케줄링 (프로세서 스케줄러)

스케줄링은 여러 프로세스의 상황을 고려하여 CPU와 시스템 자원을 어떻게 배정할지 결정하는 일을 말한다.

스케줄링의 단계

  • cpu 스케줄러도 관리의 범주를 나누어 스케줄링을 한다.
  • cpu 스케줄링은 규모에 따라 고수준 스케줄링, 중간 수준 스케줄링, 저수준 스케줄링으로 구분된다.

고수준 스케줄링 (장기 스케줄링, 작업 스케줄링, 승인 스케줄링)

  • 가장 큰 틀에서 이루어지는 CPU 스케줄링
  • 시스템 내의 전체 작업 수를 조절하는 것
  • 어떤 작업을 시스템이 받아들일지 거부할지 결정한다.
  • 고수준 스케줄링에 따라 시스템 내에서 동시에 실행 가능한 프로세스의 총개수가 정해진다.
  • 단점
    • 프로세스가 활성화된 후에도 여러가지 사정으로 시스템 과부화가 걸릴 수 있다.

저수준 스케줄링 (단기 스케줄링 short-term scheduling)

  • 가장 작은 단위의 스케줄링을 저수준 스케줄링
  • 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지를 결정한다.
  • 준비 상태에 있는 프로세스 중 하나 → 실행 상태
    실행 상태에 있는 프로세스 → 대기 상태
    대기 상태에 있는 프로세스 → 준비 상태
  • 짧은 시간에 일어난다.

중간 수준 스케줄링

  • 중지와 활성화로 전체 시스템의 활성화된 프로세스 수를 조절하여 과부하를 막는다.
    (일부 프로세스를 중지 상태로 옮겨서 프로세스가 원만하게 한다)
  • 저수준 스케줄링이 원만하게 이루어지도록 하는 buffer역할을 한다.

스케줄링의 단계 정리

  • 고수준 스케줄링
    • 전체 시스템 부하를 고려해 작업을 시작할지 말지
    • 결정에 따른 전체 프로세스 수 (멀티프로그래밍 정도)
  • 중간수준 스케줄링
    • 시스템에 과부하가 걸려서 전체 프로세스 수를 조절해야 한다면 이미 활성화된 프로세스 중 일부를 보류상태로 보낸다.
  • 저수준 스케줄링
    • 실제로 작업이 이루어진다.
    • 필요에 따라 프로세스 상태를 변경한다.

스케줄링의 목적

  • CPU 스케줄링의 목적은 모든 프로세스가 공평하게 작업하도록 하는 것이다.
  • 특정 프로세스가 시스템 자원을 독점하거나 파괴하는 것을 막기 위해 중요도에 따라 우선순위를 배정해야 한다.
  • 공평성
    • 모든 프로세스가 자원을 공형하게 배정받아야 한다.
  • 안정성
    • 우선순위를 사용하여 중요프로세스가 먼저 작동하도록 배정해야한다.
  • 효율성
    • 시스템 자원이 유휴 시간 없이 사용되도록 스케줄링
    • 유휴 자원을 사용하려는 프로세스에게 우선권을 줘야한다.
  • 확장성
    • 프로세스가 증가해도 안정적으로 작동하도록 조치해야 한다.
  • 반응 시간 보장
    • 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야한다.
  • 무한 연기 방지
    • 특정 프로세스의 작업이 무한히 연기되어서는 안된다.

스케줄링 시 고려 사항

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

선점은 빼앗을 수 있음을 뜻하고 비선점은 빼앗을 수 없음을 뜻한다.

  • 선점형 스케줄링
    어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식이다.
    • 예) 인터럽트 (interrupt)
      cpu가 인터럽트를 받으면 현재 실행 중인 작업을 중단하고 커널을 깨워서 인터럽트를 처리시키며 인터럽트 처리가 완료되면 원래 작업으로 돌아간다.
  • 비선점형 스케줄링
    어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식이다. 비선점형 스케줄링은 선점형 스케줄링보다 스케줄러의 작업량이 적고 문맥교황에 의한 낭비도 적다. 하지만 CPU 사용 시간이 긴 프로세스 때문에 CPU사용 시간이 짧은 여러 프로세스가 오랫동안 기다리게 되어 전체 시스템의 처리율이 떨어진다.

프로세스 우선순위

프로세스의 우선순위가 없다는 것은 모든 프로세스의 중요도가 같다는 의미이다.

프로세스는 크게 커널 프로세스와 일반 프로세스로 나뉜다. 커널 우선순위가 일반 프로세스 보다 높다.

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

  • cpu 집중 프로세스
    수학 연산과 같이 cpu를 많이 사용하는 프로세스를 말한다. cpu버스트가 많은 프로세스이다.
  • 입출력 집중 프로세스
    저장장치에서 데이터를 복사하는 일과 같이 입출력을 많이 사용하는 프로세스를 말한다.

cpu 집중 프로세스와 입출력 집중 프로세스가 같이 있을 때는 입출력 집중 프로세스를 먼저 실행 상태로 옮기는 것이 효율적이다. 스케줄링을 할 때 입출력 집중 프로세스의 우선순위를 CPU 집중 프로세스보다 높이면 시스템의 효율이 향상된다.

사이클 훔치기

입출력 집중 프로세스가 CPU 집중 프로세스보다 실행 상태에 먼저 들어가는 경우를 말한다.

전면 프로세스와 후면 프로세스

  • 전면 프로세스(상호작용 프로세스)
    GUI를 사용하는 운영체제에서 화면의 맨 앞에 놓인 프로세스. 현재 입력과 출력을 사용하는 프로세스이다.
  • 후면 프로세스(일괄 작업 프로세스)
    사용자와 상호작용이 없는 프로세스이다.

다중 큐

프로세스의 중요도는 프로세스 제어 블록에 표시된다.

준비상태의 다중 큐

  • 준비상태의 다중 큐는 프로세스의 우선순위에 따라 여러개의 큐를 만든다. 만약 우선 순위별로 정리되어 있지 않으면 매번 우선순위가 높은 프로세스 제어블록을 찾아야해서 불편하다.
  • 프로세스는 준비 상태에 들어올 때마다 자신의 우선순위에 해당하는 큐의 마지막에 삽입된다.
  • 큐를 몇개로 나눌지 어떤 프로세스를 할당 할지는 스케줄링 알고리즘을 따른다.
  • 고정 우선순위 방식
    • 운영체제가 프로세스에 우선순위를 부여하면 프로세스가 끝날 때까지 바뀌지 않는 방식이다.
    • 구현이 쉽지만 시스템의 변화에 대응하기 어려워 작업 효율이 떨어진다.
  • 변동 우선순위 방식
    • 프로세스 생성 시 부여받은 우선순위가 프로세스 작업 중간에 변하는 방식이다.
    • 구현이 어렵지만 시스템 효율성을 높일 수 있다.

대기상태의 다중 큐

  • 시스템 내에는 다양한 종류의 입출력장치가 있기 때문에 대기 상태의 프로세스를 한곳에 모아 놓으면 관리하기 불편하다. 따라서 시스템 효율을 높이기 위해서 대기 상태에서는 같은 입출력을 요구한 프로세스끼리모아놓는다.

준비상태의 다중 큐 vs 대기상태의 다중 큐

준비 큐는 한번에 하나의 프로세스를 꺼내서 CPU를 할당한다. 대기 큐는 여러개의 프로세스 제어블록을 동시에 꺼내어 준비 상태로 옮긴다.

스케줄링 알고리즘

  • 선점형 알고리즘
    • 시분할 시스템을 고려하여 만들어진 알고리즘으로 어떤 프로세스가 CPU를 할당 받아 실행 중이라도 운영체제가 CPU를 강제로 빼앗을 수 있다.
    • RoundRobin scheduling, SRT, mutilevel queue
  • 비선점형 알고리즘
    • FCFS, SJF, HRN

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

어떤 스케줄링 알고리즘이 효율적인지 파악하려면 평가기준이 있어야 한다.

  • 평가기준
    • CPU 사용률 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법
    • 처리량 단위 시간당 작업을 마친 프로세스의 수 (클수록 좋은 알고리즘)
    • 대기 시간 실제 작업이 이루어지기 전까지 대기 시간 (짧을 수록 좋다.)
    • 응답 시간 프로세스 시작 후 첫번째 출력 또는 반응이 나올 때까지 걸리는 시간
    • 반환시간 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간
  • 알고리즘의 성능을 비교할 때는 주로 평균 대기 시간(모든 프로세스의 대기 시간을 합한 값 / 프로세스 수)을 본다.

FCFS스케줄링

  • 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식
  • 큐가 하나라 모든 프로세스는 우선순위가 동일하다.
  • 단점
    • 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다려 시스템의 효율성이 떨어지는 문제가 있다. (콘보이 효과)
    • 현재 작업 중인 프로세스가 입출력 작업을 요청하는 경우 CPU가 작업하지 않고 쉬는 시간이 많아져 작업 효율이 떨어진다.

SJF (Shortest Job First)

  • 프로세스 중에서 실행시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식
  • 평균 대기 시간이 FCFS 스케쥴링보다 줄어든다.
  • 단점

    • 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다.

      현대의 프로세스는 사용자와의 상호작용이 빈번히 발생하기 때문에 프로그램 종료 시간을 파악하기 어렵고 이때문에 SJF 스케줄링을 사용하기 힘들다.

      • 해결
        프로세스가 자신의 작업 시간을 운영체제에 알려주어 해결할 수 있다. 하지만 프로세스가 자신의 작업 시간을 정확히 알기 어렵다.

    • 공평하지 못하다

      실행시간이 짧은 작업이 계속 새로 들어오면 기존에 있던 프로세스 작업이 연기 되면서 아사현상이 일어날 수 있다.

      • 해결 에이징으로 완화할 수 있다. 에이징은 프로세스가 양보할 수 있는 상한선을 정하는 방식이다. (프로세스가 순서를 양보할때마다 나이를 먹어 최대 몇살까지 양보하도록 함) 하지만 에이징 값을 어떤 기준으로 정할 것인지가 문제라 에이징에도 한계가 있다.

HRN (Highest Response Ratio Next)

  • SJF스케줄링에서 발생할 수 있는 아사 현상을 해결하기 위해 만들어진 비선점형 알고리즘
  • 서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 스케줄링을 하는 방식이다.
  • 단점
    • 여전히 공평성이 위배된다 실행 시간이 짧은 프로세스의 우선순위를 높게 설정하면서도 대기 시간을 고려하여 아사 현상을 완화한다.

라운드 로빈 스케줄링

  • 한 프로세스가 할당받은 시간동안 작업을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식의 선점형 스케줄링 방식이다.
  • 타임 슬라이스의 크기는 프로세스의 반응 시간에 영향을 미친다.

    • 타임 슬라이스가 큰 경우

      타임슬라이스가 너무 크면 하나의 작업이 끝난 뒤 다음 작업이 시작되는 것처럼 보이고 반응 속도가 매우 느리다.

    • 타임 슬라이스가 작은 경우

      타임 슬라이스가 너무 작은 경우 시스템 전반적인 성능이 떨어진다. 문맥 교환이 너무 자주 일어나 문맥 교환에 걸리는 시간이 실제 작업 시간보다 상대적으로 커지며, 문맥 교환에 많은 시간을 낭비하여 실제 작업을 못하는 문제가 발생한다.

  • 타임슬라이스는 되도록 작게 설정하되 문맥 교환에 걸리는 시간을 고려하여 적당한 크기로 하는 것이 중요하다.

SRT 우선 스케줄링

  • SJF 스케줄링 + 라운드 로빈 스케줄링
  • SJF 스케줄링의 선점형 버전이다.
  • 남은 시간이 적은 프로세스에 CPU를 먼저 할당한다.
  • SJF와 비교했을 때 평균 대기 시간이 짧지만 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고 남은 시간이 더 적은 프로세스와 문맥교환해야한다.
  • 단점
    • 운영체제가 프로세스의 종료 시간을 예측하기 어렵고 아사 현상이 일어나기 때문에 잘 사용하지 않는다.

우선순위 스케줄링

  • 우선순위를 반영한 스케줄링 알고리즘이다.
  • 어떤 기준으로 우선순위를 정하느냐에 따라 다양하게 구현할 수 있다.
  • 프로세스의 우선순위는 프로세스의 중요도를 기준으로 결정된다. (일반 프로세스가 실행된 다음 커널 프로세스가 실행되면 커널 프로세스가 제 역할을 못할수도 있다.)
  • 단점
    • 공평성을 위배하고 아사현상을 일으킨다는 문제
    • 준비 큐에 있는 프로세스의 순서를 무시하고 프로세스의 우선순위를 매번 바꿔야하기에 오버헤드가 발생

다단계 큐 스케줄링

  • 우선순위에 따라 준비 큐를 여러개 사용하는 방식이다.
  • 프로세스는 운영체제로부터 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입된다. 상단의 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선 순위 큐의 작업이 시작된다.
  • 우선순위에 따라 타임 슬라이스를 조절해 작업 효율을 높일 수 있다.
  • 단점
    • 우선순위가 높은 상위 큐 프로세스의 작업이 끝나기 전에는 하위 큐 프로세스의 작업을 할 수 없다. 때문에 우선순위가 낮은 프로세스의 작업이 연기된다는 문제가 있다.

다단계 피드백 큐 스케줄링

  • 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완한 방식
  • 다단계 큐 스케줄링의 경우 각 단계의 큐에 RR방식을 사용하고 우선순위에 변화가 없지만, 다단계 피드백 큐스켈줄링은 CPU를 사용하고 난 프로세스의 우선순위가 낮아진다. (CPU를 사용하고 난 프로세스는 원래의 큐로 되돌아오지 않고 우선순위가 하나 낮은 큐의 끝으로 간다.)
  • 우선순위가 낮아질수록 해당 큐의 타임슬라이스가 커진다.
  • 오늘날 운영체제가 일반적으로 사용하는 방식이고 변동 우선순위 알고리즘의 전형

인터럽트 처리

인터럽트

  • 이벤트 드리븐 방식과 마찬가지로 입출력을 요청하고 입출력이 완료되면 이벤트를 발생시켜 이 사실을 알리게 되는데 이것을 인터럽트라고 한다.
  • 어떤 프로세스가 실행 중 다른 프로세스가 사용 중인 메모리 영역을 침범하면 CPU에 있는 메모리 관련 레지스터가 인터럽트를 발생시켜 해당 프로세스를 강제 종료한다.
  • 인터럽트 번호와 그 번호에 붙어 있는 함수의 쌍으로 이루어져 있다.

동기적 인터럽트와 비동기적 인터럽트

  • 동기적 인터럽트

    프로세스가 실행중인 명령어로 인해 발생한다.

    • 프로그램 상의 문제로 발생하는 인터럽트 (오버플로우, 언더플로우)
    • 컴퓨터 작업자가 의도적으로 프로세스를 중단하기 위해 발생시킨 인터럽트
    • 산술 연산 중 발생하는 인터럽트 (어떤 수를 0으로 나눔)

  • 비동기적 인터럽트

    실행 중인 명령어와 무관하게 발생한다.

    • 하드웨어적인 오류로 발생하는 인터럽트 (하드디스크 읽기 오류)

인터럽트 벡터

  • 인터럽트가 한순간엔 여러 개가 동시에 발생할 때 인터럽트를 하나로 묶어서 처리하는 개념

인터럽트 처리 과정

  1. 인터럽트 발생 시 현재 실행 중인 프로세스는 일시 정지 상태가 되며 재시작하기 위해 현재프로세스 관련 정보는 임시로 저장한다.
  2. 인터럽트 컨트롤러가 실행되어 인터럽트의 처리 순서를 결정한다.
  3. 먼저 처리할 인터럽트가 결정되면 인터럽트 벡터에 등록된 인터럽트 핸들러가 실행된다.
  4. 인터럽트 벡터에 연결된 핸들러가 인터럽트 처리를 마치면 일시 정지된 프로세스가 다시 실행된다.

인터럽트와 이중모드

  • 이중모드

    • 운영체제가 사용자모드와 커널모드를 전환하여 일 처리를 하는 것을 이중모드라고 한다.
    • 운영체제가 자원을 보호하기 위해 사용하는 기법이다.

  • 사용자가 커널 모드로 진입하는 경우

  • 시스템 호출을 사용한 경우 (자발적)

  • 인터럽트를 발생시킨 경우(비자발적)

reference: 쉽게 배우는 운영체제

profile
searchortype
이전 포스트

process 와 thread

다음 포스트

프로세스 동기화

0개의 댓글