CH10-1 Multiprocessor and Real-Time Scheduling

Classifications of Multiprocessor Systems

Loosely coupled or distributed multiprocessor, or cluster

: 각 CPU는 자신만의 메인 메모리와 I/O 채널을 갖는다.

 

Fucntionally specialized processors

: 시스템 내에서 마스터 CPU가 핵심 역할을 하고 다른 CPU들은 주로 특정 작업을 수행하고 마스터 CPU의 지시에 따른다.

 

Tightly coupled multiprocessor - 10장에서 다루는 내용

: 하나의 공통된 메인 메모리를 공유하는 CPU들의 집합으로 구성되며 하나의 통합된 운영체제에 의해 제어된다.

: 모든 CPU가 메모리를 공유하기 때문에 데이터 공유와 통신이 매우 빠르다.

 

Synchronization Granularity and Processes

프로세스들의 동기화 정도에 따라서 구분

 

Fine: 20개 명령어 미만 단위 당 동기화가 필요해서 매우 빈번하게 동기화가 일어난다.

Medium: 수백 개 명령어 단위의 작업이 병렬로 실행되며 스레드 간의 동기화가 필요하다.

Coarse: 프로세스 간 동기화는 드물게 발생하고 수천 개 명령어 단위의 큰 작업 덩어리로 나뉜다.

Very Coarse: 동기화 간격이 매우 길다.(수백만 명령어 단위)

Independent: 서로 아무 관련 없는 여러 프로세스들이 각자 실행되는 경우로 동기화가 필요하지 않다.

 

Scheduling Design Issues

3가지 이슈

(1) 프로세스의 CPU 할당

: 레디 큐에 있는 프로세스를 어떤 CPU에 배정할지를 결정하는 문제

 

(2) 개별 CPU에서의 멀티프로그래밍 사용

: 각 CPU에 할당된 프로세스들을 어떤 방식으로 처리할지에 대한 문제

 

(3) 프로세스의 실제 디스패치

: 특정 CPU에서 실행된 준비가 된 프로세스들 중에서 지금 당장 어떤 프로세스를 선택해서 CPU를 할당할지를 결정하는 가장 짧은 단위의 스케줄링이다.

 

multiprocessor 시스템의 scheduling 방법은 시스템 내의 porcessor의 수, 시스템에서 주로 실행할 process들의 동기화 정도에 따라 달라져야 한다.

 

Assignment of Processes to Processors

(1) 프로세스를 특정 CPU에 영구 할당: 각 CPU는 자신만의 독립된 큐를 갖는다.

- 스케줄링 결정이 각 CPU 내에서만 이루어지므로 오버헤드가 적다.

- 특정 CPU는 할 일이 없어서 쉬고 있는데 다른 CPU는 처리할 프로세스들이 길게 줄 서 있는 비효율적인 상황이 발생할 수 있다.

 

(2) Global queue 사용: 모든 프로세스를 하나의 공통된 전역 큐에 넣고 관리하는 방식

- 어떤 CPU든 작업이 끝나면 쉬지 않고 바로 전역 큐에서 다음 프로세스를 가져와서 실행한다.

- 특정 CPU만 쉬는 비효율을 막을 수 있다.

- 여러 CPU가 동시에 큐에 접근하려고 할 때 병목 현상이 발생할 수 있고 큐를 관리하기 위한 추가적인 오버헤드가 발생한다.

 

Global queue를 사용하는 것으로 결정

 

The Use of Multiprogramming on Individual Processor

(1) 처리 단위가 크거나(Coarse-grained) 독립적인 경우(애플리케이션의 작업 단위가 크거나 다른 작업과 거의 관련이 없는 경우)

: 멀티프로그래밍하는 것이 효율적이다.(각각의 CPU는 여러 프로세스를 전환하며 실행하는 것이 효율적)

 

(2) 처리 단위가 중간(Medium-grained) 크기인 경우 - 하나의 애플리케이션이 수많은 스레드로 구성되어 있다.

: 멀티프로그래밍하지 않는 것이 좋다.

