OS의 process scheduling

운영체제는 자원관리 기능을 수행하는데, 자원관리 기능 중 프로세스 관리가 있다.

프로세스란 무엇이고, 어떻게 프로세스를 관리(스케줄링, 동기화, 교착상태해결)하는지 자세히 알아보자.

Process

프로세스(process) :

 - 현재 CPU에 의해 실행 중인 프로그램

   (프로그램을 실행하면 OS로부터 실행에 필요한 자원(메모리)를 할당 받아 프로세스가 된다.)

 - PCB를 가진 실행이 가능한 프로그램

 - 프로세서가 할당하는 개체로서 디스패치가 가능한 단위이다.

 - 비동기(Asynchronous)적인 행위이다.

 - 목적 또는 결과에 따라 발생되는 사건들의 과정이다.

 - 운영체제가 관리하는 실행 단위이다.

1. 프로세스의 상태 전이

  프로세스가 시스템 내에 존재하는 동안 프로세스의 상태 변화

  

   프로세스 상태

①     New : 프로세스가 만들어진 상태

         사용자의 작업이 디스크의 할당 위치에 저장된 상태

②     Ready : 프로세스가 CPU를 할당 받기 위해 메모리에서 준비 중인 상태(준비상태 큐 즉 스케줄링 큐에서 준비)

③     Running : 프로세스가 CPU를 할당 받아 실행 중인 상태

④     Waiting : 프로세스가 어떤 이벤트가 완료될 때까지 대기 큐에서 대기하고 있는 상태

⑤     Terminated : 프로세스가 실행을 완료한 상태

2. 프로세스의 상태 전환

①     Dispatch(Ready -> Running) : 준비상태의 프로세스 중에서 우선순위가 가장 높은 프로세스를 선정하여 CPU를 할당받음으로써 실행상태로 전환

②     Interrupt (Running -> Ready) : 프로세스 수행이 완료되기 전, 프로세스에게 주어진 CPU 할당 시간이 종료되면 프로세스는 다른 프로세스를 위해 준비상태로 전환

③     Block(Running -> Waiting) : 실행 중인 프로세스가 입출력 명령을 만나면 입출력 전용 프로세서에게 CPU를 스스로 양도하고 자신은 대기 상태로 전환

④     Wake Up(Waiting -> Ready) : 입출력이 완료되어 대기 중인 프로세스는 준비상태로 전환

***참고 running 되는 프로세스가 바뀔 때 일어나는 것***

문맥교환(Context Switch)

- 현재 CPU를 사용하여 실행되고 있는 프로세스의 상태 정보를 제어권을 인터럽트 서비스 루틴에게 넘기는 작업

- 이전 프로세스의 상태 레지스터 정보를 보관하고 다른 프로세스의 레지스터들을 적재하는 과정

- 빈번한 문맥교환은 시스템의 과부하를 초래

*********************************************************************************************************************

3. 프로세스 제어 블록(PCB, Process Control Block)

 - 운영체제가 프로세스에 대한 중요한 정보를 제공해 주는 저장 장소

 - 프로세스가 생성 시 고유의 PCB가 생성되고, 프로세스 완료 시 PCB 또한 제거

 - PCB에 저장되어 있는 정보

   

① 프로세스의 현재 상태 : 실행, 준비, 대기 등의 상태

② 프로세스 식별자 : 프로세스의 고유 번호

③ CPU 레지스터 정보 : PC, 누산기, 인덱스 레지스터 등 상태코드 정보

④ 계정 정보 : CPU 사용시간, 시간의 범위, 계정번호, 작업번호

⑤ 기억장치 정보 : 기준 레지스터나 페이지 테이블의 값

           기준 레지스터란?

           주 기억장치가 분할된 영역으로 나뉘어 관리될 때, 프로그램이 한 영역에서 다른 영역으로 옮겨지더라도 

  명령의 주소 부분을 바꾸지 않고 정상적으로 수행될 수 있도록 하기 위한 레지스터

           페이지 테이블?

           페이징 기법에서 주소 변환을 위해 페이지가 존재하는 주기억장치의 위치 정보를 가지고 있는 테이블 의미

    -> 나중에 배울거임

⑥ 입출력 상태 정보 : 할당받은 입출력 장치들과 개방된 파일 정보

⑦  포인터 정보 : 부모 및 자식 프로세스에 대한 포인터, 할당된 자원에 대한 포인터

           부모 프로세스/자식 프로세스란?

           하나의 프로세스로 다른 프로세스를 생성할 수 있음. 그래서 생성된 프로세스를 자식

           기존에 있던 프로세스를 부모 프로세스라고 함.

