Classifications of Multiprocessor Systems

Multiprocessor System은 세가지로 구분할 수 있다.

1. Loosely coupled or distributed multiprocessor, or cluster

각각의 CPU 가 자기 메모리, 자기 I/O 채널을 가지고 있다.

consists of a collection of relatively autonomous systems, each processor having its own main memory and I/O channels

Autonomous System

각자 자기 OS 를 실행한다.

⇒ 각자 하나의 독립적인 컴퓨터가 네트워크로 연결해서 사용하는 시스템이다.

2. Functionally specialized processors

CPU O, I/O, 서로 다른 기능을 하는 여러 Processor 들이 하나의 Computer 안에 있다.

there is a master, general-purpose processor; specialized processors are controlled by the master processor and provide services to it

3. Tightly coupled multiprocessor ✅

CPU 가 여러개 있으며 메모리 하나를 공유하고 OS가 하나 존재한다.
⇒ 하나의 OS 가 여러 CPU 작업을 한번에 관리한다.

우리가 앞으로 multiprocessor 라고 말할 애이다.

consists of a set of processors that share a common main memory and are under the integrated control of an operating system

---

Synchronization Granularity and Processes

Schedululing 은 좋은 성능을 내는 것이 목적이다.

9장에서는 CPU 1개로 프로세스 실행시간이 중요했지만, 10장에서는 CPU가 여러개 이므로 프로세스의 실행시간 보다는 동기화 시간 간격 이 중요해졌다.
프로그램을 구성하는 스레드나 프로세스가 얼마나 빈번하게 동기화 하느냐에 따라 스케쥴링하는 방법이 달라진다.

1. Independent

한 시스템에 여러 프로그램이 동시에 실행이 되는데 독립적으로 실행된다.

동기화 간격

개별적으로 동작하기 때문에 동기화하지 않는다.

2. Very Coarse

Client 와 Server 사이에 networking 을 통해서 request 와 response 를 주고 받는 것이다.

동기화 간격

2000 instructions 당 동기화 1번씩한다.

3. Coarse

하나의 application 이 여러개의 프로세스로 만들어진 경우

동기화 간격

200 instructions 당 동기화 1번씩한다.

4. Medium

하나의 application 이 여러개의 스레드로 만들어진 경우

동기화 간격

20 instructions 당 동기화 1번씩한다.

Medium 과 Coarse 에서 여러개의 thread 와 process 의 차이?

→ 같은 작업을 한다고 할 때, 동기화 통신 빈도가 어떻게 될까?

Thread 의 경우 code, data 공간을 공유하기 때문에 data 를 주고 받으며 통신할 수 있다.

이때, Process 는 OS 를 거쳐 통신해야하는 반면, Thread 는 OS 를 거칠 필요가 없이 통신이 가능해 빈번하게 동기화가 이루어진다.

5. Fine

특수 목적으로 만들어진 Parallel Program 으로, 굉장히 많은 Data set에 대해여 굉장히 많은 computation 을 한다.

굉장히 많은 CPU에게 일을 나누어준다.
⇒ 굉장히 밀접하게 서로 동기화를 많이 해야한다.

동기화 간격

20 미만의 instructions 당 동기화 1번씩한다. (빈번하게 동기화)

스케쥴링을 어떻게 하면 좋을까?

1, 2, 3 은 실행시간이 길고 짧은 건 중요하지 않다.
↔ 그러나 4, 5는 실행시간이 길고 짧은 것이 중요하다.

⇒ 스케쥴링을 어떻게 하면 좋을까? → 결국 어떤 프로그램이냐가 중요하다!

---

Scheduling Design Issues

Scheduler 를 만들 때, 3가지 이슈가 존재한다.

1. Assignment of processes to processors
2. Use of multiprogramming on individual processors
3. Actual dispatching of a process

1. Assignment of processes to processors

각각의 프로세스에게 CPU 를 어떻게 할당할까? → Ready Queue 여러개 생성

원래 CPU 가 1개일때는 Ready Queue에 들어 있는 Process 가 CPU 를 가져갔는데 이제는 CPU가 여러개이기 때문에 Process 가 어느 CPU 로 가야할지 고민해야 한다.

2. Use of multiprogramming on individual processors

multiprogramming 을 할지말지를 고민해야한다.

3. Actual dispatching of a process

그래서 어떤 순서로 프로세스를 실행해야할까?

The approach taken will depend on the degree of granularity of applications and the number of processors available

---

1. Assignment of Processes to Processors

(1) Permanently assign process to a processor

CPU 마다 Ready Queue 를 따로둔다.
시스템 안에 CPU가 10개이면, Ready Queue도 10개가 있는 것이다.
→ 1번 CPU 를 위한 Ready Queue ~ 10번 CPU 를 위한 Ready Queue

프로세스가 시스템에 들어오게 되면 OS 가 10개 중 하나의 CPU Ready Queue 로 보내준다.

이때, 각각의 CPU 입장에서는 자기 Queue 에 있는 프로세스만 실행시키면 된다. (마치 9장의 uni-processor 처럼)

