PintOS priority donation MLFQS 4BSD nice time slice I/O bound preemption jungle 운영체제

Pintos 1주차 컴퓨터 시스템 용어 정리2

정글일지 27

컴퓨터 시스템 관련 용어 정리

Priority Donation(Priority inheritance)

priority inheritance는 무한한(unbounded) 우선순위 도치(inversion)을 제거하기 위한 방법이다. 이 프로그래밍 방식을 쓰는 프로세스 스케쥴링 알고리즘은 A가 resourece lock이 되어있는 어떤 자원을 기다리는 다른 프로세스들의 우선순위 중 최댓값으로 A의 우선순위를 증가시킨다.

priority inheritance protocol의 기본 아이디어는 한 작업이 더 높은 우선순위의 작업에게 가로막혔을 때, 그 작업이 원래의 우선순위를 무시하고 상승한 우선순위 수준에서 [^critical section](임계 영역)을 수행하는 것이다. critical section(임계 영역)을 수행하고 lock을 release하고 나면, 포로세스는 원래의 우선순위 수준으로 돌아간다.

Multi-Level Feedback Queue(+ scheduler)(MLFQS)

스케쥴링 알고리즘 중 하나다. 스케쥴링 알고리즘은 CPU가 바쁘도록 몇 프로세스들을 항상 작동시키기 위해 고안되었다. Multilevel feedback queue는 여기서 더 확장되었다.

  1. 각 프로세스들의 요구(프로세서에게)를 바탕으로하여 프로세스들을 다수의 ready queues로 분리한다.
  2. short CPU bursts(CPU 과활성화?)로 프로세스들을 처리(원문 : Give preference to processes with short CPU bursts)
  3. high I/O bursts(높은 입출력장치의 작동?)로 프로세스들을 처리(I/O bound processes는 다른 프로세스들에게 CPU 시간을 주기 위해 대기 리스트에서 잘 것이다.)(원문 : Give preference to precesses with high I/O bursts. (I/O bound processes will sleep in the wait queue to give other precesses CPU time.))

multilevel queue 알고리즘이 초기 큐 배열에 따라 영구적으로 프로세스를 유지하는 반면, multilevel feedback queue는 큐들 사이에서 프로세스를 전환(shit)한다. 이 전환은 이전의 time-slice의 CPU bursts과 유관하다.

  • 만약 한 프로세스가 너무 많은 CPU 시간을 사용하면, 낮은 우선순위 큐로 옮겨진다.
  • 만약 한 프로세스가 I/O-bound거나 상호작용하는 process라면, 높은 우선순위 큐로 옮겨진다.
  • 만약 한 프로세스가 너무 오래 낮은 우선순위 큐에서 대기하면, 높은 우선순위 큐로 aged된다.

알고리즘

다수의 FIFO(First in First Out, 선입선출) 큐들이 쓰이고 오퍼레이션은 다음과 같다.

  1. 새로운 프로세스가 가장 높은 큐에 tail(end)에 삽입된다.
  2. 몇 stage에서 프로세스가 큐의 head에 도달하고 CPU에 배정된다.
  3. 주어진 큐의 time-slice 내에 프로세스가 완성된다면, 프로세스는 시스템을 떠난다.
  4. 만약 프로세스가 자발적으로 CPU의 제어권을 포기한다면, 프로세스는 queuing nwetwork를 떠난다. 그리고 프로세스가 다시 준비 되었을 때 이전에 포기했던(떠났던) 똑같은 큐의 tail로 삽입된다.
  5. 만약 프로세스가 모든 quantum time을 사용한다면, 프로세스는 pre-empted(선점적인?)하고, 다음으로 낮은 레벨의 큐의 tail에 삽입된다. 이 다음으로 낮은 레벨의 큐는 이전의 더 높은 레벨의 큐보다 더 많은 quantum time을 가진다.
  6. 이 일련의 계획은 프로세스가 완성되거나 기초 레벨 큐에 도달할때 까지 계속된다.
    • 기초 레벨 큐에서 프로세스는 완성하여 시스템을 떠나기 전 까지 round-robin을 순환한다. 또한, 기초 레벨 큐에서 프로세스들은 first come first served 원리로 스케쥴링 될 수도 있다.
    • 부가적으로, 프로세스가 I/O에게 막힌다면, 프로세스는 한 레벨(level)을 ‘승진’하고, 다음으로 높은 큐의 end에 위치하게 된다. 이것은 I/O bound porcesses 가 스케쥴러에게 간섭(favored)되고 프로세스들이 기초 레벨 큐에서 ‘탈출’할 수 있도록 해준다.

스케쥴링을 위해, 스케쥴러는 항상 가장 높은 레벨의 큐의 head에서 프로세스를 고르면서 시작한다. 가장 높은 레벨의 큐가 텅텅 비었을때만 스케쥴러가 다음으로 낮은 레벨의 큐에서 프로세스를 받을 것이다. 이와 같은 규칙은 차후로 낮은 레벨의 큐에서 고를 때에도 적용된다. 반면에, 프로세스가 더 높은 레벨의 큐 중 한 곳에서 온다면, 그것은 더낮은 레벨의 큐에 있는 프로세스를 preempt(선점)할 것이다.

