[공룡책🦖] 쓰레드 & 동시성 Threads & Concurrency

본 포스팅은 공룡책으로 불리는 Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 10th』 기반으로 정리한 글입니다.

---

Overview

Thread란?

• 하나의 process에 존재하는 LWP (Lightweight Process) 
• CPU utilization의 기본 단위
• thread ID, program counter(PC), register set, stack으로 구성
• 동일한 process에 속하는 다른 thread들과 core, data, resource, file signal 공유
• 동시에 하나 이상의 task 실행 가능

현대 운영체제는 한 process가 다중 스레드를 포함하기에, 다중 CPU를 제공하는 multicore system에서 thread를 통한 병렬 처리가 중요하다.

 

application이 비슷한 여러 task를 수행할 일이 많기에 multi thread process를 사용한다.

ex) 여러 client들의 비슷한 request를 처리하는 web server

multit thread process의 경우 code, data, files는 동일하되 thread별로 registers, stack, PC를 각각 구비한다.

 

 

Single-thread process VS Multi-thread process

Multithreaded server architecture

• Single-thread process를 여러 개 생성하여 일 처리 → 시간, 자원 소모가 큼
• Multi-thread process → 한 process가 더 효율적으로 여러 일을 처리할 수 있음

⇒ 요청할 때마다 process를 생성하지 않음 → Thread 단위로 처리해서 자원과 시간 사용을 효율적으로 함

 

 

장점

1. Responsiveness
   • 스레드 단위로 분리하여 한 작업에 대해 응답을 기다리지 않고 다른 작업 수행 가능
   • UI 처리할 때 blocking 할 필요 없이 non blocking으로 계속 실행 가능
2. Resource Sharing
   
   • Process와 Process 처리할 때 자원 공유
   • 동일 주소 공간 내에 다른 여러 스레드 가질 수 있음
3. Economy 
   • 프로세스 생성하려면 메모리와 자원을 할당하는데 cost 소요
   • Process 내 thread 생성하여 자원을 공유하며 처리하는 것이 더 경제적
   • thread 생성이 process 생성보다 비용 저렴
   • thread 간 Context switching은 process보다 빠름
4. Scalabiliy
   • multiprocessor 구조의 이점으로 thread는 다른 core에서 병렬 수해 가능
   • core가 많더라도 single-threaded process는 한 프로세서에서만 실행

 

 

 

Multicore Programming

multi core를 효율적으로 사용하고 병행성을 향상시키는 프로그래밍 방법

 

• Multicore 있으면 동시성 매우 향상
• ex) 4개의 스레드 고려해보자
  • 싱글 : 시간에 따라 interleave (배치) → time sharing
  • 멀티 : 병렬로 실행 → time sharing 하는 동시에 parallel

1 core 4 thread (Single)

processing core가 한 번에 하나의 스레드만 실행하여 스레드의 실행이 interleave된다.

 

2 core 4 threads (Multi)

개별 thread가 각 core에 할당되어 thread들이 병렬로 실행된다.

 

 

Concurrency VS Parallelism

• concurrency 병행 : 모든 task가 진행되도록 하여 둘 이상의 task 지원
• parrallel 병렬 : 둘 이상 task가 동시에 실행

parallelism 없이 concurrency를 가질 수 있다.

Single processor에서는 process들이 concurrently하게 동작했으나 parallel하게는 못했고 마치 그렇게 보이는 것처럼 매우 빠르게 process간 switch하였다.

 

 

Programming Challenges in Multicore systems

1. Identifying tasks
   • 명확하게 독립된 태스크로 분류되도록 영역을 찾기
2. Balance
   • equal value로 equal work하도록 해야함 (밸런싱) → 작업 기여도 균등하도록
3. Data splitting
   • task가 사용하는 data를 seperate core에서 나눠서 실행되도록
4. Data dependency 
   • task에 접근하는 data의 의존성에 따라 동기화되도록 확인 필요
