리눅스 환경에서 프로세스 스케줄링 알고리즘은 무엇입니까?

1 부: 실시간 스케줄링 알고리즘소개 < P > 실시간 시스템의 경우 POSIX 13.b 는 제한된 응답 시간 내에 필요한 수준의 서비스를 제공할 수 있는 시스템을 정의합니다. Donald Gillies 가 제안한 보다 수용 가능한 정의는 실시간 시스템은 계산의 정확성이 프로그램의 논리적 정확성뿐만 아니라 결과 생성 시간에 달려 있다는 것입니다. 시스템의 시간 제약이 충족되지 않으면 시스템 오류가 발생합니다.

실시간 시스템은 실시간 요구 사항에 따라 소프트 실시간 및 하드 실시간 유형으로 나눌 수 있습니다. 하드 실시간 시스템은 시스템이 보장해야 하는 최악의 경우 서비스 시간, 즉 이벤트에 대한 응답 시간 마감일은 어쨌든 충족되어야 한다는 것을 의미합니다. 예를 들어, 우주 왕복선의 통제 등은 현실 속의 이런 시스템이다. 실시간 특성을 가진 다른 모든 시스템을 소프트 실시간 시스템이라고 부를 수 있습니다. 분명히 소프트 실시간 시스템은 통계적 관점에서 볼 때, 작업 (아래 논술에서 우리는 작업과 프로세스를 구분하지 않음) 이 확실한 처리 시간을 얻을 수 있고, 시스템에 도착한 이벤트도 마감일이 도착하기 전에 처리될 수 있지만, 마감일을 위반해도 치명적인 오류는 발생하지 않습니다. 실시간 멀티미디어 시스템은 소프트 실시간 시스템입니다.

한 컴퓨터 시스템이 실시간 지원을 제공하기 위해서는 운영 체제가 CPU 및 기타 자원을 효과적으로 예약하고 관리해야 합니다. 멀티 태스킹 실시간 시스템에서는 자원 스케줄링 및 관리가 더욱 복잡합니다. 이 문서에서는 다양한 실시간 작업 스케줄링 알고리즘에 대해 분류 관점에서 논의한 다음, 일반적인 Linux 운영 체제의 프로세스 스케줄링 및 다양한 실시간 Linux 시스템이 실시간 기능을 지원하기 위해 일반 Linux 시스템의 개선을 연구합니다. 마지막으로 Linux 운영 체제를 실시간 영역에 적용할 때 발생하는 몇 가지 문제를 분석하고 다양한 실시간 Linux 가 이러한 문제를 어떻게 해결하는지 요약합니다.

1. 실시간 CPU 스케줄링 알고리즘 분류

다양한 실시간 운영 체제에 대한 실시간 스케줄링 알고리즘은 우선 순위 기반 스케줄링 알고리즘 (priority-driven scheduling) 의 세 가지 범주로 나눌 수 있습니다 공유 스케줄링 알고리즘 (Share-driven scheduling-SD) 및 시간 기반 프로세스 스케줄링 알고리즘 (Time-driven scheduling-TD) 이 세 가지 스케줄링 알고리즘에 대해 하나씩 설명합니다.

1.1. 우선 순위 기반 스케줄링 알고리즘

우선 순위 기반 스케줄링 알고리즘은 각 프로세스에 우선 순위를 지정합니다. 스케줄러는 프로세스가 예약될 때마다 항상 우선 순위가 가장 높은 작업을 예약하여 실행합니다. 우선 순위 할당 방법에 따라 우선 순위 기반 스케줄링 알고리즘은 두 가지 유형 [Krishna1] [Wang99] 으로 나눌 수 있습니다. < P > 정적 우선 순위 스케줄링 알고리즘: < P > 이 스케줄링 알고리즘은 시스템에서 실행되는 모든 프로세스에 정적으로 우선 순위를 할당합니다. 정적 우선 순위 할당은 작업 주기, 사용자 우선 순위 또는 기타 미리 결정된 정책과 같은 적용된 속성에 따라 수행할 수 있습니다. RM(Rate-Monotonic) 스케줄링 알고리즘은 작업의 실행 주기 길이를 기준으로 스케줄링 우선 순위를 결정하는 일반적인 정적 우선 순위 스케줄링 알고리즘으로, 실행 주기가 작은 작업의 우선 순위가 높습니다.