Idle-while-Busy

프로세스마다의 실행시간을 모르기 때문에 어떤 CPU 에는 실행시간이 긴 프로세스만 줄 서 있을 수 있고, 다른 CPU 에는 실행시간이 짧은 프로세스만 줄을 서 있을 수 있다. 따라서 어떤 CPU 는 계속 일하는 반면, 다른 CPU 는 계속 놀고 있을 수도 있다(Idle-while-Busy).

• Dedicate short-term queue for each processor
• Less overhead
• Processor could be idle while another processor has a backlog

(2) Global queue ✅

각각의 CPU가 작업을 마치면 OS 를 실행시켜서 다음에 실행시킬 프로세스를 찾아가는 방법이다. 실행을 마칠때마다 프로그램을 찾아서 실행시키기 때문에 모두가 일을 할 수 있게 된다.

Schedule to any available processor

---

2. The Use of Multiprogramming on Individual Processors

multiprogramming 을 할지말지를 고민해야한다.

Multiprogramming

메모리 안에 여러 프로그램이 있는데 이 중, 하나의 프로그램이 I/O 작업으로 Block 이 되면 다른 프로세스를 실행하는 것이다.

프로그램을 실행한 뒤 I/O 가 발생하면 Blocked X, Switching X

만약 5가지 종류의 동기화 단계의 프로그램들 중 완전히 Independent 하거나Coarse-grained 단계의 애들은 당연히 Multiprogramming 이 필요하다. 동기화 작업을 하지 않기 때문에 Block 되면 무조건 I/O 작업 때문이다.

그러나, 나머지 3단계는 Multiprogramming 을 안하는게 좋을 수도 있다.

Multiprogramming 을 안하는게 좋을 수도있는 이유

Block 이 되는 세가지 상황

• I/O
• Semaphore Wait
• Message Recieve

프로세스간 동기화가 빈번하다고 가정하자.

CPU가 1개일 때는 내가 Message Recieve 를 받아야하는데 상대방이 send 할때까지 Wait 했어야 한다. 즉, CPU 를 양보해줬어야 한다.

CPU가 여러개일 때

• I/O 작업은 Blocked 된다.
• Semaphore Wait 하려는데 이미 Semaphore 가 0 이라 Block 이 되어야 하기에 Switching 을 한지만 하는데 시간이 걸리게된다. 그런데, CPU 가 여러개이기 때문에 다른 CPU 가 Signal 을 해주어서 조금만 더 기다리면 SemWait 를 통과할 수 있었지만 Block 을 한 상황이 된다.
• Message 도 마찬가지이다. 나를 BLock 에서 풀어줄 사람이 다른 CPU 에서 작업 중이라면 굳이 Block 되지 않고 잠깐 기다리면 된다.

Coarse-grained or independent synchronization granularity

얘네들은 동기화를 거의하지 않기 때문에 Block 을 해주어야 한다.
⇒ Multiprogramming 이 필요하다.

Each individual processor should be able to switch among a number of processes to achieve high utilization and better performance

Medium-grained application running on a multiprocessor with many processors

동기화가 빈번하기 때문에 Block 을 안하고 잠깐 기다리게 한다.
⇒ 어떤 종류의 프로그램이냐에 따라 Multiprogramming 을 할지 안할지 선택한다.
⇒ Busy-Waiting 이 필요하다.

An application that consists of a number of threads may run poorly unless all of its thread are available to run simultaneously

---

Process Dispatching

어떤 순서로 Scheduling 할 것인가?

Specific scheduling disciplines is less important with more than one processor

X 축

실행시간이 짧은 것과 긴 것이 얼만큼 섞여있는가?

• 값이 작을 수록 실행시간이 같은 애들끼리 섞여 있다. → 어떤 순서로 스케쥴링해도 상관 없다. 달라질 게 없다.
• 값이 클 수록 실행시간이 길고 짧은 애들이 엄청 섞여 있는 상황이다. → 어떤 순서로 스케쥴링하는것이 상관 O

Y 축

Througput을 의미한다.

Througput: 짧은 거 부터 하면 좋다. 값이 클수록 좋다.

y 값이 증가할 수록 FCFS 보다 다른 방식의 성능이 더 좋은 것이다.

• 왼쪽 그림은 RoundRobin VS. FCFS
• 오른쪽 그림은 SRT VS. FCFS

FCFS: 최악의 스케쥴링 기법이다.

Dual Processor

Single Processor 에 비해 Dual Processor 는 거의 성능 차이가 없다.
⇒ 프로세스 실행시간에 편차가 있어도 거의 차이가 없다.

Q. 9장의 여러가지 방식으로 스케쥴링할시, reponse time이 여러가지 기법들간의 차이 확인하기

CPU 의 개수에 따른 제일 Response time 이 짧은 애와 Response time 이 긴 애의 차이를 확인하기

Q. 왜 CPU 가 늘어날 수록 reponse time 이 영향을 안미칠까?

