운영체제(이론) - 핀토스-1

스케쥴링 알고리즘의 다양한 목표와 평가 기준

<비율>

1. CPU 활용률 - 전체 시간 중 CPU의 사용시간 비율 (운영체제 입장)

2. 처리율 - 단위 시간 당 처리하는 프로세스의 개수 (운영체제 입장)

3. 공평성 - CPU를 스레드들에게 공평하게 배분 (사용자 입장)

• 시분할(스케줄링)
• 무한정 대기하는 기아 스레드가 생기지 않도록 스케줄링

<시간>

1. 응답 시간 - 대화식 사용자의 경우, 명령에 응답하는데 걸리는 시간 (사용자 입장)

2. 대기 시간 - 스레드가 준비 큐에서 머무르는 시간 (운영체제와 사용자 입장)

3. 소요 시간 - 프로세스(스레드)가 컴퓨터 시스템에 도착한 후 완료될 때까지 걸린 시간 (사용자 입장) - 배치 처리 시스템에서 주된 스케줄링의 기준

4. 시스템 정책 우선 - 컴퓨터 시스템의 특별한 목적을 달성하기 위한 스케줄링 (운영체제 입장)

• ex) 실시간 시스템에서는 스레드가 완료 시한 내에 이루어지도록 하는 정책
• ex) 급여 시스템에서는 안전을 관리하는 스레드 우선 정책 등

1. 자원 활용률

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

1. 스레드가 시스템 호출 끝에 I/O를 요청하여 블록될 때

• 스레드를 블록 상태로 만들고 스케줄링
• CPU의 활용률 향상

2. 스레드가 자발적으로 CPU를 반환할 때

• yield() 시스템 호출 등을 통해 스레드가 자발적으로 CPU 반환
• 커널은 현재 스레드를 준비 리스트에 넣고, 새로운 스레드 선택
• CPU의 자발적 양보

3. 스레드의 타임슬라이스가 소진되어 > 타이머 인터럽트 발생

• 균등한 CPU 분배 목적

4. 더 높은 순위의 스레드가 요청한 입출력 작업 완료, 인터럽트o

• 현재 스레드를 강제 중단시켜 준비 리스트에 넣기
• 높은 순위의 스레드를 깨워 스캐줄링
• 우선순위를 지키기 위한 목적

CPU 스케줄링과 디스패치

CPU 스케줄링 코드의 위치와 실행 시점

• 스케줄링을 담당하는 커널 스레드나 프로세스x
• 스케줄링 코드는 커널 내에 코드 형태로 위치 스케줄링 코드는 커널 코드의 일부 별도로 실행되는 프로세스나 스레드 형태가 아님 커널은 마치 응용프로그램을 컴파일(빌드) 하여 완성한 바이너리 모듈 같음, 메모리에 그대로 적재되는 한 덩어리의 바이너리
  
• 스케줄링 코드가 실행되는 시점 시스템 호출이나 인터럽트 서비스 루틴이 끝나는 마지막 단계에서 실행
  
• 디스패쳐 코드 실행
• 디스패쳐 코드 : 컨택스트 스위칭을 실행하는 커널 코드 스케줄러에 의해 선택된 스레드를 CPU가 실행하도록 하는 작업
  • 커널 모드에서 사용자 모드로 전환
  • 새로 선택된 스레드가 이전에 중단된 곳에서 실행하도록 점프
• 스케줄러 and 디스패쳐 모두 실행 시간이 짧도록 작성

선점 vs 비선점 스케줄링

비선점 스케줄링

• 이미 할당된 자원을 다른 프로세스가 강탈할 수 없음
• 응답시간의 예측이 편하며, 일괄처리 방식에 적합
• 단점으로는 덜 중요한 작업이 자원을 할당받으면 중요 작업이 와도 먼저 처리될 수 없음
• FCFS(FIFO구조 알고리즘), SJF, HRN, 우선순위, 기한부

선점 스케줄링

• 우선순위가 높은 프로세스를 빠르게 처리할 수 있음
• 어떤 프로세스가 자원을 사용하고 있을 때 우선순위가 더 높은 프로세스가 올 경우 자원을 강탈함
• 빠른 응답 시간을 요구하는 시스템에서 사용
• 오버헤드가 크다
• Round Robin, SRT, 선점 우선순위, 다단계 큐, 다단계 피드백큐

기아

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

ex)

• 우선 순위 기반으로 하는 시스템에서 더 높은 순위의 스레드가 계속 시스템에 들어오는 경우
• 짧은 스레드를 우선 실행시키는 시스템에서, 자신보다 짧은 스레드가 계속 도착하는 경우

에이징

기아의 해결책

스레드가 준비리스트에 머무는 시간에 비례하여 스케줄링 순위를 높이는 방법

FCFS

