갱 스케줄링

컴퓨터 과학에서 갱 스케줄링은 다른 프로세서에서 동시에 실행되도록 관련 스레드 또는 프로세스를 스케줄링하는 병렬 시스템의 스케줄링 알고리즘이다.보통 이것들은 모두 동일한 과정에 속하는 나사산이 될 것이지만, 또한 다른 공정에서 나온 것일 수도 있는데, 이 공정들은 생산자와 소비자 관계를 가질 수도 있고 동일한 MPI 프로그램에서 나온 것일 수도 있다.

갱 스케줄링은 둘 이상의 스레드 또는 프로세스가 서로 통신할 경우 모두 동시에 통신할 수 있도록 하기 위해 사용된다.만약 그들이 조직폭력배 일정을 잡지 않았다면, 사람들은 그들이 자고 있는 동안 다른 사람에게 메시지를 보내거나 받기 위해 기다릴 수 있었고, 그 반대의 경우도 있었다.프로세서가 초과 구독되고 서로 통신하는 프로세스 또는 스레드 그룹 내에서 갱 스케줄링이 사용되지 않는 경우, 각 통신 이벤트는 컨텍스트 스위치의 오버헤드를 겪을 수 있다.

갱 스케줄링은 오스터아웃 매트릭스라고 불리는 데이터 구조를 기반으로 한다.이 행렬에서 각 행은 시간 조각을 나타내고 각 열은 프로세서를 나타낸다.각 작업의 스레드 또는 프로세스는 매트릭스의 단일 행으로 포장된다.^[1]실행 중에 조정된 컨텍스트 전환은 한 행의 프로세스에서 다음 행의 프로세스로 전환하기 위해 모든 노드에 걸쳐 수행된다.

조직폭력배 스케줄링은 공동 스케줄링보다 엄격하다.^[2]같은 공정의 모든 스레드를 동시에 실행해야 하는 반면, 코스체결은 나머지 패거리와 동시에 실행되지 않는 스레드 집합인 파편을 허용한다.

강 스케줄링이 구현되어 여러 병렬 기계, 특히 Connection Machine CM-5에서 생산 모드로 사용되었다.

종류들

폭력배 가방(BoG)

갱 스케줄링에서 1:1 매핑이 발생하며, 이는 각 작업이 프로세서에 매핑됨을 의미한다.보통 일자리는 독립된 갱단으로 간주되지만 갱단 조직도 한 봉지만 있으면 모든 갱단을 결합해 함께 시스템으로 보낼 수 있다.시스템에서 일자리가 집행될 때 같은 BoG에 속한 갱단이 모두 집행을 완료할 때까지, 아니면 집행을 완료할 수 없다.^[3]따라서 어떤 직업에 속하는 한 갱단이 집행을 마치면 모든 갱단이 집행을 완료할 때까지 기다려야 할 것이다.이것은 동기화 지연 오버헤드를 증가시킨다.

