🐢 chap13. 동시성

⭐ 13.1 동시성 소개

• 의사코드 seudo-code 사용
• 동시 시스템concurrent system과 본질적 속성
• POSIX 스레딩 라이브러리 POSIX threading library

• 동시에 실행되는 프로그램 내부에 여러 로직이 있다는 의미
• 동시에 여러 작업을 처리할 수 있는 프로그램을 작성하는 강력한 도구
• 주로 커널에서 지원하는데, 커널은 운영체제의 심층부에 있다.
• 동시에 처리하는 이유
  • 파일을 다운로드하는 동안 웹 서핑
  • 유튜브에서 비디오를 볼 때와 같은 비디오스트리밍 시나리오 비디오 플레이어는 이전에 다운받은 콘텐츠 , 즉 청크chunk를 계속 보는 동안 다음 비디오 청크를 다운로드
  • 워드 프로세싱 프로그램 백그라운드에서 동시에 여러 작업을 실행 워드로 타이핑하는 동안에도 맞춤법 검사기나 포맷터가 백그라운 드에서 실행
• 혜택과 더불어 골칫거리도 함께
• 작업이 병렬적으로 실행된다는 의미이지만, 엄밀히 말해 ‘참’은 아닙니다 동시적이라는 말은 병렬적인 것과는 다르기 때문

⭐ 13.2 병렬성

• 병렬은 두 가지가 동시에 발생한다는 의미
• 동시 시스템에서는 다른 작업이 계속 실행하려면 한 작업을 일시 정지
• 프로세싱 유닛processing unit을 분리하고 격리하며 각각 특정 작업에 할당
• 가상의 CPU가 내부에 코어를 오직 하나만 가져서 병렬 작업을 행할 수 없다고 가정
• 대부분의 알고리듬은 순차적sequential 이며 본질적으로 병렬적이지는 않습니다. 스레딩조차 각 스레드는 병렬적인 실행 흐름 excution flow 으로 나눌 수 없는 여러 순차적 지시어를 갖습니다.
• 순차적 알고리듬은 운영체제에 의해 실행에 병렬적인 흐름으로 쉽게 자동 분할될 수 없습니다. 따라서 멀티 코어 CPU라면 특정 CPU 코어에 실행 흐름을 각각 할당해야 하며, 해당 코어에 두 개 이상의 실행 흐름이 할당되었다면 이들은 모두 병렬적으로 실행될 수 없고 동시적인 행위가 즉시 관찰됩니다.
• 멀티 코어 에서는 사실상 코어 간 병렬성 및 동일 코어의 동시성이 둘 다 보이는, 혼합된 행위가 나타납니다.
• 현재의 운영체제는 아직 분할 작업을 수행하지 못합니다

⭐ 13.3 동시성

• 다중 작업 multitasking → 동시성은 같은 개념입
• 시스템이 동시에 여러 작업을 관리할 때, 반드시 작업이 병렬적으로 실행중이라는 의미는 아님
• 작업 스케줄러 task scheduler는 서로 다른 작업을 아주 빠르게 전환하며, 상당히 짧은 시간 동안 각각의 작업을 아주 조금씩 수행합니다.
• 전환switching
• 인위적인 병렬성의 한 형태
• 멀틱스는 다중 작업과 동시적인 프로세스를 처리하기 위해 고안된 최초의 운영체제
• POSIX 호환 운영체제

⭐ 13.4 작업 스케줄러 유닛