: 일부 실행 중인 스레드가 아직 실행되지 않은 다른 스레드의 작업 결과를 기다리며 멈춰버리는 문제가 발생할 수 있기 때문에 애플리케이션에 속한 모든 스레드가 동시에 실행될 수 없다면 성능이 크게 저하될 수 있다. 

 

Process Dispatching

x축: 커질수록 다양한 실행시간의 프로세스가 존재 (1 - 모든 프로세스의 실행시간이 같다, 5 - 실행시간이 가장 짧은 프로세스와 실행시간이 가장 긴 프로세스의 실행시간이 5배 차이 난다)

y축: throughput

 

CPU가 1개일 때는 프로세스의 실행 순서에 따라 성능 차이가 크다. (1에서 5로 갈수록 성능 차이가 크다.)

CPU가 여러 개일 때는 프로세스를 어떤 순서로 실행시키든 크게 성능 차이가 없다. (1에서 5로 가도 성능 차이가 크지 않다.)

 

multiprocessor 시스템에서는 스케줄링 방식이 중요하지 않다.

하나의 CPU가 실행시간이 긴 프로세스를 실행하고 있더라도 다른 프로세스는 놀고 있는 다른 CPU에서 즉시 실행할 수 있다.

 

Thread Scheduling

하나의 애플리케이션을 구성하는 여러 스레드들을 어떤 순서와 방식으로 실행할지 결정하는 것

 

Multiprocessor thread scheduling

(1) Load sharing

: 특정 CPU가 유휴 상태(idle)가 되면 전역 큐에서 다음 스레드를 가져와 실행한다.

- 글로벌 큐를 사용한다. 따라서 Idle-while-busy 문제가 없다. 모든 CPU에 작업이 고르게 분배된다.

- 각 CPU가 알아서 큐에서 작업을 가져오기 때문에 중앙 스케줄러가 필요 없다.

- 큐는FCFS, 가장 적은 스레드를 가진 프로세스를 우선으로 또는 preemtive로 다양한 방식으로 구현해봤을 때 차이가 별로 없다.

(어떤 프로세스를 먼저 실행할 지는 별로 중요하지 않다.)

 

단점

1. 여러 CPU가 동시에 전역 큐에 접근하려고 할 때 mutual exclusion 때문에 큐 자체의 병목 현상이 발생할 수 있다.

2. 캐시 효율성 저하: 선점됐던 스레드가 이전에 실행되던 CPU가 아닌 다른 CPU에서 실행을 재개할 가능성이 높다. 이전 CPU의 캐시에 남아있던 데이터는 무용지물이 돼서 캐시 효율이 떨어진다. CPU 개수가 n배여도 n배만큼 성능이 증가하지 않는다. (치명적인 단점)

3.모든 스레드가 하나의 큐에 섞여 있어서 특정 프로그램에 속한 모든 스레드가 동시에 실행되기를 보장하기 어렵다.

 

잠재적인 단점에도 불구하고 이 방식은 구현이 간단하고 효율적이어서 가장 널리 사용되는 방식이다.

- 다른 방식은 CPU가 수십개일 때 적합한 방법이다.

- 실제로 사용하는 프로세스들은 대부분 동기화 작업이 빈번하게 일어나지 않아서 load sharing을 사용해도 큰 문제가 없다.

 

(2) Gang scheduling

- 서로 밀접하게 관련된 스레드들의 묶음을 여러 CPU에 동시에 함께 스케줄링하는 방식

- medium이나 fine 단위의 병렬 처리 애플리케이션에 특히 유용하다. (동기화가 자주 발생)

- 레디 큐에는 애플리케이션이 줄을 서고 A라는 애플리케이션의 스레드가 10개라면 10개의 CPU를 할당해준다.

- 만족해야 하는 조건: CPU의 개수 >= Application의 thread 개수

- 각 애플리케이션은 N개의 CPU 전체 사용 시간의 1/M 만큼을 할당 받는다. (N개의 CPU를 M개의 애플리케이션이 사용하는 상황)