4BSD

4BSD는 1983년에 출시된 BSD(Berkeley Software Distribution) Unix 운영체제의 한 버전이다. 이것은 FFS(Berkeley Fast File System), 가상 메모리 향상 그리고 네트워킹 스택에 의미있는 강화를 포함하는 여러 새 기능과 진보가 이루어졌다.

4BSD는 또한 후에 MLFQS 알고리즘의 기초로 사용되는 동적 우선순위 스케쥴링 알고리즘(dynamic priority scheduling algorithm)의 개념을 도입했다. 4BSD의 동적 우선순위 스케쥴링 알고리즘은 CPU-bound 프로세스들이 CPU를 독점하는 것도 막으면서 상호작용 하는 프로세스들에 대한 더 나은 반응성을 제공하는 것을 목표로, 우선순위 큐를 사용하여 프로세스들을 스케쥴링한다.

MLFQS는 CPU 사용 기록, 상호작용, 그리고 다른 기준을 바탕으로 복수의 우선순위 큐에 프로세스들을 나누고, 그리고 각각의 큐에 다른 스케쥴링 알고리즘을 사용하는 방법을 이용하여 이 개념위에 지어졌다. MLFQS는 또한 time slicing, preemption, 그리고 공평한 CPU의 분배와 starvation(결핍) 방지 확보같은 기능들을 갖고 있다.

전체적으로, 4BSD는 Unix 운영 체제의 개발에 중요하고 획기적인 마일스톤이였고 BSD의 차후 버전과 다른 Unix 기반 시스템의 개발에 지대한 영향력을 끼쳤다. 이 동적 우선순위 스케쥴링 알고리즘은 효율적이고 공평한 시스템 자원 스케쥴링을 제공하는 현대의 운영체제에도 계속해서 사용되는 MLFQS 알고리즘을 위한 기반을 닦았다.

nice</span>

“nice” value는 CPU 스케쥴링 알고리즘에서 프로세스의 우선순위를 조절하는 Unix와 유사한 운영체제에서 parameter이다. 더 높은 nice value는 더 낮은 우선순위를 의미하는 반면, 더 낮은 nice value는 더 높은 우선순위를 의미한다. nice value는 “nice”나 “renice”같은 시스템 유틸리티를 사용할 때도 적용될 수 있다.

MLFQS에서, 프로세스의 우선순위 레벨은 그것의 최근 CPU 사용 내역을 기반으로 동적으로 조정될 수 있다. 이것은 많은 CPU 시간을 소모한 프로세스가 더 낮은 우선순위의 큐로 이동될 수 있고, idle(이상적인?) 프로세스는 더 높은 우선순위의 큐로 옮겨질 수 있다는 것을 의미한다. “nice” value도 또한 MLFQS에서 프로세스의 우선순위 레벨을 조정하는데 사용될 수 있다.

전반적으로, MLFQS와 “nice”value는 둘다 CPU 스케쥴링 알고리즘에서 프로세스들의 우선순위와 연관되어 있다. MLFQS는 다른 우선순위를 가진 여러 큐를 사용하는 반면, “nice” value는 개별 프로세스의 우선순위 레벨을 조정한다. 모두 합쳐, 이 메커니즘들은 CPU의 효율적 사용과 모든 프로세스들에게 적용되는 공평함을 확보하는데 도움이 된다.

time-slice

preemptive 멀티태스킹 시스템에서 프로세스가 실행되도록 허용된 시간을 보통 time slice나 quantum라고 한다. 스케쥴러는 다음 실행할 프로세스를 선택하기 위해 매 time slice 당 한번만 실행된다. 각 time slice의 길이는 시스템 성능과 프로세스 반응성(responsiveness)간에 균형을 조정하는데 핵심적이다. 만약 time slice가 너무 짧으면 스케쥴러는 너무 많은처리 시간(processing time)을 소모하게 되지만, time slice가 너무 길면 프로세스들은 반응하고 투입(input)되는데 더 오래 걸리게 된다.

I/O-bound

I/O bound는 연산을 완료하는데 걸리는 시간이 결정되는 조건을 말하는데, 주로 입출력 과정이 완성되기를 기다리느라 소비되는 시간에 의해서 이루어진다. 이것은 보통 CPU bound인 업무와 반대다. 이 상황은 데이터가 요청되는 속도가 소비되는 속도보다 느릴때, 다시 말해 데이터를 처리하는 것보다 요청하는데 더 많은 시간이 소비될 때 발생한다.

I/O bound as an inherent problem in computing

I/O bound state(상태)는 거의 컴퓨터의 시작때부터 인지된 문제다. 많은 컴퓨터 장치에 사용되는 [^Von Neumann architecture]는 프로그램의 지시를 저장하는 것과 마찬가지로 실제 데이터도 주로 메인 메모리에서 회수하고 이걸 사용하는 것을 작업을 위해 더욱 접근하기 쉬운 데이터로 만드는, 논리적으로 분리된 CPU를 실행하는 것과 같은 다양하고 가능한 해결책을 갖고 있다. 프로세스가 종결될 때 그것은 원래 저장소에 결과를 다시 적는다(보통 메인 메모리에).

