다중프로그래밍
시분할...?
여러 프로세스 중 누구를 선택하고 cpu를 넘겨줄지에 대한 선택 기준이 스케줄링 기법
4.1 스케줄링의 단계
수행단계 : 장기, 중기, 단기 스케줄링
4.2 스케줄링 목적과 기준
시스템성능 높이기 = 스케줄링목적
<사용자관점>
-응답시간이 얼마나 빠르니?
-일괄처리 즉 반환시간이 얼마나 빠르니?
-예측가능성이 높고 응답시간이 빠를수록 성능이 좋다고 본다
<시스템관점>
-스ㅔ줄링을 통해 cpu얼마나 잘 활용했니? 처리량과 활용도
처리량은 단위시간에 완료된 프로세스 개수, 활용도는 주어진 시간동안 CPU가 실제로 가동된 시간의 비율로 계산한 지표
공평성이 권장되며 cpu 사용시간 공평하게 나눠주는 편이 좋다
<무엇을 우대할까?>
-연산위주 프로세스(CPU bound) : 연산이 입출력에 비해 상대적으로 많을 때
-입출력위주 프로세스(I/O bound) : 입출력이 상대적으로 많을때 (70~80% 차지)
-응답시간을 우선할지 처리량을 우선할지 고려한다
4.3 스케줄링 기법들
-스케줄링이 가동되어야 할 시점들(언제 스케줄링이 가동되어야 하느냐??)
1) 프로세스 실행상태에서 대기상태로 전환될 때. 예) 입출력 요청
2) 프로세스가 실행상태에서 준비상태로 전환될 때. 예) 시간종료와 같은 인터럽트 발생 시
3) 프로세스가 대기 상태에서 준비상태로 전환될 때 예) 입출력 종료시
4) 프로세스가 수행을 마치고 종료될 때
1), 2)의 경우 : 비선점 스케줄링
3), 4)의 경우 : 선점 스케줄링
비선점 스케줄링 : 한 프로세스가 cpu 할당받았을 때 cpu 스스로 반납할 때까지계속 사용하도록 허용하는 방법 (한번 실행되면 끝까지 간다~)
-> 프로세스가 실행상태에서 대기상태로 전환될때(입출력요청)
-> 프로세스가 수행을 마치고 종료될 때
선점스케줄링 : cpu할당받아 실행중인 프로세스로부터 cpu를 우선순위 높은 프로세스가 도착하면 cpu빼앗아서 사용하는 것 (실행되다가 중간에 뺏겨..)
-> 프로세스가 실행상태에서 (다른 프로세스에 의해) 준비상태로 전환될 때
-> 프로세스가 (다른 프로세스에의해) 대기 상태에서 준비상태로 전환될 때
1) FCFS(First come First Service)
: cpu 독점 사용하는 비선점방식, 들어온 순서대로 순차적으로 진행된다
: 대화식 시스템에 적합하지 x, 평균응답시간 길어질 수 있음
: 다른 스케줄링 기법의 보조장치로 사용하기 좋음, 도착순서만이 실행순서를 결정짓는다는 점에서 공평하다고 말할 수 있음. 준비상태 프로세스들의 개수와 크기를 짐작할 수 있다면 각각의 프로세스의 실행 시간을 예측할 수 있다.
cpu 요구량을 계산한다.그러기 위한 결과값 : 평균 응답시간(average waiting time)을 본다 (각 프로세스가 끝나는 시간을 보고 평균 응답시간(완료시간)을 계산한다)
평균대기시간 = 평균응답시간 = average waiting time
응답시간을 근접하게 표현할 수 있는 것 평균대기시간을 말한다
선점 : fcfs
비선점: spn
2) SPN(Shortest Process Next) 스케줄링
: 프로세스 중 가장 짧은 놈부터 cpu가져다 실행시키는 비선점방식
: 평균응답시간 최소화 가능
: 프로세스 사이즈가 우선순위!
: 기준이 도착시간 짧은순 > cpu 요구량
-단점
1)실행시간 긴 프로세스가 cpu 할당받지 못해서 대기하는 무한 대기현상이 발생한다.
*에이징기법 : 기다린만큼 우선순위를 높여 실행 가능성을 높여주는 방식으로 해결한다
2)각 프로세스들의 크기를 실행 이전에는 정확히 확인 불가(프로세스가 오고 있으니까..) 그런데 그 크기를 갖고 스케줄을 해야하니까(도착시간이 프로세스마다 다른데...오면 바로 스케줄링 하니까...허점이 많아요 ㅎㅎ)
average waiting time? 평균 대기 시간? -
이해갔음!
도착시간에 대한 걸 기준으로 계산하는 거였음!
0(바로 실행) + 이미 p2, p3 도착함..! 이 중 p3가 cpu더 짧기 때문에 먼저 실행됨
{0(바로실행) + (10-1) + (12-0.5)}/3
즉 (0+9+11.5)/3=Average Waiting Time이 되겠음
평균대기시간 != 평균응답시간
+future knowledge기법 존재??
: 미래 도착시간을 미리 안다면..! 그 도착시간을 지연시켜서 cpu 요구량이 짧은 애부터 실행시키는 기법
중요한 건 idle 시간이 있다는 거다! SPN을 토대로 만들어짐!!!
3) SRT(Shortest Remaining Time)
: SPN을 선점 방식으로 운영한다
: 실행도중 남은 실행시간이 더 짧은 프로세스가 준비큐에 들어오면, 현재 실행인 것을 중단하고 새 프로세스에게 cpu를 할당한다(선점방식)
: 적은놈 먼저 진행하는게 장땡임~
: 기준이 cpu 요구량 > 도착시간 짧은순!!
SRT의 AWT도 구해봄
{0+(7.5-0.5)+(3-1)}/3
p1은 들어오자마자 실행되었고, waiting이 전혀 없었다!
질문) p2가 실행된게 부분부분 실행되었는데, 1-0.5를 해줘야하는 거 아닌가?
4) HRRN (Highest Response Ratio Next)
: SPN과 SRT 방식의 약점! 수행시간이 긴~프로세스의 무한대기 현상!!을 방지!!하려고 요놈이 등장했다~
: 준비 큐에 있는 프로세스들 중에서~응답률이 가장 높은 프로세스에게 높은 우선순위를 준다
: 비선점방식, 응답률 높은애부터 끝까지 간다~~
응답률 = (대기시간+CPU 요구량) / CPU 요구량 : 많이 기다렸고, cpu요구량 큰 놈
5) 라운드로빈 스케줄링(Round Robin)
: Fcfs기반으로 cpu할당하지만, 시간할당량(time quantum)이 지나면 시간종료 인터럽트에의해 cpu를 뺏기게 됨 -> cpu를 골고루 분배해주겠다는 전략..!
: 선점방식
장점
-선입선출에서의 단점인 한 프로세스가 cpu 독점문제 방지가능하다
단점
-문맥 오버헤드가 많다, 그럼에도 대화식 시스템이나 시분할 시스템에 적합한 방식이다(장점)
시간할당량에 따라
-시간할당량이 크다 : Fcfs방식과 같아진다
-시간할당량이 아주 작다 : 문맥교환의 오버헤드가 커진다 (적절한 시간할당량 세팅이 중요하겠다)
5-1) 가상 라운드로빈 (virtual rr)
: 입출력 완료큐가 하나 더 있는 것이다. 2번 우선순위가 더 높다
: i/o 완료가 되면 2번 입출력완료큐로 간다. i/o에 못 쓰고 남은 시간할당량분만 2번에 올라간 i/o를 cpu에 가져다 준다. 불균형? 어쩌구를 상쇄하기 위해 생긴 기법
선점 : fcfs, SRT, RR(Round Robin) (cpu 뺏김)
비선점: spn, HRRN (끝까지간다~~) (cpu 안뺏김)
!!우선순위스케줄링
: 프로세스에 주어진 우선순위에 따라 스케줄링한다
: 대부분 선점형이다
: 정적우선순위 - 프로세스가 생성될 때 부여된 우선순위가 완료될 때까지 변하지 않는다
: 동적우선순위 - 그 반대. 시스템에 있는 동안 조정되어 순위 받음
6) 다단계큐(Multi-level Queue)
: 정적 우선순위 스케줄링에 가장 적합한 자료구조
: 같은 우선순위 값을 갖는 프로세스들을 위해 큐가 필요함, 동시에 서로 다른 우선순위의 프로세스들을 구별하고 관리해야한다, 우선순위 개수만큼 큐가 필요하다 (0~31개 프로세스 : 32개의 큐 필요함)
: 우선순위 낮은 큐는 작업 실행중 상위 단계 큐 프로세스가 도착시 cpu 뺏긴다 ㅠㅠ
: 정적우선순위이기 때문에 큐들 간 프로세스의 이동은 불가능함다
: 선점방식
7) 다단계 피드백 큐(MFQ) 스케줄링
: 동적 우선순위, 상위단계 큐들이 모두 비어있을 경우 그 다음 순위의 큐에서 cpu를 받을 수 있고, 입출력이 발생하지 않는 한 할당된 시간을 다 사용할 수 있다!
: 프로세스 성격에 맞게 그때그때마다~~우선 순위 조정이 가능하므로 적응성있다!
: 우선순위 우대를 받는 기준은 어떻게 정해지지?? (질문하기)
: 적응성이 있는(Adaptive)스케줄링 기능이 있다. 프로세스의 성격에 맞도록 우선순위를 조정하기 때문에 적으엉있는 스케줄링이 가능하다
: I/O bound, CPU bound process에 따라 큐의 이동이 달라진다
?입출력 bound, cpu bound? 이게 뭘까? +뭐가 짧지?
8) fair-share 스케줄링
: 프로세스 특성, 중요도에 따라 나눠서 일정량의 각각의 그룹에 일정량을 할애한다. 다른 그룹에는 시간, 불이익 등이 없고 그룹 내 프로세스끼리만 선점방식이 존재하는 것
: time-sharing + fair sharing 방식으로 진행
4.4 실시간 스케줄링
: ㅎㅎㅎ...어렵다 ㅠㅠㅠㅠㅠ
: 이건 패스...포기한다
: real time 스케줄링 : 마감시간 내에 스케줄링을 끝내야한다
정적인 방법 : 프로세스 특징, 개수 알면 사용
동적인 방법 : 프로세스 생성시간이나 특성 알 수 없을 경우 사용
RM(Rate Monotonic) 스케줄링
: 정적 스케줄링방식, 크기와 개수가 알려진 프로세스들이 각자 주기적으로 발생되는 환경에서 사용한다, 주기가 짧을수록 높은 우선순위를 받는다.
주기가 짧은 애들이 먼저 실행된다!
2/3 + 2/6 = 1 (가능하다!) 1이하면 무조건 가능이다
밑에 그림을 보면 완료가 안되었음, 실패!
EDF(Earlist Deadline First) 스케줄링
: 프로세스 마감시간에 가까운 순서로 우선순위를 높게 준다
: rm적용 가능하면 edf도 적용 가능하다
: 선점방식
: 동적 스케줄링
: 결과가 1이면 무조건 된다
마감시간이 짧은 애부터..!! 먼저 집에 보내줘야하니까~!! 먼저 cpu 돌려주는거야
각각의 task 들은 상호독립적이다! 그럴때 해당하는 개념이다!!
(pip, pcp 스케줄링 같은 경우는 task가 상호 의존적일때의 개념으로 학부수준에서는 패스한다. 이름만 알아두기)
