Concurrent Programming - 편집 역사

Pinkgo: /* Concurrent Programming with I/O Multiplexing */

2025-06-19T09:16:52Z

Concurrent Programming with I/O Multiplexing

← 이전 판		2025년 6월 19일 (목) 09:16 판
103번째 줄:		103번째 줄:
	# connfd와 listenfd 중 어떤 파일 디스크립터에 읽을 수 있는 데이터가 준비되었는지를 확인한다.		# connfd와 listenfd 중 어떤 파일 디스크립터에 읽을 수 있는 데이터가 준비되었는지를 확인한다.
	# listenfd에 데이터가 있다면, 새로운 클라이언트 연결 요청이 들어왔다는 뜻이다.		# listenfd에 데이터가 있다면, 새로운 클라이언트 연결 요청이 들어왔다는 뜻이다.
	#* 이 경우 <code>accept() </code> 함수를 호출하여 새 연결을 수락하고, connfd[] 배열에 새로운 connfd[]를 등록한다.		#* 이 경우 <code>accept()</code> 함수를 호출하여 새 연결을 수락하고, connfd[] 배열에 새로운 connfd[]를 등록한다.
	# 프로세스는 connfd[] 배열을 검사하여 입력이 존재하는 것만 찾아서 처리한다.		# 프로세스는 connfd[] 배열을 검사하여 입력이 존재하는 것만 찾아서 처리한다.
	이때 여러 파일 디스크립터에 대해서 I/O 이벤트를 감시하는 것은 <code>select(), epoll()</code> 함수들을 사용한다. 해당 함수들은 커널이 프로세스를 잠시 중단(block)시키고, 여러 파일 디스크립터에 대해 I/O 이벤트를 감시하도록 한다. 이때 하나 이상의 이벤트가 생기면 깨어나서 처리하도록 한다. 즉, I/O multiplexing을 간단하게 설명하면, '''<code>select(), epoll()</code> 함수를 사용하여 커널로 하여금 프로세스를 중지(suspend)시키고, 하나 이상의 I/O 이벤트가 발생했을 때, control을 애플리케이션으로 이전'''하는 것이다.		이때 여러 파일 디스크립터에 대해서 I/O 이벤트를 감시하는 것은 <code>select(), epoll()</code> 함수들을 사용한다. 해당 함수들은 커널이 프로세스를 잠시 중단(block)시키고, 여러 파일 디스크립터에 대해 I/O 이벤트를 감시하도록 한다. 이때 하나 이상의 이벤트가 생기면 깨어나서 처리하도록 한다. 즉, I/O multiplexing을 간단하게 설명하면, '''<code>select(), epoll()</code> 함수를 사용하여 커널로 하여금 프로세스를 중지(suspend)시키고, 하나 이상의 I/O 이벤트가 발생했을 때, control을 애플리케이션으로 이전'''하는 것이다.

Pinkgo: /* Deadlocks */

2025-06-06T11:54:08Z

Deadlocks

← 이전 판		2025년 6월 6일 (금) 11:54 판
845번째 줄:		845번째 줄:
	프로그램은 각 스레드가 뮤텍스를 그 순서대로 획득하고, 역순으로 해제해야 한다.		프로그램은 각 스레드가 뮤텍스를 그 순서대로 획득하고, 역순으로 해제해야 한다.
	예를 들어 figure 21에서의 deadlock은 각 스레드가 먼저 s를 잠그고, 그 다음 t를 잠그도록 수정하여 해결할 수 있다. 이렇게 변경된 프로그램에 대한 진행 그래프는 figure 22과 같다:		예를 들어 figure 21에서의 deadlock은 각 스레드가 먼저 s를 잠그고, 그 다음 t를 잠그도록 수정하여 해결할 수 있다. 이렇게 변경된 프로그램에 대한 진행 그래프는 figure 22과 같다:


	~~<syntaxhighlight lang="c">~~

	~~</syntaxhighlight>~~


	==각주==		==각주==
	[[분류:컴퓨터 시스템]]		[[분류:컴퓨터 시스템]]

Pinkgo: /* Deadlocks */

2025-06-06T11:53:58Z

Deadlocks

