반응형

비선점 스케줄링의 종류

   
FCFS
(First-Come
First-Service)
= FIFO
(First In First Out)
 - 큐에 도착한 순서대로 CPU를 할당
 - 먼저 도착하면 먼저 처리되므로 공평성은 유지되나, 짧은 작업이 긴 작업을, 중요한 직업이 중요치 않은 직업을 기다림
SJF
(Shortest Job First)
 - 실행 시간이 가장 짧은 프로세스에 먼저 CPU 할당
 - 가장 적은 평균 대기 시간 제공
HRN
(Hightest Response-ratio Next)
 - 실행 시간이 긴 프로세스에 불리한 SJF기법 보완. 대기 시간과 서비스(실행 시간)을 이용
 - 우선 순위 계산 공식 = (대기 시간 + 서비스 시간) / 서비스 시간
 - 우선 순위 계산 결과값이 높은 순으로 순위 부여, 대기 시간이 길 수록 계산 결과값이 높음
기한부
(Deadline)
 - 일정 시간 안에 프로세스를 완료
 - 프로세스 할당 시간을 추정해야 하므로, 요구된 프로세스에 대한 정확한 정보 제공 필요
우선순위
(Priority)
 큐의 각 프로세스마다 우선순위 부여 후, 우선순위가 가장 높은 프로세스에게 먼저 할당

에이징(Aging) 기법

  • 특정 프로세스를 무한정 기다리면, 대기 시간에 비례하여 우선순위를 높여 자원을 할당받도록 하는 기법
  • SJF나 우선순위 기법에서 발생하는 무한 연기 상태, 기아 상태 예방

선점 스케줄링의 종류

   
선점 우선순위  큐의 프로세스들 중 우선순위가 가장 높은 프로세스에게 먼저 CPU 할당
SRT
(Shortest Reamaining Time)
 비선점 기법의 SJF 알고리즘을 변경. 프로세스의 남은 시간과 큐의 프로세스 실행시간을 비교하여 가장 짧은 요구 시간을 가진 프로세스에게 CPU 할당
RR
(Round Robin)
 - 시분할 시스템(Time Sharing System)을 위한 방식. FCFS 알고리즘을 선점 형태로 변형
 - FCFS(FIFO) 와 같이 큐에 먼저 들어온 프로세스가 CPU 할당, 할당 시간(Time Slice, Quantum) 동안 실행 후 완료되지 않으면 당므 프로세스에 CPU 넘기고 큐의 뒤로 배치
 - 할당 시간이 크면 FCFS 기법과 같음, 작으면 문맥 교환 및 오버헤드 다수 발생
다단계 큐
(Multi level Queue)
 프로세스 그룹에 따라 다른 준비상태 큐를 사용
다단계 피드백 큐
(Multi level Feedback Queue)
 특정 그룹의 큐에 들어간 프로세스가 다른 큐로 이동할 수 없는 다단계 큐와 달리 준비상태 큐 사이를 이동할 수 있도록 개선

임계구역 / 상호 배제 / 세마포어

임계 구역(Critical Section)

  • 여러 프로세스가 데이터 및 자원을 공유할 때, 특정 시점에 하나의 프로세스만 데이터 및 자원을 사용하도록 지정된 공유 자원
  • 임계 구역에는 하나의 프로세스만 접근 가능, 해당 프로세스의 반납 후에 다른 프로세스가 자원 사용가능
  • 임계 구역은 특정 프로세스가 독점 불가
  • 임계 구역 자원은 여러 프로세스가 사용하므로, 임계 구역 내 작업은 신속해야함
  • 프로세스가 진입을 요청 시 일정 시간 내 진입 허락
  • 임계 구역에서 실행중인 프로세스가 없을 경우, 사용을 대기중인 프로세스에게 사용 허락, 그외는 진입 불가

상호 배제(Mutual Exclusion)

  • 특정 프로세스가 공유자원 사용시 타 프로세스가 공유 자원을 사용하지 못하도록 제어
  • 여러 프로세스가 동시에 공유 자원을 사용하려 하면, 각 프로세스가 번갈아가며 공유 자원을 사용하도록 하여 임계 구역 유지
  • 상호 배제 기법으로 임계 구역 내의 인터럽트, 교착상태, 무한반복을 제재
  • 상호 배제 구현 기법
   
소프트웨어적
구현 방법
 - 2개 프로세스 기준 : 데커(Dekker) 알고리즘, 피터슨(Peterson) 알고리즘
 - 여러 프로세스 기준 : Lamport의 빵집 알고리즘
