운영체제 (2)

스케줄링

스케줄링은 프로세스가 생성되어 실행될 때 필요한 시스템의 여러 자원은 해당 프로세스에게 할당하는 작업을 의미한다 

문맥교환 : 하나의 프로세스에서 다른 프로세스로 cpu가 할당되는 과정에서 발생한다 새로운 프로세스에 cpu를 할당하기 위해 현재 cpu가 할당된 프로세스의 사태 정보를 저장, 새로운 프로세스의 상태 정보를 설정한 후 cpu를 할당하여 실행되도록 하는 작업이다 

스케줄링의 목적은 다음과 같다

공정성, 처리율증가, cpu이용률증가, 우선순위제도, 오버헤드 최소화, 응답시간 최소화, 반환시간 최소화, 대기시간 최소화, 균형있는 자원의 사용, 무한 연기 회피 

비선점non-preemptive 스케줄링

이미 할당된 cpu를 다른 프로세스가 강제로 빼앗을 수 없는 스케줄링 기법이다

cpu를 할당받으면 해당 프로세스가 완료될 때까지만 cpu를 사용하므로 응답시간 예측이 용이하다

모든 프로세스에 대한 요구를 공정하게 처리한다

일괄처리방식에 적합하다, 중요한 작업이 중요하지 않은 작업을 기다리는 경우가 발생할 수 있다

종류 : FCFS, SJF, 우선순위, HRN 

선점preemptive 스케줄링

우선순위가 높은 다른 프로세스가 cpu를 강제로 빼앗아 사용할 수 있다

우선순위가 높은 프로세스 먼저 철처리

빠른 응답을 요구하는 대화식 시분할시스템, 온라인 응용 등에 사용한다

많은 오버헤드를 초래할 수 있따 

인터럽트 타이머 클럭이 필요하다 

종류 : SRT, 선점우선순위, Round Robin, 다단계 큐, 다단계 피드백 큐 

비선점 기법을 세부적으로 

1번 FCFS First Come First Service 

First in First Out 

도착한 순서에 따라 차례로 cpu를 할당한다 

선착순이라 공평하지만 짧은 작업이 긴작업을, 중요한 작업이 중요하지 않은 작업을 기다리게 할 수 있다 

2번 SJF Shortest job First

가장 짧은 프로세스에게 먼저 cpu를 할당한다

가장 적은 평균 대기시간을 제공한다 

실행시간이 긴 프로세스는 실행시간이 짧은 프로세스에게 밀려 계속 지연될 수 있다다 

3번 HRN Highest Response Ratio Next 

실행시간이 긴 프로세스에게 불리한 SJF기법을 보완하기 위한 것이다 

대기시간과 서비스 시간을 이용하는 기법으로 서비스 시간이 짧은 프로세스나 대기시간이 긴

프로세스에게 우선순위를 준다 

우선수위 계산식 : (대기시간+서비스실행시간)/서비스 실행 시간

4번 기한부 Deadline

일정한 시간을 프로세스에게 주어 그 시간 안에 프로세스를 완료하도록 하는 기법이다

제한된 시간 안에 프로세스가 완료되지 않은 경우 제거되고 처음부터 다시 실행된다

애초에 한 번에 처리하기 위해서 만들어진 것으로 정확한 정보와 시간이 요구되어진다

여러 프로세스들이 동시에 실행되면 스케줄링이 복잡해지고 자원관리에 오버헤드가 발생한다

5번 우선순위 Priority 

각 프로세스마다 우선순위를 부여 가장높은 프로세스에게 먼저 cpu를 할당시킨다

우선순위가 동일할 경우 FCFS기법을 사용한다

우선순위는 프로세스의 종류나 특성에 따라 다르게 부여한다

가장 낮은 순위를 부여받는 프로세스는 무한 연기 또는 기아 상태(Starvation)가 발생할 수 있다

추가정보(aging 기법)

우선순위가 낮아 무한정 기다리게 되는 경우 일정시간이 지나거나 양보를 한 횟수에 비례하여 우선순위를 높여서 가까운 시간에 자원을 할당받게 해준다(무한 연기상태, 기아상태를 예방할 수 있다)

선점우선순위 

우선선순위가 가장 높은 프로세스에게 cpu를 할당한다

순위가 높을 경우 현재의 프로세스를 보류하고 높은 것 먼저 처리한다 

SRT Shortest Remaining Time 

비선점 스케줄링인 SJF기법을 선점 형태로 변경한 기법이다

실행시간을 비교하여 가장 짧은 실행시간을 요구하는 프로세스에게 CPU를 할당하는 기법으로 시분할 시스템에 유용하다

각 프로세스의 실행시간을 추적하여 보유하고 있어야 하므로 오버헤드가 증가한다

RR Round Robin

시간분할 크기가 커지면 FCFS(FIFO)방법과 같게 한다

시분할 시스템을 위해서 고안되었다, FCFS 알고리즘을 선점형태로 변형시킨다

먼저 들어온 프로세스가 먼저 CPU를 할당받지만 각 프로세스는 할당된 시간 동안만 실행한 후 실행이 완료되지 않으면 다음 프로세스에게 