← 이전 판		2025년 6월 6일 (금) 11:53 판
836번째 줄:		836번째 줄:

	===Deadlocks===		===Deadlocks===
			[[파일:Progress graph for a program that can deadlock.png\|섬네일\|Figure 21. Progress graph for a program that can deadlock]]
			세마포어는 deadlock을 발생시킬 수 있는 잠재성을 지니다. Deadlock이란, 여러 스레드가 어떤 조건을 기다리며 모두 블락(block)되어 있고, 해당 조건은 절대 참이 되지 않는 문제이다. Figure 21은 두 개의 세마포어를 상호 배제(mutual exclusion)을 위해서 사용하는 두 스레드에 대한 진행 그래프이다. 해당 figure가 암시하는 코드를 작성하는 프로그래머는 P와 V 연산을 잘못된 순서로 작성하여, 두 세마포어에 대한 금지 영역(forbidden regions)이 겹치게(overlap) 만들었다. 이때 어떤 실행 경로가 교착 상태 지점 d에 도달하게 되면, 더 이상의 진행이 불가능해진다. 왜냐하면 겹쳐진 금지 영역들이 모든 합법적인 방향으로의 진행을 차단하기 때문이다. 해당 프로그램은 deadlock에 봉착한 것이며, 각 스레드는 다른 스레드가 수행할 V 연산을 기다리고 있지만, 그 연산은 절대로 일어나지 않는다. 이 겹쳐진 금지 영역들은 deadlock 영역이라는 상태 집합을 형성하며, 이는 어떤 실행 경로가 해당 deadlock 영역에 진입하며, deadlock을 겪는 다는 것을 의미한다. 이에 따라 프로그램은 deadlock 영역에는 진입할 수 있지만, 그로부터 탈출할 수는 없다.

			Deadlock의 큰 문제 중 하나는 예측 불가능하기 때문이다. 운이 좋으면 프로그램이 deadlock을 비껴나가서 실행될 수도 있겠지만, 어떤 경우에는 그렇지 않다. Figure 21은 이를 잘 보여준다. 또한 재현이 어렵기 때문에, 디버깅하기에도 어렵다.
			[[파일:Progress graph for a deadlock-free program.png\|섬네일\|Figure 22. Progress graph for a deadlock-free program]]
			프로그램이 deadlock에 빠지는 원인은 다양하지만, figure 22와 같이 이진(binary) 세마포어를 상호 배제를 위해 사용할 경우에는 다음과 같은 간단한 규칙을 적용하여 이를 회피할 수 있다:
			모든 뮤텍스들에 대해 total ordering이 주어졌을 때,
			프로그램은 각 스레드가 뮤텍스를 그 순서대로 획득하고, 역순으로 해제해야 한다.
			예를 들어 figure 21에서의 deadlock은 각 스레드가 먼저 s를 잠그고, 그 다음 t를 잠그도록 수정하여 해결할 수 있다. 이렇게 변경된 프로그램에 대한 진행 그래프는 figure 22과 같다:


841번째 줄:		850번째 줄:

	</syntaxhighlight>		</syntaxhighlight>


	==각주==		==각주==
	[[분류:컴퓨터 시스템]]		[[분류:컴퓨터 시스템]]

Pinkgo: /* Races */

2025-06-06T11:29:38Z

Races

@@ 752번째 줄: / 752번째 줄: @@
 ===Races===
 ==각주==
 [[분류:컴퓨터 시스템]]

Pinkgo: /* Using Library Functions in Threaded Programs */

2025-06-06T09:48:45Z

Using Library Functions in Threaded Programs

