1. FIFO 스케줄링의 장단점이 뭔가요?

FIFO(First In First Out) 스케줄링이란 대기 큐에 들어온 작업 순서대로 실행하는 스케줄링을 의미한다. 비선점형 스케줄링으로, 하나의 프로세스가 CPU에 할당받아 작업이 시작되면 해당 프로세스의 작업이 마무리되기 전까지 중단되지 않는다.

✅ 장점

1. 스케줄링 구현이 단순하다

2. 들어온 작업 순서대로 모든 작업이 실행되기 때문에 기아(Starvation)현상에 빠지지 않는다.

3. 컨텍스트 스위칭이 자주 발생하지 않아,오버헤드가 적다

✅ 단점

1. 들어온 작업 순서에 따라, 작업의 시간이 긴 프로세스가 먼저 실행될 경우 작업의 시간이 짧은 프로세스들은 오래 대기해야 하며 응답시간 또한 길어진다. (Convoy Effect, 호위효과)

2. I/O작업을 대기하는 동안 CPU는 다른 작업으로 전환할 수 없기 때문에(비선점형), CPU 사용률이 저하된다.

✅ 평균대기시간

case 1:

• 프로세스_1 (Burst Time: 25초) - 대기 시간: 0초

• 프로세스_2 (5초) - 대기 시간: 25초

• 프로세스_3 (4초) - 대기 시간: 30초

  평균 대기 시간: 55 / 3 = 18.3초

case2:

• 프로세스_3 (4초) - 대기 시간: 0초

• 프로세스_2 (5초) - 대기 시간: 4초

• 프로세스_1 (Burst Time: 25초) - 대기 시간: 9초

평균 대기 시간: 13 / 3 = 4.3초

프로세스의 실행 순서에 따라 평균대기시간의 편차가 커지기 때문에 현대 운영체제에서는 잘 사용하지 않는다.

먼저 들어온 작업 순서대로 처리를 해주는 작업 혹은 성능의 저하없이 모든 작업을 순서대로 처리하는 일괄 처리 시스템에서 효율적이다.

2. SJF를 사용하기 여러운 이유가 뭔가요?

SJF (Shortest Job First) 스케줄링은 Burst Time이 가장 짧은 작업부터 우선 실행하는 스케줄링이다. FIFO의 단점이었던 '실행 순서에 따른 평균 대기시간 편차'를 극복하기 위해 설계되어 실행 시간이 짧은 프로세스 먼저 작업하는 기법이다.

하지만 두 가지 큰 단점이 존재한다. 첫 번째는 Starvation(기아) 현상이 발생할 수 있다. 짧은 작업을 우선적으로 처리하기 때문에, 긴 작업의 프로세스는 계속 대기를 하게 되어 실행의 순서가 보장되지 않는다. 두 번째는 실제 Burst Time을 예측하기 힘들다는 것이다. 짧은 실행 순서를 먼저 실행시키는 SJF 스케줄링에서, 실제 작업이 얼마나 CPU를 사용할 것인지 혹은 I/O 작업이 언제 응답 받을 수 있는지 예측될 수 없기 때문에 실 Burst Time을 예측하여 짧은 프로세스 먼저 실행시키기 어렵다.

SJF는 결론적으로 실행 시간이 예측 가능하며 짧은 작업이 많은 환경에서 평균 대기 시간을 효율적으로 줄일 수 있는 스케줄링 기법이다.

3. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?

RR(Round Robin) 스케줄링이란 타임 슬라이스만큼 프로세스를 실행하고 다음 프로세스를 실행하는 스케줄링이며 타임 슬라이스는 CPU가 할당되는 일정한 시간을 의미한다.

타임 슬라이스가 아주 작게 실행되면 여러 프로세스가 동일한 시간에 실행되는 것처럼 보일 수 있지만 짧은 시간을 주기로 Context Switching이 많아져 오버헤드가 증가한다.

타임 슬라이스가 너무 크게 실행되면 FIFO 스케줄링과 유사하게 동작하여 효율성이 떨어지게 된다.

