공룡책 Ch 4 요약 (원서를 읽고 요약하는 과정에서 잘못된 내용이 있을 수 있습니다.)

1. Thread Overview

• 한 번에 하나의 작업만을 수행하는 전통적 의미의 단일 프로세스는 싱글 스레드 방식이 되며, 프로세스가 여러 개의 스레드를 가지게 될 경우 동시에 여러 작업을 수행할 수 있음

• 웹서버(Web Server)는 대표적인 멀티스레딩 구조로, 클라이언트의 여러 요청이 동시다발적으로 들어올 때 여러 스레드가 이를 동시에 처리함으로써 한 번에 하나씩 처리할 때보다 더욱 빠르게 응답할 수 있음
• 스레드는 스레드 아이디, 프로그램 카운터(PC), 레지스터 집합(Register Set) , 스택 메모리 공간(Stack) 을 가지고 있는 프로세스 내부의 작업 실행 단위를 말함
• 언급한 요소들을 프로세스로부터 프로세스가 개별적으로 할당받아 사용하게 되며, 이외의 코드(Code) , 전역 데이터 및 파일(Data , Files )은 여러 스레드가 공유하는 구조임

​

1-1. Benefits

멀티스레딩 방식의 장점에 대해 알아보자

• Responsiveness : 한 번에 여러 개의 작업을 처리할 수 있기 때문에 하나의 작업에 문제가 있더라도 다른 작업은 계속해서 수행할 수 있다는 점에서 높은 반응성을 보임

  (멀티스레딩 방식의 웹서버를 생각하면 됨)

• Resource Sharing : 여러 스레드는 하나의 프로세스가 가진 메모리와 자원을 공유하며, 이를 통해 여러 스레드의 작업이 동일한 공간(same address space)에서 일어나도록 할 수 있음

• Economy : 여러 스레드가 프로세스의 자원을 공유하는 방식은, 다른 작업을 수행하기 위해 별도로 프로세스를 만들고 이를 위한 Context-Switching 을 수행하는 것 보다 훨씬 경제적임

• Scalability : 멀티 프로세서 구조에서 멀티 스레딩을 적용할 경우, 여러 프로세서(코어)에 각각의 스레드가 병렬적으로(paralell) 돌아가게 함으로써 더욱 확장성 높은 구조로 발전시킬 수 있음

  (The benefits of multithreading can be even greater in a multiprocessor architecture, where threads may be running in parallel on different processing cores.)

2. Multicore Programming

• 멀티코어(multicore) 시스템은 하나의 칩(processing chip)에 여러 개의 코어(computing cores) 가 붙어 있는 구조로, 여기서 운영체제는 각각의 코어를 개별적인 CPU 자원으로 인식하게 됨

• 개별 코어는 한 번에 하나의 스레드 작업만을 처리할 수 있으며 , 멀티 코어 환경에서의 동시성(concurrency) 의 의미는 결국 여러 코어에 각각의 스레드 작업을 할당하여 동시에 실행될 수 있도록 하는 것을 의미함

• 여기서 병렬성(parallelism) 과 동시성(concurrency) 을 구분하여 알 필요가 있는데, 병렬성은 동시에 하나 이상의 작업을 수행할 수 있는 것을 의미하며 동시성은 여러 작업이 모두 처리될 수 있도록 여러 작업을 모두 지원하는 것을 의미함

• 동시성의 경우 ‘동시’라는 것이 정말로 정확히 같은 시간에 여러 작업을 처리하는 것을 의미하는 것이 아닌, 문맥 교환(Context Switching)을 통해 여러 작업을 잘게 쪼개서 순차적으로 처리함으로써 결국 모든 작업이 고르게 실행되는 식으로 흘러가도록 하는 것을 의미함.

  • 따라서, 병렬성이 굳이 담보되지 않아도 동시성을 충족시키는 것이 가능함.
  • 한 번의 하나의 작업만 처리할 수 있는 상황에서 여러 프로세스 간의 잦은 문맥교환을 통해 동시성을 만족시키면, 결과적으로 모든 프로세스가 동시에 동일하게 동작하는 것 같이 보이지만 실제로 병렬 처리된 것은 아닌 것

  (A concurrent system supports more than one task by allowing all the tasks to make progress. In contrast, a paralel system can perform more than one task simultaneously.)

​

2-1. Programming Challenges

멀티 코어 시스템 환경에서 직면하게 되는 5가지 문제들