← 이전 판		2025년 6월 6일 (금) 09:48 판
644번째 줄:		644번째 줄:
	</syntaxhighlight>		</syntaxhighlight>
	[[파일:Sequential Consistency Example.png\|섬네일\|Figure 15. Sequential Consistency Example]]		[[파일:Sequential Consistency Example.png\|섬네일\|Figure 15. Sequential Consistency Example]]
	이때 위 프로그램을 실행시킨다면, 그 결과는 메모리 일관성을 구현하는 모델에 따라 달라진다. 즉, 하드웨어가 스레드 간 접근을 어떻게 처리하느냐에 따라 달라진다. 이때 병렬적으로 실행된 여러 스레드들의 명령 실행 결과가 마치 어떤 하나의 순차적으로 실행한 프로그램에서 나올 수 있다면, 해당 시스템은 순차적인 일관성(sequential consistency)를 가진다. 이때 모든 parallel 프로그램은 스레드 간 실행 순서가 임의로 섞일 수 있음에도, 순차적인 일관성을 보장해야 한다. 이때 스레드 일관성 제약 조건(Thread consistency constraints)이라는 개념이 대두되며 이는 각 스레드 내에서 명령이 실행되는 순서를 의미한다. 즉, <code>a = 2</code> 이후에 <code>print(b)</code>가 실행된다는 것이 보장된다. Figure 15는 위 코드에 대해 가능한 실행 순서와 출력 조합을 나열한 것이다. 헤딩 figure는 스레드 일관성 제약 조건에 따라 Wa-Rb, Wb-Ra 순서를 보존하며 실행된 결과들을 보여주고, 따라서 (100, 1), (1, 100)과 같은 결과들은 두 쓰레드가 모두 쓰기 작업을 하기도 전에 읽기 작업을 시작했다는 것을 의미하므로, 쓰레드 일관성 제약 조건을 어긴다.		이때 위 프로그램을 실행시킨다면, 그 결과는 메모리 일관성을 구현하는 모델에 따라 달라진다. 즉, 하드웨어가 스레드 간 접근을 어떻게 처리하느냐에 따라 달라진다. 이때 병렬적으로 실행된 여러 스레드들의 명령 실행 결과가 마치 어떤 하나의 순차적으로 실행한 프로그램에서 나올 수 있다면, 해당 시스템은 순차적인 일관성(sequential consistency)를 가진다. 이때 모든 parallel 프로그램은 스레드 간 실행 순서가 임의로 섞일 수 있음에도, 순차적인 일관성을 보장해야 한다. 이때 스레드 일관성 제약 조건(Thread consistency constraints)이라는 개념이 대두되며 이는 각 스레드 내에서 명령이 실행되는 순서를 의미한다. 즉, <code>a = 2</code> 이후에 <code>print(b)</code>가 실행된다는 것이 보장된다. Figure 15는 위 코드에 대해 가능한 실행 순서와 출력 조합을 나열한 것이다. 헤딩 figure는 스레드 일관성 제약 조건에 따라 <code>Wa-Rb, Wb-Ra</code> 순서를 보존하며 실행된 결과들을 보여주고, 따라서 <code>(100, 1), (1, 100)</code>과 같은 결과들은 두 쓰레드가 모두 쓰기 작업을 하기도 전에 읽기 작업을 시작했다는 것을 의미하므로, 쓰레드 일관성 제약 조건을 어긴다.
	[[파일:Non-Coherent Cache Scenario.png\|섬네일\|Figure 16. Non-Coherent Cache Scenario]]		[[파일:Non-Coherent Cache Scenario.png\|섬네일\|Figure 16. Non-Coherent Cache Scenario]]
	하지만 (100, 1), (1, 100)과 같은 결과들은 캐시 일관성이 없는 시스템에서는 충분히 발생할 수 있다. Figure 16과 같이 각 스레드가 자기만의 write-back 캐시<ref>수정된 데이터를 메모리에 바로 쓰지 않고, 나중에 해당 데이터가 캐시에서 제거될 때만 메모리에 반영하는 캐시를 의미한다.</ref>를 가지고 있고, 캐시들끼리 연동(coherence)하지 않는 상황을 가정하자. 이때 Thread 1은 a = 2, print(b)명령어를 수행하고, Thread 2는 b = 200, print(a)를 실행한다. 하지만 이들은 자신만의 캐시 공간을 가지고 있으므로 Thread 1에게 b는 항상 100이고, Thread 2에게 a는 항상 1이다. 즉, Thread1과 Thread2가 서로를 인식하지 못한다.		하지만 <code>(100, 1), (1, 100)</code>과 같은 결과들은 캐시 일관성이 없는 시스템에서는 충분히 발생할 수 있다. Figure 16과 같이 각 스레드가 자기만의 write-back 캐시<ref>수정된 데이터를 메모리에 바로 쓰지 않고, 나중에 해당 데이터가 캐시에서 제거될 때만 메모리에 반영하는 캐시를 의미한다.</ref>를 가지고 있고, 캐시들끼리 연동(coherence)하지 않는 상황을 가정하자. 이때 Thread 1은 <code>a = 2, print(b)</code>명령어를 수행하고, Thread 2는 <code>b = 200, print(a)</code>를 실행한다. 하지만 이들은 자신만의 캐시 공간을 가지고 있으므로 Thread 1에게 b는 항상 100이고, Thread 2에게 a는 항상 1이다. 즉, Thread1과 Thread2가 서로를 인식하지 못한다.
	[[파일:Snoopy Caches(1).png\|섬네일\|Figure 17. Snoopy Caches(1)]]		[[파일:Snoopy Caches(1).png\|섬네일\|Figure 17. Snoopy Caches(1)]]
	이러한 문제를 해결하기 위한 캐시 일관성 유지 기법 중 하나가 snoopy caches라고 하는 개념이다. 이는 아래와 같이 각 캐시 블록에 상태 태그를 부여한다:		이러한 문제를 해결하기 위한 캐시 일관성 유지 기법 중 하나가 snoopy caches라고 하는 개념이다. 이는 아래와 같이 각 캐시 블록에 상태 태그를 부여한다:
653번째 줄:		653번째 줄:
	* Exclusive (E): 쓰기 가능, 오직 하나의 캐시에 의해서만 접근됨		* Exclusive (E): 쓰기 가능, 오직 하나의 캐시에 의해서만 접근됨
	[[파일:Snoopy Caches(2).png\|섬네일\|Figure 18. Snoopy Caches(2)]]		[[파일:Snoopy Caches(2).png\|섬네일\|Figure 18. Snoopy Caches(2)]]
	이를 통해, 위의 코드의 Wa, Wb는 figure 17과 같이 메모리/캐시에 수행된다. 해당 figure와 같이 실행된 결과, 두 스레드 캐시가 a = 2, b = ~~200을~~ 각각 보유하며, 캐시의 각 태크 블럭은 E 상태가 된다. 이때 Thread2가 a를 읽기 위해 bus를 통해 a의 값을 요청하면, Thread 1이 자기가 가지고 있는 a:2를 bus를 통해 전달하며, 해당 캐시 블록의 태그를 S로 바꾼다. 이와 마찬가지로 b = ~~200도~~ 공유된다. 이는 figure 18에 나타나 있다. bus에는 메인 메모리도 연결되어 있지만, Thread 1의 캐시가 더욱 최신 메모리를 가지고 있기 때문에 Thread 1의 캐시가 Thread 2에게 전달되는 것이다. 이를 통해서 일관된 메모리 모델 유지가 가능케 할 수 있다.		이를 통해, 위의 코드의 Wa, Wb는 figure 17과 같이 메모리/캐시에 수행된다. 해당 figure와 같이 실행된 결과, 두 스레드 캐시가 <code>a = 2, b = 200</code>을 각각 보유하며, 캐시의 각 태크 블럭은 E 상태가 된다. 이때 Thread2가 a를 읽기 위해 bus를 통해 a의 값을 요청하면, Thread 1이 자기가 가지고 있는 a:2를 bus를 통해 전달하며, 해당 캐시 블록의 태그를 S로 바꾼다. 이와 마찬가지로 <code>b = 200</code>도 공유된다. 이는 figure 18에 나타나 있다. bus에는 메인 메모리도 연결되어 있지만, Thread 1의 캐시가 더욱 최신 메모리를 가지고 있기 때문에 Thread 1의 캐시가 Thread 2에게 전달되는 것이다. 이를 통해서 일관된 메모리 모델 유지가 가능케 할 수 있다.

	==Other Concurrency Issues==		==Other Concurrency Issues==
