운영체제 - (3) CPU 스케줄링, 프로세스 동기화, 교착 상태

- 목차 -

1. CPU 스케줄링 개요

2. CPU 스케줄링 알고리즘

3. 프로세스 동기화

4. 동기화 기법

5. 교착 상태

1. CPU 스케줄링 개요

• CPU 스케줄링 : 운영체제가 프로세스들에게 공정하고 합리적으로 CPU자원을 배분하는 것. 프로세스 중요도에 맞게 프로세스가 CPU를 이용할 수 있도록 하기 위해 우선순위를 부여한다.
  • 선점형 스케줄링 : 하나의 프로세스가 자원을 사용하고 있을 때 다른 프로세스가 해당 자원을 빼앗을 수 있는 스케줄링. 자원 독점을 막고 프로세스들에 골고루 자원을 배분할 수 있지만 문맥 교환 과정에서 오버헤드가 발생할 수 있다.
  • 비선점형 스케줄링 : 빼앗을 수 없는 스케줄링. 자원을 사용 중이라면 무작정 기다리는 수밖에 없다. 

 

• 스케줄링 큐 : 운영체제는 CPU를 사용하고 싶은 프로세스들, 메모리에 적재되고 싶은 프로세스들, 특정 입출력장치를 사용하고 싶은 프로세스들을 큐로 구현하고 관리한다.
  • 준비 큐 : CPU를 이용하고 싶은 프로세스들이 서는 줄
  • 대기 큐 : 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄

스케줄링 큐

 

2. CPU 스케줄링 알고리즘

스케줄링 알고리즘	설명
선입 선처리 스케줄링	준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식. 호위 효과 : 앞에 단체 손님 주문 때문에 나의 커피 한 잔을 늦게 받아야 되는 상황.
최단 작업 우선 스케줄링	호위 효과를 방지하기 위해 CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행하는 스케줄링 방식.
라운드 로빈 스케줄링	선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 스케줄링 방식 타임 슬라이스 : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
최소 잔여 시간 우선 스케줄링	최단 작업 우선 스케줄링과 라운드 로빈을 합친 스케줄링 방식.  프로세스들은 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택된다.
우선순위 스케줄링	프로세스들에 우선순위를 부여하고 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 기아 현상 : 우선 순위가 낮은 프로세스의 실행이 계속 밀리는 현상 에이징 : 오래 대기한 프로세스의 우선순위를 점차 높이는 방식
다단계 큐 스케줄링	우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식. 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리해진다.
다단계 피드백 큐 스케줄링	다단계 큐 스케줄링을 보완한 스케줄링 방식 프로세스들이 큐 사이를 이동할 수 있어 CPU를 비교적 오래 사용해야 하는 CPU 집중 프로세스들은 우선순위가 낮아지고, CPU를 비교적 적게 사용하는 입출력 집중 프로세스들은 우선순위가 높은 큐에서 실행이 끝난다. 에이징 기법을 적용하여 기아 현상을 예방할 수도 있다.

 

 

3. 프로세스 동기화

• 동기화 : 특정 자원에 접근할 때 한 개의 프로세스만 접근하게 하거나, 프로세스를 올바른 순서대로 실행하게 하는 것을 의미한다. 동시다발적으로 실행되는 프로세스들은 공동의 목적을 올바르게 수행하기 위해 서로 협력하여 실행 순서와 자원의 일관성을 보장해야 하기 때문에 반드시 동기화 되어야 한다. 

 

• 프로세스 동기화 : 프로세스들 사이의 수행 시기를 맞추는 것
  • 실행 순서 제어 : 프로세스를 올바른 순서대로 실행하기
  • 상호 배제 : 동시에 접근해서는 안 되는 자원에 하나의 프로세스만 접근하게 하기

 

• 공유 자원 : 공동으로 이용하는 변수, 파일, 장치 등의 자원
• 임계 구역 : 공유 자원에 접근하는 코드 중 동시에 실행하면 문제가 발생하는 코드 영역
  • 레이스 컨디션 : 잘못된 실행으로 인해 여러 프로세스가 동시 다발적으로 임계 구역의 코드를 실행하여 문제가 발생하는 경우
    
    • 상호 배제 : 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임계 구역에 들어올 수 없다. 
    • 진행 : 임계 구역에 어떤 프로세스가 진입하지 않았다면 임계 구역에 진입하고자 하는 프로세스는 들어갈 수 있어야 한다.
    • 유한 대기 : 한 프로세스가 임계 구역에 진입하고 싶다면 그 프로세스는 언젠가는 임계 구역에 들어올 수 있어야 한다.(무한정 대기해서는 안된다)

 

4. 동기화 기법