• 작업의 정의(Identifying tasks) : 여러 독립적인 작업들을 병렬로 처리하고자 할 때, 어플리케이션의 작업 전체를 어떤 기준으로 어떻게 동시적인 작업 단위로 분할할 것인 지를 정의해야 함

• 균형(Balance) : 분리된 개별 작업들은 동일한 값의 동등한 양의 작업을 수행하는 구조여야 함

  (Programmers must also ensure that the tasks perform equal work of equal value.)

• 데이터 분할(Data splitting) : 어플리케이션의 전체 작업이 개별 작업 단위로 나뉘면, 나뉜 작업들이 접근하고 다루는 데이터 또한 각각의 코어에서 다룰 수 있도록 나뉘어야 함

• 데이터 의존성(Data dependency) : 분할된 작업들에 의해 다뤄지는 데이터는, 이것이 두 개이상의 작업에 의존적인 지를 반드시 고려해야 하며, 하나의 작업이 다른 작업이 다루는 데이터에 접근할 경우에는 작업들 간의 순를 명확히 함으로써(synchronized) 데이터의 상태가 항상 최신을 유지할 수 있어야 함

• 테스트 및 디버깅(Testing and Debugging) : 싱글 스레드보다 멀티 스레드 환경에서의 디버깅이 훨씬 까다롭고 어려움

​

2-2. Types of Parallelism

데이터 측면의 병렬성과, 작업 측면의 병렬성에 대해 각각 알아보도록 한다.

Data parallelism

• 각각의 코어에 동일한 데이터를 배분하여 모두 같은 작업을 수행하는 개념

  (Distributing subsets of the same data across multiple computing cores and performing the same oepration on each core.)

• 예를 들어 1부터 10까지의 합계를 구하는 작업을 수행하고자 할 때, 싱글 스레드라면 반복문을 통해 1부터 10까지 차례대로 더하면 되지만 2개의 스레드로 이를 병렬처리하면 하나는 1부터 5까지, 나머지는 6부터 10까지 더한 후 합하면 됨

Task parallelism

• 데이터가 아닌 스레드로 대표되는 작업 자체를 코어에 배분하여 작업을 수행하는 개념으로 각각의 스레드는 독자적인 작업(unique operation)을 수행함

  (Distributing not data but tasks(threads) across multiple computing cores)

• 위와 달리 각기 다른 스레드가 동일한 데이터에 접근하는 상황도 포함함

​

3. Multithreading Models

• 운영체제에서 스레드에 대한 지원은 유저 수준과 커널 수준으로 나눠볼 수 있음
• 유저 스레드는 커널 상위 수준에서 관리되며 커널의 개입이 없는 반면, 커널 스레드는 운영체제에 의해 직접 관리됨
• 유저 스레드와 커널 스레드 간의 관계를 크게 3가지 모델로 나눠볼 수 있음

​

3-1. Many-to-One Model

• 여러 개의 유저 스레드가 하나의 커널 스레드와 관계를 맺는 구조
• 스레드의 관리는 유저 공간에 위치한 스레드 라이브러리에 의해 수행되며, 커널에의 접근이 없기 때문에 비용상 효율적임
• 하지만 특정 스레드가 작업을 차단하는 시스템 호출을 일으킬 경우에는 전체 프로세스가 멈추게될 수도 있음
• 커널 스레드에는 한 번에 하나의 유저 스레드만 접근할 수 있으며, 이로 인해 멀티 코어 환경에서 병렬적으로 여러 스레드의 작업을 수행하는 것이 불가능함
• 이로 인해 멀티 코어 시스템의 이점을 살릴 수 없기 때문에 잘 사용되지 않는 모델임

​

3-2. One-to-One Model

• 여러 유저 스레드가 각각 하나의 커널 스레드에 일일히 대응되는 구조
• One-to-One과 비교했을 때, 하나의 스레드가 작업을 차단해도 다른 스레드가 작업을 계속해서 수행할 수 있기 때문에 동시성을 더욱 보장할 수 있음
• 단, 하나의 유저 스레드를 생성할 때마다 이에 대응되는 커널 스레드를 일일히 만들어야 하는 퍼포먼스적인 부담이 존재함
• 리눅스 및 윈도우 계열의 여러 운영체제에서 One-to-One을 사용하고 있음

​

3-3. Many-to-Many Model