도착한 순서대로 스레드를 준비 큐에 넣고 도착한 순서대로 처리

• 스케줄링 파라미터 : 스레드 별 도착 시간
• 스케줄링 타입 : 비선점 스케줄링
• 스레드 우선 순위 : x
• 기아 : x

스레드가 오류로 인해 무한 루프를 실행한다면 뒤 스레드의 기아o

• 성능 이슈

처리율 : 낮음

• 호위 효과 발생 : 긴 스레드가 CPU를 오래 사용하면, 늦게 도착하면 짧은 스레드는 오래 대기

SJF

가장 짧은(최단작업) 스레드 우선 처리

스레드가 도착할 때, 예상 실행시간이 짧은 순으로 큐 삽입, 큐의 맨 앞에 있는 스레드 선택

• 스케줄링 파라미터 : 스레드 별 예상 실행 시간
• 스케줄링 타입 : 비선점 스케줄링
• 스레드 우선 순위 : x
• 기아 : o

지속적으로 짧은 스레드가 도착하면, 긴 스레드는 언제 실행 기회를 얻을지 예측x

• 성능 이슈

짧은 스레드가 먼저 실행되므로 평균 대기 시간 최소화

• 문제점

실행 시간의 예측이 x 현실에서는 거의 사용x

SRTF

최소 잔여 시간 우선 처리

• SJF의 선점 스케줄링 버전

실행시간이 짧은 순으로 스레드들을 큐에 삽입, 한 스레드가 끝나거나 실행시간이 더 짧은 스레드가 도착할 때, 가장 짧은 스레드 선택

큐의 맨 앞에 있는 스레드 선택

• 스케줄링 파라미터 : 스레드 별 예상 실행 시간과 남은 실행 시간 값

이 시간을 아는 것은 불가능. 비현실적

• 스케줄링 타입 : 선점 스케줄링
• 스레드 우선 순위 : x
• 기아 : o

지속적으로 짧은 스레드가 도착하는 경우 긴 스레드는 언제 실행 기회를 얻을 수 있을지 예상x

• 성능 이슈

실행 시간이 짧은 프로세스가 먼저 실행되므로 평균 대기 시간 최소화

• 문제점

실행 시간 예측이 불가능하므로 현실에서는 거의 사용되지 않음

RR

스레드들을 돌아가면서 할당된 시간(타임슬라이스)만큼 실행

• 도착하는 순서대로 스레드들을 큐에 삽입
• 타임 슬라이스가 지나면 큐 끝으로 이동
• 스케줄링 파라미터 : 타임 슬라이스
• 스케줄링 타입 : 선점 스케줄링
• 스레드 우선 순위 : x
• 기아 : x

스레드의 우선순위가 없고, 타임 슬라이스가 정해져 있어, 일정 시간 후에 스레드는 반드시 실행

• 성능 이슈

공평하고, 기아현상 없고, 구현이 쉬움

잦은 스케줄링으로 전체 스케줄링 오버헤드가 큼. 특히 타임슬라이스가 작을 때 더욱 큼

균형된 처리율 : 타임슬라이스가 크면 FCFS에 가까움, 작으면 SJF/SRTF 에 가까움

늦게 도착한 짧은 프로세는 FCFS보다 빨리 완료되고, 긴 프로세스는 SJF보다 빨리 완료됨

Priority

우선순위를 기반으로 하는 스케쥴링

• 가장 높은 순위의 스레드 선택현재 스레드가 종료되거나 더 높은 순위의 스레드가 도착할 때, 가장 높은 순위의 스레드 선택

모든 스레드에 고정 우선 순위 할당, 종료 때까지 바뀌지 않음

도착하는 스레드는 우선순위 순으로 큐에 삽입

• 스케줄링 파라미터 : 선점/비선점 스케줄링

선점 스케줄링 : 더 높은 스레드가 도착할 때 현재 스레드 강제 중단하고 스케줄링

비선점 스케줄링 : 현재 실행 중인 스레드가 종료될 때 비로소 스케줄링

• 스레드 우선 순위 : o
• 기아 : o

지속적으로 높은 순위의 스레드가 도착하는 경우 언제 실행 기회를 얻을 수 있을지 예상x

큐 대기 시간에 비례하여 일시적으로 우선순위를 높이는 에이징 방법으로 해결 가능

• 성능 이슈

높은 우선순위의 스레드일 수록 대기 혹은 응답시간 짧음

• 특징

스레드 별 고정 우선 순위를 가지는 실시간 시스템에서 사용

MLQ

스레드와 큐 모두 n개의 우선순위 레벨로 할당. 스레드는 자신의 레벨과 동일한 큐에 삽입

고정된 n 개의 큐 사용, 각 큐에 고정 우선순위 할당

각 큐는 나름대로의 기법으로 스케줄링

