운영 체제 소개

헤이 하브르! 제 생각에는 흥미로운 문헌 인 OSTEP에 대한 일련의 기사 번역을 여러분의 관심을 끌고 싶습니다. 이 자료는 유닉스 계열 운영 체제의 작업, 즉 프로세스, 다양한 스케줄러, 메모리 및 최신 OS를 구성하는 기타 유사한 구성 요소 작업에 대해 매우 깊이 논의합니다. 여기에서 모든 자료의 원본을 볼 수 있습니다. 여기에. 비전문적으로(상당히 자유롭게) 번역했지만 일반적인 의미를 유지했으면 합니다.

이 주제에 대한 연구실 작업은 여기에서 찾을 수 있습니다.

기타 부품 :

에서 내 채널을 확인할 수도 있습니다. 이야기 =)

계획: 다단계 피드백 대기열

이번 강의에서 우리는 가장 유명한 접근법 중 하나를 개발하는 데 따른 문제점에 대해 이야기할 것입니다.
기획이라고 불리는 다단계 피드백 대기열 (MLFQ). MLFQ 스케줄러는 1962년 Fernando J. Corbató에 의해 다음 시스템에서 처음 설명되었습니다.
호환 가능한 시간 공유 시스템(CTSS). 이 작품들(이후 작품 포함)
Multics)는 이후 Turing Award 후보로 지명되었습니다. 기획자는 이랬다
이후 개선되어 이미 볼 수 있는 외관을 획득했습니다.
일부 현대 시스템.

MLFQ 알고리즘은 두 가지 근본적인 중첩 문제를 해결하려고 합니다.
첫째로, 처리 시간을 최적화하려고 하는데, 이는 이전 강의에서 논의한 것처럼 대기열의 시작 부분에서 가장 많이 시작하는 방법으로 최적화됩니다.
짧은 작업. 그러나 OS는 이 프로세스나 저 프로세스가 얼마나 오랫동안 실행될지 알지 못합니다.
SJF, STCF 알고리즘의 동작에 필요한 지식. 둘째로, MLFQ는 다음을 시도합니다.
시스템이 사용자에게 반응하도록 만듭니다(예: 앉아 있고 앉아 있는 사람들을 위해).
작업이 완료되기를 기다리는 동안 화면을 응시하여 시간을 최소화합니다.
응답. 불행하게도 RR과 같은 알고리즘은 응답 시간을 단축하지만
처리 시간 측정항목에 나쁜 영향을 미칩니다. 그러므로 우리의 문제는: 어떻게 디자인할 것인가?
아무것도 몰라도 우리의 요구 사항을 충족하는 스케줄러
일반적으로 프로세스의 성격은 무엇입니까? 스케줄러가 작업의 특성을 어떻게 학습할 수 있는지,
출시되어 더 나은 계획 결정을 내릴 수 있습니까?

문제의 본질: 완벽한 지식 없이 작업 설정을 어떻게 계획할 수 있습니까?
응답 시간을 동시에 최소화하는 스케줄러를 설계하는 방법
대화형 작업을 수행하는 동시에 알지 못하는 사이에 처리 시간을 최소화합니다.
작업 실행 시간을 알고 있습니까?

참고: 이전 사건으로부터 배우기

MLFQ 대기열은 훈련된 시스템의 훌륭한 예입니다.
미래를 예측하기 위한 과거의 사건. 이러한 접근 방식은 종종
OS(및 여러 분야를 포함한 컴퓨터 과학의 다른 여러 분야)에서 발견됨
하드웨어 예측 및 캐싱 알고리즘). 비슷한 하이킹
작업에 행동 단계가 있어 예측이 가능할 때 트리거됩니다.
그러나 이 기술은 예측이 매우 쉽기 때문에 주의해야 합니다.
잘못된 것으로 판명되어 시스템이 더 나쁜 결정을 내리게 만들 수도 있습니다.
전혀 지식이 없을 것입니다.

MLFQ: 기본 규칙