680번째 줄:		680번째 줄:
	}		}
	</syntaxhighlight>		</syntaxhighlight>
	먼저, rand() 함수는 스레드-위험하다. 왜냐하면 현재 호출의 결과가 이전 호출의 중간 결과에 의존하기 때문이다. 단일 스레드에서는 rand()를 반복 호출하여 예측 가능한 난수열을 얻을 수 있지만, 여러 스레드에서 rand() 함수를 concurrently하게 호출하면 동일한 결과를 얻을 수 없다. 그 이유는 rand()는 내부적으로 seed 값과 같은 static 변수를 가지고 있으며, rand()를 여러 번 호출하면 이전 호출 결과를 기반으로 다음 값을 생성하기 때문이다. 즉 단일 스레드에서는 한 번에 하나씩 rand() 함수를 호출하므로, 내부의 static 변수가 안정적으로 업데이트될 수 있지만, 여러 스레드가 동시에 호출하면 해당 static 변수에 대해 race condition이 발생할 수 있기 때문이다. 이러한 함수를 스레드-안전하게 만들기 위한 유일한 방법은 static 변수를 사용하지 않도록 함수 자체를 다시 작성하는 것이다.<ref>이 경우, 해당 함수를 호출한 함수가 상태 정보를 인자로 넘겨야 한다.</ref><ref>이러한 방식은 해당 함수 뿐 아니라 호출자의 코드도 변경해야 하기 때문에, 대형 프로그램에서는 수정이 어렵다는 단점이 있다.</ref>		먼저, <code>rand()</code> 함수는 스레드-위험하다. 왜냐하면 현재 호출의 결과가 이전 호출의 중간 결과에 의존하기 때문이다. 단일 스레드에서는 <code>rand()</code>를 반복 호출하여 예측 가능한 난수열을 얻을 수 있지만, 여러 스레드에서 <code>rand()</code> 함수를 concurrently하게 호출하면 동일한 결과를 얻을 수 없다. 그 이유는 <code>rand()</code>는 내부적으로 seed 값과 같은 static 변수를 가지고 있으며, <code>rand()</code>를 여러 번 호출하면 이전 호출 결과를 기반으로 다음 값을 생성하기 때문이다. 즉 단일 스레드에서는 한 번에 하나씩 <code>rand()</code> 함수를 호출하므로, 내부의 static 변수가 안정적으로 업데이트될 수 있지만, 여러 스레드가 동시에 호출하면 해당 static 변수에 대해 race condition이 발생할 수 있기 때문이다. 이러한 함수를 스레드-안전하게 만들기 위한 유일한 방법은 static 변수를 사용하지 않도록 함수 자체를 다시 작성하는 것이다.<ref>이 경우, 해당 함수를 호출한 함수가 상태 정보를 인자로 넘겨야 한다.</ref><ref>이러한 방식은 해당 함수 뿐 아니라 호출자의 코드도 변경해야 하기 때문에, 대형 프로그램에서는 수정이 어렵다는 단점이 있다.</ref>

	세 번째로는 '''static 변수에 대한 포인터를 반환하는 함수'''가 있다. 예를 들어, ctime(), gethostbyname()과 같은 함수는 계산 결과를 static 변수에 저장하고 그 변수에 대한 포인터를 반환한다. 이러한 함수를 여러 스레드에서 concurrently하게 실행하면 호출한 스레드들이 하나의 동일한 메모리 공간을 공유하게 되므로, 언제든지 문제를 야기할 수 있다. 이를 해결할 수 있는 방식은 아래와 같은 두가지이다:		세 번째로는 '''static 변수에 대한 포인터를 반환하는 함수'''가 있다. 예를 들어, <code>ctime(), gethostbyname()</code>과 같은 함수는 계산 결과를 static 변수에 저장하고 그 변수에 대한 포인터를 반환한다. 이러한 함수를 여러 스레드에서 concurrently하게 실행하면 호출한 스레드들이 하나의 동일한 메모리 공간을 공유하게 되므로, 언제든지 문제를 야기할 수 있다. 이를 해결할 수 있는 방식은 아래와 같은 두가지이다:
	* 함수를 다시 작성하여, 호출자가 결과를 저장할 변수의 주소를 전달하게 한다.		* 함수를 다시 작성하여, 호출자가 결과를 저장할 변수의 주소를 전달하게 한다.
	* 함수가 복잡하거나 소스 코드가 없어서 수정이 어려운 경우, lock-and-copy 기법을 사용할 수 있다:		* 함수가 복잡하거나 소스 코드가 없어서 수정이 어려운 경우, lock-and-copy 기법을 사용할 수 있다:
