운영 체제 소개

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

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

• 원래의
• 원래의
• 내 개인적인 적응

기타 부품 :

• 1부: 소개
• 2부: 추상화: 프로세스
• 3부: 프로세스 API 소개
• 4부: 스케줄러 소개

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

스케줄러 소개

문제의 본질: 스케줄러 정책을 개발하는 방법
기본 스케줄러 정책 프레임워크는 어떻게 설계되어야 합니까? 핵심 가정은 무엇이어야 합니까? 어떤 지표가 중요합니까? 초기 컴퓨팅 시스템에서는 어떤 기본 기술이 사용되었습니까?

워크로드 가정

가능한 정책을 논의하기 전에 먼저 시스템에서 실행되는 프로세스에 대해 몇 가지 단순화된 설명을 만들어 보겠습니다. 작업량. 워크로드 정의는 정책 구축의 중요한 부분이며, 워크로드에 대해 더 많이 알수록 더 나은 정책을 작성할 수 있습니다.

시스템에서 실행되는 프로세스(때때로라고도 함)에 대해 다음과 같은 가정을 해보겠습니다. 작업 (작업). 이러한 가정은 거의 모두 현실적이지는 않지만 사고의 발전에 필요합니다.

1. 각 작업은 동일한 시간 동안 실행됩니다.
2. 모든 작업이 동시에 설정되며,
3. 할당된 작업은 완료될 때까지 작동합니다.
4. 모든 작업은 CPU만 사용합니다.
5. 각 작업의 실행 시간이 알려져 있습니다.

스케줄러 측정항목

로드에 대한 몇 가지 가정 외에도 다양한 스케줄링 정책을 비교하기 위한 또 다른 도구인 스케줄러 메트릭이 필요합니다. 측정항목은 단지 무언가에 대한 측정값일 뿐입니다. 스케줄러를 비교하는 데 사용할 수 있는 다양한 측정항목이 있습니다.

예를 들어, 다음과 같은 측정항목을 사용하겠습니다. 처리 시간 (처리 시간). 작업 처리 시간은 작업 완료 시간과 시스템 내 작업 도착 시간의 차이로 정의됩니다.

Tturnaround=Tcompletion−Tarrival

모든 작업이 동시에 도착했다고 가정했기 때문에 Ta=0이고 따라서 Tt=Tc입니다. 이 값은 위의 가정을 변경하면 자연스럽게 변경됩니다.

또 다른 측정항목 - 공평 (공정성, 정직성). 생산성과 공정성은 종종 계획에서 반대되는 특성입니다. 예를 들어 스케줄러는 성능을 최적화할 수 있지만 다른 작업이 실행될 때까지 기다려야 하므로 공정성이 떨어집니다.

선입선출(FIFO)

우리가 구현할 수 있는 가장 기본적인 알고리즘은 FIFO 또는 선착순(in), 선착순(out). 이 알고리즘에는 여러 가지 장점이 있습니다. 구현하기가 매우 쉽고 모든 가정에 적합하며 작업을 매우 잘 수행합니다.

간단한 예를 살펴보겠습니다. 3가지 작업이 동시에 설정되었다고 가정해 보겠습니다. 하지만 작업 A가 다른 모든 작업보다 조금 더 일찍 도착했다고 가정해 보겠습니다. 따라서 B가 C에 비해 다른 작업보다 먼저 실행 목록에 나타납니다. 각 작업이 10초 동안 실행된다고 가정해 보겠습니다. 이 경우 이러한 작업을 완료하는 데 걸리는 평균 시간은 얼마나 됩니까?

- 10+20+30 값을 세고 3으로 나누면 평균 프로그램 실행 시간이 20초가 됩니다.
이제 가정을 바꿔보도록 하겠습니다. 특히, 가정 1이므로 더 이상 각 작업을 실행하는 데 동일한 시간이 걸린다고 가정하지 않습니다. 이번에는 FIFO가 어떻게 작동할까요?