MLFQ 알고리즘의 기본 규칙을 고려하십시오. 그리고 비록 이 알고리즘의 구현이
여러 가지가 있지만 기본 접근 방식은 비슷합니다.
우리가 고려할 구현에서 MLFQ는 여러 가지를 갖게 됩니다.
별도의 대기열은 각각 다른 우선순위를 갖습니다. 언제든지,
실행 준비가 된 작업은 동일한 대기열에 있습니다. MLFQ는 우선순위를 사용합니다.
실행을 위해 실행할 작업을 결정합니다. 즉, 더 높은 과제
우선 순위(가장 높은 우선 순위를 가진 대기열의 작업)가 처음으로 시작됩니다.
대기줄.
물론 특정 대기열에는 둘 이상의 작업이 있을 수 있으므로
따라서 그들은 동일한 우선순위를 갖게 됩니다. 이 경우 메커니즘이 사용됩니다.
RR을 사용하여 이러한 작업 중 실행을 예약합니다.
따라서 우리는 MLFQ에 대한 두 가지 기본 규칙에 도달했습니다.

규칙1: 우선순위(A) > 우선순위(B)이면 작업 A가 실행됩니다(B는 실행되지 않음).
규칙2: 우선순위(A) = 우선순위(B)인 경우 A&B는 RR을 사용하여 시작됩니다.

위 내용을 바탕으로 MLFQ 기획의 핵심요소는
우선 순위입니다. 각각에 고정된 우선순위를 부여하는 대신
작업에서 MLFQ는 관찰된 동작에 따라 우선순위를 변경합니다.
예를 들어 키보드 입력을 기다리는 동안 작업이 CPU에서 지속적으로 종료되는 경우
MLFQ는 프로세스 우선순위를 높게 유지합니다.
대화형 프로세스가 작동해야 합니다. 반대로 작업이 지속적으로 이루어지면
장기간 CPU를 많이 사용하므로 MLFQ가 이를 다운그레이드합니다.
우선 순위. 따라서 MLFQ는 프로세스가 실행되는 동안 프로세스의 동작을 연구합니다.
행동을 사용합니다.
어느 시점에서 대기열이 어떤 모습일지 예를 그려 보겠습니다.
시간이 지나면 다음과 같은 결과가 나타납니다.

이 방식에서는 2개의 프로세스 A와 B가 가장 높은 우선순위 대기열에 있습니다. 프로세스
C는 중간 어딘가에 있고 프로세스 D는 대기열의 맨 끝에 있습니다. 위의 내용에 따르면
MLFQ 알고리즘에 대한 설명에 따르면 스케줄러는 가장 높은 작업만 실행합니다.
RR에 따라 우선순위가 부여되며 작업 C, D는 작업에서 제외됩니다.
당연히 정적 스냅샷은 MLFQ 작동 방식에 대한 완전한 그림을 제공하지 않습니다.
시간이 지남에 따라 그림이 어떻게 변하는지 정확하게 이해하는 것이 중요합니다.

시도 1: 우선순위를 변경하는 방법

이 시점에서는 MLFQ가 우선순위 수준을 어떻게 변경하는지 결정해야 합니다.
수명 주기 동안 작업(및 대기열에서 작업의 위치)입니다. 을 위한
이 중 작업 흐름을 염두에 두어야 합니다.
런타임이 짧은 대화형 작업(따라서 자주 릴리스됨)
CPU) 및 작업 시간 내내 CPU를 사용하는 몇 가지 긴 작업,
그러한 작업에 대한 응답 시간은 중요하지 않습니다. 그래서 당신은 첫 번째 시도를 할 수 있습니다
다음 규칙을 사용하여 MLFQ 알고리즘을 구현합니다.

규칙3: 작업이 시스템에 들어오면 가장 높은 대기열에 배치됩니다.
우선 사항.
규칙4a: 작업이 할당된 전체 시간 창을 사용하는 경우
우선순위가 낮아집니다.
규칙4b: 태스크가 해당 기간이 만료되기 전에 CPU를 해제하면
동일한 우선순위로 유지됩니다.