738번째 줄:		738번째 줄:

	</syntaxhighlight>		</syntaxhighlight>

			===Using Library Functions in Threaded Programs===
			[[파일:Common thread-unsafe library functions.png\|섬네일\|400x400픽셀\|Figure 20. Common thread-unsafe library functions]]
			대부분의 Linux 함수들, 그리고 <code>malloc(), free(), realloc(), printf(), scanf()</code>와 같은 표준 C 라이브러리에서 정의된 함수들은 대체로 스레드-안전하다. 단 몇가지 예외가 존재하며, figure 20은 위험한 함수들을 나용한 것이다. 아래는 이들 몇가지 함수들에 대한 설명이다:
			* <code>strtok()</code> 함수는 문자열을 파싱하기 위한 사용이 권장되지 않는 함수(deprecated)이다.
			* <code>asctime(), ctime(), localtime()</code> 함수는 시간과 날짜 형식 간 변환에 널리 사용되는 함수들이다.
			* <code>gethostbyaddr(), gethostbyname(), inet_ntoa()</code> 함수는 오래된 네트워크 프로그래밍 함수들로, 각각 재진입 가능한(reentrant) <code>getaddrinfo(), getnameinfo(), inet_ntop()</code> 함수들로 대체되었다.
			이 함수들 중 <code>rand(), strtok()</code> 함수를 제외하면, 대부분은 static 변수의 포인터를 반환하는 3번 부류에 속한다. 스레드 프로그램 내에서 이들 중 하나를 호출해야 하는 경우, 가장 권장되는 방식은 lock-and-copy 기법을 사용하는 것이다. 그러나 lock-and-copy 기법은 여러 가지 단점을 가진다:
			* 추가적인 동기화 연산이 프로그램 실행을 느리게 만든다.
			* 반환되는 포인터가 구조체 안에 또 구조체를 가진 복잡한 구조체인 경우, 전체 계층을 복사하려면 깊은 복사(deep copy)가 필요하다.
			* rand() 함수와 같이 호출 간 상태를 유지하는 2번 부류의 스레드-안전하지 않은 함수에는 lock-and-copy 방식이 적용되지 않는다.
			이러한 이유로, Linux 시스템은 대부분의 스레드-안전하지 않은 함수들에 대해 재진입 가능한(reentrant) 버전을 제공하며, 이러한 함수들의 이름은 항상 '_r' 접미사로 끝난다. 예를 들어, <code>asctime()</code> 함수의 재진입 가능한 버전은 <code>asctime_r()</code> 함수이다.

			===Races===

	==각주==		==각주==
	[[분류:컴퓨터 시스템]]		[[분류:컴퓨터 시스템]]

Pinkgo: /* Reentrancy */

2025-06-06T09:29:24Z

Reentrancy

@@ 702번째 줄: / 702번째 줄: @@
 ===Reentrancy===
+[[파일:Relationships between the sets of functions.png|섬네일|Figure 19. Relationships between the sets of functions]]
 <syntaxhighlight lang="c">
+//Not thread-safe, not re-entrant
 </syntaxhighlight>
 <syntaxhighlight lang="c">
+//Thread-safe but not re-entrant
 </syntaxhighlight>
 <syntaxhighlight lang="c">

Pinkgo: /* Memory Consistency */

2025-06-06T09:16:30Z

Memory Consistency

