□공평성 :cpu 스레드들에게 공평하게 배분 → 시분할로 스케줄링 사용 ( 기아 스레드가 생기지 않도록 !!!!) [사용자 입장]
EX)10개의 스레드 중 1시간 동안 9개의 스레드만 계속 실행되고 1개는 전혀 할당 받지 못하면 공평성이 부족한 상황 ( 기아 상태 발생 )
⭐️ 공평성이 높아지면 cpu 활용률은 떨어진다 (RR생각하면 됨)
□응답시간 : 사용자에 대한 응답 시간 최소화 [사용자 입장]
EX) 사용자가 웹에서 페이지를 클릭했을때 뜨기까지의 시간이 5초 걸렸다면 응답 시간이 5초인것임.
□대기시간 : 스레드가 준비큐에서 머무르는 총 시간. [운영체제, 사용자 입장]
EX) [ new - Ready - Running ]
□소요시간:작업을 시작시킨 사용자가 결과를 얻기까지 걸린 총 시간.[사용자 입장]
대기 시간 + 실행 시간 + I/O 시간 등 모든 시간
EX) 사용자가 웹 페이지를 클릭하기전 대기 10초(대기시간) 클릭한 후 뜨는 시간이 5초(응답 시간)이면 소요 시간은 15초임.
□시스템 정책 우선 : 컴퓨터 시스펨의 특별한 목적을 달성하기 위한 스케줄링.[ 운영체제 입장]
EX) 급여 시스템에서 안전을 관리하는 스레드를 우선 실행하는 정책.
□자원 활용률 : CPU나 I/O장치 등 자원이 놀지 않도록 자원 활용률을 극대화 하는 것.
타임 슬라이스 , RR
: 하나의 스레드가 너무 오래 cpu를 사용하도록 허용하지 않음→ 스케줄된 스레드에게 한번 할당하는 cpu 시간
RR( 라운드 로빈) 스케줄링을 구현하는데 핵심적인 매개변수
CH02
스케줄링이 언제 시행 될까
1)CPU 활용률 향상 목적: 스레드가 I/O를 요청하는 시스템 호출을 실행하여 블록 상태가 될거나 ,
자원이 기다리는 상태가 될때 다른 스레드에 cpu를 할당하는 경우
2) cpu 자발적 양보 : 스레드가 yield() 호출을 통해 스스롤 실행을 중단하고 cpu를 자발적으로 내놓을때,
현재 스레드를 Ready 상태로 만들어 준비 리스트에 넣고 cpu 스케줄링 실행.
3)균등한 CPU 분배 목적 :스레드에 할당된 타임 슬라이스가 소딘되어 타이머 인터럽트 발생할때,
ISR내에서 cpu 스케줄링 실행.
4)우선 순위를 지키기 위한 목적 : 현재 실행중인 스레드 보다 우선순위가 더 높은 스레드가 요청한 입출력 작업이 완료되어 I/O인터럽트 발생한 경우, ISR에서 현재 스레드를 강제로 중단(선점) 시켜 준비 상태로 만들고 I/O를 기다렸던 더 높은 스레드를 스케줄링하여 실행.
CPU 스케줄링 코드의 위치와 실행 시점
1. CPU스케줄링을 담당하는 별도의 커널 스레드나 프로세스가 있는가? 없다
스케줄링 코드는 시스템 호출이나 ISR에 의해 호출되는 코드(함수 ) 형태로 존재
2. 스케줄링 코드가 실행되는 시점은 어디인가?
CPU 스케줄링 코드는 시스템이나 ISR이 서비스를 마치는 마지막 단계에서 실행.
디스패치
1) 스케줄러에 의해 선택된 스레드를 cpu가 실행하도록 하는 커널 코드 중 일부.
2) 컨텍스트 스위칭을 실행하는 커널 코드로 이전에 중단되었던 B 스레드가 다시 실행을 시작함.
⭐️ 디스패치 코드와 스케줄링 코드 둘다 실행 시간이 가능한 짧아야 함.
선점 스케줄링 & 비선점 스케줄링 (선점 2가지, 비선점 3가지 발생 경우)
선점: 현재 실행 중인 스레드를 강제로 중단 시켜 준비리스트로 이동 시키고 스케줄링함.
비선점: 실행 중인 스레드가 더이상 cpu를 사용할 수 없는 상황에서 스케줄링함. 강제 종료 없이 무조건 끝까지 수행함.
비선점: 현재 실행중인 스레드를 강제로 중간시키지 않는 타입.
⭐️⭐️⭐️
1) 실행 중인 스레드가 더이상 cpu를 사용할 수 없는 상황 : I/O로 인한 블록 상태, sleep()
2) 자발적 CPU 양보 : yield() 시스템 호출
3) 스레드 종료
선점 : 현재 실행중인 스레드를 강제 중단 시키 준비 상태로 만들고 다른 스레드 선택. (현재 방식)
⭐️⭐️⭐️
1) 타임슬라이스가 소진되어 타이머 인터럽트가 발생될 때
2) 인터럽트나 시스템 호출 종료 시점에서, 더 높은 순위의 스레드가 준비 상태일 때.
선점 환경에서 모든 종류의 스케줄링 유발 사례를 보여주고 있음.
기아 & 에이징
기아
: 스레드가 스케줄링에서 선택되지 못한 채 오랜동안 준비 리스트에 있는 상황
: 언제 cpu를 사용할지 알 수 없는 경우
에이징 (기아 해결책)
: 스레드가 준비 리스트에 머무르는 시간(대기시간)에 비례하여 스케줄링 순위
→ 예를 들면 경로 우대라 생각하면 된다고 하심.
→ 오래 기다릴 수는 있지만 언젠가는 가장 높은 순위에 도달하는 것 보장
CH03 CPU 스케줄링 알고리즘
선점에 들어가 있는 스케줄링 기법 / 비선점에 있는 스테줄링 기법 구분하기 (중요)
1. FCFS(First Come First Served)(비선점 스케줄링)
도착한 순서대로
먼저 도착한 스레드 먼저 스케줄링 (선입선처리)
기아가 발생하지 않음
스레드 우선순위 없음.
→ 평균 대기 시간 계산 하는거 알아두기
대기 시간 ( 반환-실행)
반환시간 (종료-도착) : 대기 +실행 OR 종료 -도착
t1
0
4
t2
3
6
t3
5
6
t4
3
6
소요 시간
11+11=22
22
2. SJF(Shortest Job First)(비선점 스케줄링)
가장 짧은 스레드 우선 처리 | 이건 기아 발생함.
실행시간이 제일 짧은 스레드를 먼저 처리함. , 실행시간을 아는건 비현실적임
스레드 우선순위 없음.현재는 같은 크기의 스레드에 대해서 FCFS를 적용해서 T2가 선택됨.
대기 시간 ( 반환-실행)
반환시간 (종료-도착) : 대기 +실행OR 종료 -도착
t1
0
4
t2
4
7
t3
2
3
t4
3
6
9(대기)+11(실행)
20
3. SRTF (Shortest Remaining Time First)(선점 스케줄링)
남은 시간이 짧은 스레드가 준비 큐에 들어오면 이를 우선 처리
최소 잔여 시간 우선 스케줄링
남은 실행 시간이 가장 짧은 스레드 선택
기아 발생 | 스레드 우선순위 없음.
실행시간 예측이 불가능하므로 현실에서는 거의 사용되지 않음(이런게 있다 정도만 알아두기)
대기 시간 ( 반환-실행)
반환시간 (종료-도착) : 대기 +실행OR 종료 -도착
t1
1
5
t2
4
7
t3
0
1
t4
3
6
소요시간
8+11=19
19
4. Round-Robin(선점 스케줄링)
스레드들을 돌아가면서 할당된 시간(타임 슬라이스)만큼 실행.
스레드들에게 공평한 실행 기회를 줌.
큐에 대기중인 스레드들을 타임 슬라이스 주기로 돌아가면서 선택함.
기아 없음, 스레드 우선순위 없음.
스케줄링 파라미터 : 타임 슬라이스
균형된 처리율 : 타임슬라이스가 크면 FCFS에 가까움, 적으면 SJF/SRTF에 가까움
단점 : 오버헤드가 많이 일어남 (타임 슬라이스가 작으면 오버헤드가 너무 많이 발생함)
타임 슬라이스 2일때→스케줄링이 총 6번 일어남.
대기 시간 ( 반환-실행)
반환시간 (종료-도착) : 대기 +실행OR 종료 -도착
t1
3
7
t2
4
7
t3
2
3
t4
3
6
소요 시간
12+11=23
23
타임 슬라이스가 1일때
대기 시간 ( 반환-실행)
반환시간 (종료-도착) : 대기 +실행OR 종료 -도착
t1
5
9
t2
4
7
t3
1
2
t4
3
6
소요 시간
13+11=24
24
5. Priority Scheduling(선점/비선점 스케줄링 둘 다 구현 가능)
우선 순위를 기반으로 하는 스케줄링. 가장 높은 순위의 스레드 먼저 실행
스레드 우선순위 있음. | 기아 발생 가능
6. MLQ(Multilevel queue scheduling)(선점/비선점 스케줄링 둘 다 구현 가능)
스레드와 큐 모두 n개의 우선순위 레벨로 구분, 레벨이 높은 스레드를 우선 처리하는 목적.
스레드는 다른 큐로 이동하지 못함
예) background process, Foreground process
우선순위 있음. | 기아가 발생함. (레벨이 높은 순위만 먼저 들어가고 레벨 낮은건 무한정 대기함)
→ 멀티 레벨 큐임.
→EX) 내가 입출금한다고 대기하고 있는데 갑자기 대출 상담 갈 순 없음 (이걸 개선한게 밑에꺼)
7. MLFQ(Multilevel feedback queue scheduling)(선점/비선점 스케줄링 둘 다 구현 가능)
큐만 n개의 우선순위 레벨을 둠. || 스레드는 동일한 우선순위 (우선 순위가 없는것 = 동일한 우선순위)
스레드는 제일 높은 순위의 큐에 진입하고 큐타임슬라이스가 다하면 아래 레벨의 큐로 이동
낮은 레벨의 큐에 오래 있으면 높은 레벨의 큐로 이동
Multilevel queue scheduling의 단점을 보완해주는 거
최하위 레벨 큐는 주로 FCFS나 긴 타임 슬라이스의 RR로 스케줄. 스레드들은 다른 큐로 이동 못함
기아가발생하지 않음 !! MLQ와 차이점 (대기하는 시간이 높아지면 다른 레벨 큐로 이동시켜줌)
MLQ와 MLFQ의 차이점 : 기아 발생 여부 (처리 방식 알아두기 - 기아가 발생하는 이유, 발생하지 않는 이유)
CPU burst가 짧은 스레드나 I/O작업이 많은 스레드 or 대회식 스레드를 우선 실행시켜 스레드의 평균 대기 시간을 줄이기 때문.
i/o완료후 어디서 나오는지 봐두기
T1이 i/o 작업이 가장 많이 발생함.
T3를 따라가면 개념에서 말하는 대기하는 시간이 높아지면 다른 레벨 큐로 이동시켜줌 이 말이 이해가 감.
Q3=2ms임.
EX) 대학에서 교수, 교직원, 대학원생, 학부생 등 사용자를 4개의 레벨로 나누고, 사용자에 따라 실행시킨 스레드 레벨로 스케줄링
CH04 멀티 코어 CPU에서의 스케줄링
프로세스1 : 싱글 스레드
프로세스 2 : 스레드 2개 이용
프로세스 3 : 스레드 3개 이용
멀티코어 시스템에서 싱글 코어 CPU 스케줄링을 사용할 때 문제점
(문제 1) 컨텍스트 스위칭 후 오버헤드 문제
이전에 실행된 적이 없는 코어에 스레드가 배치될 때,
컨텍스트 스위칭 후, 실행 중에 새로운 스레드의 코드와 데이터가 캐시에 채워지는 긴 경과 시간
(문제 2) 코어별 부하 불균형 문제
스레드를 무작위로 코어에 할당하면, 코어마다 처리할 스레드 수의 불균형 발생
컨텍스트 스위칭 후 오버헤드 문제 해결( 중요)
-cpu 친화성 적용 : 스레드를 동일한 코어에서만 실행하도록 스케줄링.
-코어 당 스레드 큐 사용 : 한 코어에서 실행이 중단된 스레드를 다시 동일한 코어의 큐에 삽입하는 방법.
코어당 스레드 큐
부화 균등화 기법( 그냥 참고만)
푸시 마이그레이션 기법 : 감시 스레드가 짧거나 빈 큐를 가진 코어에 다른 코의 스레드를 옮기는 기법.
풀 마이그레이션기법 : 코어가 처리할 스레드가 없으면 다른코어의 스레드를 자신의 큐로 가져와 실행