동적 우선 순위 스케줄링 알고리즘:

자원 할당 및 스케줄링 시 유연성을 높이기 위해 작업의 자원 요구 사항에 따라 작업 우선 순위를 동적으로 할당하는 스케줄링 알고리즘입니다. 짧은 작업 우선 순위 스케줄링 알고리즘과 같은 비 실시간 시스템에는 이러한 스케줄링 알고리즘이 많이 있습니다. 실시간 스케줄링 알고리즘에서 EDF 알고리즘은 가장 많이 사용되는 동적 우선 순위 스케줄링 알고리즘으로, 준비 대기열의 각 작업에 기한 (Deadline) 에 따라 우선 순위를 지정하고 가장 최근 기한을 가진 작업에 가장 높은 우선 순위를 부여합니다.

1.2. 비례 기반 * * * 공유 스케줄링 알고리즘 < P > 우선 순위 기반 스케줄링 알고리즘이 간단하고 효과적이지만, 이 스케줄링 알고리즘은 하드 실시간 스케줄링을 제공하며, 실시간 멀티미디어 회의 시스템과 같은 소프트 실시간 응용 프로그램에는 적합하지 않은 경우가 많습니다. 이 소프트 실시간 애플리케이션의 경우 비율 * * * 공유 자원 스케줄링 알고리즘 (SD 알고리즘) 을 사용하는 것이 더 적합합니다. < P > 비례 * * * 공유 스케줄링 알고리즘은 CPU 사용 비율에 따른 * * * 공유 스케줄링 알고리즘을 의미합니다. 기본 아이디어는 일정 가중치 (비율) 에 따라 일정이 필요한 작업 세트를 예약하여 실행 시간이 가중치에 완전히 비례하도록 하는 것입니다. < P > 두 가지 방법으로 비례 * * * 공유 스케줄링 알고리즘 [Nieh1] 을 구현할 수 있습니다. 첫 번째 방법은 각 준비 프로세스가 일정 대기열 시작 부분에 나타나는 빈도를 조정하고 대기열 시작 프로세스 실행을 예약하는 것입니다. 두 번째 방법은 준비 대기열의 각 프로세스가 순차적으로 실행되도록 일정을 잡는 것이지만 할당된 가중치에 따라 각 프로세스의 런타임 슬라이스를 할당하는 것입니다. < P > 비례 * * * 공유 스케줄링 알고리즘은 회전 방법, 공정성 * * * 공유, 공정 대기열, 복권 스케줄링 방법 등으로 나눌 수 있습니다. < P > 비례 * * * 공유 스케줄링 알고리즘의 한 가지 문제는 우선 순위 개념이 정의되지 않았다는 것입니다. 모든 작업은 요청된 비율에 따라 CPU 리소스를 즐기며 시스템이 과부하 상태일 때 모든 작업의 실행이 비례적으로 느려집니다. 따라서 시스템의 실시간 프로세스가 특정 CPU 처리 시간을 얻을 수 있도록 프로세스 가중치를 동적으로 조정하는 방법이 일반적으로 사용됩니다.

1.3. 시간 기반 프로세스 스케줄링 알고리즘 < P > 안정적이고 알려진 입력이 있는 간단한 시스템의 경우 데이터 처리를 위한 예측 가능성을 제공하는 시간 중심 (Time-driven:TD) 스케줄링 알고리즘을 사용할 수 있습니다. 이 스케줄링 알고리즘은 본질적으로 디자인 타임에 결정된 오프라인 정적 스케줄링 방법입니다. 시스템의 설계 단계에서는 시스템의 모든 처리 상황을 명확히 하여 각 작업의 시작, 전환 및 종료 시간 등에 대한 명확한 일정과 설계를 미리 수행합니다. 이 스케줄링 알고리즘은 작은 임베디드 시스템, 자동 제어 시스템, 센서 등의 어플리케이션 환경에 적합합니다. < P > 이러한 스케줄링 알고리즘의 장점은 작업 실행이 예측 가능하다는 것입니다. 그러나 가장 큰 단점은 유연성이 부족하고 작업이 실행되어야 하고 CPU 가 유휴 상태로 유지되는 경우입니다.

2. 일반 Linux 시스템의 CPU 스케줄링