하드웨어적
구현 방법
 Test & Set 기법, Swap 명령어 기법

세마포어(Semaphore)

  • 각 프로세스에 제어 신호 전달로 순서대로 작업 수행
  • E. J. Dijkstra (다익스트라)가 제안, P,V 연산으로 동기화 유지, 상호 배제 원리 보장
  • 여러 프로세스가 동시 값 수정 불가
  • S는 P, V연산으로 접근 가능한 세마포어 변수. 공유 자원의 개수를 나타냄, 0,1 혹은 0과 양의 값 가짐.
  • P 연산 : 프로세스의 진입 여부를 자원의 개수(S)를 통해 결정. 자원의 개수 감소(S=S-1)로 자원이 점유됨을 알림(Wait 동작)
  • V 연산 : 대기 중 프로세스를 깨우는 신호(Wake Up)로서, 자원 개수 증가(S=S+1)로 자원 반납을 알림(Signal 동작)

모니터(Monitor)

  • 동기화 구현을 위한 기법. 공유자원 할당에 필요한 데이터와 처리 프로시저로 구성
  • 자료 추상화와 정보 은폐 개념, 공유 자원 할당을 위한 병행성 구조로 이루어짐
  • 모니터 공유 자원 사용을 위해 모니터 진입부 호출 필요
  • 외부 프로시저는 직접 액세스 불가, 모니터 경계에서 상호 배제 시행
  • 한 순간 하나의 프로세스만 자원 사용 가능

교착 상태(Deadlock)

   
정의   상호 배제에 의한 문제점. 둘 이상의 프로세스가 자원 점유상태에서 서로 다른 프로세스가 점유한 자원을 요구하여 무한정 기다리는 현상
필요
충분
조건
 - 상호 배제(Mutual Exclusion) : 한 번에 한 개의 프로세스만이 공유자원 사용해야 함
 - 점유와 대기(Hold & Wait) : 최소 하나의 자원을 점유하며 다른 프로세스에 할당 되어 사용되는 자원 사용을 대기하는 프로세스가 있어야 함
 - 비선점(Non-preemptive) : 다른 프로세스에 할당된 자원의 사용이 끝날 때까지 강제로 빼앗을 수 없어야 함
 - 환형 대기(Circular Wait) : 공유자원과 대기 프로세스가 원형으로 구성되어 할당된 자원을 점유하면서 앞 뒤에 있는 프로세스 자원을 요구해야 함

교착 상태 해결 방법

  • 예방(Prevention) 기법 : 교착 상태 방지를 위해 사전에 시스템을 제어. 교착 상태 발생 4가지 조건 중 어느 하나를 제거함으로써 수행. 자원의 낭비가 가장 심함
   
상호 배제 부정  한 번에 여러 개의 프로세서가 공유 자원을 사용하도록 하는것. 실제로는 구현하지 않음
점유 및 대기 부정  프로세스 실행 전 필요 자원을 모두 할당하여 프로세스 대기를 없애거나, 자원이 점유되지 않은 상태에서만 자원을 요구하도록 함
비선점 부정  자원을 점유한 프로세스가 다른 자원을 요구할 때, 점유 자원을 반납 후, 요구 자원을 대기하도록 함
환형 대기 부정  자원을 선형으로 분류 및 고유 번호를 할당하여 프로세스의 점유 자원 번호보다 앞 혹은 뒤 방향으로만 자원을 요구하도록 함
  • 회피(Avoidance) 기법 : 교착 상태 발생 가능성을 배제하지 않고, 교착 상태 발생 시 적절히 피해가는 방법. 은행원 알고리즘(Banker's Algorithm)이 사용
   
은행원 알고리즘  - Dijkstra 제안. 은행에서 모든 고객의 요구가 충족되도록 하는 현금할당에서 유래
 - 각 프로세스에 자원을 할당하며 교착 상태가 발생하지 않으며 모든 프로세스가 완료될 수 있는 상태를 안전 상태, 교착 상태가 발생할 수 있으면 불안전 상태라 함
  • 발견(Detection) 기법 : 시스템 교착 상태를 점검하여, 교착 상태 프로세스와 자원을 발견하는 것. 자우너 할당 그래프 등 사용
  • 회복(Recovery) 기법 : 교착 상태 프로세스를 종료하거나 할당된 자원을 선점하여 프로세스 및 자원 회복
반응형

+ Recent posts