6. 스케줄링

다중 프로그래밍의 도입 목적

 - 여러 프로세스가 하나의 CPU를 돌아가면서 사용해야 하므로 순서를 정할 필요가 있다.

  -> 잘 하면 CPU 대기시간이 줄어들고, CPU 활용률이 향상된다.

  -> job 스케줄링 ( 디스크 -> 메모리 ), cpu 스케줄링 ( 메모리 -> CPU ) 가 필요하다.

 

프로세스는 CPU연산과 I/O작업의 연속

 - CPU Burst, I/O Burst : 연산 작업이 많이 필요한 쪽에 더 긴 CPU 시간을 준다.

 - 기본적으로 CPU가 쉬는 시간이 있어서는 안되며, 대부분의 OS에서는 하나의 스레드가 너무 오래 CPU를 점유하지 못하게 한다.

  -> Time slice(타임슬라이스) : 스케줄된 스레드에게 한 번 할당하는 CPU 시간

 

기준

 - CPU 활용률 : 전체 시간 중 CPU 사용 시간

 - 처리율 : 단위시간 당 처리하는 프로세스

 - 공평성 : 프로세스들이 공평하게 기회를 가졌는가.

 - 응답시간 : 명령에 응답하는데 걸리는 시간

 - 대기시간 : 스레드가 준비 큐에서 대기하는 시간

 - 소요시간 : 프로세스가 도착한 후 완료까지 걸리는 시간

 - 시스템 정책 : OS 입장에서...

 - 자원 활용률

 - 우선순위 등...

 

작업 순서

 - 작업 도착 > 실행 시작 > 출력 > 실행 종료

  대기 시간 : 작업 도착 -> 실행 시작

  응답 시간 : 작업 도착 -> 출력

  실행 시간 : 실행 시작 -> 실행 종료

  반환 시간 : 작업 도착 -> 실행 종료

 

CPU 스케줄링이 실행되는 상황

 - 스레드가 시스템 호출 중 I/O를 요청해 블록될 때

 - 스레드가 자발적으로 CPU를 반환 ( Yield 등... )

 - 타임슬라이스가 소진되어 타이머 인터럽트 발생 ( 균등한 CPU 분배를 위해.. )

 - 더 높은 순위의 스레드가 인터럽트 요청 ( 강제 높은 순위 실행 )

 

※ 스케줄링 관련 코드는 커널 내에 존재함

 - 스케줄러 : 스케줄러 타이머가 주기적으로 인터럽트 발생, 실행시간 업데이트, 플래그 비트 설정

 - 디스패쳐 : Context Switching을 실행하는 커널 코드

 - 스케줄러와 디스패처의 실행시간을 최대한 단축시켜야 한다.

 

 

비선점 스케줄링

 - 일단 스레드가 CPU를 할당받으면 작업 완료 or CPU 사용 불가까지 중단되지 않는다.

 - 스케줄러의 작업량이 적고 Context switching의 오버헤드가 적지만 처리율이 떨어진다.

 

선점 스케줄링 ( 현대 범용 OS )

 - 현재 실행중인 스레드를 강제 중단시키고 다른 스레드를 CPU에 할당할 수 있다.

 - 대화형, 시분할 시스템에 적합하지만, Context Switching의 오버헤드가 크다.

 

 

우선순위

 - 우선순위가 높은 프로세스가 CPU를 먼저, 더 오래 차지하게 된다.

 - Kernel > User-level

 - CPU burst > I/O burst

 - Foreground > Background

 정적 스케줄링

  - OS가 프로세스에 우선순위를 부여하면, 프로세스가 끝날 때 까지 우선순위가 바뀌지 않는다.

  - 구현하기 쉽지만, 시스템 변화에 대응하기 어려워 효율성이 떨어진다.

 동적 스케줄링

  - 프로세스 생성시 부여받은 우선순위가 프로세스 중간에 변할 수 있다.

  - 효율성이 높지만 구현하기 어렵다.

 기아 ( Starvation )

  - 스레드가 스케줄링에서 선택되지 못한 채 오랫동안 준비 리스트에서 대기하는 상황

   -> 우선순위가 계속 밀리는 등의 이유.. ( 스케줄링 설계에서 대비해야 함 )

 에이징 ( Aging ) : 기아의 해결책, 스레드가 준비리스트에 머무르는 시간에 비례해 스케줄링 순위를 높임.

 

멀티 코어 시스템에서 멀티 스레딩..

 - 스케줄링을 통해 프로세스는 지정된 순서에 따라 CPU에서 사용된다.

 - 멀티 코어에서는 스케줄링이 여러 코어에 발생하게 되므로, 서로 다른 코어에 Context Switching이 일어날 수 있다.

  -> 캐시에 새로운 스레드의 코드와 데이터를 입력해야 하므로 Context Switching Overhead가 커진다.

  -> CPU 피닝 ( Affinity ) : 스레드가 동일한 코어에 사용될 수 있도록 지정해 오버헤드를 줄인다.

 - 코어마다 처리할 스레드의 수가 달라서 코어별 부하 불균형이 일어날 수 있다.

  -> Push Migration ( 코어의 큐가 비어있으면 다른데서 빼서 채움 ) 이나,

     Pull Migration ( 할 게 없는 코어가 다른 스레드 큐에서 빼와서 실행함 ) 과 같은 부하 균등화 알고리즘을 통해 해결

 

※ 하나의 프로세스에서 여러 코어 스레드에 걸쳐 작업하면 공유 데이터에 잘못 접근해 훼손될 수 있다.

  -> 동기화 ( Synchronization )를 통해 해결.