일반 Linux 시스템은 일반 프로세스에 비해 절대 우선 순위를 가진 실시간 및 비실시간 프로세스를 모두 지원합니다. 이에 따라 실시간 프로세스는 SCHED_FIFO 또는 SCHED_RR 일정 정책을 사용하고, 일반 프로세스는 SCHED_OTHER 일정 정책을 사용합니다.

스케줄링 알고리즘 구현에서 Linux 의 각 작업에는 rt_priority, policy, priority(nice), counter 등 네 가지 스케줄링 관련 매개 변수가 있습니다. 스케줄러는 이 네 가지 매개 변수에 따라 프로세스를 예약합니다.

SCHED_OTHER 일정 정책에서 스케줄러는 항상 priority+counter 값이 가장 큰 프로세스를 선택하여 실행 일정을 잡습니다. 논리적으로 SCHED_OTHER 일정 정책에는 일정 주기 (epoch) 가 있으며, 각 일정 주기 동안 한 프로세스의 priority 및 counter 값의 크기는 현재 시간에 실행할 일정을 잡아야 하는 프로세스에 영향을 줍니다. 여기서 priority 는 프로세스에서 생성되는 고정 값입니다 Counter 는 현재 일정 주기에 프로세스가 남아 있는 시간 슬라이스를 반영하는 동적으로 변하는 값입니다. 각 일정 주기가 시작될 때 priority 의 값이 counter 에 지정되고 프로세스가 실행되도록 예약될 때마다 counter 값이 감소합니다. Counter 값이 이면 프로세스가 이 일정 주기에 있는 자체 슬라이스를 모두 사용하고 이 일정 주기에 대한 프로세스 일정에 더 이상 참여하지 않습니다. 모든 프로세스의 슬라이스가 다 떨어지면 일정 주기가 끝난 다음 주기가 반복됩니다. 또한 Linux 시스템의 일정 주기는 정적이 아니며, 실행 가능한 프로세스의 수와 해당 priority 값이 하나의 epoch 길이에 영향을 줄 수 있는 등 동적으로 변하는 양입니다. 주목할 만한 점은 2.4 이상의 커널에서 priority 가 nice 로 대체되었지만 두 가지가 비슷하다는 것입니다.

보이는 SCHED_OTHER 스케줄링 정책은 기본적으로 비율 * * * 의 공유 스케줄링 전략으로, 프로세스 스케줄링의 공정성을 보장하도록 설계되었습니다. 우선 순위가 낮은 프로세스는 각 epoch 에서 자신이 받아야 할 CPU 실행 시간을 얻을 수 있으며, 높은 ppu 를 가진 다양한 프로세스의 우선 순위 구분을 제공합니다

실시간 프로세스의 경우 실시간 우선 순위 rt_priority 기반 우선 순위 스케줄링 정책을 사용하지만 동일한 실시간 우선 순위의 프로세스 간 스케줄링 방법은 스케줄링 정책에 따라 다릅니다.

SCHED_FIFO: 정적 우선 순위에 따라 프로세스가 대기한 다음 동일한 우선 순위에 있습니다 자원 요청으로 인해 차단되었습니다. 3. 스스로 적극적으로 CPU 를 포기합니다 (sched_yield)； 호출).

SCHED_RR: 위의 SCHED_FIFO 와 동일한 스케줄링 전략입니다. 단, 각 프로세스에 시간 슬라이스가 할당되고 실행 중인 프로세스에 도달하면 실행이 취소됩니다. 시간 슬라이스의 길이는 sched_rr_get_interval 호출을 통해 얻을 수 있습니다.

Linux 시스템 자체는 데스크톱 지향 시스템이므로 실시간 애플리케이션에 적용할 때 다음과 같은 문제가 있습니다. < P > Linux 시스템의 일정 단위는 1ms 이므로 정확한 타이밍을 제공할 수 없습니다. < P > 프로세스가 시스템 호출을 커널 상태로 호출하면 선점할 수 없습니다.

Linux 커널 구현에 대량의 봉인 인터럽트 작업을 사용하면 중단의 손실이 발생할 수 있습니다.