• 모든 다중 작업 (멀티태스킹 ) 운영체제는 커널에 작업 스케줄러 유닛 task scheduler unit 또는 줄여서 스케줄러 유닛scheduler unit이 있어야 합니다.
• 작업 스케줄러 유닛에 관한 몇 가지 사항
  • 스케줄러는 실행을 기다리는 작업에 대한 대기열queue이 있습니다. 작업task or job이란 실행 시 별도의 흐름에서 수행되어야 하는 작업들을 의미합니다.
  • 일반적으로 이러한 대기열은 우선순위가 높은 작업이 먼저 시작되도록 선택합니다.
  • 모든 작업 사이에는 작업 스케줄러 프로세스 유닛을 관리하고 공유합니다. 프로세스 유닛이 비어 있을 때(프로세스 유닛을 사용하는 작업이 없는 경우), 작업 스케줄러는 다른 작업이 프로세서 유닛을 사용하도록 하기 전에 대기열에서 이 작업을 선택해야 합니다. 작업이 종료되면 작업 스케줄러는 프로세서 유닛을 해제해 다시 사용할 수 있도록 한 뒤에 또 다른 작업을 선택합니다. 이는 작업 스케줄링task scheduling 이라고 하며, 작업 스케줄러가 이를 단독으로 맡습니다.
  • 작업 스케줄러가 사용할 수 있는 여러 스케줄링 알고리듬이 존재합니다. 하지만 이 모든 알고리듬은 특정 요구 사항을 다루어야 합니다. 예를 들면, 알고리듬은 모두 공평해야fair 하며 어떤 작업도 오랜 시간 동안 선택되지 못한 채 대기열에서 기아 상태로starved 계속 기다려서는 안 됩니다.
  • 선택한 스케줄링 전략에 따라 스케줄러가 프로세스 유닛을 사용하려면 작업에 특정한 타임 슬라이스time slice 또는 타임 퀀텀time quantum을 지정해야 합니다. 또는 스케줄러는 반드시 작업이 프로세서 유닛을 해제할 때까지 기다려야 합니다.
  • 스케줄링 전략이 선점형preemptive일때, 스케줄러는 실행 중인 작업으로부터 CPU 코어를 강제로 회수해서 다음 작업에 코어를 제공할 수 있어야 합니다. 이를 선점 스케줄링 preemptive scheduling이라고 합니 다. 또한 작업이 CPU를 자발적으로 해제하는 다른 전략을 비선점 스케줄링 cooperative scheduling 이라고 합니다.
  • 선점 스케줄링 알고리듬은 타임 슬라이스를 서로 다른 작업 간에 균등하고 공평하게 배분하려고 합니다. 우선순위가 있는 작업은 더 자주 선택될 수 있고 스케줄러의 구현에 따라 더 긴 타임 슬라이스를 얻을 수 있습니다.
• 전화 부스

⭐ 13.5 프로세스와 스레드

• 운영체제에서 작업이란 프로세스 또는 스레드
• 시분할time-sharing 또는 선점형 스케줄러
• 선점형 스케줄러가 실행 중인 프로세스를 중단시기고 다른 프로세스를 실행 상태로 바꿀 때마다 문맥교환이 발생
• 문맥 교환이 빠르면 빠를수록, 사용자는 작업이 더 병렬적으로 실행된다고 여깁니다. 흥미롭게도 대부분의 운영체제는 선점형 스케줄러를 사용
• 문맥 교환에는 기묘하고 독특한 특징
  • 예측 가능하지 않다
  • 특정 명령어에 문맥 교환이 발생할 확률이 모든 명령어에 대해 같다고 가정하는 것

⭐ 13.6 발생 전 제약

• 문맥 교환이 예측 불가능하다는 점
• 문맥 교환이 발생하는 시간은 불확실→ 동시적으로 실행되는 명령어에 대해 확실한 것은?

• 코드 박스 13-1 다섯개 명령 가 있는 간단한 작업

  작업 p {
  	1. num = 5
  	2. num++
  	3. num = num - 2
  	4. X = 10
  	5. num = num + x
  }
  

  • 반드시 특정 순서로 실행되어야 한다
  • 모든 인접한 두 명령어 사이에 발생 전 제약이 있다
  • 이 제약은 문맥 교환이 되더라도 반드시 지켜져야 합니다.

• 코드 박스 13-2 문맥 교환과 앞의 작업에서 한 실행

  Run 1:
  	1. num = 5
  	2. num++
  >>>>> Context Switch <<<<<
  	3. num = num - 2
  	4. X = 10
  >»» Context Switch <<<<<
  	5. num = num + x
  

• 코드 박스 13-3 문맥 교환과 더불어 한 또 다른 실행

  Run 2:
  	num = 5
  » Context Switch «
  	num++
  	num = num - 2 //2
  » Context Switch «
  	X = 10
  » Context Switch «
  	num = num + x //22
  

• 이러한 제약은 특정 작업에 대해 전체적으로 결정론적인 행위가 존재하는 이유

---

• 공유 자원을 한 변수라고 하고, 이에 대해 읽기/쓰기 권한이 모두 있는 동시 작업 시스템이 있다고 가정
  • 읽기만 한다면 결과는 항상 같다.
  • 작업 중 하나라도 공유 변수에 값을 쓰려고 한다면, 작업 스케줄러가 할당한 문맥 교환이 모든 작업의 전체 상태에 영향을 줄 것, 실행할 때마다 상태가 서로 다를 수 있다는 의미
  • 작업의 중간 상태 intermediate state 가 실행마다 다를 수 있기 때문
• 문맥 교환의 영향을 상쇄하려면, 다른 실행에서 동일하게 결정되는 결과를 얻으려면 적절한 동기 synchronization 방법을 사용해야 합니다.

⭐ 13.7 동시성을 사용해야 하는 경우

