[운영체제] CH3. Threads & Concurrency

0. Overview

1) Thread란 : A basic unit of CPU utilization

- thread ID, a program counter (PC), a register set, and a stack 으로 구성됨

- 같은 process의 다른 쓰레드와 code section, data section, and other operating-system resources 공유함

 

2) Single / Multithreaded Processes

 

경우에 따라 단일 응용 프로그램이 여러 개의 유사한 작업을 수행해야 할 수 있습니다. 예를 들어, 웹 서버는 웹 페이지, 이미지, 소리 등에 대한 요청을 수락해야 할 수 있습니다. 이러한 요청을 처리하는 한 가지 해결 방법은 서버를 클라이언트 요청을 수락하는 단일 프로세스로 실행하는 것입니다. 서버는 요청을 수신할 때 해당 요청을 처리하는 별도의 프로세스를 작성할 수 있습니다. 그러나 이 접근 방식에는 프로세스 생성에 리소스가 많이 소모되고 시간이 많이 소요되므로 몇 가지 단점이 있습니다.

다른 방법은 멀티스레딩을 사용하는 것입니다. 이 접근 방식에서 웹 서버 프로세스는 클라이언트 요청을 수신하기 위해 별도의 스레드를 작성할 수 있습니다. 요청이 있을 때 서버는 새 프로세스를 만드는 대신 추가 요청을 계속 수신하는 동안 해당 요청을 처리할 새 스레드를 작성할 수 있습니다. 이 방법은 각 요청에 대해 새 프로세스를 만드는 것보다 더 효율적입니다. 리소스 및 시간 측면에서 스레드 생성 비용이 덜 들기 때문입니다. 또한 스레드는 동일한 프로세스 내에서 메모리와 리소스를 공유할 수 있으므로 성능을 향상시킬 수도 있습니다.

 

대부분의 os system kernel은 멀티스레드임

 

멀티스레드의 장점

• Responsiveness : 일부가 막히거나 너무 오랜 시간 수행하더라도 계속 실행이 가능함
• Resource Sharing : 프로세스는 shared memory와 message passing과 같은 기술을 통해 리소스를 공유할 수 있음
• Economy : threads가 resource를 공유하기 때문에, context-switch, create thread가 더욱 경제적임 
• Scalability : 쓰레드가 다른 프로세싱 core에서 평행하게 실행되는 멀티프로세서 상에서 더 greater

 

1. Multicore Programming

1) Multicore Programming이란

: 여러 computing cores를 보다 효율적으로 사용하고 concurrency(동시성)을 향상시키는 매커니즘

• single computing core
  • 시간당 쓰레드 1개 수행. 프로세싱 코어가 한 번에 하나의 스레드만 실행할 수 있기 때문에 쓰레드 실행이 interleaved 됨 (여러개 돌아가는 척!!!)
• multiple cores
  • 쓰레드 n개 동시 수행. 시스템이 각 코어에 별도의 스레드를 할당할 수 있기 때문에 일부 스레드가 병렬적으로 실행될 수 있음

• Parallelism : 시스템이 두 개 이상의 작업을 동시에 수행할 수 있음
• Concurrency : 모든 작업이 진행되도록 허용하여 동시에 둘 이상의 작업을 지원함

multicore system을 프로그래밍 할 때 해결해야 하는 5가지 영역

1. Identifying tasks

✓ To find areas that can be divided into separate, concurrent tasks

2. Balance

✓ Ensure that the tasks perform equal work of equal value

3. Data splitting

✓ The data accessed and manipulated by the tasks must be divided to run on separate cores

4. Data dependency

✓ The data accessed by the tasks must be examined for dependencies between two or more tasks

5. Testing and debugging

✓ Testing and debugging such concurrent programs is inherently more difficult than testing and debugging single-threaded applications

 

 

Parallelism의 종류

• Data parallelism
  • 같은 데이터를 multiple computing core로 나눠서 각 core가 같은 operation을 수행함
• Task parallelism
  • data를 나누지 않고, task를 각 core가 나눠가짐 (동일 데이터 다른 operation)

 

 

2) Amdahl's Law 

: 추가적으로 computing core를 추가했을 때 얻을 수 있는 performance(속도 향상) 계산하는 공식

S : portion of the application that must be performed serially on a system (무조건 시퀀셜하게 수행되어야하는 것의 수)

N : processing core 수 

 

프로그램이 두 부분으로 구성되어 있는데 그 중 하나는 병렬화할 수 있고 다른 하나는 병렬화할 수 없는 경우임. 최대 속도 향상은 병렬화할 수 없는 부분에 의해 결정됨. 

 

N이 무한대로 가면, speed up coverge는 1 / S로 수렴함. 

일부는 Amdahl's Law가 하드웨어의 향상을 고려하지 않았다고 말하기도...