• 여러 유저 스레드가 전체 유저 스레드의 양보다 같거나 작은 규모의 커널 스레드와 관계를 맺는 구조
• 커널 스레드의 수는 특정 기계나 어플리케이션 환경에 따라 상이할 수 있음
• One-to-One과 비교했을 때, 동시성을 보장하면서 더 적은 양의 커널 스레드를 생성하면 되는 이점이 있음
• 이를 변형하여 전체적으로는 Many-to-Many의 구조를 유지하면서 일부 One-to-One의 형식을 섞은 two-level model 도 존재함
• 시스템의 향상으로 인해 코어의 개수가 많아지면서 커널 스레드의 수를 제한하는 것이 점점 덜 중요해지기 때문에 One-to-One이 사실상 더 많이 쓰이고 있음

​

4. Implicit Threading

• 스레드의 생성 및 관리 책임을 개발자가 아닌 라이브러리나 컴파일러에 넘기는 것을 암묵적 스레딩(implicit threading) 이라고 부름
• 멀티 코어 프로세싱이 갈수록 복잡해지면서 수백, 수천개 규모의 스레드를 포함하는 규모로 어플리케이션이 진화함에 따라 개발자가 스레드의 생성 및 관리에 대한 책임을 온전히 지는 것이 점점 부담스러워지기 때문에 이를 라이브러리나 컴파일러에 위임하는 것
• 암묵적 스레딩에서 개발자에게 주어진 책임은 스레드의 생성 및 관리가 아닌, 스레드가 수행할 작업(task)를 정의하는 일이 됨

​

4-1. Thread Pools

• 멀티 스레딩 환경에서 직면하는 문제는 크게, 스레드를 매번 생성할 때마다 드는 시간을 고려해야 한다는 점과 한정된 자원으로 인해 스레드를 과도하게 만들 경우 자원의 낭비가 일어난다는 점임
• 이에 대한 해결책으로 미리 일정한 양의 스레드가 생성된 스레드 풀(thread pool)을 둔 후, 이후 필요에 따라 풀에 있는 스레드를 꺼내서 작업을 부여하는 방식을 생각해볼 수 있음
  • 스레드 풀의 생성은 어플리케이션의 시작 시점에 이루어짐
• 스레드 풀에서 사용 가능한 스레드가 있으면 큐에서 작업을 꺼내 스레드에 할당하고, 그렇지 않을 경우에는 사용 가능한 스레드가 있을 때 까지 작업이 큐에서 대기하게 됨
• 이러한 방식은 매번 스레드를 생성하는 것보다 더욱 빠르며, 제한된 자원을 좀 더 효율적으로 사용할 수 있고, 매 번 스레드에 작업을 할당할 때마다 시간 간격을 두는 등 작업 수행 시점마다 다른 로직을 적용할 수 있는 등의 이점이 있음

​

4-2. Fork Join

• Fork/Join은 병렬처리를 위한 대표적인 모델 중 하나로 단어 뜻 그대로 여러 개의 스레드로 나눠 작업을 수행하는 fork 와, 나뉘어 수행된 작업의 결과를 모두 합치는 join 의 과정을 거치는 구조임
• 부모 스레드가 두 개 이상의 자식 스레드로 나뉘면(fork), 부모 스레드는 자식 스레드들의 작업이 모두 끝날 때 까지 대기한 후 자식 스레드들의 작업 결과를 얻게 되는 것(join)
• fork 과정에서 스레드가 직접 구성되기 보다는 병렬적으로 수행할 작업이 지정된다는 점에서 암묵적 스레딩의 하나로 볼 수 있음
• Java의 경우 Java7 이후로 제공되는 fork-join library 의 사용을 통해 병렬 프로그래밍이 가능하며, 내부적으로 재귀적인 분할 정복 알고리즘(recursive divide-and-conquer algorithm)을 적용하고 있음
  • 또한 각 스레드가 작업 큐를 보유하고 있는 상황에서, 작업 큐가 비어있는 스레드가 다른 스레드의 작업 큐로 부터 작업을 훔쳐와서 수행하는 work-stealing algorithm 이 적용되있음

Reference

• Abraham Silberschatz, Greg Gagne, Peter B. Galvin Operating System Concepts , Wiley

• 위키 피디아 병렬 컴퓨팅

• 멀티 코어 프로세서란? - 동커벨

• 동시성과 병렬 처리의 차이점

• Wikipedia Fork-join model