예시 1: 단일 장기 실행 작업

이 예에서 볼 수 있듯이 입학 시 과제는 가장 높은 수준으로 설정됩니다.
우선 사항. 10ms의 시간이 지나면 프로세스의 우선순위가 낮아집니다.
스케줄러. 다음 기간이 지나면 작업은 최종적으로 다음으로 강등됩니다.
시스템에서 가장 낮은 우선순위로 남아 있습니다.

예시 2: 짧은 작업 전달

이제 MLFQ가 SJF에 접근하려고 시도하는 방법의 예를 살펴보겠습니다. 그 안에
예를 들어, 두 가지 작업: 지속적으로 장기 실행되는 작업인 A
짧은 대화형 작업인 CPU와 B를 점유합니다. 가정하다
작업 B가 도착했을 때 A는 이미 한동안 실행 중이었습니다.

이 그래프는 시나리오의 결과를 보여줍니다. 태스크 A는 다른 태스크와 마찬가지로
CPU를 사용하는 것은 맨 아래에 있었습니다. 작업 B는 T=100 시간에 도착하고
가장 높은 우선순위 대기열에 배치됩니다. 러닝타임이 짧기 때문에
마지막 대기열에 도달하기 전에 완료됩니다.

이 예에서 알고리즘의 주요 목표를 이해해야 합니다.
긴 작업이나 짧은 작업을 알고 있으면 먼저 그 작업이
짧으며 가장 높은 우선순위를 부여합니다. 정말 짧은 작업이라면
빠르게 실행됩니다. 그렇지 않으면 긴 작업인 경우 천천히 이동합니다.
우선 순위를 낮추고 곧 그녀가 실제로는 그렇지 않은 긴 작업임을 증명할 것입니다.
응답이 필요합니다.

예 3: I/O는 어떻습니까?

이제 I/O 예제를 살펴보겠습니다. 규칙 4b에 명시된 바와 같이,
프로세스가 프로세서 시간을 모두 사용하지 않고 프로세서를 해제하는 경우
그러면 동일한 우선순위 수준이 유지됩니다. 이 규칙의 의도는 매우 간단합니다.
- 대화형 작업이 많은 I/O를 수행하는 경우(예: 대기 중)
사용자의 키 입력이나 마우스에서 이러한 작업을 수행하면 프로세서가 해제됩니다.
할당된 창 앞에 우리는 이러한 우선순위 작업을 생략하고 싶지 않으며,
따라서 동일한 수준으로 유지됩니다.

이 예에서는 알고리즘이 이러한 프로세스(실행 전 1ms 동안만 CPU가 필요한 대화형 작업 B)에서 어떻게 작동하는지 보여줍니다.
I/O 프로세스와 항상 CPU를 사용하는 긴 작업 A.
MLFQ는 프로세스 B를 계속해서 가장 높은 우선순위로 유지합니다.
CPU를 풀어주세요. B가 대화형 작업인 경우 이 경우 알고리즘은 다음과 같습니다.
그 목적은 대화형 작업을 신속하게 시작하는 것입니다.

현재 MLFQ 알고리즘의 문제점

이전 예에서는 MLFQ의 기본 버전을 구축했습니다. 그리고 그는 것 같습니다
작업을 훌륭하고 공정하게 수행하여 CPU 시간을 공정하게 분배합니다.
긴 작업 및 짧은 작업 또는 자주 액세스되는 작업 허용
I/O로 처리하여 빠르게 처리합니다. 불행하게도 이 접근 방식에는 여러 가지가 포함되어 있습니다.
심각한 문제.
첫째로, 배고픔의 문제: 시스템에 상호작용이 많을 경우
작업은 모든 CPU 시간을 소비하므로 단 한 번의 긴 시간도 소비하지 않습니다.
작업이 실행될 기회를 얻지 못합니다(굶어 죽습니다).