즉, RR 스케줄링은 최적의 타임 슬라이스를 설정하는 것이 중요하며 최적의 타임 슬라이스는 여러 프로세스가 버벅이지 않으면서 동시에 실행시키는 효과를 줌과 동시에 오버헤드가 너무 크지 않은 정도의 할당 시간을 의미한다. 윈도우에서는 20ms, 유닉스에선 100ms정도로 설정된다.

4. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?

MLFQ(Multi Level Feedback Queue)란 프로세스를 여러 개의 우선순위 큐로 분류하고, 실행 시간에 따라 큐 간 이동이 가능한 스케줄링 알고리즘이다. 처음 프로세스가 실행되면 높은 우선순위의 큐에서 실행되며, 실행되는 시간에 따라 우선순위가 변동되어 점차 다른 큐에 할당된다.

주어진 타임 슬라이스 내에 작업이 완료된다면 I/O Bound Process로 간주하여 높은 우선순위를 유지하고,

해당 타임 슬라이스를 초과하면 CPU Bound Process로 간주되어 낮은 우선순위 큐로 이동하게 된다.

실행 순서는 우선순위가 높은 큐부터 순차적으로 실행되며, 낮은 우선순위의 큐는 오래 동안 실행되지 않는 상태인 기아(Starvation) 현상을 겪을 수도 있기 때문에 Aging을 통해 문제를 해결할 수 있다. Aging은 낮은 우선순위 큐에서 오랫동안 기다린 프로세스들을 점진적으로 다시 우선순위를 높여주는 기법이다.

I/O Bound Process가 우선순위가 높은 이유
처음에는 I/O 작업은 요청을 한 뒤에 응답까지 기다려야 하니, 작업 시간이 예측하기 힘들고 오래걸리지 않나? 라고 생각하였고

타임 슬라이스 안에 작업이 보통 완료하지 못하지 않을까라는 생각에 우선순위가 높은 이유가 궁금하여 다시 해당 부분을 찾아보았다.

I/O 작업은 CPU를 거의 사용하지 않고 보통 외부 장치를 통해 응답을 기다리는 작업들이다. CPU의 점유를 가로채지 못하는 비선점형 스케줄링 기법에서는 I/O작업이 실행되면 응답까지 기다려야 하니(대표적으로 FIFO 같은 기법) 작업이 빠르다고 말할 수는 없지만, 선점형 스케줄링 기법에서는 I/O 작업이 요청되면 해당 프로세스는 대기 상태로 상태값이 변경되고 응답이 오기 전까지(인터럽트) 다른 프로세스의 작업을 실행할 수 있기 때문에 작업이 빠르다고 얘기할 수 있으며 우선순위 또한 높게 가져갈 수 있는 것이다.

5. 공유자원이란무엇인가요?

공유자원이란 여러 프로세스 간 공유되는 자원(변수나 파일 등)을 의미한다. 여러 프로세스는 서로 통신을 하며 한 가지 작업을 동시에 수행할 수도 있는데, 이 과정에서 공유자원을 여러 프로세스가 접근하게 되면 경쟁 조건이 발생하면서 동기화 문제가 생긴다.

경쟁 조건이란 다수의 프로세스(혹은 쓰레드)가 같은 데이터(공유자원)에 동시에 접근 혹은 조작의 순서에 따라 결과의 일관성을 해칠 수 있는 상태를 의미하며 이를 해결하기 위해서는 상호 배제가 필요히다. 상호배제는 하나의 프로세스만 접근할 수 있는 구역인 임계구역을 설정하여 데이터의 동기화를 유지시키는 것을 의미한다.

상호배제 요구사항

1. 임계영역엔 하나의 프로세스만 접근 가능하다

2. 여러 요청에도 하나의 프로세스만 접근을 허용한다

3. 임계구역에 들어간 프로세스는 최대한 빠르게 나와야 한다.

상호배제의 매커니즘

1. Mutex

   1. 임계 구역에 진입하면 lock을 획득하고 acquire()와 release()를 통해 획득 및 반납

   2. 프로세스가 임계구역에 진입하기 위해 무한 루프가 돌며 이를 spinlock이라고도 부른다