가상 메모리 기술 사용으로 인해 페이지 오류가 발생할 경우 하드 드라이브에서 스왑 데이터를 읽어야 하지만, 하드 드라이브 읽기 및 쓰기는 스토리지 위치의 무작위성으로 인해 임의 읽기 및 쓰기 시간이 발생할 수 있으며, 경우에 따라 일부 실시간 작업의 마감 기한에 영향을 미칠 수 있습니다. < P > Linux 프로세스 스케줄링도 실시간 우선 순위를 지원하지만 효과적인 실시간 작업에 대한 스케줄링 메커니즘 및 스케줄링 알고리즘이 부족합니다. 네트워크 하위 시스템의 프로토콜 처리 및 기타 장치의 인터럽트 처리는 해당 프로세스의 일정과 연관되지 않으며 자체 스케줄링 메커니즘이 없습니다.

3. 다양한 실시간 리눅스 시스템

3.1.rt-Linux 와 RTAI

RT -Linux 는 뉴멕시코 과학기술대학 (New Mexico Institute of Technology) 이다 기본 아이디어는 Linux 시스템에서 하드 실시간 지원을 제공하기 위해 마이크로 커널의 작은 실시간 운영 체제 (RT-Linux 의 실시간 하위 시스템이라고도 함) 를 구현하고 일반 Linux 시스템을 해당 운영 체제에서 우선 순위가 낮은 작업으로 실행한다는 것입니다. 또한 일반 Linux 시스템의 작업은 FIFO 및 실시간 작업을 통해 통신할 수 있습니다. RT-Linux 의 프레임워크는 그림 1 과 같습니다. < P > 그림 1 RT-Linux 구조

RT -Linux 의 핵심 기술은 소프트웨어를 통해 하드웨어의 인터럽트 컨트롤러를 시뮬레이션하는 것입니다. Linux 시스템이 CPU 의 인터럽트를 차단하려고 할 때 RT-Linux 의 실시간 하위 시스템은 이 요청을 가로채서 기록하지만 실제로는 하드웨어 인터럽트를 실제로 차단하지 않으므로 인터럽트 차단으로 인한 시스템이 일정 기간 동안 응답하지 않는 상황을 방지하여 실시간을 높입니다. 하드웨어 중단이 발생하면 RT-Linux 는 인터럽트를 가로채고 처리를 위해 실시간 하위 시스템의 인터럽트 루틴이 있는지 아니면 일반 Linux 커널로 전달되는지 결정합니다. 또한 일반 Linux 시스템의 최소 타이밍 정밀도는 시스템의 실시간 클럭 빈도에 의해 결정되며, 일반 Linux 시스템은 초당 1 개의 클럭 인터럽트로 설정되므로 Linux 시스템의 일반적인 타이밍 정밀도는 1ms, 즉 클럭 주기는 1ms 이고 RT-Linux 는 시스템의 실시간 클럭을 단일 트리거 상태로 설정하여 십여 개를 제공할 수 있습니다.

RT-Linux 실시간 서브시스템의 작업 스케줄링은 RM, EDF 등의 우선 순위 기반 알고리즘이나 다른 스케줄링 알고리즘을 사용할 수 있습니다.

RT -Linux 는 과부하로 작동하는 독점 시스템에 좋은 선택이지만 CPU 자원에 대한 일정만 제공합니다. 또한 실시간 시스템과 일반 Linux 시스템 간의 관계는 그리 밀접한 관계가 없기 때문에 개발자는 스택 등과 같은 Linux 시스템에서 이미 구현된 기능을 충분히 활용할 수 없습니다. 따라서 RT-Linux 는 산업 제어와 같은 실시간 작업 기능이 간단하고 하드 실시간 요구 사항이 있는 환경에 적합하지만, 응용 프로그램 및 멀티미디어 처리에는 많은 작업이 필요합니다.

이탈리아의 rtai (real-time application interface) 는 RT-Linux 에서 유래한 것으로 RT-Linux 와 디자인 사상적으로 동일합니다. RT-Linux 가 서로 다른 Linux 버전 간에 이식하기 어려운 문제를 해결하기 위해 RTAI 는 Linux 에 실시간 하드웨어 추상화 계층을 정의했습니다. 실시간 작업은 Linux 커널에 실시간 지원을 추가할 때 Linux 커널 소스 코드를 최대한 수정할 수 있도록 이 추상화 계층에서 제공되는 인터페이스를 통해 Linux 시스템과 상호 작용합니다.

3.2. Kurt-Linux

Kurt -Linux 는 Kansas university 에서 개발한 것으로 마이크로를 제공합니다