[Operating System] 중간 범위 key note (Process ~ deadlock)
아래의 조건으로 MLFQ를 설계해야한다 (중요)
- 큐의 개수와/ 각 큐의 알고리즘 정책
- 큐간의 이동 조건(demotion/ upgrade) Ex) 각큐에서 할당 시간동안 못끝내면 하위큐로.
- 처음 들어오는 프로세스는 어떤 큐에? 그리고 running process 선택 조건
- ex) 처음 들어오면 무조건 q0에, 제일 하위(숫자 낮은) 큐가 우선순위가지고 스케줄됨
MLFQ의 규칙 요약
규칙 1 : 우선 순위가 높은 큐에 존재하는 프로세스들이 먼저 실행됩니다.
규칙 2: 작업들이 같은 우선 순위를 가진다면 RR을 사용하여 실행합니다.
규칙 3 : 작업이 시스템에 진입하면, 가장 높은 우선순위 즉 맨 위의 큐에 놓여진다.
규칙 4 : 주어진 단계에서 시간 할당량을 소진하면 ( CPU를 몇 번 양도하던 상관없이 ), 우선 순위는 낮아진다.
규칙 5 : 일정 기간 S가 지나면, 시스템의 모든 작업을 다시 최상위 큐로 이동시킵니다
- 기아 상태(starvation)가 발생할 수 있다.
시스템에 너무 많은 대화형 작업이 존재하면 그들이 모든 CPU 시간을 소모하게 될 것이고 따라서 긴 실행 시간 작업은 그 작업들이 끝날때까지 CPU 시간을 할당 받지 못할 것이다.
- 스케줄러를 속이기위해, 계속 우선순위를 높이는 프로그램이 존재할 수 있다
타임 슬라이스가 10초로 정해져있는 스케줄러에서, 9.9초 동안 수행하고 I/O 작업을 발생시킨다고 생각해보자. 그럼 스케줄러의 규칙에 따라 계속 높은 우선순위를 유지하게 된다. 이렇게 되면 CPU를 거의 독점할 수 있다는 문제가 생긴다.
- 마지막으로 프로그램이 수행되는 동안 특성이 변할 수도 있다
CPU만 사용하는 작업인 줄 알고, 우선순위를 낮췄는데 I/O를 실행하려한다거나 대화형 작업으로 변화한다면 어떻게 될까? 이 작업은 운도없게 다른 대화형 작업같은 대우를 못받게 된다.
Stack 용도:
Context switch: PSW( pc등등 현상태 ) 저장후, sp를 저장함.
Function call.
- 동기(programmed, asynchronized) IO / 비동기(interrupt driven IO/ dma입출력
- 동기 IO 는 io wait 시 대기. /cpu 가 계속해서 io가 입출력완료했는지 질문
- 비동기 IO는 wait시 cpu가 다른일하고있는다. / cpu가 행동한다. 하지만 word단위로 읽는 cpu가 계속해서 io된 모든 데이터 확인하기에 여전히 cpu를 과사용한다
- dma입출력: cpu 대신해서 Io검사.IO와 메모리간의 직접적인 교환. 전부 다하고 나면 dma가 인터럽트 보내 cpu에게 다 인증된 데이터 교환.
동기 IO: 첫 write시 io에서 끝날떄까지대기, 다음 줄,
->io 명령 보내고 io 의 state 확인 (읽힐 준비 됬어?) 됬으면 read. 다읽을떄까지 반복.
비동기 IO: 첫 write시 io한테 명령보내고 확인받고( 해당 I/O가 제대로 전달되었다는 것을 확인 시키기 위해 신호를 보낸다)
다음줄. 만약 다음 write까지 완료 interrupt 안오면 그때부터 완료 interupt올때까지 대기.
(멀티 프로그램으로 이시간 마저 절약가능!)
IO, cpu bound
I/O Bound job: 입출력이 많은 작업으로 cpu를 상대적으로 조금 사용하는 대신 시간이 많이 걸린다(disk I/O).
CPU Bound job: CPU Bound job이란 상대적으로 CPU를 많이 소비하는 작업이다.
따라서, 상대적으로 cpu를 적게 사용하지만, 작업 시간이 긴 I/O bound에게 CPU를 우선적으로 할당하여 일을 처리한 뒤, 오랜 시간이 걸리는 disk I/O를 수행하게 한 뒤, CPU bound job을 수행하는 것이 합리적이다. 이를 위한 개념이 SJF, SRTF 이다.
SJF,SRTF
io bound job 은 작은 cpu burst time 따라서 자동으로 io bound 작업 먼저이 먼저 스케줄 된 후 cpu bound 작업이 스케줄 된다.
Sjf 스케줄러의 단점과 Mlfq를 통한 해결
Sjf는 cpu burst time이 낮은게 우선순위로오는 priority scheduler 의 한 종류이다.
Waittime은 최적화되지만 cpu burst time을 예측해야한다는 한다는 점이있는데, 이를 과거 데이터를 기반하여 추측할 수 도 있지만, 결국 예측값이고, 오류가 날 수 있다. 또한 이러한 오류는 커다란 손실을 야기할 수 있기에 문제가 되고,
MLFQ의 특성을 활용하여 극복할 수 도 있다. 큐간의 이동이 가능한 특성을 활용하여 만약 일정시간동안 프로세스가 끝나지 않는다면, 큐를 이동시킨다. 이렇게 많은 횟수 이동된 프로세스는 cpu burst 타임이 높은, 즉 SJF상에서 우선순위가 낮은 process일 것이기에 이런식으로 걸러낼 수 있다. 또한 priority 스케줄러의 특성상 starvation 이 발생할 가능성 역시 존재하는데, 이경우 MLFQ 에서 일정시간 동안 실행되지 못한 process 들을 우선순위가 높은 큐로 올려주는 priority boosting을 활용한다면, starvation 문제또한 해결 가능하다.
Round robin:
''user response time'에 중심을 두는 방식이다. 일정 time 퀀텀마다 cpu의 작업을 교체하기에, 소요 시간이 긴 작업에 막혀 모든 일이 멈추는 일이 없다. ( 검색 입력 중인데, 백그라운드에서 조각 모음 작업이 안끝났다고 검색 작업이 cpu를 할당 받지 못하고 중지되는 것은 유저 사용성에 최악일 것이다.)
하지만 RR 역시 문제점이 있다. 초과된 프로세스 들을 cpu에서 내보내고, 이 과정에서 context switch 가 발생하게 된다. Io bound job의 경우,유저와 의 상호작용을 중요시 여기기에 round robin에서 지속적으로 cpu에 할당할 프로세스를 갈아주는 것이 좋은 효과를 보이지만, cpu bound job의 경우, 이러한 interactive가 중요한 영역이 아니고, 한번 cpu를 잡으면 오랫동안 차지하는 특성상, 이 프로세스가 계속하여 cpu에 들어왔다 나가며 context switch를 반복할 것이다.
장점
- Good response, bad turnaroundtume( 1개 수행에 걸리는 시간)
각 proc이 제한된 시간동안 만 cpu를 잡고있기 때문에, 대기중인 프로세스들이 기다리는 시간의 bound를 알 수 있다>> 이는 알고리즘상 엄청난 이점을 가져다 준다.
단점
- 빈도 높은 context switch 로 인해 딜레이 되는 문제가 생긴다.
RR(round robin) 의 time 퀀텀 별 특성
Time quantum 이 클경우: FIFO로 동작하게 된다. Context switch가 줄어 오버헤드가 적어지고 가벼워지고, fairness 가 생기겠지만, 반대로 기존 FIFO가 가지는 단점인 waiting time 관련 문제 역시 그대로 발생하고, response time 역시 좋지 않아질 것이다.
Time quantum 이 작을경우: round robin 은 계속해서 cpu에서 일하는 process를 갈아끼워주기 때문에, 유저와의 상호작용이 좋아질 것이다. 하지만 context switch의 잦은 발생으로 오버헤드가 증가하여 전체적으로 무거워 질 것이다.
동기화 문제
- Mutual exclusion
- Bounded wait
- Progress
Cpu 성능지표
- Throughput : cpu가 일정 시간 동안 어느정도의 작업량을 처리 가능한가?
- Waiting time (대기 시간) : 프로세스가 Ready queue에서 기다린 시간
- Response time (응답 시간) : 프로세스가 최초로 CPU를 얻기까지 걸린 시간
- Turnaround Time (소요시간, 반환 시간) : 프로세스가 처음 도착해서 끝나기까지 걸린 시간