결과적으로 다양한 작업 실행 시간은 FIFO 알고리즘의 생산성에 극도로 부정적인 영향을 미칩니다. 작업 A가 완료되는 데 100초가 걸리는 반면, B와 C는 여전히 각각 10초가 걸린다고 가정해 보겠습니다.

그림에서 볼 수 있듯이 시스템의 평균 시간은 (100+110+120)/3=110입니다. 이 효과를 호송 효과, 리소스의 일부 단기 소비자가 대량 소비자 뒤에 대기하는 경우입니다. 마치 식료품점에 카트를 가득 담은 고객이 앞에 줄을 서 있는 것과 같습니다. 문제에 대한 가장 좋은 해결책은 금전 등록기를 바꾸거나 긴장을 풀고 심호흡을 하는 것입니다.

최단 직업 우선

중량급 프로세스로 유사한 상황을 어떻게든 해결할 수 있습니까? 틀림없이. 또 다른 유형의 계획을 계획이라고 합니다.최단 직업 우선 (SJF). 그 알고리즘도 매우 원시적입니다. 이름에서 알 수 있듯이 가장 짧은 작업이 먼저 시작되고 차례로 시작됩니다.

이 예에서 동일한 프로세스를 실행하면 평균 프로그램 처리 시간이 향상되며 이는 다음과 같습니다. 50 대신 110, 이는 거의 2배 더 좋습니다.

따라서 모든 작업이 동시에 도착한다는 가정하에 SJF 알고리즘이 가장 최적의 알고리즘인 것으로 보입니다. 그러나 우리의 가정은 여전히 ​​현실적이지 않은 것 같습니다. 이번에는 가정 2를 변경하고 작업이 동시에 존재할 수는 없고 언제든지 존재할 수 있다고 가정합니다. 이로 인해 어떤 문제가 발생할 수 있나요?

태스크 A(100c)가 먼저 도착하여 실행되기 시작한다고 가정해보자. t=10에서 작업 B와 C가 도착하며 각각 10초가 걸립니다. 따라서 평균 실행 시간은 (100+(110-10)+(120-10))3 = 103입니다. 이를 개선하기 위해 스케줄러는 무엇을 할 수 있습니까?

STCF(최단 완료 시간 우선)

상황을 개선하기 위해 프로그램이 시작되어 완료될 때까지 실행된다는 가정 3을 생략합니다. 또한 하드웨어 지원이 필요하며 짐작할 수 있듯이 타이머 실행 중인 작업을 중단하고 컨텍스트 전환. 따라서 스케줄러는 작업 B, C가 도착하는 순간 작업을 수행할 수 있습니다. 즉, 작업 A 실행을 중지하고 작업 B 및 C를 처리에 넣은 다음 완료 후 프로세스 A를 계속 실행합니다. 이러한 스케줄러를 호출합니다. STCF또는 선제적 작업 우선.

이 플래너의 결과는 다음과 같습니다: ((120-0)+(20-10)+(30-10))/3=50. 따라서 이러한 스케줄러는 우리 작업에 더욱 적합해집니다.

측정항목 응답 시간

따라서 작업의 실행 시간을 알고 이러한 작업이 CPU만 사용한다는 것을 알고 있다면 STCF가 최상의 솔루션이 될 것입니다. 그리고 초기에는 이러한 알고리즘이 꽤 잘 작동했습니다. 그러나 이제 사용자는 대부분의 시간을 터미널에서 보내며 생산적인 대화형 경험을 기대합니다. 따라서 새로운 측정항목이 탄생했습니다. 응답 시간 (응답).

응답 시간은 다음과 같이 계산됩니다.

응답=Tfirstrun−Tarrival

따라서 이전 예의 경우 응답 시간은 A=0, B=0, C=10(abg=3,33)이 됩니다.