• 동시성에는 언제 사용해야 하는지를 알 수 있는 몇 가지 일반적인 패턴
• 현재 명령어가 다음 명령어를 블로킹blocking
• 서버 프로그램, 사용자로부터 문자열을 읽으려는 경우
• 첫 번째 패턴은 무기한으로 실행 흐름을 차단할 수 있는 명령어가 있는 경우 이 지점에서 기존의 흐름을 두 개의 별도의 흐름 또는 작업으로 분할해야 합니다
• 세 가지 목표를 갖는 서버 그램
  • 클라이언트로부터 읽은 두 수의 합을 계산 하고 클라이언트에게 그 결과를 반환합니다.
  • 클라이언트에 대한 서비스 여부에 상관없이, 서비스하는 클라이언트의 수를 파일에 규칙적으로 작성합니다.
  • 한 번에 여러 클라이언트에게 서비스할 수 있어야 합니다.
• 코드 박스 13-4 단일 작업을 이용해 작동하는 서버 프로그램

  계산기 서버 {
  	작업 Tl {
  		1. N = 0
  		2. 서버 준비
  		3. 영원히 수행 {
  			4. 클라이언트를 기다리기
  			5. N = N + 1
  			6. C에서 첫 번째 수를 읽고 X에 저장
  			7. C에서 두 번째 수를 읽고 Y에 저장
  			8. Z = X + Y
  			9. Z를 C에 쓰기 (write)
  			10. C에 대한 연결을 종료
  			11. N을 파일에 쓰기 (write )
  		}
  	}
  }
  

  • 이 코드가 앞서 언급한 목표를 달성할 수 없음을 곧 보여드리겠습니다.
  • 네 번째 명령어 클라이언트를 기다리기는 완료 시간을 알 수 없는 블로킹 명령어입니다.그러므로 명령어 5,6과 나머지는 실행되지 않습니다. 따라서 이들 명령어는 새 클라이언트가 올 때까지 반드시 대기해야 하고 클라이언트가 온 뒤에 이들 명령어가 실행될 수 있습니다.
  • 명령어 4의 출력에 의존적

• 코드 박스 13-5 세 동시 작업으로 작동하는 서버 프로그램의 의사코드

  계산기 서버 {
  	공유 수: N
  
  	작업 T1 {
  
  		1. N = 0
  		2. 서버 준비
  		3. 작업 T2를 스폰
  		4. 영원히 수행 {
  			5. N을 파일에 쓰기
  			6. 30초 대기
  		}
  	}
  
  	작업 T2 {
  
  		1. 영원히 수행 {
  			2. 클라이언트 C를 대기=>블록킹
  			3. N = N + 1
  			4. C에 대한 작업 T3를 스폰
  		}
  	}
  
  	작업 T3 {
  		1. C에서 첫 번째 수를 읽고 X에 저장
  		2. C서서 두 번째 수를 읽고 Y에 저장
  		3. Z = X + Y
  		4. Z 를 C에 쓰기 (write)
  		5. C에 대한 연결을 종료
  	}
  }
  

  • 핵심에 중요한 설계 원칙 종료 시각을 알 수 없거나 완료할 때까지 시간이 오래 걸리는 블로킹 작업이 있을 때마다 작업을 두 개의 동시 작업으로 나누어야 합니다.
  • 스폰 명령어는 속도가 꽤 빨라서 새 클라이언트를 받는 작업을 블로킹하지 않습니다.
  • 작업 T1의 인스턴스는 하나, 작업T2의 인스턴스도 하나만 있지만, 작업T3 는 모든 클라이언트에 대해 여러 인스턴스를 가질 수 있습니다.

  • 서버 프로그램은 클라이언트에 대한 서비스 중단합니다. 이를 서비스 거부denial of service (DoS)

    • 공유된 변수 N에 대해 특히 T2의 인스턴스와 같은 작업 중 하나가 그 값을 변경할 수 있다는 점입니다. 한 작업이 수정할 수 있는 공유 변수 가 존재하므로, 동시 작업 시스템은 동시성 문제가 발생하기 쉽습니다.
    • 공유 변수 에 대해 심각한 데이터 경쟁data race 문제

⭐ 13.8 공유 상태

• 수정 가능한 공유상태가 있는 여러 개의 동시 작업이 실행되는 동안, 문맥 전환 패턴의 불확실성이 모든작업의 전체 상태를 어떻게 비결정론적 non-deteminism으로 만드는지 간략히 설명
• 상태state 라는 용어를 들으면 특정 시점의 일련의 변수와 그에 해당하는 값
• 중간 상태란 이와 비슷하게 작업이 특정 명령을 실행했을 때 기존의 모든 공유되지 않은 변수 및 그에 해당하는 값의 집합
• 공유 상태란 특정 시점에 동시 작업 시스템이 읽거나 수정할 수 있는 변수와 그에 해당하는 값의 모음