데이터가 전송 속도가 제한된 bus를 따라 CPU와 메모리 사이를 움직여야만 하기 때문에, [^Von Neumann bottleneck] 이라고 알려진 조건이 존재한다. 간단히 말해, 이것은 CPU와 메모리간의 데이터 bandwidth(어떤 통로에서의 최대 데이터 전송 속도)가 전반적인 연산 속도를 제한하는 경향이 있음을 의미한다. 컴퓨터를 구성하는 실제 기술의 관점에서, Von neumann bottleneck은 CPU가 계산을 더 빠르게 수행하도록 만드는 것이 CPU에게 데이터를 가능한한 필요한 속도로 공급하는 것이 더 어렵다는 것을 내포한다.

최근 역사에서, Von Neumann bottleneck은 좀더 명백해졌다. 현대 컴퓨터의 고안 철학은 물리적으로 분리된 CPU와 메인 메모리를 바탕으로 한다. 데이터는 그들 내부 위치에서 아주 작은 거리를 돌아다니기 때문에 CPU를 높은 데이터 전송 속도에서 실행하는 것은 가능하다. 그러나 CPU와 메인 메모리의 물리적인 분리는 센티미터 나 그 이상 되는 상대적으로 더 긴 거리를 옮길 수 있는 data bus를 필요로 한다. 시스템의 이 부분을, CPU를 따라잡을 만큼 충분히 빠른 속도를 유지하며 작동하도록 만드는 것에 관한 문제는 더 거대한 도전이 되가고 있다.

Preemption

실행중인 task를 나중에 재개하려는 의도로 잠깐 interrupt하는 행동이다. 이 interrupt는 task의 도움 없이 외부 scheduler에 의해 발생한다. 이 preemptive한 scheduler는 대개 interruption과 재개(resuming)이 매우 안전한 행동으로 고려되는, 가장 privileged protection ring(특별히 보호받는 고리?)에서 작동한다. 프로세서의 최근 수행 task의 변화는 context switching으로도 알려졌다.

우리가 지금 구현하는 priority donation도 이 개념이다.

Preemptive multitasking

preemptive multitasking이라는 용어는 task의 preemption을 허용하는 멀티태스킹 운영체제를 프로세스들과 tasks들이 시스템 자원이 필요하지 않을 때 yield하도록 명시적으로 프로그래밍된 협동 멀티태스킹 시스템(cooperative multitasking system)과 구별하기 위해 사용된다.

간단한 말로, preemptive multitasking은 최근에 수행된 프로세스를 지연시키고 다음 수행되어야할 프로세스를 결정할 스케쥴러를 호출하는 interrupt 메커니즘을 사용하기도 한다. 그러므로, 모든 프로세스들은 정해진 시간내에서 어느정도의 CPU 시간을 받을 것이다.

preemptive multitasking에서, operating system kernel은 또한 스케쥴링 규칙의 우선순위 제한을 만족시키기 위한 context switch를 개시할 수 있어서, 활성화 task를 선점할 수 있다. 일반적으로, preemption은 “미리 사전에 점령”을 의미한다. 높은 우선순위의 task가 최근에 실행된 task를 포착할 때를 preemptive scheduling이라고도 한다.

Preemptive and Non-Preemptive Scheduling

CPU Scheduler

CPU 가 idle이 될때 마다, 운영체제는 Readty queue에서 실행될 프로세스들 중 하나를 선택해야만 한다. 선택 과정은 CPU scheduler(short-term scheduler)가 수행한다. scheduler는 메모리에 있는 실행될 준비가 된 단일 프로세스를 선택하고 그 프로세스에게 CPU를 할당한다.

Dispatcher

dispatcher는 CPU의 제어권을 스케쥴러에게 선택된 프로세스에게 주는 모듈이다. dispatcher가 한 프로세스를 멈추고 다른 것을 작동시키는 데 걸리는 시간이 dispatch latency 라고 한다.

CPU 스케쥴링이 발생할 수 있는 4가지 상황

  1. 프로세스가 작동 상태(running state)에서 대기 상태(wating state)로 전환 되었을 때
  2. 프로세스가 작동 상태(running state)에서 준비 상태(ready state)로 전환 되었을 때(예를 들어, interrupt 발생)
  3. 프로세스가 대기 상태(wating state)에서 준비 상태(ready state)로 전환 되었을 때(예를 들어, I/O의 완결(completion))
  4. 프로세스가 종결(terminate)되었을 때

1,4번 상황에서는 선택권이 없다. 새로운 프로세스가 실행되도록 선택해야 한다(준비 상태인 프로세스가 있다면).

이 상황을 nonpreemptive or cooperative 라고 한다.

하지만 2,3번 상황에서는 선택을 해야한다. 이 상황을 preemptive라고 한다.

CATALOG
    log