j ${\displaystyle t^{}}$ ${\displaystyle h^{}}$ ${\$J$$ t h의 응답시간 ${\displaystyle R_{}}$ j ${\$강스백은$$ 격자배출기에 BoG가 도착하여 BoG에 속하는 모든 하위강들의 작업이 완료될 때까지의 시간 간격으로 정의된다.평균 응답시간은 다음과 같이 정의된다.

응답 시간(RT)= ${\displaystyle \underset{}{\overset{}{1N}}}$ ${\displaystyle \sum \underset{}{\overset{}{}}}$ j${\displaystyle \underset{}{\overset{}{}}}$- 1 ${\displaystyle \underset{}{\overset{}{\mathrm{N}}}}$ ${\displaystyle R_{}}$ ${\displaystyle \underset{}{\overset{}{}}{}_{}}$ $displaystyle {\frac {1}{N}}\textstyle \sum _{j-1}^{N}R_{j}\displaystyle$^[3]$}.$

우선 순위가 높은 작업이 도착하면 응답 시간이 더 영향을 받는다.우선 순위가 높은 작업이 시스템에 도착할 때마다 해당 작업은 프로세서에서 현재 실행 중인 작업보다 더 우선 순위가 부여된다.이 경우 우선순위 작업이 도착하면 현재 시스템에서 실행 중인 서브강(subgang)이 중단되고 그동안 진행됐던 모든 진행상황이 상실돼 재조정이 필요하다.이러한 업무 중단은 BoG의 총 응답 시간을 더욱 지연시킬 것이다.^[3]

적응된 선착순 서비스(AFCFS)

적응된 선착순(AFCFS) 체계는 선착순(first come)과 선착순(first serves) 체계의 변형된 버전이다.선착순 계획과 같이, 먼저 오는 어떤 일이든 실행을 위해 전달될 것이다.그러나 AFCFS 체계에서는 일단 작업이 시스템에 도달하면 해당 작업의 실행에 필요한 프로세서가 충분히 확보되지 않는 한 그리고 그 때까지 작업이 예약되지 않는다.^[3]대규모 작업이 시스템에 도착하여 준비된 대기열의 시작 부분에 있지만 프로세서가 충분하지 않은 경우, AFCFS 정책은 해당 작업이 대기열의 뒤에 있더라도 충분한 프로세서를 사용할 수 있는 소규모 작업을 예약할 것이다.즉, 이 계획은 프로세서 가용성에 기반한 대규모 작업과 비교하여 소규모 작업을 선호하기 때문에 시스템의 단편화를 증가시킬 것이다.^[3][4]

최대 규모의 조직 최초 서비스(LGFS)

위의 실행 방식에서는, 작업규모의 증가에 해당하는 작업을 대기열에 배치하고, 가장 큰 갱에 속하는 작업을 우선 예정하고 있지만, 이 실행방식은 소규모 작업의 자원의 기아를 초래하는 경향이 있어, 프로세서의 수가 비교되는 시스템에서는 실행하기에 부적합하다.낮게 ^[5]깔리다

AFCFS와 LGFS도 프로세서 장애 발생 가능성에 대처해야 한다.이러한 경우 해당 프로세서에서 실행되는 태스크는 실행을 위해 다른 프로세서에 제출된다.태스크는 현재 프로세서를 복구하는 동안 이러한 프로세서의 대기열 머리에서 대기한다.

상기 이슈에서 나오는 시나리오는 다음과 같은 두 가지가 있다.^[5]

• 차단 케이스:중단된 작업에 할당된 프로세서는 차단되며 손상된 프로세서에서 작업이 지워질 때까지 대기열에서 다른 작업을 실행할 수 없다.^[5]
• 비차단 사례:차단된 작업이 다시 실행될 때까지 기다리지 않고 프로세서에서 이미 실행 중인 작업이 조기에 처리될 때 이 경우가 발생한다.^[5]

쌍으로 구성된 갱 스케줄링

I/O 바인딩 프로세스를 실행하는 동안 gang 스케줄링은 다른 프로세서의 응답을 기다리는 동안 CPU를 유휴 상태로 유지하는 반면 유휴 프로세서는 작업 실행에 사용할 수 있다.만일 갱단이 CPU와 I/O 프로세스의 혼합으로 구성된다면, 이러한 프로세스는 서로의 운영에 거의 간섭하지 않기 때문에, CPU와 I/O 모두를 동시에 바쁘게 하고 병렬주의를 이용하도록 알고리즘을 정의할 수 있다.이 방법은 I/O 기반 1개, CPU 바인딩 1개의 갱단을 일치시키는 아이디어를 제시할 것이다.각 갱은 서로 다른 장치를 사용하기 때문에 이 장치가 분리되어 작동한다고 가정할 것이다.^[6]

스케줄링 알고리즘

• 일반 사례:일반적인 경우에, 중앙 노드는 네트워크에 지정되어 작업 할당과 자원 할당을 처리한다.그것은 정보를 오스터홀트 매트릭스로 유지한다.엄격한 갱 스케줄링에서 노드 스케줄러가 해당 행의 각 셀에서 프로세스를 스케줄링하는 한 번에 하나의 행을 선택한다.^[6]
• 쌍으로 구성된 갱:쌍으로 구성된 갱 스케줄링에서 I/O 바인딩된 갱과 CPU 갱 각각 1개씩 2개의 행이 선택된다.최대 허용 병렬 처리를 이끌어내기 위해 적절한 프로세서에 작업을 할당하는 것은 로컬 스케줄러의 재량에 달려 있다.^[6]

동기화 방법

동시 갱 스케줄링(CGS)

확장성이 뛰어나고 다용도 높은 알고리즘을 스케줄링하는 동시 갱으로, 각 노드의 내부 클럭을 활용하는 싱크로나이저의 존재를 가정한다.CGS는 주로 다음과 같은 세 가지 요소로 구성된다.^[7]

• 프로세서/메모리 모듈(처리 요소라고도 함).
• 1-1 통신을 허용하는 2방향 네트워크.
• 일정한 간격 후에 모든 PE의 동기화를 수행하는 싱크로나이저.

동기화 알고리즘은 두 단계로 수행된다.^[7]

• 로드가 변경되면 프런트 엔드 스케줄러에 의해 전용 시간표가 생성된다.
• 그런 다음 로컬 스케줄러는 프런트 엔드 스케줄러에 의해 배포된 작업 간에 전환하여 시간 테이블을 따른다.

우리는 일정한 간격으로 클러스터의 모든 노드에 신호를 보내는 싱크로나이저의 존재를 가정한다.CGS는 PC에서 발생하는 가장 일반적인 이벤트는 타이머 인터럽트이며 내부 클럭과 동일한 파라미터를 사용한다는 사실을 활용한다.^[7]

• 인터럽트가 발생할 때마다 증가되는 공통 카운터가 초기화되며 OS의 내부 클럭으로 지정된다.
• 모든 노드는 확인 간격 't' 후 동기화되며 개별 노드의 내부 클럭을 활용한다.
• 시간 t 후 노드의 개별 클럭과 전역 클럭의 불일치가 없으면 시간 간격 t가 연장된다.그렇지 않으면 단축된다.
• 확인 간격 t를 지속적으로 확인하고 업데이트하십시오.

공유 스케줄링 시스템

SHARE 스케줄링 시스템은 각 노드의 내부 시계 시스템을 활용하고 NTP 프로토콜을 사용하여 동기화된다.스케줄링의 풍미는 그룹 내에서 동일한 리소스 요구사항을 가진 작업을 수집하여 미리 정의된 시간 간격에 대해 동일한 작업을 실행하는 방식으로 구현된다.불완전한 작업은 시간 슬라이스가 소진된 후에 미리 비워진다.^[8]

노드의 로컬 메모리는 미리 비워진 작업을 위한 스왑 공간으로 활용된다.SHARE 스케줄링 시스템의 가장 큰 장점은 수용된 일자리의 서비스 시간을 보장하고 일괄 및 대화형 일자리를 모두 지원한다는 점이다.

동기화:

동일한 자원을 이용하는 각 프로세스 그룹은 다른 프로세서에 매핑된다.SHARE 시스템은 주로 3개의 협업 모듈로 구성되어 있다.^[8]

• 글로벌 스케줄러:이 스케줄러는 로컬 스케줄러에게 프로세스를 실행할 특정 순서(로컬 갱 멤버)를 지시한다.
• 로컬 스케줄러: 로컬 스케줄러가 글로벌 스케줄러에 의해 실행할 작업을 제공한 후, 주어진 시간 슬롯에 있는 프로세서 중 하나에서 병렬 프로세스 하나만 실행되도록 보장한다.로컬 스케줄러는 타임슬라이스가 만료된 후 작업을 선점하고 해당 위치에서 새 작업을 스왑할 컨텍스트 스위치를 요구한다.
• 통신 시스템과의 인터페이스:통신 서브시스템은 스케줄러의 오버헤드 요구사항을 크게 증가시키는 몇 가지 요건을 충족해야 한다.주로 다음과 같이 구성된다.
  • 효율성:인터커넥트의 하드웨어 성능을 클라이언트 수준에 노출해야 함
  • 액세스 제어:통신 서브시스템에 대한 액세스를 관리해야 함
  • 보호 및 보안:상호연결은 프로세서가 다른 프로세서의 성능에 영향을 미치지 않도록 함으로써 프로세서의 분리를 유지해야 한다.
  • 멀티프로토콜: 상호연결은 다양한 고객 니즈를 충족시키기 위해 다양한 프로토콜을 동시에 매핑할 수 있어야 한다.

포장기준

작업을 사용 가능한 슬롯에 넣을 수 없을 때 새 슬롯이 생성된다.사용 가능한 슬롯에 작업을 채울 수 있더라도 새 슬롯이 열리는 경우, 사용된 슬롯 수보다 1이 많은 실행 비율이 증가한다.따라서 특정 알고리즘은 포장 기준에 대해 고안되었으며, 아래에 언급되어 있다.

용량 기반 알고리즘

이 알고리즘은 슬롯 용량을 모니터링하여 새 슬롯을 열 필요가 있는지 여부를 결정한다.이 알고리즘에는 다음 두 가지 변형이 있다.

1. 퍼스트 핏여기서 사용된 슬롯은 순차적으로 용량을 확인한 후 충분한 용량을 가진 첫 번째 슬롯을 선택한다.사용 가능한 슬롯 중 용량이 충분하지 않은 슬롯이 없는 경우, 새 슬롯이 열리고 처리 요소(PE)가 순차적으로 슬롯에 할당된다.^[9]

2. 가장 잘 맞는다.첫 번째 적합과는 달리 사용된 슬롯은 용량에 따라 정렬되지만 순차적인 순서는 아니다.충분한 용량이 가장 작은 슬롯을 선택한다.사용된 슬롯 중 용량이 충분하지 않은 슬롯이 없는 경우, 새 슬롯을 하나만 열린다.새 슬롯이 열리면 이전 알고리즘에 따라 처리 요소(PE)가 순차적으로 슬롯에 할당된다.^[9]

왼쪽-오른쪽 기반 알고리즘

이 알고리즘은 최량 적합 알고리즘의 변형된 버전이다.최적의 적합 알고리즘에서는 PE를 순차적으로 할당하지만, 이 알고리즘에서는 PE를 양방향에서 삽입하여 다른 작업에 할당된 여러 PE 세트 사이의 중첩을 줄일 수 있다.^[9]

1. 크기별 좌우.여기서 PE는 작업 규모에 따라 순차적으로, 역순차로 삽입할 수 있다.작업 규모가 작으면 왼쪽에서 오른쪽으로 PE를 삽입하고, 작업이 크면 오른쪽에서 왼쪽으로 PE를 삽입한다.^[9]

2. 슬롯에 의한 좌우.작업 크기에 따라 선택이 이루어졌던 이전의 알고리즘과 달리, 여기서는 슬롯에 따라 선택이 달라진다.이제 슬롯은 왼쪽 또는 오른쪽에서 채워지는 것으로 표시된다.PE는 동일한 순서에 따라 작업에 할당된다.양쪽의 슬롯 수는 대략 같기 때문에 새로운 슬롯을 열면 양방향의 슬롯 수를 기준으로 방향이 표시된다.^[9]

로드 기반 알고리즘

용량 기반 알고리즘과 왼쪽-우측 알고리즘 모두 개별 PE에 대한 부하를 수용하지 않는다.부하 기반 알고리즘은 개별 PE에 대한 부하를 고려하면서 다른 작업에 할당된 PE 세트 간의 중첩을 추적한다.^[9]

1.최소 최대 부하이 계획에서 PE는 각 작업이 PE에 가해질 부하를 기준으로 정렬된다.슬롯에 있는 무료 PE의 가용성은 슬롯의 용량을 결정한다.PE가 $x{\displaystyle }$ ${\displaystyle x}$ 스레드가$$ 있는 작업에 할당되었다고 가정하면, 로드 순서(마지막 순서)의 x ${\displaystyle t^{}}$ ${\displaystyle h^{}}$ ${\$ x$^{th}$ PE는$$ 슬롯에서 사용 가능한 모든 PE가 가질 수 있는 최대 부하를 결정하게 된다.PE에 최소 최대 부하가 있는 슬롯을 선택하고 슬롯에 최소 부하가 없는 여유 PE를 많이 사용한다.^[9]

2. 최소 평균 하중$x{\displaystyle {}^{}}$ ${\displaystyle t^{}}$ ${\displaystyle h^{}}$ ${\$ PE의$$ 최소 최대 부하에 기반하여 슬롯을 선택했던 이전 방식과 달리, 여기서는 가장 부하가$$ 적게 걸리는 x ${\displaystyle x}$ PE의 부하 평균을 기준으로 슬롯을 선택한다.^[9]

버디 기반 알고리즘

이 알고리즘에서 PE는 개별적으로 할당되지 않고 클러스터로 할당된다.PE는 먼저 두 개의 힘을 가진 그룹으로 분할된다.그룹의 각 멤버에게는 컨트롤러가 할당되며, 크기가 n인 작업이 도착하면 크기 2의^{[lg 2]} 컨트롤러(n보다 크거나 같은 2의 최소 전력)에 할당된다.컨트롤러는 먼저 사용된 모든 슬롯을 분류한 다음 연속적인 2개의^{[lg 2]} 자유 프로세서로 구성된 그룹을 식별하여 할당된다.컨트롤러가 일부 슬롯에 모든 PE를 사용할 수 있는 경우 새로 도착한 작업만 해당 컨트롤러에 할당된다.그렇지 않으면 새 슬롯이 열린다.^[9]

마이그레이션 기반 알고리즘

위에서 언급한 모든 알고리즘에서 초기 배치 정책은 고정되어 있고, 그에 근거하여 PE에 작업이 할당된다.그러나 이 계획은 작업을 한 세트의 PE에서 다른 세트의 PE로 마이그레이션하여 시스템의 실행 비율을 개선한다.^[9]

참고 항목

• 코스케딩
• 병렬 컴퓨팅

참조

• 강 스케줄링, 병렬 컴퓨터의 시간 공유, SC98, 1998년 11월(요약)
• SC97, 1997년 11월 복합환경에서의 갱 스케줄링의 성능특성