둘째로, 똑똑한 사용자는 자신의 프로그램을 작성할 수 있습니다.
스케줄러를 속이세요. 속임수는 강제로 무언가를 하는 것입니다.
프로세스에 더 많은 CPU 시간을 제공하는 스케줄러입니다. 알고리즘은
위에서 설명한 공격은 이러한 공격에 매우 취약합니다.
이상, I/O 작업을 수행해야 합니다(어떤 파일에 관계없이 일부에 대해).
따라서 CPU를 확보합니다. 그러한 행동은 당신이 같은 상태를 유지하도록 허용합니다
대기열 자체가 다시 CPU 시간의 더 큰 비율을 얻습니다. 완료되면
이는 정확합니다(예: CPU를 해제하기 전에 창 시간의 99%를 실행).
그러한 작업은 단순히 프로세서를 독점할 수 있습니다.

마지막으로 프로그램은 시간이 지남에 따라 동작을 변경할 수 있습니다. 그 작업
CPU를 사용하는 것은 대화형이 될 수 있습니다. 우리의 예에서는 비슷한
작업은 다른 작업처럼 스케줄러로부터 적절한 처리를 받지 못합니다.
(원본) 대화형 작업.

청중을 위한 질문: 현대 세계에서는 스케줄러에 대해 어떤 공격이 수행될 수 있습니까?

시도 2: 우선순위 높이기

규칙을 변경하여 문제를 피할 수 있는지 살펴보겠습니다.
굶주림. 관련성을 보장하기 위해 우리가 할 수 있는 일은 무엇입니까?
CPU 작업에는 시간이 걸립니다(길지 않더라도).
문제에 대한 간단한 해결책으로 주기적으로 제안할 수 있습니다.
시스템에서 이러한 모든 작업의 우선순위를 높입니다. 여러 가지 방법이 있습니다
이를 달성하기 위해 예를 들어 간단한 것을 구현해 보겠습니다.
모든 작업을 동시에 가장 높은 우선순위로 지정하므로 새로운 규칙이 적용됩니다.

Rule5: 일정 기간 S 이후 시스템 내 모든 작업을 최상위 대기열로 이동합니다.

우리의 새로운 규칙은 두 가지 문제를 동시에 해결합니다. 첫째, 프로세스
기아 방지 보장: 가장 높은 큐에 있는 작업은 공유됩니다.
RR 알고리즘에 따라 프로세서 시간을 수신하므로 모든 프로세스는
프로세서 시간. 둘째, 이전에 사용했던 일부 프로세스가 있는 경우
프로세서만 대화형이 되며 가장 높은 값을 가진 대기열에 남아 있게 됩니다.
한 번 가장 높은 우선순위로 부스트된 후 우선순위를 지정합니다.
예를 고려하십시오. 이 시나리오에서는 다음을 사용하는 단일 프로세스를 고려하십시오.

CPU와 두 개의 대화형 짧은 프로세스. 그림의 왼쪽 그림은 우선순위 승격이 없는 동작을 보여줍니다. 따라서 두 개의 대화형 작업이 시스템에 도착한 후 장기 실행 작업이 중단되기 시작합니다. 오른쪽 그림에서는 50ms마다 우선순위 증가가 이루어지므로 모든 프로세스는 CPU 시간을 보장받으며 주기적으로 시작됩니다. 이 경우 50ms를 예로 들었지만 실제로는 이 숫자가 약간 더 높습니다.
분명히, 주기적인 증가 시간 S를 추가하면
논리적 질문: 어떤 값을 설정해야 합니까? 그럴만한 가치가 있는 것 중 하나
시스템 엔지니어 John Ousterhout는 시스템에서 비슷한 양을 voo-doo라고 언급했습니다.
어떤 식으로든 올바른 작업을 수행하려면 흑마법이 필요했기 때문에 상수입니다.
노출. 그리고 안타깝게도 S에는 그런 맛이 있습니다. 값도 설정하면
크고 긴 작업은 굶어 죽게 됩니다. 그리고 너무 낮게 설정하면
대화형 작업은 적절한 CPU 시간을 받지 못합니다.

