[스터디] 운영체제 #5

CPU 스케줄링 -> 멀티프로그래밍에서는 필수적임.
1. 계속 프로세스를 실행시키기 위해
2. CPU 효율의 최대화

CPU스케줄러 - 어느 프로세스에게 메모리를 할당할것인가?

 

다음 프로세스를 고르는 기준은?

- 링크드 리스트? or 이진트리?
- FIFO 큐(First In First Out)
- 우선순위 큐 : 어떻게 우선순위를 결정할 것인가?

 

 

 

 

선점형 vs 비선점형

비선점형 : 자발적으로 프로세스가 나오기 전까지는 해당 프로세스가 메모리를 쓰게 놔두는 것
선점형 : 어떠한 이유로 선점중인 프로세스를 쫓아낼 수 있음

 

 

CPU스케쥴링을 위한 의사결정

1. running -> waiting
2. running -> ready
3. wating -> ready
4. terminate

1번과 4번은 자발적으로 일어나는 일이지만, 
2번과 3번은 자신이 비키고 싶어서 비키는 것이 아니라 우선순위에 밀렸거나 등으로 인해 자발적이지 않은 이유일 수 있다. (3번은 이해가 잘안됐는데, 강의에서는 waiting에서 ready로 갔을 때 우선순위로 인해 기존에 ready queue에 있던 프로세스들 보다 더 빨리 running상태에 갈 수도 있는 경우를 말씀해주셨다)

1번과 4번은 비선점
2번과 3번은 선점 or 비선점

 

dispatcher  - CPU코어의 컨트롤을 주는 모듈 - context switching을 해주는 모듈
* 문맥교환
* 유저모드로 스위치
* 새로운 프로세스의 적당한 위치로 재개

디스패처는 가급적 짧아야한다.
디스패처 레이턴시 == 현재 프로세스를 멈추고 다른 프로세스를 run하게하는 시간

 

 

스케쥴링 목표

1. CPU의 효율성
2. 단위시간내에 완료되는 프로세스의 수
3. 한 프로세스 실행에서 종료까지의 시간의 최소화
4. 한 프로세스가 Ready 큐에서 기다리는 시간의 최소화
5. 응답시간

FCFS(First come, Frist served)
SJF(Shortest Job First / SRTF : Shorted Remaining Teime Frist)
RR(Round-Robin) 일정시간을 정해두는 것
Priority-based 우선순위
MLG(Multi-Level Queue)
MLFQ(Multi-Level Feedback Queue)

FCFS
1. 먼저 온 프로세스에 먼저 CPU를 할당
2. 가장 간단하고 쉬운 방법
3. 평균 waiting time이 최소가 아니며 다양해짐
4. 비선점

SJF
1. 각 프로세스의 다음 CPU burst 길이가 가장 작은 프로세스에게 할당
2. 만약 여러개의 프로세스가 모두 동일하다면, 그때는 FCFS
3. 최소의 평균 waiting time 

근데..다음 CPU burst 타임을 어떻게 알수있을까?
-> 근사치로 예측
-> 어떻게 예측?
-> 예전 CPU burst를 보고 지수적평균을 측정함
-> 하지만 계산하는것도 만만치 않다.
-> 이론적으로는 최적이다

SRTF 

1. 선점형 SJF 스케쥴링
2. 한 프로세스가 현재 실행중인 프로세스의 남은 시간보다 더 짧으면 해당 프로세스로!

RR
1. preemptive FCFS with a quantum
2. circular queue
3. 선점적
4. time quantum을 얼마나 하냐에 따라 달라짐

우선순위 스케쥴링
* SJF는 일종의 우선순위 스케쥴링
1. 기아의 문제(starvation)
2. 우선순위가 낮은 프로세스는 계속 기다리게 됨
3. 해결책 -> aging : 오래기다리면 우선순위를 높여주기

MLFQ(Multi-Level Feedback Queue)

실시간 OS에서의 스케쥴링
Soft realtime vs Hard Realtime


--------------------------
데드락 : 교착상태

 

데드락의 조건

1. 상호배재(Mutual Exclustion) : 적어도 하나의 리소스가   non-sharable mode 여야 힘
2. 점유대기(hold and wait) : 쓰레드가 적어도 하나의 리소스를 hold하고 waiting 하고 있음
3. No preemption : 선점 불가
4. Circular Wait : 순환 
-> 4개의 조건을 만족해야 데드락에 걸림

 

데드락문제 해결책

1. 무시하기
2. 미리 방지하기(거의 불가능) or 피하기(벵크알고리즘)
3. 탐지하고 다시 복구하기

deadlock avoidance 
미래에 데드락이 걸릴것같으면, request 거절하기
그럴려면 최대의 자원개수를 알고 있어야함

