메인 주제

교착 상태와 기아 상태

교착 상태

• 두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있어서 실질적으로 무한정 대기하는 상태이다
• 발생 조건
  • 상호 배제 : 자원은 한 번에 한 프로세스만 사용 가능하다
  • 점유 대기 : 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다
  • 비선점 : 프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺐을 수 없다
  • 순환 대기 : 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다

기아 상태

특정 프로세스의 우선 순위가 낮아서 자원을 할당 받지 못하는 상태이다

• 해결 방안
  • 오래 기다린 프로세스의 우선순위를 높인다
  • 프로세스 우선순위 수시 변경을 통해 각 프로세스의 높은 우선순위를 가지도록 기회를 부여한다
  • 우선순위가 아닌 요청 순서대로 처리하는 요청 큐 사용한다

선점 스케줄링

우선순위가 높은 프로세스가 현재 프로세스를 중지시키고 자신이 CPU를 점유하는 기법이다

• 응답이 빠르지만, 처리 시간을 예측하기 힘들고 높은 우선순위의 프로세스들이 계속 들어오는 경우 오버헤드가 발생한다
• 종류
  • RR, SRT

RR

• 프로세스마다 같은 크기의 CPU 점유 시간을 할당 받는다
• 프로세스가 할당된 시간 내에 작업을 처리하지 못하면 레디 큐 리스트의 맨 뒤로 보내지며 CPU는 대기 중인 다음 프로세스로 넘어간다
• 모든 프로세스가 CPU를 균등하게 점유하므로 기아 현상이 발생하지 않는다
• 할당된 시간이 크면 FCFS와 유사해지며 작으면 잦은 문맥 교환이 발생한다

SRT

• SJF를 선점형으로 변경한 스케줄링 기법
• 남은 시간이 가장 적은 프로세스를 먼저 수행한다. 더 짧은 시간이 남은 프로세스가 들어오면 실행 중인 프로세스를 중단 시키고 더 짧은 처리 시간의 프로세스를 처리한다
• 처리 시간이 짧은 프로세스가 계속 추가되면 기아 현상이 발생할 수 있다

Multu-Level Queue

• 작업들을 각 목적에 맞게 여러 종류의 그룹으로 분할한다
• 각 그룹의 큐에는 독자적인 스케줄링 알고리즘(RR, FCFS) 등을 사용할 수 있다
• 더 높은 우선순위를 갖는 큐가 비워지지 않는 경우 기아 현상이 발생할 수 있다

Multi-Level Feedback Queue

• 각 준비 상태 큐마다 서로 다른 CPU 할당 시간을 부여해 Time-out 되면 처리하지 못한 프로세스를 다음 단계의 큐로 이동 시킨다
• 하위 단계로 내려갈 수록 할당 시간을 증가 시킨다
• 마지막 단계에서는 라운드 로빈 또는 FCFS로 처리한다
• 최하위 큐에서 너무 오래 대기 시 에이징 기법을 통해 상위로 이동 시켜 처리한다

비선점 스케줄링

프로세스가 자원을 할당 받은 경우 자원을 스스로 반납할 때 까지 계속 그 자원을 사용하도록 허용하는 정책

• 종류
  • FCFS, SJF, HRN

FCFS

• 프로세스의 도착 순으로 CPU를 배정한다
• 데이터를 일괄적으로 처리하는 batch 작업 등, 장기 스케줄러에서 사용 가능 하다
  • 장기 스케줄러 : 어떤 프로세스를 디스크에서 가져와 레디 큐에 삽입할지 결정하는 역할을 한다
• 여러 개의 짧은 작업이 먼저 수행중인 긴 작업을 기다리는 Convoy Effect가 발생할 수 있다
• 간트 차트

  작업	Burst Time
  p1	24
  p2	3
  p3	3

  • 작업 도착 순서 : p1 - p2 - p3
  • 평균 반환 시간 : (24+27+30)/3
  • 평균 대기 시간 : (0+24+27)/3

SJF

• 대기하는 작업 중 CPU Burst Time이 가장 작은 작업에 CPU를 할당하는 기법이다
• 평균 대기 시간에 있어 최적의 알고리즘이다
• 간트 차트

  작업	Burst Time
  p1	6
  p2	3
  p3	8

  • 작업 도착 순서는 Burst Time이 작은 순대로이다
  • 평균 반환 시간 : (3+9+17)/3
  • 평균 대기 시간 : (3+0+16+9)/3

면접 질문

CPU 스케줄링이란 무엇인가요?

운영체제가 프로세스에게 합리적으로 CPU 자원을 할당하는 정책이다

CPU 스케줄링의 목적이 무엇인가요?

• 공평성
  • 모든 프로세스가 자원을 공평하게 배정받아야 합니다
• 효율성
  • CPU를 필요로 하는 자원에게 우선권을 주어야 한다
• 안정성
  • 시스템을 강제로 점유하거나, 파괴하려는 프로세스부터 자원을 보호해야 한다
• 반응 시간 보장
  • 적절한 시간 안에 프로세스의 요구에 반응해야한다
• 무한 연기 방지
  • 특정 프로세스의 작업이 무한하게 연기 되어서는 안된다