시도 3: 더 나은 회계

이제 해결해야 할 문제가 하나 더 있습니다.
스케줄러를 속이는 것을 허용하시겠습니까? 이 가능성의 원인은 다음과 같습니다.
프로세서를 해제하여 작업의 우선순위를 유지하도록 허용하는 규칙 4a, 4b
할당된 시간이 만료되기 전에. 그것을 처리하는 방법?
이 경우 솔루션은 각 CPU 시간을 더 잘 계산하는 것으로 간주될 수 있습니다.
MLFQ 수준. 프로그램이 사용한 시간을 잊어버리는 대신
할당된 기간 동안 프로세서를 사용하는 경우 이를 고려하고 저장해야 합니다. 후에
프로세스가 할당된 시간을 모두 사용했습니다. 다음 프로세스로 강등되어야 합니다.
우선순위 수준. 이제 프로세스가 시간을 어떻게 사용하는지는 중요하지 않습니다.
프로세서에서 또는 일련의 호출로 지속적으로 컴퓨팅합니다. 따라서,
규칙 4는 다음 형식으로 다시 작성되어야 합니다.

Rule4: 작업이 현재 대기열에서 할당된 시간을 모두 사용한 후에(CPU를 해제한 횟수에 관계없이) 해당 작업의 우선 순위는 감소합니다(대기열 아래로 이동합니다).

예를 살펴보겠습니다:
»

그림은 다음과 같이 스케줄러를 속이려고 하면 어떤 일이 발생하는지 보여줍니다.
이전 규칙 4a, 4b를 사용했다면 왼쪽의 결과를 얻게 됩니다. 새로운
규칙은 결과가 오른쪽에 있다는 것입니다. 보호 이전에는 모든 프로세스가 완료되기 전에 I/O를 호출할 수 있으며
따라서 보호를 활성화한 후 동작에 관계없이 CPU를 지배합니다.
I/O, 그는 여전히 대기열에 남아 있으므로 부정직하게 할 수 없습니다.
CPU 자원을 차지합니다.

MLFQ 및 기타 문제 개선

위의 개선 사항으로 인해 새로운 문제가 발생합니다.
질문 - 그러한 스케줄러를 매개변수화하는 방법은 무엇입니까? 저것들. 얼마가되어야합니까?
대기열? 대기열 내의 프로그램 창 크기는 얼마입니까? 어떻게
기아와 기아를 피하기 위해 프로그램이 우선순위가 되어야 하는 경우가 많습니다.
프로그램 동작의 변화를 고려합니까? 이 질문에 대한 간단한 대답은 없습니다.
응답 및 로드 및 후속 구성에 대한 실험만 수행
플래너는 어느 정도 만족스러운 균형을 이룰 수 있습니다.

예를 들어 대부분의 MLFQ 구현에서는 서로 다른 할당을 허용합니다.
다양한 대기열의 시간 슬롯. 우선순위가 높은 큐는 일반적으로
짧은 간격. 이러한 대기열은 대화형 작업으로 구성됩니다.
그 사이를 전환하는 것은 매우 민감하며 10 이하가 소요됩니다
ms. 대조적으로, 낮은 우선순위 대기열은 다음을 사용하는 장기 실행 작업으로 구성됩니다.
CPU. 그리고 이 경우 긴 시간 간격(100ms)이 매우 잘 맞습니다.

이 예에는 높은 우선순위 대기열 2에서 작동한 20개의 작업이 있습니다.
ms, 10ms 창으로 나뉩니다. 중간 대기열(40ms 창) 및 낮은 우선순위에서 20ms
작업이 작업을 완료하는 대기열 시간 창이 40ms가 되었습니다.