• 뮤텍스 락 : 상호 배제를 위한 동기화 도구로 동시에 접근해서는 안되는 자원을 접근하지 않게 잠구는 자물쇠 역할. 하나의 공유자원에 접근하는 프로세스를 상정한 방식
  • lock 함수 : 프로세스들이 공유하는 전역 변수로 자물쇠 역할을 한다.
  • acquire 함수 : 프로세스가 임계 구역에 진입하기 전에 호출하는 함수. 임계 구역이 잠겨 있다면 임계 구역이 열릴 때까지(lock이 false가 될 때까지) 임계 구역을 반복적으로 확인하고, 임계 구역이 열려 있다면 임계 구역을 잠그는 함수
  • release 함수 : 임계 구역에서의 작업이 끝나고 호출하는 함수. 현재 잠긴 임계 구역을 열어주는(lock을 false로 바꾸는) 함수이다.
  • 단점 : 바쁜 대기해서 임계 구역에 들어가기 위해 acquire()을 호출하는 반복문을 실행한다. lock이 가용되길 기다리면서 프로세스가 계속 반복 회전해서 스핀락이 발생. 결국, CPU Cycle 낭비를 초래한다.

 

 

• 세마포어 : 공유된 자원 속 하나의 데이터는 한 번에 하나의 프로세스만 접근할 수 있도록 제한을 두는 것. 공유 자원이 여러 개 있는 상황에서도 적용이 가능한 동기화 도구
  • wait 함수 : 임계 구역에 들어가도 좋은지, 기다려야 할지를 알려주는 함수
  • signal 함수 : 임계 구역 앞에서 기다리는 프로세스에 이제 가도 좋다고 신호를 주는 함수
  • 단점 : 매번 임계 구역에 앞뒤로 일일이 wait와 signal 함수를 명시하는 것은 번거로운 일이다.

뮤텍스	세마포어
공유된 자원의 데이터를 여러 스레드가 접근하는 것을 막는 것	공유된 자원의 데이터를 여러 프로세스가 접근하는걸 막는 것
상태가 0,1 두개(이진 세마포어)	세마포어는 뮤텍스가 될 수 있음
뮤텍스 소유 중인 스레드가 뮤텍스 해제	세마포어를 소유하지 않는 스레드가 세마포어 해제
프로세스 범위를 가지고 종료될 때 자동 Clean	파일 시스템 상의 파일 형태로 존재
동기화 대상이 오직 하나일 때	동기화 대상이 하나 이상일 때

 

• 모니터 : 공유 자원과 공유 자원에 접근하기 위한 인터페이스를 묶어 관리한다. 프로세스는 반드시 인터페이스를 통해서만 공유 자원에 접근한다 
  • 상호 배제를 위한 동기화 : 모니터는 공유 자원을 다루는 인터페이스에 접근하기 위한 큐를 만들고, 모니터 안에 항상 하나의 프로세스만 들어오도록 한다. 
  • 실행 순서 제어를 위한 동기화 : 세마포에 비해 사용자가 사용하기 편리한 동기화 도구로 조건 변수를 사용한다. 조건 변수는 프로세스나 스레드의 실행 순서를 제어하기 위해 사용하는 특별한 변수이다.  
    • 특정 프로세스가 아직 실행될 조건이 되지 않았을 때에 wait를 통해 실행을 중단한다
    • 특정 프로세스가 실행될 조건이 충족되었을 때에는 signal을 통해 실행을 재개한다.

 

 

5. 교착 상태

- 교착 상태란 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 가리킨다.

 

• 자원 할당 그래프 : 교착 상태가 발생한 상황은 자원 할당 그래프가 원의 형태를 띄고 있다.

교착 상태의 자원 할당 그래프

 

• 교착 상태 발생 조건 : 조건을 만족할 경우 교착상태가 발생할 가능성이 생긴다.
  • 상호 배제 : 한 프로세스가 사용하는 자원을 자원을 다른 프로세스가 사용할 수 없을때 발생할 수 있다.
  • 점유와 대기 : 어떠한 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다릴때 발생할 수 있다.
  • 비선점 : 비선점 자원은 그 자원을 이용하는 프로세스의 작업이 끝나야만 이용할 수 있다. 즉, 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못했기 때문에 발생할 수 있다.
  • 원형 대기 : 프로세스들과 프로세스가 요청 및 할당받은 자원이 원의 형태를 이룰 때 발생할 수 있다.

 

- 교착 상태 해결 방법

• 예방 : 프로세스들에 자원을 할당할 때 상호 배제, 점유와 대기, 비선점, 원형 대기 중 하나의 조건이라도 만족시키지 않게 할당하면 교착상태는 발생하지 않는다.

 

• 회피 : 안전 상태를 유지하도록 자원을 할당하는 방식.
  • 안전 순서열 : 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서 
  • 안전 상태 : 안전 순서열대로 자원을 배분하여 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태
  • 불안전 상태 : 안전 순서열이 없고 교착 상태가 발생할 수도 있는 상태

 

• 회복 : 교착 상태 발생을 인정하고 사후에 조치하는 방식
  
  • 선점을 통한 회복 : 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
  • 프로세스 강제 종료를 통한 회복 : 교착 상태에 놓인 프로세스를 강제 종료하는 방식