• 코드 박스 13-7 수정 가능한 공유 상태가 있는 동시 작업 두 개로 구성된 시스템

  동시 시스템 {
  
  	공유 상태 {
  		X : 정수 = o
  	}
  
  	작업 P {
  		A: 정수
  			1. A = X
  			2. A = A + 1
  			3. X = A
  			4. X를 출럭
  	}
  
  	작업 Q {
  		B : 정수
  			1. B = X
  			2. B = B + 2
  			3. X = B
  			4. X를 출럭
  	}
  }
  

  • 순차적으로 이러한 작업 실행하면 문맥 교환을 정하지 않고도 결정론적인 결과가 나옵니다.
• 코드 박스 13-8 동시적으로 실행했을 때 작업 P와 Q에 대해 한 인터리빙 | 작업 P | 작업 스케줄러 | 작업 Q | | ——— | ————- | ——- | | | 문맥 교환 | | | | | B = X | | B = B + 2 | | | 문맥 교환 | | | A = X | | | | | 문맥 교환 | | | | | X = B | | | 문맥 교환 | | | A = A + 1 | | X = A | | | | | 문맥 교환 | | | | | print X | | | 문맥 교환 | | | print X | | | | | 문맥 교환 | |
  • 이 시나리오는 특정 지점에서 문맥 교환이 발생하는 여러 시나리오 중 하나일 뿐입니다. 각 시나리오는 인터리빙이라고 합니다
  • 실행 사이에는 틈이 존재할 수 있습니다 . 이러한 틈은 예측할 수 없으며, 실행을 추적하면 이 인터리빙은 놀라운 결과를 낳습니다. 최종 결과로 둘 다 3을 출력하리라 예상했지만, 프로세스P는 값 1을출력하고 프로세스Q는 출력2를 출력합니다.
  • 변하지 않은 채 남아 있어야 하는 다른 중요한 제약이 존재합니다. 이러한 제약들은 데이터 경쟁 또는 경쟁상태 race condition 를 포함
• 코드 박스 13-9 동시적으로 실행할 때 작업 P와 Q의 다른 인터리빙 | 작업 P | 작업 스케줄러 | 작업 Q | | —— | ————- | —— | | | 문맥 교환 | | | | | B = X | B = B + 2 X = B | | | 문맥 교환 | | | A = X A = A + 1 | | | | | 문맥 교환 | | | | | print X | | | 문맥 교환 | | | X = A print X | | | | | 문맥 교환 | |
  • 더 작은 3개의 작업으로 이루어진 C의 간단한 X++ 구문이 단일 타임 슬라이스에서 실행 되지 않으리라는 점.
  • 원자적인 작업이 아니며 3개의 더 작은 원자적 명령어로 구성되어 있습니다. 원자적 명령어는 더 작은 작업으로 나뉠 수 없으며 문맥 교환으로 인해 인터럽트될 수도 없습니다.
  • 공유 자원에 접근하려는 작업이 많을 수 있으므로, 동시성 문제는 깊게 공부해 결과를 예측할 수 있는(결정론적인) 메커니즘을 찾야야 합니다.
  • 작업 스케줄러는 타이머 인터럽트timer interrupt를 발생시키기 위해 타이머를 맞추기 전에 대기열에서 작업을 선택합 니다. 그리고 CPU 코어를 떠나서 선택한 작업을 위한 자원을 할당합니다

⭐ 13.9 마무리

• 동시성과 병렬성을 정의했습니다.
• 각 병렬 작업은 작업을 소유한 프로세서 유닛이 필요하지만.
• 동시 작업은 프로세서 하나를 공유할 수 있습니다.
• 동시 작업은 하나의 프로세서 유닛을 사용하지만, 작업 스케줄러는 프로세서의 시간을 관리하고 프로세서를 다른 작업 간에 공유합니다. 그 결과 각각의 작업에서 수많은 문맥 전환과 서로 다른 인터리빙이 발생합니다.
• 블로킹 명령어를 소개했습니다. 또한 동시성을 사용할 시점을 암시하는 패턴과, 작업 하나를 둘 또는 셋 이상의 동시 작업으로 분할하는 방법을 설명했습니다.
• 공유 상태가 무엇인지 설명했습니다. 여러 작업이 같은 공유 상태를 읽고 쓰려고 할 때. 공유 상태가 데이터 경쟁과 같은 심각한 동시성 문제를 어떻게 야기할 수 있는지도 살펴봤습니다.