다중 프로그래밍이 아니면 cpu 스케쥴링을 고려할 필요가 없습니다.
여러 프로세스가 돌고 있기 때문에 스케줄링이 필요한 것 이죠
cpu버스트를 이용한 스케줄링은 적절히 섞는 것입니다.
적절히 혼합한다
짧은 프로세서 버스트, 긴 입출력 버스트를 먼저 수행해야 합니다.
먼저 끝나기 때문입니다.
입출력 중심 버스트를 먼저 처리하는 게 유리합니다.
1번 같습니다.
아니였습니다.
3번이었습니다.
먼저 들어온 것을 처리하면 공정하게 처리가 안될 수 있습니다.
짧게 cpu를 사용하는 것을 먼저 처리해야 합니다.
스케줄링 단계
단기 스케줄링으로 갈수록 수행 빈도가 높습니다.
- 작업이 도착하면 디스크에 도착합니다.
- 그것을 메모리에 올려서 "프로세스 화" 합니다.
- 그리고 준비 큐에 넣습니다.
- 결국은 프로세스로 만드는 과정입니다.
이러한 과정을 장기(작업) 스케줄러입니다.
우리가 아는 스케줄러는 준비 큐에서 cpu로 보내는 것입니다.
이것을 단기(프로세서) 스케줄러입니다.
장기 스케줄링의 중요한 역할이 다중 프로그래밍 정도를 조절하는 것입니다. 왜 그럴까요?
다중 프로그래밍 정도가 높으면 프로세스가 100개가 도는 것이고 낮으면 10개가 도는 것입니다.
많이 메모리에 올려놓을 것인지, 조금 올려놓을 것인지 결정하는 것입니다.
- 장기 스케줄링 - 디스크에서 메모리로 얼마나 올릴지
- 단기 스케줄링 - 메모리에 있는 것들을 cpu에 갔다 놓는 역할
중기 스케줄링
- 준비 큐에 넣었어도 무슨 이유로 메모리를 차지하지 않고 다시 디스크에 나가 있어야 할 때도 있습니다.
- 사용자가 강제로 내보낼 수도 있고, 안에 많은 프로세스가 있어서 일 수도 있습니다.
- 그런 애들은 다시 준비 큐에 들어와야 합니다.
이러한 상태를 "중단 상태"라고 합니다.
중기 스케줄링은 중단 상태를 결정합니다.
프로세스가 new에 들어가는 건 "장기 스케줄러"가 합니다.
실행 -> 대기로 가는 것은 스케줄러의 역할은 아닙니다.
준비 상태에서 뭘 실행상태로 넣을지 결정하는 것은 "단기 스케줄러"가 합니다.
- Blocked -> Blocked Suspend
- Ready -> Ready Suspend
는 "중기 스케줄러"의 역할입니다.
중기 스케줄러는
내보낼 때는 메모리
들어올 때는 디스크에서 선택합니다.
장기 스케줄러입니다.
단기 스케줄러입니다.
단기 스케줄러
중기 스케줄러는 프로그래밍 정도를 조절합니다.
스케줄링 큐
준비 큐, 대기 큐
- 자식 프로세스가 끝나기를 대기하는 큐
- 뭔가를 자기가 자발적으로 인터럽트가 오기를 기다리고 있는 큐
- cpu를 사용하기 위한 큐
- i/o를 사용하기 위한 큐
time slice expired -> cpu에서 실행하다가 "시간이 다돼서" 내쫓겨 나는 경우이니 바로 "준비상태"로 들어갑니다.
실행상태에서 "자발적"으로 나오는 경우는?
time slice expired를 제외한 3가지입니다.
모두 자기가 필요해서 기다려야 할 수밖에 없기 때문에 cpu에서 나온 것입니다.
결국 큐에서 기다리고 있는 것들이 뭐냐면 프로세스 제어 블록입니다.
큐는 줄 서기입니다.
- 디스크에 있는 큐입니다.
준비 큐
- cpu에 올라갈 프로세스가 기다리는 큐입니다.(메모리에 존재합니다.)
중단된 준비 큐( suspend queue)
- 원래 준비상태였다가 중단 상태로 간 거입니다.(큐에서 꺼내는 애는 중기 스케줄러입니다.),
(메모리에 프로레스가 많아서 내려온 상태입니다, 이것 또한 중기 스케줄러가 실행합니다.)
중단 상태는 하드디스크에 있습니다.
중단 큐
- cpu에서 자기 스스로 나와서 기다리고 있는 큐입니다.(메모리에 존재합니다.)
중단된 중단 큐, (suspend queue)
- 메모리에 다중 프로그래밍 정도가 커서 중단 큐에서 보내는 것입니다.
- 여기서 기다리고 있던 애들이 이벤트가 발생하면 중단된 준비 큐에 보냅니다.
디스패처
단기 스케줄러가 선택을 해주고
디스패처는 일꾼입니다.
원래 cpu를 쓰고 있는 프로세스의 레지스터를 PCB에 저장합니다.
그리고 새로운 프로세스를 cpu에 올립니다.
이러한 시간을 dispatch latency라고도 하고 Context Switcher라고도 합니다.
1번입니다.
나머지는 모두 대기 큐 에 있습니다.
1번은 준비 큐에 있습니다.
1번입니다.
이건 단기 스케줄러의 역할입니다.
선점 스케줄링과 스케줄링
선점 - cpu를 강제로 뺏는다.
비선점 - cpu를 스스로 종료, 이벤트를 기다리지 않으면 끝까지 합니다.
선점 - 강제로 내쫓기는 경우가 1가지 더 추가됩니다.(인터럽트 당할 때)
선 비 비
대화형 - 계속 답을 줘야 합니다. 그러면 오래 차지하고 있는 애들을 내보내야 합니다.
시분할 - 시간이 되면 내쫓아야 합니다.
문맥 교환이 적습니다.
스케줄러 - 지가 나올 때까지 내버려 둡니다.
일괄처리 - 한번 들어가서 혼자 쭉 실행할 수 있는 것입니다.
HRN - 기다린 시간까지 고려해서 조금 길더라도 먼저 해주는 것
- SRTF - 짧은 것을 먼저 해주다가 남은 작업이 더 짧은 게 있다면 바꿔서 해줍니다.
- Round-robin - 순서대로 돌아가면서 순서대로 자원을 할당해 줍니다.
스케줄링 알고리즘의 평가 척도
도착 - 메모리에 도착한다는 것입니다.
이 그림은 대기하는 시간이 없다고 가정하고 그린 것입니다.
사실 cpu를 계속 사용하는 게 아니고 대기하는 시간을 뺀 것입니다.
대기시간은 실행시간 중간중간에 껴있습니다.
P1의 대기시간은 0
반환시간은 그림만큼입니다.
3 -> 2 -> 1
반환 시간이 길어지려면 많이 기다리면 됩니다.
실행시간 + 대기시간이 반환시간인데 실행 시간은 고정되어 있으니 대기시간을 늘리면 됩니다.
12
8 + (8+5) +(8+5+2) = 36을 3으로 나누면 됩니다.
1 -> 2 -> 3
8
2 + (2+5) + (2 + 5 + 8) = 24를 3으로 나누면 8이 됩니다.
결국 짧게 실행 순서를 하는 게 평균 반환 시간이 적습니다.
FIFO 스케줄링
먼저 들어온 것을 먼저 처리
먼저 들어온 게 길면은 평균 대기시간과 평균 반환시간이 길어집니다.
운으로 스케줄링 하는 것입니다.
큐에 먼저 들어온 것이 대기시간이 많겠구나!
B가 먼저 실행될 것이다.
오래 기다린 것이 먼저 실행됩니다.
FIFO의 장/ 단점
프로세서가 쉴 일은 없습니다.(=처리율은 높다.)
최소 작업 우선 스케줄링(SJF, Shortest Job First)
이런 큐를 자료구조에서 우선수위 큐라고 배웠습니다.
알고리즘의 전재는 프로세스의 cpu 버스트를 모두 알아야 합니다.
장기 스케줄링에 많이 사용됩니다.
순서를 좀 바꿔 서서
대기 시간의 합이 가장 짧아지면 평균 반환시간도 짧아집니다.
SRT
짧은 것을 먼저 하긴 하는데 더 짧은 게 있다면 뺏어서 합니다.
preempitve 성격을 가지고 있습니다.
0시간에서는 P1 밖에 없기 때문에 P1을 실행한 것입니다.
P1이 1 실행한 순간 P1,2가 존재합니다.
remaining time은
- P1은 7
- P2는 4
그래서 P2를 실행합니다.
P2가 4를 실행한 순간 P1,3,4가 존재합니다.
remaining time은
- P1은 7
- P2는 0
- P3는 9
- P4는 5
그래서 P4를 실행합니다.
'Computer Science > OS' 카테고리의 다른 글
| 실제로 os에서 사용되는 스케쥴링, 다중프로세서에서 강결합된 공유 메모리 주소 2가지 비교, 다중 프로세서 스레드 스케줄링 (0) | 2021.11.30 |
|---|---|
| SJF, FIFO, 라운드로빈(RR), 다단계 큐(MQL), 다단계 피드백 큐(MLFQ), 응답비율(HRN) (0) | 2021.11.29 |
| 교착 상태 회복, 기아상태,교착상태 정리, 프로세스 스케줄링 (0) | 2021.11.22 |
| 은행가 알고리즘 코드, 시간복잡도, 회복 알고리즘 (0) | 2021.11.16 |
| 교착상태 회피 - 은행가 알고리즘 자세히 (0) | 2021.11.15 |