← 이전 판		2025년 6월 6일 (금) 09:16 판
655번째 줄:		655번째 줄:
	이를 통해, 위의 코드의 Wa, Wb는 figure 17과 같이 메모리/캐시에 수행된다. 해당 figure와 같이 실행된 결과, 두 스레드 캐시가 a = 2, b = 200을 각각 보유하며, 캐시의 각 태크 블럭은 E 상태가 된다. 이때 Thread2가 a를 읽기 위해 bus를 통해 a의 값을 요청하면, Thread 1이 자기가 가지고 있는 a:2를 bus를 통해 전달하며, 해당 캐시 블록의 태그를 S로 바꾼다. 이와 마찬가지로 b = 200도 공유된다. 이는 figure 18에 나타나 있다. bus에는 메인 메모리도 연결되어 있지만, Thread 1의 캐시가 더욱 최신 메모리를 가지고 있기 때문에 Thread 1의 캐시가 Thread 2에게 전달되는 것이다. 이를 통해서 일관된 메모리 모델 유지가 가능케 할 수 있다.		이를 통해, 위의 코드의 Wa, Wb는 figure 17과 같이 메모리/캐시에 수행된다. 해당 figure와 같이 실행된 결과, 두 스레드 캐시가 a = 2, b = 200을 각각 보유하며, 캐시의 각 태크 블럭은 E 상태가 된다. 이때 Thread2가 a를 읽기 위해 bus를 통해 a의 값을 요청하면, Thread 1이 자기가 가지고 있는 a:2를 bus를 통해 전달하며, 해당 캐시 블록의 태그를 S로 바꾼다. 이와 마찬가지로 b = 200도 공유된다. 이는 figure 18에 나타나 있다. bus에는 메인 메모리도 연결되어 있지만, Thread 1의 캐시가 더욱 최신 메모리를 가지고 있기 때문에 Thread 1의 캐시가 Thread 2에게 전달되는 것이다. 이를 통해서 일관된 메모리 모델 유지가 가능케 할 수 있다.

			==Other Concurrency Issues==
			동기화는 매우 복잡한 문제이며, 상호 배제(mutual exclusion)과 생산자-소비자 동기화 기법은 동기화에 관련된 이슈들의 빙산의 일각일 뿐이다. 해당 문단에서는 동기화를 구현하기 위해서 기본적으로 점검해야할 기본적인 상황이다. 이때 설명은 기본적으로 스레드를 중심으로 이루어지지만, 대부분의 내용은 공유 자원에 접근하는 모든 concurrent flow에 대해서 해당된다.

			===Thread Safety===
			스레드를 사용할 때는 스레드-안전(thread safe) 특성을 가진 함수를 작성해야 한다. 어떤 함수가 여러 개의 concurrently하게 실행 중인 스레드에서 반복적으로 호출되어도 항상 올바른 결과를 낸다면, 해당 함수는 스레드-안전 특성을 가진 것이다. 만약 그렇지 않다면, 즉 여러 스레드가 동시에 호출할 때 올바른 결과를 보장하지 않는 다면, 그 함수는 스레드-위험(thread-unsafe)하다고 한다. 스레드-위험한 함수는 네 가지 부류로 구분된다<ref>서로 겹칠 수 있는 부류들이다.</ref>

			먼저''' 공유 변수를 보호하지 않는 함수'''가 있다. 이는 공유 변수에 대한 적절한 동기화가 수행되지 않아 race condition을 가지고 있는 함수이다.<ref>스레드-안전하게 바꾸기 쉬우며, 단지 공유 변수를 P, V 등의 동기화 연산으로 보호하면 된다.</ref> 하지만 이 경우, 동기화 연산이 해당 함수의 실행 속도를 느리게 할 수 있다.

			또한 '''여러 번 호출될 때 내부적으로 상태(state)를 유지하고 이에 따라 실행되는 함수'''도 스레드-위험하다. 아래는 간단한 예시인 의사 난수 생성기(pseudorandom number generator)에 대한 코드이다:
			<syntaxhighlight lang="c">
			unsigned next_seed = 1;

			/* rand - return pseudorandom integer in the range 0..32767 */
			unsigned rand(void)
			{
			next_seed = next_seed * 1103515245 + 12543;
			return (unsigned)(next_seed >> 16) % 32768;
			}

			/* srand - set the initial seed for rand() */
			void srand(unsigned new_seed)
			{
			next_seed = new_seed;
			}
			</syntaxhighlight>
			먼저, rand() 함수는 스레드-위험하다. 왜냐하면 현재 호출의 결과가 이전 호출의 중간 결과에 의존하기 때문이다. 단일 스레드에서는 rand()를 반복 호출하여 예측 가능한 난수열을 얻을 수 있지만, 여러 스레드에서 rand() 함수를 concurrently하게 호출하면 동일한 결과를 얻을 수 없다. 그 이유는 rand()는 내부적으로 seed 값과 같은 static 변수를 가지고 있으며, rand()를 여러 번 호출하면 이전 호출 결과를 기반으로 다음 값을 생성하기 때문이다. 즉 단일 스레드에서는 한 번에 하나씩 rand() 함수를 호출하므로, 내부의 static 변수가 안정적으로 업데이트될 수 있지만, 여러 스레드가 동시에 호출하면 해당 static 변수에 대해 race condition이 발생할 수 있기 때문이다. 이러한 함수를 스레드-안전하게 만들기 위한 유일한 방법은 static 변수를 사용하지 않도록 함수 자체를 다시 작성하는 것이다.<ref>이 경우, 해당 함수를 호출한 함수가 상태 정보를 인자로 넘겨야 한다.</ref><ref>이러한 방식은 해당 함수 뿐 아니라 호출자의 코드도 변경해야 하기 때문에, 대형 프로그램에서는 수정이 어렵다는 단점이 있다.</ref>

			세 번째로는 '''static 변수에 대한 포인터를 반환하는 함수'''가 있다. 예를 들어, ctime(), gethostbyname()과 같은 함수는 계산 결과를 static 변수에 저장하고 그 변수에 대한 포인터를 반환한다. 이러한 함수를 여러 스레드에서 concurrently하게 실행하면 호출한 스레드들이 하나의 동일한 메모리 공간을 공유하게 되므로, 언제든지 문제를 야기할 수 있다. 이를 해결할 수 있는 방식은 아래와 같은 두가지이다:
			* 함수를 다시 작성하여, 호출자가 결과를 저장할 변수의 주소를 전달하게 한다.
			* 함수가 복잡하거나 소스 코드가 없어서 수정이 어려운 경우, lock-and-copy 기법을 사용할 수 있다:
			** 해당 함수에 mutex를 연결하고, 호출 지점에서 mutex를 잠근 후 함수 호출 → 반환값을 개인 메모리에 복사 → mutex 해제
			** 이 과정을 수행하는 래퍼 함수를 정의하여 기존의 함수 호출을 모두 교체하면 된다. 예를 들어, 아래는 ctime() 함수에 대해 lock-and-copy를 사용한 래퍼 함수이다:
			<syntaxhighlight lang="c">
			/* lock-and-copy version */
			char ctime_ts(const time_t timep, char *privatep)
			{
			char *sharedp;
			P(&mutex);
			sharedp = ctime(timep);
			strcpy(privatep, sharedp);
			V(&mutex);
			return privatep;
			}
			</syntaxhighlight>
			마지막으로는 '''스레드-위험한 함수를 호출하는 함수'''가 있다. 이는 직관적으로 당연하며, 이는 호출한 스레드-위험한 함수 대신 스레드-안전한 함수를 대신 호출하여 해결할 수 있다.

			===Reentrancy===

			<syntaxhighlight lang="c">

			</syntaxhighlight>
	<syntaxhighlight lang="c">		<syntaxhighlight lang="c">