- 4개의 CPU를 2개의 애플리케이션이 사용한다면 각 애플리케이션은 전체 시간의 절반 동안 4개의 CPU를 모두 사용하며 자신의 스레드를 동시에 실행한다.

- 스케줄링 시 단순히 1/M로 나누는 것 외에 애플리케이션이 가진 스레드의 수에 따라 가중치를 두어 할당 시간을 조절할 수 있다. (아래 그림)

 

위의 그림은 4개의 CPU를 사용하여 4개의 스레드를 가진 그룹 1과 1개의 스레드를 가진 그룹 2를 실행하는 상황을 가정한 그림이다.

 

왼쪽은 두 그룹에게 시간을 1/2씩 공평하게 나누어 준다. 처음 1/2시간에는 그룹 1이 실행되고 4개의 CPU를 모두 사용한다. 나머지 1/2시간에는 그룹 2가 실행된다. 하지만 이 그룹은 스레드가 1개뿐이라 CPU 1개만 사용하고 나머지 3개는 유휴 상태가 된다. 결과적으로 37.5%의 자원 낭비가 발생한다.

 

오른쪽은 각 그룹의 스레드 수에 비례하여 가중치를 두어 시간을 분할한다. 그룹 1에게 시간의 4/5를, 그룹 2에게는 1/5를 할당한다.전체 시간의 4/5 동안 스레드가 많아서 모든 CPU를 사용하는 그룹 1을 더 길게 실행한다. 전체 시간의 1/5 동안 대부분의 CPU를 놀게 만든는 그룹 2는 더 짧게 실행한다. 결과적으로 자원 낭비가 15%로 크게 감소한다.

 

(3) Dedicated processor assignment

- 특정 애플리케이션의 스레드들을 정해진 CPU 집합에 고정하여 실행하는 방식이다.

- 애플리케이션이 실행될 때, 스레드 개수와 할당되는 CPU의 개수가 같다.

- gang scheduling과의 차이점: time sharing을 하지 않는다. (process switching x)

애플리케이션이 실행되는 동안, 할당된 CPU들은 오직 그 애플리케이션의 스레드만 처리하며 다른 애플리케이션과 절대 공유하지 않는다.

*gang: 여러 애플리케이션이 정해진 시간 단위로 CPU 그룹을 번갈아 가며 사용한다. 

 

[단점]

- 만약 어떤 스레드가 block되면 그 스레드에 할당된 CPU는 다른 일을 하지 못하고 그대로 유휴 상태가 된다.

- Processor Fragmentation: 놀고 있는 CPU는 충분히 많지만 이들이 흩어져 있어서 특정 애플리케이션이 필요로 하는 만큼의 CPU가 한 번에 할당되지 못하는 문제

 

CPU 개수

Load Sharing < Gang Scheduling < Dedicated processor assignment

 

(4) Dynamic scheduling

- os의 역할: 레디 큐에 있는 애플리케이션에 CPU를 할당해주는 역할

- 애플리케이션의 역할: 자신의 실행 가능한 스레드들 중 어떤 것을 실행할지 스스로 결정

 

CPU 요청 시 동작

애플리케이션이 5개의 CPU를 요청한 상황

- 5개의 쉬고 있는 CPU가 있으면 즉시 모두 할당한다. 만약 쉬고 있는 CPU가 5개보다 적으면 현재 가용한 만큼만 우선 할당한다.

- 쉬고 있는 CPU가 아예 없으면 다른 애플리케이션으로부터 뺏어오는 것을 고려한다. 새로운 요청의 우선순위가 높은 경우에는 현재 여러 개의 CPU를 사용 중인 다른 애플리케이션으로부터 CPU를 하나 뺏어와 할당할 수 있다.

- 당장 할당할 CPU가 없다면 사용 가능한 CPU가 생길 때까지 요청을 대기시킨다.

 

CPU 반납 시 동작

- 현재 할당받은 CPU가 하나도 없는 애플리케이션들에게 우선적으로 CPU를 하나씩 나누어 준다.

- 그러고도 남는 CPU가 있다면 큐에서 기다리고 있던 순서(FCFS)대로 나머지 애플리케이션들에게 할당한다.