운영체제 프로세스 2/2

운영체제 프로세스

스케줄링 알고리즘 기술

스케줄링 성능 평가 기준

CPU 이용률(CPU utilization) : 프로세스들이 CPU를 사용하는 비율로 실제로는 CPU가 쉬는 시간을 측정하여 그 시간을 제외한 나머지 시간을 사용

시스템 처리율(Throughput) : 단위 시간당 완료된 프로세스의 개수

반환 시간(Turnaround time) : 프로세스들이 시스템에 들어간 시간과 마친 시간의 차이를 말하며 출력장치의 속도에 제한을 받음

대기 시간(Waiting time) : 프로세스가 준비 큐에서 대기하는 시간으로 큐의 길이에 의해 측정

응답 시간(Response time) : 프로세스의 요구한 시간으로부터 첫 번째 응답이 나올 때까지의 시간

스케줄링 기법

비선점 스케줄링(Non-Preemptive Scheduling)

• CPU를 차지하고 실행 중인 프로세스는 자신의 실행이 종료될 때까지 CPU를 빼앗기지 않고 독점하며 사용하는 방식(양보)
• 어떤 프로세스가 CPU를 할당받으면 종료될 때까지 처리기를 독점하는 방식으로, 이미 할당된 CPU를 다른 프로세스가 강제로 빼앗을 수 없는 방식
• 선입선출 스케줄링, 단기작업우선 스케줄링, 최고응답률우선 스케줄링, 기한부 스케줄링, 우선순위 스케줄링

선점 스케줄링(Preemptive Scheduling)

• 어떤 프로세스가 CPU를 차지하고 실행 중, 다른 프로세스의 CPU 할당에 대한 요구를 받으면 CPU 사용권을 돌려주는 방식(강제)
• 높은 우선순위의 프로세스로부터 긴급 처리 요구에 유용하며, 실시간 프로세스, 대화식 시분할 시스템에서 빠른 응답 가능
• 순환 할당 스케줄링, 최소잔류시간우선 스케줄링, 선점 우선순위 스케줄링, 다단계 큐 스케줄링, 다단계 피드백 스케줄링

비선점 스케줄링

선입선출(FIFO, First In First Out) : 가장 간단한 방법으로 프로세스들이 준비 상태 큐에 도착한 순서에 따라 차례대로 CPU를 할당, 공평성은 유지되나 짧은 작업이나 중요한 작업이 지연될 수 있어 대화식 시스템에는 부적합

단기작업우선(SJF, Shortest Job First) : 준비 상태 큐에서 기다리고 있는 프로세스 중에서 실행시간이 가장 짧은 것부터 먼저 실행하는 방식, 평균 대기시간이 가장 짧으나 실행시간이 긴 프로세스 순위가 계속 밀리는 무한연기가 발생할 수 있어 대화식 시분할 시스템에는 부적합

최고응답률우선(HRN, Highest Response-ratio Next) : 우선순위 공식을 이용하여 실행시간이 짧은 프로세스나 대기시간이 긴 프로세스의 우선순위를 높여 줌. 우선순위 = (대기시간 + 실행시간(서비스 시간))/실행시간(서비스 시간)

기한부(Deadline) : 각 프로세스는 실행 종료 시간을 가지고 제출되어 주어진 기한 내에 완료되도록 계획하는 방식으로 실시간 시스템과 같은 제한된 응답시간 요구 분야에 유용

우선순위(Priority) : 프로세스의 중요도에 따라 우선순위를 결정, 우선순위는 시스템에 의해 결정되거나 사용자에 의한 외부 사항에 따라 결정이 가능. 가장 낮은 우선순위의 프로세스는 무한연기 되거나 기아 상태가 될 수 있는데 오랫동안 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 에이징(Aging)기법으로 해결

선점 스케줄링

순환 할당(RR, Round Robin) : 준비 상태 큐에 먼저 들어온 프로세스가 CPU를 할당받은 후 주어진 시간 동안에 완료되지 못하면 다음 프로세스에 CPU 할당을 넘기고 자신은 준비 상태 큐의 가장 뒤로 가서 대기, 시스템이 사용자에게 적합한 응답 시간을 제공해야 하는 대화식 시분할 시스템에 적합

최소잔류시간우선(SRT, Shortest Remaining Time) : 새로운 프로세스가 준비 상태 큐에 도착하면 현재 실행 중인 프로세스의 남은 실행시간과 비교하여 가장 짧은 실행 시간의 프로세스를 CPU에 할당하는 방법으로 시분할 시스템에 적합

