CS 기술면접 운영체제 끝내기(4) - 교착상태, 스케줄링 등

교착상태 필요 조건

• 상호 배제 : 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다.
• 비선점 : 한 프로세스가 사용 중인 자원은 다른 프로세스가 뺏을 수 없는 비선점 자원이어야 한다.
• 점유와 대기 : 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태
• 원형 대기 : 점유와 대기를 하는 프로세스 간에 관계가 원을 이루어야 한다.

교착상태 해결 방법

• 예방 : 유발하는 4가지 조건을 무력화 → 현실적으로 어렵고, 자원을 낭비하게 될 수 있음
• 회피 : 교착상태가 발생하지 않는 수준으로 자원을 할당. 할당되는 자원 수를 조절하여 교착상태를 피한다.
  • 안정 상태 (자원 할당 가능하다고 판단 한 상태) : 기대 자원 < 가용 자원
  • 문제점 :
    • 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 한다.
    • 시스템 전체 자원수가 고정적이어야 한다.
    • 자원이 낭비된다.
• 검출 : 자원할당 그래프 또는 타임아웃을 사용해 교착 상태를 발견한다.
  • 타임아웃을 이용한 교착상태 검출 : 일정 시간동안 작업이 진행되지 않은 프로세스를 교착상태가 발생한 것으로 간주하여 처리하는 방법.
  • 자원할당 그래프를 이용한 교착상태 검출
• 회복 : 교착상태를 검출한 후 해결한다. 교착상태를 유발한 프로세스를 강제 종료한다.
  • 교착상태를 일으킨 모든 프로세스를 동시에 종료 → 다시 실행할 때는 순차적으로 실행해야 함
  • 하나를 골라 순서대로 종료. 하나씩 골라서 순서대로 종료하면서 나머지 프로세스의 상태 파악

CPU 스케줄링

어떤 작업에 CPU를 배정할지 결정하는 것

CPU 스케줄러 (= 프로세스 스케줄러)

프로세스가 생성된 후 종료될 때까지 모든 상태 변화를 조정하는 일을 한다.

운영체제에서 기아(starvation)란 무엇입니까

기아란 특정 프로세스의 우선순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태입니다. 대기중인 프로세스는 리소스가 다른 프로세서에 할당되어 있기 때문에 오랫동안 필요한 리소스를 얻지 못합니다.

운영체제에서 에이징이란 무엇입니까?

에이징은 프로세스의 우선순위가 낮아 무한정 기다리게 되는 경우, 한 번 양보하거나 기다린 시간에 비례하여 일정 시간이 지나면 우선순위를 한 단계씩 높여 가까운 시간 안에 자원을 할당받도록 하는 기법을 말합니다.

스케줄링의 단계

1. 고수준 스케줄링 (= 장기 스케줄링 = 작업 스케줄링 = 승인 스케줄링)
   • 시스템 내의 전체 작업 수를 조절한다. (작업 : 운영체제에서 다루는 일의 가장 큰 단위로, 1개 또는 여러 개의 프로세스로 이루어진다.)
   • 시스템 부하를 고려하여 어떤 작업을 시스템이 받아들일지 또는 거부할지를 결정한다.
   • 이에 따라 시스템의 전체 프로세스 수(=멀티프로그래밍 정도)가 결정된다.
2. 저수준 스케줄링 (= 단기 스케줄링)
   • 준비 상태에 있는 프로세스 중 하나를 골라 실행 상태로 보내고, 실행 상태에 있는 프로세스를 대기 상태로 보내며, 대기 상태의 프로세스를 준비 상태로 보내는 결정을 한다.
   • 어떤 프로세스에 cpu를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정
3. 중간 수준 스레드
   • 중지와 활성화로 전체 시스템의 활성화된 프로세스 수를 조절하여 과부화를 막는다.
   • 활성화된 프로세스 중 일부를 보류 상태로 보냄
   • 보류된 프로세스는 처리 능력에 여유가 생기면 다시 활성화 시킴

선점형 스케줄링 vs 비선점형 스케줄링

• 선점형 스케줄링
  • 작업 방식 : 실행 상태에 있는 작업을 중단시키고 새로운 작업을 실행
  • 장점 : 우선순위가 높은 프로세스를 빠르게 처리할 수 있음. 대화형, 시분할 시스템에 적합
  • 단점 : 우선순위가 높은 프로세스가 생길 때 마다 문맥교환이 일어나 오버헤드가 크다. 문맥 교환의 오버헤드가 많다
  • 사용 : 시분할 방식 스케줄러에 사용
  • 중요도 : 높다