Pinkgo: /* Memory Consistency */

2025-06-06T08:31:16Z

Memory Consistency

← 이전 판		2025년 6월 6일 (금) 08:31 판
654번째 줄:		654번째 줄:
	[[파일:Snoopy Caches(2).png\|섬네일\|Figure 18. Snoopy Caches(2)]]		[[파일:Snoopy Caches(2).png\|섬네일\|Figure 18. Snoopy Caches(2)]]
	이를 통해, 위의 코드의 Wa, Wb는 figure 17과 같이 메모리/캐시에 수행된다. 해당 figure와 같이 실행된 결과, 두 스레드 캐시가 a = 2, b = 200을 각각 보유하며, 캐시의 각 태크 블럭은 E 상태가 된다. 이때 Thread2가 a를 읽기 위해 bus를 통해 a의 값을 요청하면, Thread 1이 자기가 가지고 있는 a:2를 bus를 통해 전달하며, 해당 캐시 블록의 태그를 S로 바꾼다. 이와 마찬가지로 b = 200도 공유된다. 이는 figure 18에 나타나 있다. bus에는 메인 메모리도 연결되어 있지만, Thread 1의 캐시가 더욱 최신 메모리를 가지고 있기 때문에 Thread 1의 캐시가 Thread 2에게 전달되는 것이다. 이를 통해서 일관된 메모리 모델 유지가 가능케 할 수 있다.		이를 통해, 위의 코드의 Wa, Wb는 figure 17과 같이 메모리/캐시에 수행된다. 해당 figure와 같이 실행된 결과, 두 스레드 캐시가 a = 2, b = 200을 각각 보유하며, 캐시의 각 태크 블럭은 E 상태가 된다. 이때 Thread2가 a를 읽기 위해 bus를 통해 a의 값을 요청하면, Thread 1이 자기가 가지고 있는 a:2를 bus를 통해 전달하며, 해당 캐시 블록의 태그를 S로 바꾼다. 이와 마찬가지로 b = 200도 공유된다. 이는 figure 18에 나타나 있다. bus에는 메인 메모리도 연결되어 있지만, Thread 1의 캐시가 더욱 최신 메모리를 가지고 있기 때문에 Thread 1의 캐시가 Thread 2에게 전달되는 것이다. 이를 통해서 일관된 메모리 모델 유지가 가능케 할 수 있다.



	<syntaxhighlight lang="c">		<syntaxhighlight lang="c">
661번째 줄:		663번째 줄:

	</syntaxhighlight>		</syntaxhighlight>


	==각주==		==각주==
	[[분류:컴퓨터 시스템]]		[[분류:컴퓨터 시스템]]

Pinkgo: /* Memory Consistency */

2025-06-06T08:29:59Z

Memory Consistency

← 이전 판		2025년 6월 6일 (금) 08:29 판
631번째 줄:		631번째 줄:
	메모리 일관성(Memory Consistency)에 대해서 설명하기 위해, 아래와 같은 간단한 예제 코드를 살펴보자:		메모리 일관성(Memory Consistency)에 대해서 설명하기 위해, 아래와 같은 간단한 예제 코드를 살펴보자:
	<syntaxhighlight lang="c">		<syntaxhighlight lang="c">
			//a, b는 전역 변수
	int a = 1;		int a = 1;
	int b = 100;		int b = 100;