↳ 계산대가 여러개 있을 때, service 시간이 하나가 길어도 다른 짧은 process 들은 다른곳에서 처리가 가능하기 때문에, Waiting Time 이 상관이 없다.
⇒ 따라서 전체적 Response time 은 그렇게 중요하지 않다.

모든 프로그램이 아니라 우리가 사용하는 프로그램이 얼만큼 동기화를 하는지가 주요하다.
⇒ Processor 의 개수가 중요하다.

FCFS 가 제일 좋지 않을까?

• Starvation X
• Fair O
• Overhead X

---

Thread Scheduling

An application can be a set of threads that cooperate and execute concurrently in the same address space

Small differences in thread management and scheduling can have a significant performance impact

Multiprocessor thread scheduling

프로세스 처리순서는 더 이상 중요하지 않고, Multiprogramming 을 하냐 하지 않냐가 중요해졌다.

• 프로세스가 동기화 하는 정도
• 다른 프로세스가 다른 프로세서 사이에서 실행이 가능한지? 가 중요하다.

결론

application 이 여러 스레드 집합으로 이루어져 있을 때 Multiprocessor System 에서는 한 application 의 스레드들을 동시 실행시키는게 굉장히 중요하다. Ready Queue 에 줄 설 때 스레드들이 각자 줄을 서 있는게 아니라, Process 가 줄을 서는 것이다. (프로세스 단위로) 프로세스 하나를 실행시키면, 이 프로세스의 스레드 개수를 파악하고, 스레드 다섯개 이면, CPU 다섯개를 확보해서 5개의 스레드를 동시에 실행시키는게 굉장히 중요하다.

⇒ Perfomance impact 가 크다.

4가지 스케쥴링 기법이 존재한다.

1. Load sharing

↳ 동시 스레드 실행 보장하지 못하는 방식이다.

2.Gang scheduling

↳ 항상 다른 프로세스 안에 속해 있는 애들을 동시 실행하는 것을 보장하는 방식이다.

단, 조건: 스레드의 개수 < CPU 의 개수
→ 보장이 안되는 경우 Global Queue 를 사용하고, Load Sharing 을 사용할 수 밖에 없다.

3. Dedicated processor assignment

↳ 항상 다른 프로세스 안에 속해 있는 애들을 동시 실행하는 것을 보장하는 방식이다.

단, 조건: 스레드의 개수 < CPU 의 개수
→ 보장이 안되는 경우 Global Queue 를 사용하고, Load Sharing 을 사용할 수 밖에 없다.

4. Dynamic scheduling

↳ 가능한 최대한 동시 실행을 보장하지만, 안되면 어쩔 수 없이 넘어간다.

---

Load Sharing

global queue 를 사용한다.

여러개의 CPU 가 존재한다. ← 2개, ..., 16, 32 개 정도
↳ 각각의 CPU 는 작업이 끝나면 다음 작업할 것을 가져온다.
⇒ Load 가 완벽히 분산 된다. ⇒ 모든 CPU 가 똑같은만큼 계속 일한다.

An idle processor selects a thread from the global queue

• Even load distribution across the processors
• No idle-while-busy (누구는 놀고 누구는 일하는 일이 발생하지 않는다.)
• No centralized scheduler required

Global queue +

Global queue 자체가 Critical Section 이다.

실제 실행순서 (Dispatching)

• FCFS
  ↳ 가장 편하다. CPU 가 2개만 되어도 순서가 상관이 없기 때문이다.
• Smallest number of threads first (SNP 처럼)
  ↳ 스레드를 가장 적게 가진 애
• Preemptive smallest number of threads first (SRT 처럼)

Central queue needs mutual exclusion

queue 는 Critical Section 이어야 한다.

ex) A CPU 와 B CPU 가 하나의 Queue에 동시접근을 하면 안되기 때문에 
⇒ 다른 CPU 는 하나의 큐에 동시에 접근할 수 없도록 한다.
⇒ Queue 는 Critical Section

Performance Bottleneck

may be a bottleneck when more than one processor looks for
work at the same time

제일 큰 문제점은 bottleneck 이다. 이것 때문에 실행 속도가 느려질 수 있다.

Performance Bottleneck 해결을 위해 Queue 를 별도로 두는 것이다. (하지만 이게 idle while busy 상황보다는 낫다고 판단함)

Preemptive threads are unlikely resume execution on the same processor

cache use is less efficient

CPU 를 계속 옮겨 다니면 Cache 는 쓸모가 없다.

동시에 CPU를 잡는다는 보장이 없다.

If all threads are in the global queue, all threads of a program will not gain access to the processors at the same time

CPU 가 1개일때보단 2개일때 성능이 좋다. 하지만 그렇게 좋아지진 않는다. (2배, 4배 이렇게 증가하진 않는다.)

결론

Despite the potential disadvantages, load sharing is one of the most commonly used schemes

여러가지 단점에도 불구하고 load sharing 은 가장 많이 사용되는 기법이다. 뒤에 나오는 기법들은 CPU 가 수십 ~ 수백개인 경우여야 한다.

But, 우리가 쓰는건 10개정도 뿐이기에 load sharing 이 최선이다!