• 비선점형 스케줄링
  • 실행상태에 있는 작업이 완료될 때까지 다른 작업 불가능
  • 장점 : cpu스케줄러의 작업량이 적고 문맥교환의 오버헤드가 적다
  • 단점 : 기다리는 프로세스가 많아 처리율이 떨어진다.
  • 사용 : 일괄 작업 방식 스케줄러에 사용된다
  • 중요도 : 낮다

다중 큐

• 대기상태 : 입출력이 완료되기를 기다리는 프로세스가 모여있는 곳, 시스템의 효율을 위해 대기상태에서는 같은 입출력을 요구한 프로세스끼리 모아놓는다.
• 준비 큐 : 한 번에 하나의 프로세스를 꺼내어 CPU에 할당
• 대기 큐 : 여러개의 프로세스 제어 블록을 동시에 꺼내어 준비상태로 옮긴다. 여러 개의 인터럽트가 한꺼번에 처리될 수 있다.

스케줄링 알고리즘의 선택 기준

: cpu사용률, 처리량, 대기시간, 응답시간, 실행시간, 반환시간 → 주로 프로세스들의 평균 대기시간을 본다.

• 대기시간 : 프로세스 생성 후 실행되기 전까지 대기하는 시간
• 응답시간 : 첫 작업을 시작한 후 첫 출력이 나오기까지 시간
• 실행시간 : 프로세스 작업이 시작된 후 종료되기까지 시간
• 반환시간 : 대기시간을 포함하여 실행이 종료될 때까지의 시간

스케줄링 알고리즘의 분류

• 비선점형 알고리즘 : FCFS, SJF, HRN
• 선점형 알고리즘 : 라운드로빈, SRT, 다단계 큐, 다단계 피드백 큐
• 둘 다 가능 : 우선순위 스케줄링

FCFS

• (First Come First Served) 준비 큐에 도착한 순서대로 cpu할당 → 처리 시간이 긴 프로세스가 cpu를 차지하면 다른 프로세스들이 하염없이 기다려 시스템의 효율성이 떨어지는 문제(=콘보이 효과)발생

SJF

• (Shortest Job First) 실행시간이 가장 짧은 작업부터 cpu를 할당하는 비선점형 방식 → 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다. 공평X 실행시간이 긴 작업들이 계속 밀려나 기아(아사, starvation) 현상 발생

HRN 

(Highest Response Ratio Next) 최고 응답률 우선 스케줄링으로 실행시간과 대기시간을 함께 고려해서 기아 현상을 완화한다.

우선순위 = (대기시간 + cpu사용시간)/cpu사용시간 → 여전히 공평성 위배

라운드로빈 

한 프로세스가 할당받은 시간(타임 슬라이스)동안 작업하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식

SRT

(Shortest Remaining Time) 최소 잔류 시간 우선 스케줄링. 라운드 로빈을 방식을 사용하지만 남은 시간이 적은 프로세스에 cpu를 먼저 할당한다. → 현재 실행중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산해야함

우선순위 스케줄링

우선순위를 지정하고 그대로 → 공평성 위반, 기아(아사) 현상

다단계 큐 스케줄링

우선순위에 따라 준비 큐를 여러개 사용한다. 라운드로빈 방식으로 운영되는 큐는 우선순위에 따라 다단계로 나뉘어 있어, 프로세스가 큐에 삽입되는 것 만으로 우선순위 결정.

다단계 피드백 큐 스케줄링 

다단계 큐와 방식과 형태가 같지만 cpu를 사용하고 난 프로세스가 원래의 큐로 되돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어간다. 우선순위가 낮을수록 해당 큐의 타임슬라이스가 커진다. → 오늘날의 일반적인 방식

컴파일러

소스코드를 컴퓨터가 실행할 수 있는 기계어로 번역한 후 한꺼번에 실행한다. 자바, c언어 등이 이 방식으로 프로그램을 실행한다. (전체 컴파일 후 실행)

• 목적 : 코드를 점검하여 오류를 수정하고 최적화함으로써 작고 빠른 실행 파일을 만든다.
• 사용할 변수를 먼저 선언한 후 코드를 작성한다. 이를 통해 선언하지 않은 변수의 사용을 찾고, 실제로는 사용되지 않는 변수를 삭제할 수 있다.
• 크고 복잡한 프로그램에 사용

인터프리터 

소스코드를 한 행씩 번역하여 실행한다. 자바스크립트, 베이직이 이 방식으로 프로그램을 실행한다. (한 줄씩 실행)

• 같은 일을 반복하는 경우나 필요 없는 변수를 확인할 수 없다.
• 간단한 프로그램에 사용
• 실행이 편리하다. 변수를 미리 선언할 필요가 없다.