스레드는 도착 시 우선 순위에 따라 해당 레벨 큐에 삽입. 다른 큐로 이동할 수 없음

가장 높은 순위의 큐가 빌 때, 그 다음 순위의 큐에서 스케줄링

• 스케줄링 파라미터 : 스레드의 고정 우선순위
• 스케줄링 타입 : 비선점/선점o

비선점 스케줄링 : 현재 실행중인 스레드가 종료할 때 비로소 스케줄링

선점 스케줄링 : 높은 레벨의 큐에 스레드가 도착하면 중단하고 높은 순위의 레벨 큐에서 스케줄링

• 기아 : o

지속적으로 높은 순위의 스레드가 도착하는 경우 언제 실행 기회를 얻을 수 있을지 예상x

• 성능 이슈와 활용 사례

스레드의 고정 순위를 가진 시스템에서 활용

• ex : 전체 스레드를 백그라운드 스레드와 포그라운드 스레드의 2개의 그룹을 구성
• ex : 시스템 스레드, 대화식 스레드, 배치 스레드 등 3개의 레벨로 나누고 시스템 스레드를 우선적으로 스케줄링
• ex : 대학에서 교수, 교직원 , 대학원생, 학부생 등 사용자를 4개의 레벨로 나누고, 사용자에 따라 실행시킨 스레드 레벨로 스케줄링

MLFQ

큐만 n개의 우선순위 레벨을 둠. 스레드는 레벨이 없어 동일한 우선 순위

• 설계 의도

기아를 없애기 위해 여러 레벨의 큐 사이에 스레드 이동o

짧은 스레드와 I/O가 많은 스레드, 대화식 스레드의 우선처리. 스레드 평균대기시간 줄임

• n개의 레벨 큐

n개의 고정 큐. 큐마다 서로 다른 스케줄링 알고리즘

큐마다 스레드가 머무를 수 있는 큐타임 슬라이스가 있음. 낮은 레벨의 큐일 수록 더 긴 타임 슬라이스

I/O 집중 스레드(대화식 스레드)는 높은 순위의 큐에 있을 가능성이 높음

• 알고리즘

스레드는 도착 시 최상위 레벨의 큐에 삽입. 가장 높은 레벨의 큐에서 스레드 선택.

비어 있으면 그 아래의 큐에서 스레드 선택

스레드의 CPU-burst가 큐 타임 슬라이스를 초과하면 강제로 아래 큐로 이동 시킴

스레드가 자발적으로 중단한 경우, 현재 큐의 끝에 삽입스레드가 I/O로 실행이 중단된 경우, I/O가 끝나면 동일한 레벨 큐 끝에 삽입

큐에 있는 시간이 오래되면 기아를 막기 위해 하나의 위 레벨 큐로 이동

최하위 레벨 큐는 주로 FCFS나 긴 타임 슬라이스의 RR로 스케줄.

스레드들은 다른 큐로 이동x

• 스케줄링 파라미터 : 각 큐의 큐 시간 할당량
• 스케줄링 타입 : 선점 스케줄링
• 스레드 우선 순위 : x
• 기아 : x

. 큐에 대기하는 시간이 오래되면 더 높은 레벨의 큐로 이동시킴(에이징 기법)

• 성능 이슈

짧거나 입출력이 빈번한 스레드, 혹은 대화식 스레드를 높은 레벨의 큐에서 빨리 실햄 -> CPU 활용률이 높음

멀티코어 PCU에서의 스케줄링

멀티코어 시스템의 구조

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

멀티 코어 시스템에서의 CPU 스케줄링

• 멀티코어 시스템에서 싱글코어 CPU의 스케줄링을 사용할 때 문제점

1) 컨텍스트 스위칭 오버헤드 증가문제

• 이전에 실행된 적이 없는 코어에 스레드가 배치될 때
• 캐시에 새로운 스레드의 코드와 데이터로 채워지는 긴 경과 시간
• 해결
  • CPU 친화성 (CPU affinity) 적용
  • 스케드를 동일한 코어에서만 실행하도록 스케줄링
  • 코어 친화성 (Core affinity), CPU 피닝(pinning), 캐시 친화성(cache affinity) 라고도 부름

2) 코어별 부하 불균형 문제

• 스레드를 무작위로 코어에 할당하면, 코어마다 처리할 스레드 수의 불균형 발생
• 해결
  • 부하 불균등 기법으로 해결
  • 푸시 마이그레이션 : 감시 스레드가 짧거나 빈 큐를 가진 코어에 다른 큐의 스레드를 옮겨놓는 기법
  • 풀 마이그레이션 : 코어가 처리할 스레드가 없게 되면, 다른 코어의 스레드 큐에서 자신이 큐에 가져와 실행시키는 기법

출저 : https://velog.io/@passion_man/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-5.-CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81