642번째 줄:		643번째 줄:
	print(a); // Ra: 변수 a에 대한 읽기		print(a); // Ra: 변수 a에 대한 읽기
	</syntaxhighlight>		</syntaxhighlight>
			[[파일:Sequential Consistency Example.png\|섬네일\|Figure 15. Sequential Consistency Example]]
			이때 위 프로그램을 실행시킨다면, 그 결과는 메모리 일관성을 구현하는 모델에 따라 달라진다. 즉, 하드웨어가 스레드 간 접근을 어떻게 처리하느냐에 따라 달라진다. 이때 병렬적으로 실행된 여러 스레드들의 명령 실행 결과가 마치 어떤 하나의 순차적으로 실행한 프로그램에서 나올 수 있다면, 해당 시스템은 순차적인 일관성(sequential consistency)를 가진다. 이때 모든 parallel 프로그램은 스레드 간 실행 순서가 임의로 섞일 수 있음에도, 순차적인 일관성을 보장해야 한다. 이때 스레드 일관성 제약 조건(Thread consistency constraints)이라는 개념이 대두되며 이는 각 스레드 내에서 명령이 실행되는 순서를 의미한다. 즉, <code>a = 2</code> 이후에 <code>print(b)</code>가 실행된다는 것이 보장된다. Figure 15는 위 코드에 대해 가능한 실행 순서와 출력 조합을 나열한 것이다. 헤딩 figure는 스레드 일관성 제약 조건에 따라 Wa-Rb, Wb-Ra 순서를 보존하며 실행된 결과들을 보여주고, 따라서 (100, 1), (1, 100)과 같은 결과들은 두 쓰레드가 모두 쓰기 작업을 하기도 전에 읽기 작업을 시작했다는 것을 의미하므로, 쓰레드 일관성 제약 조건을 어긴다.
			[[파일:Non-Coherent Cache Scenario.png\|섬네일\|Figure 16. Non-Coherent Cache Scenario]]
			하지만 (100, 1), (1, 100)과 같은 결과들은 캐시 일관성이 없는 시스템에서는 충분히 발생할 수 있다. Figure 16과 같이 각 스레드가 자기만의 write-back 캐시<ref>수정된 데이터를 메모리에 바로 쓰지 않고, 나중에 해당 데이터가 캐시에서 제거될 때만 메모리에 반영하는 캐시를 의미한다.</ref>를 가지고 있고, 캐시들끼리 연동(coherence)하지 않는 상황을 가정하자. 이때 Thread 1은 a = 2, print(b)명령어를 수행하고, Thread 2는 b = 200, print(a)를 실행한다. 하지만 이들은 자신만의 캐시 공간을 가지고 있으므로 Thread 1에게 b는 항상 100이고, Thread 2에게 a는 항상 1이다. 즉, Thread1과 Thread2가 서로를 인식하지 못한다.
			[[파일:Snoopy Caches(1).png\|섬네일\|Figure 17. Snoopy Caches(1)]]
			이러한 문제를 해결하기 위한 캐시 일관성 유지 기법 중 하나가 snoopy caches라고 하는 개념이다. 이는 아래와 같이 각 캐시 블록에 상태 태그를 부여한다:
			* Invalid (I): 사용 불가능
			* Shared (S): 읽기만 가능, 여러 캐시에 공유
			* Exclusive (E): 쓰기 가능, 오직 하나의 캐시에 의해서만 접근됨
			[[파일:Snoopy Caches(2).png\|섬네일\|Figure 18. Snoopy Caches(2)]]
			이를 통해, 위의 코드의 Wa, Wb는 figure 17과 같이 메모리/캐시에 수행된다. 해당 figure와 같이 실행된 결과, 두 스레드 캐시가 a = 2, b = 200을 각각 보유하며, 캐시의 각 태크 블럭은 E 상태가 된다. 이때 Thread2가 a를 읽기 위해 bus를 통해 a의 값을 요청하면, Thread 1이 자기가 가지고 있는 a:2를 bus를 통해 전달하며, 해당 캐시 블록의 태그를 S로 바꾼다. 이와 마찬가지로 b = 200도 공유된다. 이는 figure 18에 나타나 있다. bus에는 메인 메모리도 연결되어 있지만, Thread 1의 캐시가 더욱 최신 메모리를 가지고 있기 때문에 Thread 1의 캐시가 Thread 2에게 전달되는 것이다. 이를 통해서 일관된 메모리 모델 유지가 가능케 할 수 있다.

	<syntaxhighlight lang="c">		<syntaxhighlight lang="c">

648번째 줄:		661번째 줄:

	</syntaxhighlight>		</syntaxhighlight>


	==각주==		==각주==
	[[분류:컴퓨터 시스템]]		[[분류:컴퓨터 시스템]]

Pinkgo: /* Threads for Concurrent Programming */

2025-06-06T07:18:52Z

Threads for Concurrent Programming

← 이전 판		2025년 6월 6일 (금) 07:18 판
628번째 줄:		628번째 줄:
	속도 향상도를 보는 다른 관점은 weak scailing이다. 이는 프로세서의 수를 늘릴 때 문제의 크기도 함께 늘려서, 각 프로세서가 처리하는 작업량이 일정하도록 하는 방식이다. 이 경우 속도 향상도와 효율성은 단위 시간당 수행된 총 작업량을 기준으로 측정된다. 예를 들어, 프로세서 수를 2배로 늘리고 처리하는 작업량도 2배로 늘렸을 때, 한 시간당 처리량이 두 배가 되면 선형적인 속도 향상도와 100% 효율을 얻는 것이다.		속도 향상도를 보는 다른 관점은 weak scailing이다. 이는 프로세서의 수를 늘릴 때 문제의 크기도 함께 늘려서, 각 프로세서가 처리하는 작업량이 일정하도록 하는 방식이다. 이 경우 속도 향상도와 효율성은 단위 시간당 수행된 총 작업량을 기준으로 측정된다. 예를 들어, 프로세서 수를 2배로 늘리고 처리하는 작업량도 2배로 늘렸을 때, 한 시간당 처리량이 두 배가 되면 선형적인 속도 향상도와 100% 효율을 얻는 것이다.

			===Memory Consistency===
			메모리 일관성(Memory Consistency)에 대해서 설명하기 위해, 아래와 같은 간단한 예제 코드를 살펴보자:
	<syntaxhighlight lang="c">		<syntaxhighlight lang="c">
			int a = 1;
			int b = 100;

			Thread1:
			a = 2; // Wa: 변수 a에 대한 쓰기
			print(b); // Rb: 변수 b에 대한 읽기

			Thread2:
			b = 200; // Wb: 변수 b에 대한 쓰기
			print(a); // Ra: 변수 a에 대한 읽기
	</syntaxhighlight>		</syntaxhighlight>
	<syntaxhighlight lang="c">		<syntaxhighlight lang="c">