선점우선순위 : 준비 상태 큐의 프로세스 중에서 가장 우선순위가 높은 프로세스에 CPU를 할당하는 방법, 새로 제출되어 준비 상태 큐에 도착한 프로세스와 현재 CPU를 할당받고 실행 중인 프로세스의 우선순위를 비교하여 우선순위가 높은 프로세스에 CPU를 할당하는 방식

다단계 큐(MLQ, Multi-Level Queue) : 작업을 여러 개의 특징적 그룹으로 나누어 유형별로 그룹별 큐를 두어 스케줄링하는 기법, 일반적으로 프로세스들은 대화식 프로세스와 편집 프로세스 및 일괄처리 프로세스 등으로 나누고 대화식 작업이 높은 우선순위를 갖게 함

다단계 피드백 큐(MFQ, Multi-Level Feedback Queue) : 준비 상태 큐 사이의 이동이 가능한 방법, 요구 시간이 적은 프로세스, 입출력 중심의 프로세스, 낮은 우선순위에서 너무 오래 기다린 프로세스 등을 기준으로 높은 우선순위를 할당

프로세스 간 협조

임계영역(Critical Section) 문제

어떤 프로세스가 임계 영역에 있을 때 다른 프로세스는 임계 영역 내에 들어가지 못 함

임계영역 해결 조건

상호배제 : 두 개 이상의 프로세스가 임계구역 동시 참여 불가

진행(Progress) : 임계구역 외부 프로세스가 다른 프로세스의 임계구역 접근 제한 불가, 여러 개의 프로세스 중 하나만 임계구역 차지

한계대기(Bounded Waiting) : 어떤 프로세스도 임계구역으로의 접근 무한연기 불가(기아(Starvation) 상태 예방)

프로세스 간 통신

공유 메모리 방식

• 어떤 변수들을 공유함으로써 프로세스 간의 통신이 이루어지는 기법으로 프로세스들은 공유 변수를 통해 정보를 교환하며 운영체제는 공유 메모리만 제공
• 프로그래머는 공유 메모리를 통해 통신 기능 구현 가능

메시지 시스템 방식

• 프로세스들이 메시지를 교환하도록 허용하는 기법

교착상태(Deadlock)

다중 프로그래밍 체제에서 하나 또는 그 이상의 프로세스가 일어날 수 없는 어떤 특정 사건(Event)을 무한정 기다리고 있는 상태

발생 조건

상호배제(Mutual Exclusion) : 프로세스들이 각각 필요 자원에 대해 배타적 통제권을 요구할 때

점유대기(Hold and Wait) : 프로세스가 다른 자원을 요구하면서 자신에게 할당된 자원을 해제하지 않을 때

비선점(No Preemption) : 프로세스에 할당된 자원을 끝날 때까지 해제할 수 없을 때

순환대기(Circular Wait) : 각 프로세스가 점유와 대기하는 자원이 원형 관계를 이루고 있을 때

해결 방안

예방(Prevention)

• 상호배제 : 공유 자원은 배타적 접근을 요구하지 않으므로 교착상태도 될 수 없음
• 점유대기 : 프로세스는 수행 전에 모든 자원을 요청하거나 프로세스가 자원을 전혀 갖고 있지 않을 때만 자원을 요청
• 비선점 : 자원 요청이 거부되면 점유하고 있는 모든 자원들을 반납(암시적 해제)
• 순환대기 : 모든 자원 형태에 전체 순서를 부여하여 각 프로세스가 열거된 상태에서 오름차순으로 자원 요청

회피(Avoidance)

• 순환대기 : 자원 할당 상태(가용한 자원의 수, 할당된 자원의 수, 프로세스들의 최대 요구 수에 의해 정의)를 검사
• 안정상태 : 특정한 순서대로 각 프로세스에 자원을 할당할 수 있고 교착상태를 저지할 수 있는 상태
• 은행원 알고리즘(banker’s Algorithm) : 다수 개의 자원을 가진 시스템에 적용될 수 있지만, 자원 할당 그래프 방법보다는 덜 효과적

탐지(Detection)

• 타임아웃(Time Out) : 교착상태가 자주 발생하지 않을 것이라는 가정하에 작업이 일정 시간 동안 진행되지 않는 프로세스를 교착상태가 발생한 것으로 간주
• 자원 할당 그래프 이용(Resource Allocation Graph) : 자원 할당 그래프를 완성하였을 때 사이클이 발생하면 교착상태 발생

회복(Recovery)

• 프로세스 종료 : 교착상태를 발생시킨 모든 프로세스 종료
• 자원 선점 : 교착상태에 있는 프로세스가 지닌 자원을 선점하여 다른 프로세스에 할당하고 해당 프로세스 일시 정지