그리고 3개의 작업이 동시에 도착하는 상황에서는 STCF 알고리즘이 그다지 좋지 않은 것으로 나타났습니다. 작은 작업이 완전히 완료될 때까지 기다려야 합니다. 따라서 알고리즘은 처리 시간 측정 항목에는 적합하지만 상호 작용 측정 항목에는 적합하지 않습니다. 터미널에 앉아 편집기에 문자를 입력하려고 하는데 다른 작업이 CPU를 차지하기 때문에 10초 이상 기다려야 한다고 상상해 보십시오. 별로 즐겁지 않습니다.

그래서 우리는 또 다른 문제에 직면하게 됩니다. 응답 시간에 민감한 스케줄러를 어떻게 구축할 수 있을까요?

원형으로 서명한 청원서

이 문제를 해결하기 위해 알고리즘이 개발되었습니다. 원형으로 서명한 청원서 (RR). 기본 아이디어는 매우 간단합니다. 작업이 완료될 때까지 실행하는 대신 특정 기간(타임 슬라이스라고 함) 동안 작업을 실행한 다음 대기열에서 다른 작업으로 전환합니다. 알고리즘은 모든 작업이 완료될 때까지 작업을 반복합니다. 이 경우 프로그램 실행 시간은 타이머가 프로세스를 중단한 후의 시간의 배수여야 합니다. 예를 들어 타이머가 x=10ms마다 프로세스를 중단하는 경우 프로세스 실행 창의 크기는 10의 배수이고 10,20 또는 x*10이어야 합니다.

예를 들어 보겠습니다. ABC 작업이 시스템에 동시에 도착하고 각 작업은 5초 동안 실행되기를 원합니다. SJF 알고리즘은 다른 작업을 시작하기 전에 각 작업을 완료합니다. 대조적으로, 시작 창 = 1초인 RR 알고리즘은 다음과 같은 작업을 수행합니다(그림 4.3).