4. 스레드(thread) : 프로세스 내에서 실행되는 흐름의 단위

프로세스에 대해 대략 알았다면, 이제 OS가 프로세스 관리 하는 방법인 scheduling에 대해 설명해보겠다.

Process Scheduling

스케줄링(Scheduling) 

- 여러 프로세스가 실행될 때 필요로 하는 자원을 어떻게 할당해 줄 것인가를 결정하는 작업

- 한 프로세스는 상태 전이가 진행되면서 여러 형태의 스케줄 과정을 거치게 된다.

 

1. 스케줄링의 형태

 1) 장기 스케줄링(Long-term scheduling) :

           - Job scheduler에 의해 담당.

           - 디스크 공간에 제출된 프로세스를 선택하여 메모리로 적재한다.(ready상태로 바꿈)

 2) 중기 스케줄링

           - CPU를 차지하기 위해 경쟁하는 프로세스들의 수를 줄여서 CPU의 과부하를 방지

           - 경쟁 프로세스들을 일시적으로 디스크에 저장한 후 부하가 적어지면 다시 실행하는 스케줄링

3) 단기 스케줄링(Short-term scheduling)

           - 일반적인 스케줄링의 개념, CPU scheduler에서 담당

           - 메모리 안의 준비 상태 프로세스들 중 한 프로세스를 선택하여 CPU 할당(running상태로 바꿈)

2. 스케줄링의 목적

①     공정성 보장 : 모든 프로세스에게 공정하게 자원을 할당한다.

②     처리량 최대화 : 단위 시간당 프로세스 처리량을 최대환한다.

③     반환시간 최소화 : 작업이 제출되어 결과를 반환할 때까지의 시간을 최소화한다.

④     대기시간 최소화 : 작업이 제출되었지만 시작하지 못하고 대기하는 시간을 최소화한다.

⑤     응답시간 최소화 : 작업 요청에 반응하는 시간을 최소화한다.

⑥     오버헤더 최소화 : 자원의 낭비를 예방하여 오버헤더를 줄인다.

⑦     무한대기 방지 : 자원을 오래 기다릴 수록 우선순위를 부여하는 에이징(aging)기법*(아래에서 설명) 사용한다

⑧     균형 있는 자원 사용 : 시스템의 모든 자원을 가능한 한 균형 있게 사용할 수 있어야 한다.

3. 스케줄링 정책

 진행하는 프로세스의 CPU 선점 가능성에 따라 비선점형, 선점형으로 크게 분류된다.

 Short-term scheduling에 대해서 다루는 것이다.

 1) 비선점(non preemptive) 방식

    - 한 프로세스가 CPU를 할당 받으면 다른 프로세스는 이전 프로세스가 CPU를 반환할 때까지 CPU를 점유하지 못하는 방식으로 일괄처리 시스템이서 사용

    - 모든 작업이 공정하게 처리되지만 짧은 작업은 긴 작업이 끝나길 기다릴 수 있다.

    - 응답시간 예측이 용이하다

    - 적용 알고리즘 : FIFO(FCFS), SJF, HRN, 우선순위, 기한부 스케줄링

 2) 선점(preemptive) 방식

    - 한 프로세스가 CPU를 차지하고 있을 때 우선순위가 높은 다른 프로세스가 현재 실행 중인 프로세스를 중지시키고 자신이 CPU를 점유하는 방식으로 시분할 시스템에서 사용된다,

    - 우선순위가 높은 프로세스가 먼저 수행할 때 유리하다

    - 응답 시간 예측이 어렵고 많은 오버헤드를 초래한다.

    - 적용 알고리즘 : RR. SRT, MLQ, MFQ

4. 비선점 스케줄링 알고리즘

 1) FIFO(First-In First-Out) or FCFS (First-Come First-Served) Scheduling

    - 프로세스가 준비 큐에 도착한 순서대로 CPU를 할당하는 가장 간단한 알고리즘

    - 공평성은 좋지만 긴 작업이 짧은 작업을 기다리게 할 수 있다.

           Convoy effect : 소요시간이 긴 프로세스가 먼저 도달하여 시간을 잡아먹고 있는 부정적인 현상

    - 일괄처리 작업에 적합하고, 대화식 시스템에는 부적합하다.

    - 예시

       

  2) SJF(Shortest-Job-First) Scheduling

    - 준비 큐 내의 프로세스 중 실행시간이 가장 짧은 프로세스에게 CPU를 할당

    - 평균 대기시간이 최소인 최적의 알고리즘

    - 실행시간이 긴 작업인 경우 무한연기(starvation)가 발생될 수 있다.

SJF 기법에서 제출시간이 없는 경우

