03. CPU 스케줄링

CPU 스케줄링

운영체제가 프로세스들에게 공정하고 합리적으로 CPU자원을 배분하는 것

• 입출력 집중 프로세스I/O bound process
  실행상태 < 입출력을 위한 대기상태 에 더 많이 머무는 프로세스. 입출력 버스트가 많은 프로세스
  ex. 비디오 재생, 디스크 백업 작업
• CPU 집중 프로세스CPU bound process
  실행상태 > 대기 상태 에 더 많이 머무는 프로세스. CPU 버스트가 많은 프로세스
  ex. 컴파일, 그래픽 처리 작업, 복잡한 수학 연산

  CPU 버스트burst : CPU를 이용하는 작업
  입출력 버스트burst : 입출력장치를 기다리는 작업
  프로세스는 일반적으로 CPU버스트와 입출력 버스트를 반복하면서 실행

프로세스 우선순위

priority. 입출력 집중 프로세스를 가능한 빨리 실행시키고 CPU 집중 프로세스에 집중적으로 CPU를 할당하는 것이 효율적.

ps -el 명령을 통해 우선순위 확인 가능. nice 로 프로세스 우선순위 변경 가능
윈도우에서는 Process Explorer 소프트웨어를 통해 확인/변경 가능

스케줄링과 큐

운영체제가 프로세스들에게 '줄을 서서 기다릴 것'을 요구하는 것(하나씩 뒤적거리긴 비효율적이니까!)

스케줄링 큐scheduling queue
메모리에 적재되고 싶은/특정 입출력장치 사용하고 싶은/CPU사용하고 싶은 프로그램들을 각각 세운 줄. 정확히는 PCB가 줄을 섬
→ 자료구조 관점에서 큐는 선입선출 자료구조지만, 스케줄링의 큐는 반드시 선입 선출일 필요X

• 준비 큐ready queue
  프로세스 PCB들이 CPU를 이용하기 위해 기다리는 줄
• 대기 큐waiting queue
  (대기 상태에 들어간) 프로세스 PCB들이 입출력장치를 이용하기 위해 기다리는 줄운영체제는 PCB가 삽입된 순서대로 프로세스를 하나씩 꺼내어 실행하되, 우선순위가 높은 프로세스 먼저 실행
  

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

• 선점형 스케줄링preemptive scheduling
  프로세스마다 정해진 시간만큼 CPU를 사용하고 타이머 인터럽트가 발생하면 운영체제가 해당 프로세스로부터 CPU 자원을 빼앗아 다음 프로세스에게 할당. 하나의 프로세스가 자원 독점 불가능
  → 한 프로세스의 자원 독점 방어, 골고루 자원 배분 가능
  → 문맥 교환 과정에서 오버헤드 발생 가능
• 비선점형 스케줄링non-preemptive scheduling
  하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 들어가기 전까지 다른 프로세스가 끼어들 수 없는 스케줄링 방식. 하나의 프로세스가 자원 독점 가능
  → 문맥 교환 오버헤드 발생 가능성↓
  → 당장 자원을 사용해야 하는 경우여도 무작정 대기해야함. 골고루 자원 사용 불가

CPU 스케줄링 알고리즘

❗ 작업 방식과 장단점 이해에 집중하기.

• 선입 선처리 스케줄링(FCFS; First Come First Served)
  준비 큐에 삽입된(먼저 요청한) 순서대로 프로세스 처리. 비선점형

  • 프로세스가 기다리는 시간이 길어질 수 있음
  • 실행시간이 짧은 프로세스가 오랫동안 기다리는 호위효과convoy effect 발생 가능

• 최단 작업 우선 스케줄링(SJF; shortest Job First)
  준비 큐의 프로세스중 CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행. 기본적으로 비선점형이지만, 선점형으로도 구현 가능

  • 호위 효과 방지

• 라운드 로빈 스케줄링round robin
  선입 선처리 스케줄링 + 타임 슬라이스. 정해진 타임 슬라이스 만큼의 시간동안 돌아가며 CPU사용. 선점형

  🐥 타임 슬라이스 : 프로세스가 CPU사용할 수 있는 정해진 시간

  • 타임 슬라이스 크기가 너무 작으면 문맥교환이 지나치게 자주 일어남
    타임 슬라이스 크기가 너무 크면 호위 효과가 생길 수 있음
    💡 작업이 끝나면 타임 슬라이스가 끝날 때까지 기다리는게 아니라 그냥 끝냄

• 최소 잔여 시간 우선 스케줄링(SRT 스케줄링; Shortest Remaining Time)
  최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링. 정해진 타임 슬라이스 만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스는 남아있는 작업시간이 가장 적은 프로세스가 됨. 선점형
  

• 우선순위 스케줄링priority scheduling
  프로세스들에 우선순위 부여하고 가장 높은 우선순위 가진 프로세스부터 실행. 우선순위가 같다면 선입 선처리.

  • 우선순위가 낮은 프로세스는 준비 큐에 먼저 들어갔음에도 불구하고 우선순위가 높은 프로세스들에 의해 실행이 계속 연기될 수 있음(기아starvation 현상)

    💡 에이징aging : 기아 현상 방지 기법. 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식.

• 다단계 큐 스케줄링multilevel queue scheduling
  우선순위별로 큐를 여러개 사용. 우선순위가 가장 높은 큐에 있는 프로세스 먼저 처리, 우선순위가 가장 높은 큐가 비어있다면 다음 우선순위 큐의 프로세스 처리

  • 큐를 여러개 두면 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리해짐
  • 큐별로 타임슬라이스를 여러개 지정할 수도 있고, 다른 스케줄링 알고리즘을 사용할 수도 있음

• 다단계 피드백 큐 스케줄링multilevel feedback queue scheduling
  기아 현상이 발생을 방지한 기법(프로세스들이 큐 사이 이동 불가능)
  프로세스들이 큐 사이를 이동할 수 있음. 새로 준비 상태가 된 프로세스가 있다면 우선순위가 가장 높은 우선순위 큐에 삽입되고 타임 슬라이스 동안 실행. 프로세스가 해당 큐에서 실행이 끝나지 않으면 다음 우선순위 큐에 삽입되어 실행됨.
  → CPU에 오래 사용해야하는 프로세스는 점차 우선순위가 낮아짐.

  • 큐 사이를 이동할 수 있기 때문에 낮은 우선순위 큐에서 너무 오래 기다리고있는 프로세스가 있다면 에이징 기법을 이용해 기아 현상 예방 가능