목표
CPU 스케줄링의 여러가지 알고리즘에 대해 알아본다.
Scheduling Algorithms
FCFS
- 빼앗지 않는다.
- 선착순대로
- cpu 스케줄링은 이 방법을 안좋아해.
전쟁이 났을 때 Convoy effect는 좋은 효과다. 안죽는 병사가 앞에서 뻐팅기니까 뒤 병사가 호위되는 좋은 효과다. 근데 cpu 스케줄링에서는 안좋음
SJF
- cpu를 가장 짧게 쓰는 job한테 cpu를 먼저 준다.
- 2가지 중 평균 대기 시간을 더 짧게 하는 방법일까? 더 짧은 애가 도착하면 걔한테 cpu를 주는 방법이 더 optimal하다. : SRTF 남은시간이 더 짧은 친구한테 CPU를 주는 방법
Example of Non-Preemptive SJF
Example of Preemptive SJF
SJF가 Optimal 하니까, 다른 알고리즘은 안배워도 되는걸까?
nope !!!. 치명적인 약점이 있다.
굶어죽는 starvation을 발생시킬 수 있다.
long job은 영원히 cpu를 못얻을 수 있다. => 그래도 기회가 오지 않을까? => queue가 계속 쌓일 수 있기 때문에 long job에게도 기회를 !!!
두번째 문제점은, 누가 짧게 쓰는지 누가 길게 쓰는지 처음에 안알려준다. !!!! cpu burst를 알 수 없다. => 그럼 sjf는 쓸 수 없는 것인가? => 그렇지 않다. 예측을 하면 된다. 이 친구의 과거의 cpu burst를 보면 예측 가능할 것임.
다음 CPU Burst Time의 예측
- 최신 cpu burst를, 직전꺼를 더 반영한다
요약을 하자면,
sjf는 cpu burst가 더 짧은 친구한테 cpu를 주는 것이다.
=> 이 방법의 문제점은 starvation이 생길 수 있다는 문제가 있다.
=> 또 한가지 문제점은 cpu burst를 알 수 없다.
=> 과거를 통해 예측할 수는 있다.
Priority Scheduling
Round Robin
실제로 cpu 스케줄링에서 근간이 되는, 제일 많이 사용되는 방법이다.
- response times은 본인이 cpu를 쓰고자 하는 queue에서 첫번째 응답시간까지다. (단무지 나오기까지 걸리는 시간)
- interact가 많은 상황에서, 대단히 좋은 장점이 된다.
- long job과 short job이 함께 있기 때문에 round robin을 쓰는 것이다. => 만약 전부다 10초 짜린데 1초짜리 round robin을 돌면 어떻게 되는가?,, => 조금씩 일처리를 하다가 말고, 하다가 말고 맨 마지막에 다같이 집 가는 상황이 생긴다. 한명씩 다 처리했으면 한명씩 집 갔을 텐데,,, => response time은 빠르지만
- 기다리는 시간이 본인이 CPU를 쓰려는 시간에 비례하다. => SHORT JOB은 한번에 할당 시간 내에 다 쓰고 나가지. LONG JOB은 얻었다가 뺏겼다가를 반복한다. => CPU를 다섯번에 걸쳐야 하는 친구는 다섯번 기다린거고, SHORT JOB은 한번만 기다릴 수 있다. => ROBIN ROUND는 short job과 long job 특별히 누가 손해본 건 없고, 공평하다. !!!!
이건 그냥 참고사항
강의 기록 블로그