교착 상태와 기아 상태를 비교해 설명 해주세요

교착 상태는 프로세스가 자원을 얻지 못해 다음 프로세스를 실행하지 못하고 무한 대기 상태에 빠지는 것이고, 기아 상태는 프로세스가 원하는 자원을 할당 받지 못하는 상태입니다

즉 교착 상태는 여러 프로세스가 동일한 자원을 점유하고자 할 때 발생하고, 기아 상태는 여러 프로세스가 자원을 점유하기 위해 경쟁 할 때 특정 프로세스는 영원히 자원 할당을 받지 못하는 것입니다

CPU Burst와 CPU Bound가 무엇인지 설명 해주세요

CPU Burtst는 프로세스가 실행되는 동안 CPU에서 연산을 처리하는 시간을 의미합니다.

CPU Bound는 CPU Burst 시간이 I/O Burst보다 긴 프로세스를 말합니다

SJF를 설명해주세요

최단 시간으로 처리될 수 있는 작업에 우선순위를 주고 우선적으로 처리하는 스케줄링 방식입니다

FCFS 방식의 Convoy 효과를 보완한 것이다

운영체제

SJF와 SRTF를 사용하지 않는 이유를 설명해주세요

SJF 스케줄링은 비선점형 스케줄러이기 때문에 만약 점유 시간이 짧은 B와 C가 점유 시간이 긴 A보다 늦게 도착하면 FCFS와 같이 Convoy 현상이 발생한다

SRTF 스케줄링은에서 위와 같은 A, B, C 프로세스가 동시에 도착했다면 C는 A와 B가 모두 종료될 때까지 기다려야하기 때문에 응답 시간이 길어진다

라운드 로빈 스케줄링이란 무엇인가요?

선점형 스케줄링 방식으로 프로세스들 사이에 우선 순위를 두지 않고 순서대로 CPU를 할당하는 방식입니다

특징

• 운영체제가 프로세스 종료 예측 시간은 불확실합니다
• long job을 배척해 공평성에 위배된다
• 기아 현상과 프로세스 종료 시간 예측에 대한 어려움으로 사용성이 낮다

RR 스케줄링 방식에서 CPU 할당 시간이 커질 경우와 작아질 경우 어떤 변화가 생길까요?

할당 시간이 아주 커진다면 각 프로세스가 충분한 CPU 점유 시간을 가지게 되어 FCFS 방식과 같이 됩니다. 즉 짧은 응답 속도의 장점을 잃어버리게 됩니다

할당 시간이 작아진다면 문맥 교환이 빈번해져 오버헤드가 발생할 수 있습니다

스케줄링 알고리즘의 평가 기준에 대해 설명해주세요

• CPU 이용률 (CPU Utilization): CPU가 실제로 일을 하고 있는 시간의 비율 → 유휴 시간이 적을수록 사용률 높습니다.
• 처리량 (Throughput): 주어진 시간 동안 시스템이 완료한 프로세스의 수
• 대기 시간 (Waiting Time): 프로세스가 대기 큐에서 기다린 시간의 합. → 짧을 수록 좋습니다.
• 응답 시간 (Response Time): 프로세스가 요청을 제출한 시점부터 첫 번째 응답을 받을 때까지의 시간. → 짧을 수록 좋습니다.
• 반환 시간 (Turnaround Time): 프로세스가 제출된 시점부터 완료될 때까지 걸린 시간.

멀티 레벨 큐와 멀티 레벨 피드백 큐 알고리즘에 대해 말씀해 주세요

멀티 레벨 큐 방식은 레디 큐를 여러 개로 분할 해 큐들의 우선순위를 다르게 하는 것을 말합니다.

한 번 큐에 배정되면, 다른 큐로 이동이 불가능 합니다.

하위에 있는 큐의 프로세스는 모든 상위 프로세스가 종료되어야 실행 가능합니다.

그러나 멀티 레벨 피드백 큐의 경우, 한 번 큐에 배정된 것이라도 CPU Burst time에 따라 큐 간 이동을 할 수 있는 특징을 가집니다

• 작업이 시스템에 진입하면 가장 높은 우선순위 큐에 놓여집니다
• 주어진 단계에서 시간 할당량을 소진하면 우선순위는 낮아집니다
• 일정 기간이 지나면 시스템의 모든 작업이 최상위 큐로 이동해 기아 상태를 완화합니다

싱글 코어 CPU에서 사용한 스케줄링 기법을 멀티 코어 CPU에 그대로 사용하면 발생하는 문제점과 해결법을 말씀해 주세요

멀티 코어 CPU에서는 코어 간 작업을 전달 하거나 데이터를 공유할 때 통신 오버헤드가 발생할 수 있습니다. 같은 데이터에 자주 접근하는 작업은 가능한 동일한 코어에서 작업을 처리하도록 하여 통신 오버헤드를 줄입니다

싱글 코어에서는 작업에 대한 부하 계산이 필요없지만 멀티 코어에서는 각 코어에 부하를 고르게 분산하기 위한 계산이 필요합니다. 작업 스틸링을 통해 덜 바쁜 코어가 더 바쁜 코어의 작업을 가져와 처리합니다