5. Testing and debugging
   • 병렬 수행하는 경우 다양한 실행 경로에 대해 test 및 debug 필요

 

 

Types of parallelism

• data parallelism : multiple core로 데이터를 분할
  • 동일한 task에 대해 수행 
  • 동일 data의 부분집합 분배
• task parallelism : 데이터는 유지하되 일을 분담
  • 다른 task를 분배하여 수행
  • 동일 data 또는 다른 data
    • 각 thread별 고유의 연산 수행

 

 

Amdahl’s Law

• 코어는 많을수록 좋은가? → 무조건 좋지는 않다!
• core의 개수가 performance에 주는 영향은 linear하지 않고 log 형태로 증가
• application 내에서 병렬적으로 수행될 수 없는 component들은 어쩔 수 없이 serial하게 수행되어야 하므로 병렬 처리가 불가능

 

 

Multithreading Model

• user thread (green thread)
  • 커널 support 없이 usermode에서 스레드 진행
  • system call 사용 안하는 thread
  • Java JVM
• kernel thread 
  • OS에 의해 직접 관리됨
  • 코어에서 직접 스레딩할 수 있음

 

user & kernel thread 사이 세 관계 (user, kernel thread 간 개수가 안맞을 가능성 O)

• Many to One Model
• One to One Model
• Many to Many Model

 

 

출처 : https://www.researchgate.net/figure/Three-types-of-thread-models-Popular-operating-systems-5-22-24-adopt-the_fig1_346379550

1. Many to one model
   • 한 번에 한 thread만 커널에 접근
   • 병렬 수행 X
   • 입출력 같은 system call이 필요하면 kernel thread에 접근
2. One to one model
   
   • thread가 blocking system call을 하더라도 다른 thread가 실행 가능
   • Linux, Window에서 사용
   • user thread 생성시 kernel thread도 생성 → kernel thread의 증가로 시스템 부담
     • 병렬 수행이 가능하지만 너무 많은 thread가 생성되지 않도록 관리 필요 
3. Many to many model
   • user thread를 개수가 작거나 kernel thread로 multiplex
   • user thread ≥ kernel thread
   • 4개보다 8개의 core를 가진 시스템에서 더 많은 kernel thread를 할당 받음
     • 개발자가 필요한 만큼 user thread 생성하여 대응되는 kernel thread가 병렬로 수행
4. Two-level model
   • Many to many model 변형
   • user level thread가 kernel thread에 묶일 수 있음
   • 가장 flexible하지만 구현 어려움 

core 수의 증가에 따라 kernel thread 수 제한의 중요성이 줄어들고 switching 부담이 증가하고 있다.

따라서 대부분의 OS들은 one to one model을 사용하고 있다.

 

 

 

Thread Libraries

개발자에게 thread를 생성, 관리하기 위한 API를 제공한다

 

구현 방법

1. user-level threads library
   • kernel 도움 없이 전적으로 user space에서 thread library 제공
   • 함수 호출은 system call이 아닌 user space에서의 local 함수 호출
2. kernel-level threads library
   
   • OS에 의해 직접 지원되는 kernel-level library 제공
   • API에서의 함수 호출은 kernel에 대한 system call 야기

 

3가지 main Thread Library

• Pthread (유닉스 계열의 user level, kernel level 라이브러리 제공)
• Windows thread library (윈도우 system의 kernel-level 라이브러리 제공)
• Java thread API (JVM이 host OS에서 실행되므로 host system에서 가용한 thread library로 구현)

 

 

Multiple threads 생성 전략

1. Asynchronous threading (비동기 스레딩)
   
   • 부모는 자식을 생성 후 자신의 실행 재개 → 동시/독립적 실행
   • data sharing이 거의 없음
   • multithreaded server, user interface 구현에 사용 (각 요청에 대해 비동기적으로 처리)