2. Semaphore

   1. 공유자원 수용 가능 수에 따라 정수의 변수 s를 선언

   2. wait(s) signal(s) 를 통해 s값을 증가 차감한다

   3. 함수 호출 순서를 잘못하면 문제가 발생한다.

3. Monitor

   1. 세마포어의 단점을 해결한 상호배제 메커니즘

   2. 운영체제의 차원이 아닌 프로그래밍 언어에서 처리한다

   3. 자바에서 synchronized 붙은 함수가 실행되면 다른 프로세스가 접근 할 수 없음

   4. 함수를 임계 영역을 감싸지 않아도 되어 편리함.

6. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?

교착상태(Deadlock)란 여러 프로세스가 서로 다른 프로세스의 작업이 끝나기를 기다리다가 아무도 작업을 진행하지 못하는 상태를 의미한다.

교착상테 필요조건

1. 상호배제: 한 프로세스가 리소스를 점유하였다면 다른 프로세스 접근 불가

2. 비선점: 점유중인 프로세스의 리소스를 뺏어갈 수 없음

3. 점유와 대기: 한 프로세스는 리소스를 점유하고 있는 상태에서 다른 프로세스의 리소스 점유를 대기해야 함

4. 원형대기: 점유와 대기를 하는 프로세스들의 관계가 원형이어야 함.

데드락의 발생은 막을 수 없으니, 발생 후의 해결 방법을 고민해본다.

1. 가벼운 교착상태 검출: 타이머 이용. 프로세스가 일정 시간동안 작업을 진행하지 않는다면 교착상태로 검출

- 일정시간마다 체크포인트 생성, 교착상태 예상 시에 롤백

2. 무거운 교착상태 검출: '자원 할당 그래프'를 통해 프로세스에 할당된 자원을 모니터링

- 교착상태를 일으킨 프로세스 강제종료

- 체크포인트로 롤백

자원할당 그래프(Resource Allocation Graph)란 무엇일까?

운영체제에서 자원이 할당되어 있는 상태를 그래프로 그려, 시각적으로 데드락의 여부를 판단

- T = {T1, T2, ..., Tn}: 실행 중인 쓰레드

- R = {R1, R2, ..., Rm}: 할당될 자원 타입

- T_i → R_j: i 쓰레드가 j 자원을 요청한다

- R_j → T_i: j 자원을 i 쓰레드에 할당되어 있다.

위 예제에서는 3개의 쓰레드와 4개의 자원이 있으며 2개의 순환 구조를 갖고 있다.

T1 → R1 → T2 → R3 → T3 → R2 → T1

T2 → R3 → T3 → R2 → T2

모든 쓰레드는 하나의 자원을 점유 중인 상태에서 다음 자원을 점유하기 위해 대기 상태에 있고, 이러한 상태가 원형을 이루어지고 있기 때문에 데드락에 빠질 확률이 높다고 판단한다.

📔 회고

미션을 수행하면서도 강의를 들었을 때 고민하지 못했던 부분에 대해서 더 찾아보고 전체적인 흐름을 다시 정리해볼 수 있었다.

MLFQ 스케줄링에서 I/O Boud Process를 정리하면서 우선순위가 높은 이유에 대해서 생각해보진 못했던 것 같은데,

선점형과 비선점형의 특징을 알고, 선점형에서 I/O 작업이 응답 대기를 통해 다른 프로세스로 전환될 경우 CPU 작업 처리 비중은 적으니 빠른 작업 실행과 높은 우선순위를 가져갈 수 있다라는 것을 다시 한 번 전체적인 흐름과 다른 개념과의 연관을 통해 정리해볼 수 있었다.

또한 질문의 답변을 통해서 강의를 듣고 추가로 공부해봤던 것들에 대해서 한 번 더 정리해볼 수 있는 시간을 가졌는데, 뮤텍스와 같은 상호배제 메커니즘이나 처음에 이해하지 못했던 자원 할당 그래프를 직접 다시 확인해보고 개념들을 이해해볼 수 있었던 것 같다.