CPU를 넘겨주고 준비상태큐의 가장 뒤로 배치된다

할당되는 시간이 클 경우 FCFS기법과 같아지고, 할당되는 시간이 작을 경우 문맥교환 및 오버헤드가 자주 발생된다

시간 할당량이 너무 작으면 스레싱에 소요되는 시간의 비중이 커진다

대화식 시스템에 유용하다

기한부Deadline과 달리

RR은 중간에 처리가 멈추더라도 처음부터 시작하지는 않는다 

다단계 큐 MQ Multi-level Queue 

우선순위에 따라 시스템 프로세스, 대화형 프로세스, 일괄처리 프로세스 등으로 상위, 중위, 하위 단계의 단계별 준비 큐를 배치하는 cpu 스케줄링 기법이다

독자적인 스케줄링을 가지고 있으므로 각 그룹룹의 특성에 따라 서로 다른 스케줄링 기법을 사용할 수 있다

다단계 피드백 큐 Multi-level feedback Queue

특정 큐에서 오래 기다린 프로세스나 I/O 작업주기가 큰 프로세스 또는 Foreground 큐에 있는 프로세스는 우선순위가 높은 단계의 준비큐로 이동시키고, cpu의 점유 시간이 긴 작업은 우선순위가 낮은 하위 단계의 큐로 이동시킨다

마지막 단계 큐에서는 작업이 완료될 때까지 RR스케줄링 기법을 사용한다

짧은 작업에 우선권을 준다, 입출력 위주의 작업권에 우선권을 준다

병행 프로세스 Concurrent Process

병행 프로세스란 두 개 이상의 프로세스들이 동시에 존재하며 실행상태에 있는 것을 의미한다

자원을 공유하고, 동시에 작업을 수행하기 위해 사용하는 개념이다

독립적으로 실행되는 것을 독립적 병행 프로세스, 서로 협력하며 동시에 실행되는 것을 협동적병행 프로세스라 한다

다중처리시스템이나 분산처리시스템에서 중요한 개념으로 사용된다  

동시에 두 개 이상의 프로세스를 병행처리 하면 여러 가지 문제점 발생 

해결방법 : 임계구역, 상호배제기법, 동기화 기법 

해결방법 1 임계구역 critical section

어느 한 시시점에서는 하나의 프로세스만 자원 또는 데이터를 사용하도록 지정된 공유자원이다

운영체제의 제어 권한으로 프로세스 진입여부를 결정한다

특정프로세스가 독점해서는 안 되며, 임계구역 내에서의 작업은 신속하게 진행되어야 한다

무한루프에 빠지지 않도록 해야한다

임계구역에는 하나의 프로세스만 접근할 수 있으며, 자원을 반납한 후에야 다른 프로세스가 자원이나 데이터를 사용할 수 있다 

해결방법 2 상호배제기법 Mutual Exclusion

특정 프로세스가 공유 자원을 사용하고 있을 경우 

다른 프로세스가 해당 공유 자원을 사용하지 못하게 제어하는 기법이다 

각 프로세스가 번갈아가며 공유자원을 사용하도록 하는 것으로 임계 구역을 유지하는 기법이다 

소프트웨어적인 방법과 하드웨어적인 방법이 있다 

소프트 웨어 

두 개의 프로세스 기준 : 데커알고리즘, 피터슨 알고리즘

여러 개의 프로세스 기준 : lemport의 빵집 알고리즘

하드웨어 

test_and_set 기법과 swap 명령어 기법이 있다

해결방법 3 동기화 기법 syncronization _(1)세마포어

두 개 이상의 프로세스를 한 시점에서는 동시에 처리할 수 없으므로 각 프로세스에 대한 처리순서를 결정하는 것으로, 상호배제의 한 형태이다

세마포어는 신호기, 깃발 제어신호를 전달하여 순서대로 작업을 한다

E.J.Dijkstra가 제언했다 

사용되는 연산에는 p와 v , 초기치연산이 있고 상호 배제의 원리를 보장한다

s는 공유자원의 개수를 나타낸다 0 또는 1 0 또는 양의 정수 값을 가진다

p 연산 프로세스들의 진입여부를 s의 개수로 정한다 wait 동작

v연산 프로세스르 깨우는 것이다 signal 동작 

동기화 기법 synchronization_(2)모니터

내부의 프로시저와 데이터 정보를 은폐시켜서 다른 외부 프로시저가 접근하거나 병경하지 못하도록 하는 기법이다

동기화를 구현하기 위한 특수 프로그램 기법으로 프로시저가 공유자원을 프로세스에게 할당하는데 필요한 데이터를 처리한다

공유자원을 할당하기 위해 병행성 구조로 이루어진다

모니터 내의 공유자원을 사용하려면 프로세스는 반드시 모니터의 진입부를 호출해야만 한다

외부의 프로시저는 직접 액세스 할 수 없으며, 모니터의 경계에서 상호배제가 시행된다

한 순가에 하나의 프로세스만 진입하여 자원을 사용한다

wait 연산과 signal 연산이 사용된다