728x90
반응형
비선점 스케줄링의 종류
| 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) 기법 : 교착 상태 프로세스를 종료하거나 할당된 자원을 선점하여 프로세스 및 자원 회복
728x90
반응형