뱅커 알고리즘
* 다수 인스턴스의 경우에는 RAG를 적용할 수 없어서 등장
* 데드락에 한번걸리면 데미지가 큰 것이 아니고서는 부담스러움



----------------------



3 Ack Duplicate

이것보다 찰떡인 그림은 없다(출처 : https://steady-coding.tistory.com/507)

 

생각해봤던 질문

>>>>>>>>>>>>>>>>>>>>단기, 중기, 장기 스케쥴러에 대해 설명해 주세요.
단기 스케쥴러는 어떤 프로세스를 실행시킬지, 중기 스케쥴러는 메모리 공간이 부족한 경우 어떤 프로세스를 Swap Out(프로세스를 내리는 것) 할건지, 장기 스케쥴러는 어떤 프로세스를 Ready Queue에 보낼지 결정한다. 

>>>>>>>>>>>>>>>>>>>>현대 OS에는 단기, 중기, 장기 스케쥴러를 모두 사용하고 있나요?
아니요 현재는 단기 스케쥴러만 사용하고 있으며, 중기와 장기는 가상메모리로 인해 없어진 상태입니다. 
+) 가상메모리로 인해 Ready Queue에 올라갈 프로세스의 수를 조절하지 않아도 되기 때문에

>>>>>>>>>>>>>>>>>>>>프로세스의 스케쥴링 상태에 대해 설명해 주세요.
New, Ready, Running, Waiting, Terminated가 있습니다. New는 프로세스 생성단계, Ready는 프로세스가 CPU를 기다리는 상태, Running은 프로세스가 CPU를 할당받아 명령어를 수행중인 상태, Waiting 은 프로세스가 어떤 사건이 완료되기를 기다리는 상태, Terminated는 프로세스의 실행 종료를 의미합니다.

>>>>>>>>>>>>>>>>>>>>preemptive/non-preemptive 에서 존재할 수 없는 상태가 있을까요?
(질문이 이해가 잘안가지만, CPU 스케쥴링시의 상태변화들이 있는데(running->waiting, running->ready, waiting->ready,terminated) 여기 속하지 않는 상태를 말하는 걸로 이해했음) New 상태이다.

>>>>>>>>>>>>>>>>>>>>Memory가 부족할 경우, Process는 어떠한 상태로 변화할까요?
메모리가 부족할 경우, 시스테은 메모리부족상태(OOM) 상태가 되어 적절한 프로세스를 선택하여 강제종료한다. 

>>>>>>>>>>>>>>>>>>>>프로세스 스케줄링 알고리즘에는 어떤 것들이 있나요?
FCFS, SJF, SRT, RR, 우선순위, MLQ, MLFQ

>>>>>>>>>>>>>>>>>>>>스케쥴링의 조건
오버헤드가 적고 사용률이 커야하며 기아현상이 적어야한다.

>>>>>>>>>>>>>>>>>>>>스케쥴링의 목표는?
가능하면 많은 일을 수행해야하며 시간보단 처리량이 중요하다. 빠른 응답시간과 적은 대기시간을 가지고 기한을 맞출 수 있어야한다.

>>>>>>>>>>>>>>>>>>>>우선순위 스케줄링의 문제점과 해결방법은?
starvation 기아문제가 존재하며, Aging 즉, 오래 기다릴 수록 우선순위를 높여주는 방법을 사용한다.

>>>>>>>>>>>>>>>>>>>>타 스케쥴러와 비교하여, Multi-level Feedback Queue는 어떤 문제점들을 해결한다고 볼 수 있을까요?
다른 큐로 이동이 가능하기 때문에 유연하며 turnaround 시간에 최적화되어있으며 응답시간도 빠르다.

------------------------------------------------------------------------------------------------------------------
>>>>>>>>>>>>>>>>>>>>데드락이란?
두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 다음 처리를 하지 못하고 무한히 다음 자원을 기다리게 되는 상태(즉, 교착상태)

>>>>>>>>>>>>>>>>>>>>데드락의 발생조건?
상호배재(자원은 한번에 한 프로세스만 사용할 수 있음), 
점유대기(최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 함), 
비선점(다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없음), 
순환대기(프로세스의 집합에서 순환형태로 자원을 대기하고 있어야함)