(SJF Again(응답 시간이 좋지 않음)

(라운드 로빈(응답 시간에 좋음)

RR 알고리즘의 평균 응답 시간은 (0+1+2)/3=1인 반면 SJF의 경우 (0+5+10)/3=5입니다.

시간 창이 RR에 대해 매우 중요한 매개변수라고 가정하는 것은 논리적이며, 시간 창이 작을수록 응답 시간이 길어집니다. 그러나 컨텍스트 전환 시간도 전체 성능에 중요한 역할을 하므로 너무 작게 설정해서는 안 됩니다. 따라서 실행 창 시간 선택은 OS 설계자에 의해 설정되며 실행되도록 계획된 작업에 따라 달라집니다. 컨텍스트 전환은 시간을 낭비하는 유일한 서비스 작업이 아닙니다. 실행 중인 프로그램은 다양한 캐시와 같은 다른 많은 작업에서 작동하며 각 스위치를 사용하면 이 환경을 저장하고 복원해야 하며 이 작업에는 많은 시간이 걸릴 수도 있습니다. 시간.

응답 시간 측정항목에 대해서만 이야기한다면 RR은 훌륭한 스케줄러입니다. 하지만 이 알고리즘을 사용하면 작업 처리 시간 측정항목이 어떻게 작동할까요? A, B, C의 작동 시간 = 5s이고 동시에 도착할 때 위의 예를 고려하십시오. 작업 A는 13시에 종료되고 B는 14시에 종료되며 C는 15초에 종료되며 평균 처리 시간은 14초입니다. 따라서 RR은 회전율 지표에 대한 최악의 알고리즘입니다.

보다 일반적인 용어로 말하면 모든 RR 유형 알고리즘은 공정하며 모든 프로세스 간에 CPU 시간을 균등하게 나눕니다. 따라서 이러한 측정항목은 지속적으로 서로 충돌합니다.

따라서 우리는 몇 가지 대조되는 알고리즘을 가지고 있으며 동시에 작업 시간이 알려져 있고 작업이 CPU만 사용한다는 몇 가지 가정이 여전히 남아 있습니다.

I/O와 혼합

먼저 프로세스가 CPU만 사용한다는 가정 4를 제거해 보겠습니다. 당연히 그렇지 않으며 프로세스가 다른 장비에 액세스할 수 있습니다.

프로세스가 I/O 작업을 요청하는 순간 프로세스는 차단 상태에 들어가 I/O가 완료될 때까지 기다립니다. I/O가 하드 드라이브로 전송되는 경우 이러한 작업은 최대 수 ms 이상이 소요될 수 있으며 현재 프로세서는 유휴 상태입니다. 이 시간 동안 스케줄러는 다른 프로세스로 프로세서를 점유할 수 있습니다. 스케줄러가 내려야 할 다음 결정은 프로세스가 I/O를 완료하는 시기입니다. 이런 일이 발생하면 인터럽트가 발생하고 OS는 I/O를 호출한 프로세스를 준비 상태로 전환합니다.

몇 가지 문제의 예를 살펴보겠습니다. 각각에는 50ms의 CPU 시간이 필요합니다. 그러나 첫 번째 항목은 10ms마다 I/O에 액세스합니다(이 역시 10ms마다 실행됩니다). 그리고 프로세스 B는 I/O 없이 단순히 50ms 프로세서를 사용합니다.

이 예에서는 STCF 스케줄러를 사용합니다. A와 같은 프로세스가 시작되면 스케줄러는 어떻게 작동합니까? 그는 다음을 수행합니다. 먼저 프로세스 A를 완전히 수행한 다음 프로세스 B를 수행합니다.

이 문제를 해결하기 위한 전통적인 접근 방식은 프로세스 A의 각 10ms 하위 작업을 별도의 작업으로 처리하는 것입니다. 따라서 STJF 알고리즘으로 시작할 때 50ms 작업과 10ms 작업 사이의 선택이 분명합니다. 그런 다음 하위 작업 A가 완료되면 프로세스 B와 I/O가 시작됩니다. I/O가 완료된 후 프로세스 B 대신 10ms 프로세스 A를 다시 시작하는 것이 일반적입니다. 이러한 방식으로 첫 번째 프로세스가 기다리는 동안 다른 프로세스에서 CPU를 사용하는 오버랩을 구현할 수 있습니다. I/O. 결과적으로 시스템 활용도가 높아집니다. 대화형 프로세스가 I/O를 기다리는 순간 다른 프로세스가 프로세서에서 실행될 수 있습니다.

오라클은 더 이상 존재하지 않습니다.

이제 작업의 실행 시간이 알려져 있다는 가정을 없애도록 하겠습니다. 이는 일반적으로 전체 목록에서 가장 최악이고 가장 비현실적인 가정입니다. 실제로 일반적인 일반 OS에서 OS 자체는 일반적으로 작업 실행 시간에 대해 거의 알지 못하는데, 작업을 실행하는 데 걸리는 시간을 알지 못한 채 어떻게 스케줄러를 구축할 수 있습니까? 아마도 이 문제를 해결하기 위해 몇 가지 RR 원칙을 사용할 수 있을까요?

합계

우리는 작업 스케줄링의 기본 아이디어를 살펴보고 두 가지 스케줄러 제품군을 살펴보았습니다. 첫 번째는 가장 짧은 작업을 먼저 시작하여 처리 시간을 늘리는 반면, 두 번째는 모든 작업을 균등하게 나누어 응답 시간을 늘립니다. 다른 계열의 알고리즘이 좋은 경우 두 알고리즘 모두 좋지 않습니다. 또한 CPU와 I/O의 병렬 사용이 어떻게 성능을 향상시킬 수 있는지 살펴보았지만 OS 투시 문제는 해결되지 않았습니다. 그리고 다음 수업에서는 바로 과거를 들여다보고 미래를 예측하는 플래너를 살펴보겠습니다. 그리고 이를 다단계 피드백 대기열이라고 합니다.

출처 : habr.com