Solaris OS에서 MLFQ 구현은 시간 공유 스케줄러 클래스입니다.
스케줄러는 스케줄링 방법을 정확하게 정의하는 테이블 세트를 제공합니다.
프로세스의 우선순위는 수명 주기에 따라 변경됩니다. 크기는 어떻게 되어야 합니까?
할당할 창과 작업 우선순위를 높이는 빈도입니다. 관리자
시스템은 이 테이블과 상호 작용하고 스케줄러가 작동하도록 할 수 있습니다.
다르게. 기본적으로 이 테이블에는 점진적으로 증가하는 60개의 대기열이 있습니다.
창 크기는 20ms(높은 우선순위)부터 수백 ms(낮은 우선순위)까지입니다.
또한 초당 한 번씩 모든 작업이 향상됩니다.

다른 MLFQ 플래너는 테이블이나 특정 항목을 사용하지 않습니다.
이 강의에서 설명하는 규칙은 반대로 우선순위를 다음을 사용하여 계산합니다.
수학 공식. 예를 들어, FreeBSD의 스케줄러는 다음 공식을 사용합니다.
프로세스의 양에 따라 현재 작업 우선 순위를 계산합니다.
CPU를 사용했습니다. 또한 CPU 사용량은 시간이 지남에 따라 감소하므로
따라서 우선순위 증가는 위에서 설명한 것과 다소 다릅니다. 이것은 사실이다
붕괴 알고리즘이라고 합니다. 버전 7.1부터 FreeBSD는 ULE 스케줄러를 사용합니다.

마지막으로 많은 기획자에는 다른 기능이 있습니다. 예를 들어 일부
스케줄러는 운영 체제 작동을 위해 더 높은 수준을 예약하므로
따라서 어떤 사용자 프로세스도 가장 높은 우선순위를 받을 수 없습니다.
체계. 일부 시스템에서는 도움을 줄 수 있는 조언을 제공할 수 있습니다.
플래너는 우선 순위를 올바르게 설정할 수 있습니다. 예를 들어, 다음 명령을 사용하면 좋은
작업의 우선순위를 높이거나 낮출 수 있으며 이에 따라 높이거나 낮출 수 있습니다.
프로그램이 CPU 시간을 사용할 가능성을 줄입니다.

MLFQ: 요약

우리는 MLFQ라는 계획 접근 방식을 설명했습니다. 그의 이름
작동 원리에 포함됨 - 여러 개의 대기열이 있고 피드백을 사용합니다.
작업의 우선순위를 정하는 것.
규칙의 최종 형태는 다음과 같습니다.

Rule1: 우선순위(A) > 우선순위(B)이면 태스크 A가 실행됩니다(B는 실행되지 않음).
Rule2: 우선순위(A) = 우선순위(B)인 경우 RR을 사용하여 A&B가 시작됩니다.
Rule3: 작업이 시스템에 들어오면 가장 높은 우선순위 대기열에 배치됩니다.
Rule4: 작업이 현재 대기열에서 할당된 시간을 모두 사용한 후에(CPU를 해제한 횟수에 관계없이) 해당 작업의 우선 순위는 감소합니다(대기열 아래로 이동합니다).
Rule5: 일정 기간 S 이후 시스템 내 모든 작업을 최상위 대기열로 이동합니다.

MLFQ는 다음과 같은 이유로 흥미롭습니다.
작업의 성격을 미리 파악하여 알고리즘은 작업의 과거 동작을 학습하고 설정합니다.
그에 따라 우선순위를 정하세요. 그래서 그는 작은 작업(SJF, STCF)의 생산성을 높이고 정직하게 오래 달리기 위해 동시에 두 개의 의자에 앉으려고 노력합니다.
CPU 로딩 작업. 따라서 BSD 및 그 파생물을 포함한 많은 시스템은
Solaris, Windows, Mac은 일정 형태의 알고리즘을 스케줄러로 사용합니다.
MLFQ를 기준으로 삼습니다.

추가 자료 :

출처 : habr.com

운영 체제: 세 가지 쉬운 부분. 5부: 계획: 다단계 피드백 대기열(번역)