>>>>>>>>>>>>>>>>>>>>데드락 해결 방법?
4가지의 발생 조건 중 하나라도 제거하면 교착상태를 막을 수 있지만, 그 중에서 순환대기 조건에 초점이 맞춰져있다. 그러한 맥락에서 예방방법이 있지만 자원낭비가 심하다.
회피방법은 데드락 발생 가능성을 회피하는 방식으로 은행원 알고리즘이 많이 쓰인다. 프로세스가 자원을 요구할 때 시스템은 자원을 할당한 후에도 안정상태로 남아있게 되는지 사전에 검사하는 알고리즘이다.
발생하지 않으면 자원할당, 발생하면 다른 프로세스가 자원을 해재할 때까지 대기한다. 최대 자원 요구량을 미리 알아야하고 자원 이용도가 낮다는 문제점이 있다.
마지막으로는 탐지 및 회복으로, 자원 요청시 탐지 알고리즘을 실행시켜 그에 대한 오버해드를 발생시키는 것. 
데드락상태의 프로세스를 모두 중단시키거나 프로세스를 하나씩 중단시킬때마다 데드락탐지를 하며 회복시키기, 마지막으로 데드락상태의 프로세스 자원을 다른 프로세스에게 할당하는 방법이 있다.

>>>>>>>>>>>>>>>>>>>>식사하는 철학자문제?
모두가 왼쪽 포크를 집게되면 모두 오른쪽 포크를 대기하게 되어 기아상태 발생한다. 

--------------------------------------------------------------------------------------------------------------------------
>>>>>>>>>>>>>>>>>>>>흐름제어와 혼잡제어란?
흐름 제어는 송 수신 측 사이의 패킷 수를 제어하는 기능이라 할 수 있으며, 혼잡 제어는 네트워크 내의 패킷 수를 조절하여 네트워크의 오버플로우를 방지하는 기능이다.

>>>>>>>>>>>>>>>>>>>>흐름제어의 방법들을 말해보시오
Stop and Wait과 Sliding Window 기법이 있다. 
Stop and Wait은 전송한 패킷에 대해 확인 응답(ACK)을 받으면 다음 패킷을 전송하는 제어 기법이고, 
Sliding Window는 수신 측에서 설정한 윈도우 크기만큼 송신 측에서 확인 응답(ACK) 없이 패킷을 전송할 수 있게 하여 데이터 흐름을 동적으로 조절하는 제어 기법이다.

>>>>>>>>>>>>>>>>>>>>혼잡제어 기법들을 설명하시오.
AIMD - 처음 패킷 하나씩 보내고 문제 없으면 윈도우의 크기 1씩 증가, 실패하면 반으로 줄이기/제대로 된 속도로 통신하기까지 시간이 걸림
Slow Start -  윈도우 크기의 지수적 증가. 하지만 실패하면 윈도우 크기를 1로 줄인다. / 처음엔 느릴지라도 갈수록 윈도우 크기가 빠르게 증가한다
Fast Retransmit(빠른 재전송) - 수신측에서 순서대로 잘 도착한 마지막 패킷의 다음 순번을 ACK 패킷에 실어 보낸다. 이런 중복 ACK를 3개 받으면 재전송
Fast Recovery(빠른 회복) - 혼잡한 상태가 되면 윈도우 크기를 반으로 줄이고 선형증가(한번 혼잡하면 AIMD)

>>>>>>>>>>>>>>>>>>>>TCP/IP 통신에서 흐름 제어 기법이 왜 사용되는가?
송 수신자 간의 TCP 버퍼의 크기 차이로 인해 생기는 데이터 처리 속도 차이를 해결하기 위해 사용된다.


>>>>>>>>>>>>>>>>>>>>TCP/IP 혼잡 제어 기법이 왜 사용되는가?
송신 측에서 보내는 데이터의 양이 라우터가 처리할 수 있는 양을 초과하면 초과된 데이터는 라우터가 처리하지 못한다. 
송신 측은 초과된 데이터를 손실 데이터로 간주하고 계속 재전송하여 네트워크를 혼잡하게 한다. 
이런 상황을 예방하기 위해 송신 측의 전송 속도를 적절히 조절하는 혼잡 제어 기법이 사용된다. 
대표적으로 AIMD, Slow Start, 빠른 재전송, 빠른 회복 등이 있다.

>>>>>>>>>>>>>>>>>>>>TCP/IP 혼잡 제어 정책은 무엇이 있는가?
대표적으로 TCP Tahoe와 TCP Reno가 있다. 
TCP Tahoe는 처음에는 Slow Start를 사용하여 자신의 윈도우 크기를 지수적으로 빠르게 증가시키다가 ssthresh를 만난 이후부터는 AIMD을 사용하여 선형적으로 윈도우 크기를 증가시킨다. 
반면, TCP Reno는 Tahoe와 마찬가지로 Slow Start로 시작하여 임계점을 넘어서면 AIMD을 사용하되, Tahoe와 다르게 3 ACK Duplicated와 Timeout 혼잡 상황을 구분한다.

참고 : 인프런