운영체제 정리3(프로세스 스케줄링)

다중 프로그래밍의 장점 : 1. 프로세서 이용률 ↑. 2. 프로세서 처리율 ↑

 

스케줄링 : 여러 프로세스가 번갈아 사용하는 자원을 어떤 시점에 어떤 프로세스에 할당할지 결정하는 것. 시스템의 성능에 영향

 

프로세스 버스트 : 프로세스를 프로세서에서 실행할 때

입출력 버스트 : 프로세스가 추가로 실행하려고 입출력을 기다리고 있을 때 프로세스는 입출력 버스트 후 다음 프로세서 버스트를 위해 준비큐로 이동

 

스케줄링의 단계

큐잉 도표 : 스케줄링을 표현하는 방법이다.(큐 : 사각형, 자원 : 원, 프로세스 흐름 : 화살표)

장기 스케줄러는 작업 스케줄러라고도 하며, 스케줄링에 따라 디스크에서 메모리로 작업을 가져와 처리할 순서를 결정한다. 작업 스케줄링에 필요한 정보로 제출시간, 작업이름, 작업길이(용량) 등이 있다. 선택한 작업에 프로세스 제어블록을 부착시켜 메모리를 적재한 것이 프로세스이다. 속도↓

 

단기 스케줄러는 메모리에 적재된 프로세스 중 프로세서를 할당하여 실행 상태가 되도록 결정하는 프로세스 스케줄링을 한다. 이때는 프로세스가 실행하는데 필요한 자원의 요청을 만족해야 한다. 속도 ↑

 

중기 스케줄러 : 프로세스들이 프로세서를 서로 차지하려고 할 때 프로세스를 별도의 기억 장소에서 빼낼 수 있어 다중 프로그래밍의 정도를 줄일 수 있다.(스왑)

 

선점 스케줄링 : 한 프로세스가 자원을 선택했을 때 다른 프로세스가 해당 자원을 빼앗을 수 있을 때

비선점 스케줄링 : 자원을 빼앗을 수 없을 때

 

스케줄링 알고리즘(반환시간, 대기시간 중요)

1. FCFS(First Come First Served) 선입선처리 또는 선입선출 스케줄링 : 비선점 방법으로 선입선출 큐로 구성

=> 호위효과 : 프로세서 중심 프로세스 하나가 프로세서를 떠나기를 기다리는 현상.

장점 : 단순, 기아x, 처리율↑

단점 : 비선점식이므로 프로세스에 부적합, 대기시간 최악, 호위효과 발생

 

2. SJF(Shortest Job First) 최소작업우선 스케줄링 : 각 작업의 프로세서 실행 시간을 이용하여 프로세서가 사용 가능할 때 실행시간이 가장 짧은 작업에 할당하는 방법. 선점형과 비선점형이 존재

장점 : 평균 대기시간↓

단점 : 초기의 긴 작업을 대기시켜 기아발생, 불공정, 실용적x

 

3. 우선순위 스케줄링 : 프로세스가 준비큐에 도착하면 도착한 프로세스의 우선순위와 현재 실행 중인 프로세스의 우선순위를 비교하여 우선순위가 가장 높은 프로세스에 프로세서를 할당. 선점, 비선점 가능

장점 : 각 프로세스의 상대적 중요성 정확히 정의 가능

단점 : 무한 기아 발생

 

4. 라운드 로빈 스케줄링 : 시분할 시스템을 위해 설계. 작은 단위의 규정 시간량을 정의. 준비큐를 순환큐로 설계하여 스케줄러가 준비큐를 돌아가면서 한번에 한 프로세스에 정의된 규정 시간량만큼 프로세서를 제공하는 방법

장점 : 공정, 기아x

단점 : 작업이 비슷해야 좋다. 너무 길면 선입 선처리, 너무 짧으면 문맥교환↑,비용↑,평균 처리시간↑

 

5. MLQ(MultiLevel Queue) 다단계 큐 스케줄링 : 각 작업을 서로 다른 묶음으로 분류할 수 있을 때 준비상태큐를 종류별로 여러 단계로 분할하여 각 큐는 순서대로 절대적인 우선순위를 가진다. 또 각 큐는 자신만의 독자적인 스케줄링을 가지며, 우선순위가 높은 큐가 비어있기 전에는 낮은 우선순위 큐에 있는 프로세스를 실행할 수 없다.

장점 : 응답이 빠르다.

단점 : 여러 준비큐와 스케줄링 알고리즘 때문에 추가 오버헤드 발생. 우선순위가 낮은 큐의 프로세스는 기아 발생 가능

 

6. MLFQ(MultiLevel Feedback Queue) 다단계 피드백 큐 스케줄링 : 작업이 큐 사이를 이동할 수 있고, 프로세서 버스트의 특성에 따라 분리. 프로세서 버스트 시간이 작은 프로세스에 높은 우선순위를 주어 일찍 종료시키고 다음 입출력 버스트를 실행하도록 하여 효율성은 향상된다. 하지만 낮은 우선순위의 큐에 입력된 작업이 기아상태에 빠질수 있다는 문제가 있고 설계가 복잡하다.

 

7. Highest Response-ratio Next HRN 스케줄링 : 비선점 스케줄링이며 우선순위 스케줄링의 또 다른 예로, 선입 선처리와 최소작업 우선 스케줄링의 약점을 해결하려고 제안했다.

우선순위=(서비스를 받을 시간+대기한시간)/서비스를 받을시간

장점 : 자원을 효율적으로 활용

단점 : 오버헤드가 높을 수 있다.

 

8. 다중 프로세서 스케줄링 : 각 프로세서에 서로 독립된 준비 큐를 제공하거나 공동의 준비큐를 사용하여 모든 작업이 이용 가능한 프로세서 큐로 가도록 스케줄링해야 한다.

장점 : 자원충돌 문제는 주 프로세서가 메인 메모리와 입출력 자원들을 제어하기 때문에 간단히 해결

단점 : 주 프로세서의 오류는 시스템 전체를 정지

 

9. 스레드 스케줄링 : 스레드를 이용하여 응용 프로그램을 동일한 주소 공간에서 동시에 실행하고 협동하는 스레드로 구현한다. 부하 공유, 갱 스케줄링, 동적 스케줄링 등이 있다.

 

스케줄링 알고리즘의 평가

평가기준 : 알고리즘의 선택이 어려운 이유 중 한가지는 기준이 모호하다는 것이다. 다음을 기준으로 삼자

1. 최대 응답시간이 1초라는 제약 조건에서 프로세서 이용률

2. 평균 반환시간이 전체 실행 시간에 선형적으로 비례하는 처리율