4개의 프로세스가 동시에 제출된 경우로, 제출시간이 모두 0이다.

제출시간이 있는 경우

        

 

 3) HRN(Highest Response ratio Next) Scheduling

    - 긴 작업과 짧은 작업 간의 지나친 불평등을 어느 정도 보완한 기법

    - 우선 순위 식에 의해 우선순위 값을 계산한 후, 값이 높은 프로세스를 먼저 스케쥴

우선순위식

    - 짧은 작업이나 대기시간이 큰 작업은 우선순위가 높아진다.

 4) 우선순위(Priority) Scheduling

    - 프로세스마다 우선순위를 부여하여 우선순위가 높은 순서대로 CPU를 할당

    - 우선순위가 낮은 프로세스는 무한 연기되는 기아상태(Starvation) 발생

    - 무한 연기의 해결책으로 에이징(aging)기법 사용

           에이징(Aging) : 프로세스의 우선순위가 낮아 점유할 자원을 양보하거나 대기시간이 증가할수록 프로세스의 우선순위를 한 단계씩 높여주는 기법, 기아현상을 방지할 수 있다.

    - 프로세스 별 우선순위의 비교

①     입출력 프로세스는 연산 프로세스보다 우선순위가 높다

②     짧은 작업 프로세스는 긴 작업 프로세스보다 우선순위가 높다

③     시스템 작업은 대화형 작업보다, 대화형 작업은 일괄처리 작업보다 우선순위가 높다.

    - 예시

 5) 기한부(deadline) Scheduling

    - 프로세스들을 특정시간이나 기한 내에 완료하도록 스케줄링

    - 만약 데드라인을 놓치면 프로세스의 가치는 낮아짐

    - 특정 시간 내에 완료하기 위해 요구되는 자원의 집중은 많은 오버헤드 발생

    - 오버헤드를 줄이기 위해 정확한 자 요구량을 미리 세시하는 것이 필요

5. 선점 알고리즘

 1) RR(Round Robin) Scheduling

    - 시분할 시스템에서 적용하는 스케줄링 방식

    - 프로세스는 FIFO 알고리즘에 의해 순서대로 CPU를 할당받고, CPU의 시간할당량(time slice)동안만 실행

    - 할당시간내에 처리가 안되면, 다른 프로세스에게 CPU를 반납하고 준비큐의 가장 뒤로 보내져 다음 순서를 기다린다.

    - 시간 할당량이 너무 크면 FIFO방식과 동일해지고, 시간할당량이 너무 작으면 문맥교환이 자주 발생하여 오버헤드가 크다.

 

    - 예시) 시간할당량이 20일 때

 

 2) SRT(Short Remaining Time) Scheduling

    - 실행시간 추정치가 가장 작은 프로세스에게 먼저 CPU를 할당하는 기법

    - SJF기법에 선점방식을 도입한 변형된 방법, 프로세스 처리 중 선점을 허용한다.

    - 예시

 

 3) MLQ(Multi level queue) Scheduling

    - 프로세스를 작업 유형에 따라 여러 그룹으로 분류하고 그룹별로 준비 큐를 준비하여 프로세스 진입 시 유형이 따라 어떤 한 큐에 배당한다,

    - 각 큐는 자신만의 독자적인 스케줄링을 수행할 수 있어서 그룹별로 서로 다른 스케줄링이 가능하다.

    - 특정 큐에 진입한 프로세스는 다른 준비 큐로의 이동을 할 수 없다.

    

 4) MFQ(Multi level Feedback Queue) Scheduling

    - 적응 기법(adaptive Mechanism)의 개념을 적용하여 준비큐간 이동을 가능하게 한 기법이다.

    - 준비 큐를 상위 큐에서 하위 큐로 여러 개 준비하고 프로세스 진입은 상위 큐로 하게 한다.

    - 각 큐마다 CPU 시간 할당량(time slice)를 다르게 부여한다.

      상위 큐는 작게, 하위 큐로 갈수록 크게

    - 상위 큐로 진입한 프로세스가 실행 완료 안되면 하위 큐로 이동하게 이동하면서 실행하게 되고, 맨 아래 큐에서도 실행이 안되면 RR스케줄링을 하위 큐에서 반복하는 방식이다.

      (맨 아래를 제외한, 위의 큐들은 FIFO 방식)

    - CPU를 적게 사용하는 짧은 작업 및 입출력 위주의 프로세스에 우선권을 준다.

      -> 우선순위가 낮은 프로세스는 밀리는 starvation 문제 발생 -> aging 방법 도입

++ 동기화랑, 교착상태는 다음 포스팅에서 다루겠음