2. Synchronous threading (동기 스레딩)
   
   • 부모는 모든 자식 thread가 종료되길 기다림
   • 자식 thread는 concurrently하게 실행되어 종료되면 부모가 실행
   • 자식이 끝나서 종료되면 부모와 join (모든 자식들이 join되어야 부모가 실행 재개)
   • data sharing이 많이 일어남

부모가 자식의 수행 결과를 모아서 실행하기에 data sharing이 활발하다

 

 

 

Implicit Threading

multi core 시스템에서 multi threading application, design이 등장하게 되었다.

그러나 이는 처리가 어려우며, explicit threading은 너무 복잡하고 어렵다.

이에 따라 밑단에서 thread를 생성하며 관리를 알아서 해주는 implicit threading이 등장하게 되었다.

• application 개발자가 병렬 수행되는 task를 구분해야 함
• task는 함수로 작성하여 run-time library가 개별 thread로 map함

 

 

Threading Issues

1. Semantices of fort() and exec() system calls (복제)
   • UNIX의 두 버전 fork() 제공 (모든 thread 복제 vs 호출한 thread만 복제)
   • fork() 후 자식 스레드가 본인만의 코드를 실행하기 위해 exec()를 호출하는 경우 굳이 모든 thread를 복제할 필요가 없고 해당되는 thread만 복제
   • 부모와 똑같은 코드를 실행하는 경우 모든 thread 복제
2. Single handling (신호 전달)
   
   • signal : process에게 특정 event가 일어났음을 알림
   • Synchronous Signals : process 내부 이벤트 (같은 process)
     • 프로그램이 특정 행동시 signal 발생 (불법적인 행동)
     • signal을 야기한 연산을 수행한 process에게 전달
       • ex) 불법적인 메모리 접근
   • Asynchronous Signals : process 외부 이벤트
     
     • signal이 실행 중인 process의 외부 이벤트에 의해 생성 → 비동기적 전달
     • 보통 비동기적 signal은 다른 process로 전달됨
       • ex) ctrl + c
3. Thread cancellation of target thread (취소)
   • thread가 완료되기 전에 강제 종료
   • 병렬로 검색하다 하나가 결과를 찾으면 나머지 thread를 종료
   • Asynchronous cancellation
     • 다른 process에 의해 즉시 종료
   • Deferred cancellation
     • 지연 시간 제공, 값을 변경하는 경우 완료될 때까지 기다려줌
     • 종료시켜도 되는지 확인하는 시간을 줌
     • target thread가 스스로 종료되어야 하는지 확인하여 순차적으로 종료
       • * target thread : 취소되어야 하는 thread
   • Difficulty with cancellation
     • 만약 바로 종료시켜버릴 때 문제 되는 경우
       • 취소된 thread에 자원이 할당된 경우
       • 공유 데이터를 갱신하는 동안 취소되는 경우
         • ⇒ 필요 시스템 자원이 사용하지 못하게 될 수 있음
         • ⇒ deferred cancellation으로 target thread가 안전하게 취소될 수 있는지 검사
4. Thread-local storage (TLS) (저장소) 
   • thread 자신만의 data 필요 ⇒ Thread-local Storage (TLS)에 저장
     • ex) 각 트랜잭션을 독립된 thread로 서비스하는 경우
       • 트랜잭션별 id 부여
       • thread와 id를 연관시키기 위해 TLS 사용
5. Scheduler Activations (스케줄러)
   • kernel과 thread library 간 통신을 고려
   • many to many model, two-level model이 사용
   • Light Weight Process (LWP) 자료구조 
     • user와 kernel thread 사이 중재하는 자료 구조
     • application(user thread) 입장에서는 LWP가 마치 user thread를 스케줄하는 processor처럼 보임 (virtual processor)
     • 각 LWP는 하나의 kernel thread에 부착됨
     • ⇒ kernel thread의 수를 동적으로 조절