S가 클 수록, 즉 병렬화 불가능한 것이 50%면 최대 2배까지만 증가할 수 있음

 

2. Multithreading Models

 

User Threads : 커널 위에서 지원되며 커널 지원 없이 관리됨

 

kernal space: core와 연결하는 bridge 역할을 함. 이 안에 커널 레벨 스레드가 존재함

이 위에 있는 user space에 있는 것이 유저 레벨 스레드!

 

Thread library는 thread를 생성하거나 없애는 코드, threads간 데이터와 메시지를 넘겨주는 코드, thread execution을 스케줄링하는 코드, thread context를 저장하거나 불러오는 코드를 포함하고 있음

 

장점 

• Thread switching 할 때 kernel mode 권한을 필요로 하지 않는다
• 유저 스레드는 어느 os에서나 실행된다
• 유서 스레드는 만들고 관리하는게 빠르다

단점

• 한 유저 스레드가 blocking operation을 수행하면 모든 프로세스가 blocked 된다
• 멀티스레드 application은 multiprocessing의 이점을 갖지 못한다.
  • user thread는 user level에서 관리되기 때문에 운영 체제가 multiple process를 넘어서 scheduling thread 할 수 없음. 따라서 user thread를 사용하는 멀티스레드 응용프로그램은 멀티프로세싱을 활용하기 어려움

 

kernel threads : OS에 의해 직접적으로 지원되고 관리되는 스레드

 

장점

• 커널 스레드의 서로 다른 프로세서에서 동일한 프로세스의 멀티 스레드를 스케줄링 할 수 있음
• 한 프로세스가 blocked 되어도, 커널이 같은 프로세스의 다른 스레드로 스케줄링 할 수 있음

단점

• 한 스레드에서 다른 프로세스로 전송하기 위해서는 커널 모드로 switch 해야함
• 스레드 operation이 user thread에 비해 100배 이상 느림

커널이 사용자 수준 스레드의 존재를 인식하지 못하고 스레드가 아닌 프로세스를 예약하고 관리하기 때문에 사용자 스레드가 있는 다중 스레드 응용 프로그램에서 다중 처리를 최대한 활용하기 어렵습니다. 이는 커널이 프로세스 내에서 사용 가능한 스레드 수에 관계없이 프로세스에서 한 번에 하나의 스레드만 예약할 수 있음을 의미합니다. 결과적으로 시스템에 여러 개의 프로세서가 있더라도 한 번에 하나의 스레드만 실행할 수 있고 다른 프로세서는 유휴 상태를 유지할 수 있습니다.

반대로 커널 수준 스레드를 사용하면 커널이 프로세스의 모든 스레드를 인식하고 여러 프로세서에서 스레드를 보다 효율적으로 예약할 수 있으므로 스레드가 동시에 실행되고 다중 처리를 최대한 활용할 수 있습니다. 또한 커널 수준 스레드는 사용자 수준 스레드에서는 불가능한 전체 프로세스를 차단하지 않고 차단 작업을 수행할 수 있습니다.

 

1) Many-to-One Model

 

여러개의 user thread - 하나의 kernel thread

한 번에 하나의 스레드만 커널에 액세스할 수 있으므로 multicore system 상에서 여러 스레드를 병렬로 실행할 수 없음.

 

2) One-to-One Model

user thread - kernel thread 1대1 대응

many to one 보다 concurrency ! 동시에 여러 작업 처리 가능

multiprocessor 에서 parallel 하게 실행됨

이 모델의 유일한 단점은 유저 스레드를 생성하려면 해당 커널 스레드를 생성해야 하며,  커널 스레드가 많아져 시스템 성능에 부담을 줄 수 있다는 것임

 

3) Many-to-Many Model

 

one-to-one과 many-to-many의 단점을 해결함

유저 스레드는 그것과 같거나 적은 수의 kernel thread와 연결됨. kernel thread의 수는 application이나 machine에 따라 결정될 수 있음

 

◦ many-to-one model은 개발자가 원하는 만큼의 유저 스레드를 만들 수 있지만 커널이 한 번에 하나의 커널 스레드만 예약할 수 있기 때문에 병렬 처리가 되지 않음
◦ one-to-one model 은 더 큰 동시성을 허용하지만 응용프로그램 내에 너무 많은 스레드를 만들게 될 수도 있음

• many-to-many model은
◦ 개발자는 필요한 만큼의 사용자 스레드를 생성할 수 있으며 해당 커널 스레드는 멀티프로세서에서 병렬로 실행
◦ 또한 스레드가 blocking system call을 수행해도 커널은 다른 스레드의 실행을 scheldule 할 수 있음

 

4) Two-level Model

many-to-many model과 거의 유사하지만, 하나의 유저 스레드가 하나의 커널 스레드를 담당할 수도 있음