2일간 이론 진도를 따로 적어둔것이다......
내일 여기 내용으로 발표해야되는데 진짜 언제 다외우지....ㅋㅋ
병렬성 프로그래밍
논리 제어흐름이 시간적으로 중첩되면 동시적이라고 표현한다.
동시성은 주로 운영체제 커널이 다수의 응용 프로그램을 돌리기 위해 사용하는 메커니즘으로만 취급했지만 동시성은 커널에만 국한된게 아니다.
application에서도 쓰인다.
app 수준에서도 쓰이는데
- 느린 I/O 디바이스 접근하기
- 사람들과 상호작용하기
- 작업 지연시켜서 시간지연 줄이기
- 다수의 네트워크 클라이언트 처리
- 멀티코어 머신에서 병렬로 계산하기 : CPU포함해서 멀티코어 프로세서를 가지고 있는데
- 프로세스 간 통신 : 명시적 프로세스 간 통신
- I/O 다중화 : I/O 프로그램이 한개의 프로세스이므로 모든 흐름들은 동일한 주소공간 공유
- 쓰레드 : 쓰레드 하이브리드로 사용해서 동일한 가상 주소 공유
프로세스를 사용한 동시성 프로그래밍
가장 간단한 방법은 프로세스를 사용하는 것이다.
fork,exec,waitpid 같은 친숙한 함수를 사용한다.
새로운 자식 프로세스를 생성해서 각각 새로운 클라이언트를 서비스한다.
만약 동시성 서버를 구현하는 자연스러운 방법은 부모에서 클라이언트 연결 오청을 수락하는것이고, 이후에 새로운 자식 프로세스를 생성해서 각가 새로운 클라이언트를 서비스한다.
프로세스의 장단점
프로세스는 부모와 자식 사이에 상태정보를 공유하는 것에 대해서 깔끔한 모델을 가지고있다.
파일 테이블은 공유되고 사용자 주소공간은 공유되지 않는다.
프로세스들이 분리된 주소공간을 가직는 것은 장점이자 단점이다.
한 개의 프로세스가 우연히 다른 프로세스의 가상메모리에 쓰는 것은 불가능하고, 이로인해 많은 혼란스러운 오류들을 제거할 수 있다.
별도의 주소공간은 프로세스가 상태정보를 공유하는 것을 어렵게 한다.
프로세스 기반 설계의 또 다른 단점은 프로세스 제어와 IPC의 오버헤드가 크기 때문에 더 느려지는경향이 있다.
I/O 다중화를 이용한 동시성 프로그래밍
표준 입력에 타이핑한 인터랙티브한 명령에도 응답할 수있는 echo서버를 작성할 것을 요구 받았으면 이 경우 서버는 두개의 독립적인 I/O 이벤트에 대해 응답해야한다.
- 연결요청하는 네트워크 클라이언트
- 키보드에서 명령줄을 입력하는 사용자
이중 우리는 어떤 이벤트를 먼저 기다려야 하는가?
어떤 선택을 해도 이상적인 선택은 아니다.
연결요청을 기다린다면 입력 명령을 처리할 수 없다.
이 딜레마의 해결책은 I/O 다중화라고 부르는 기술인데
아이디어는 select 함수를 사용해 커널에게 프로세스 정지를 요구해서 한개이상의 I/O 이벤트가 발생한 후에만 app에게 제어를 돌려주도록 하는것
I/O 다중화에 기초한 동시성 이벤트 기반 서버
I/O 다중화는 동시성 이벤트 기반 프로그램을 위한 기초 과정으로 사용될 수 있으며, 이 경우 흐름들은 특정 이벤트의 결과로 진행한다.
일반적인 아이디어는 논리흐름 상태 머신으로 모델링하는것.
비공식적으로 상태머신은 상태,입력 이벤트, 상태와 입력 에빈트를 상태로 매핑하는 전환의 집합이다.
I/O 다중화의 장단점
장점 : 이벤트 기반 설계로 프로그래머가 프로세스 기반 설계보다 자신의 프로그램을 더 잘 제어 가능
ex) 클라이언트들에게 우선적인 서비스를 제공하는 이벤트 기반 동시성 서버를 작성 -> 프로세스 기반에서는 어려움
장점2: I/O 다중화에 기초한 이벤트 기반 서버는 단일 프로세스의 컨텍스트에서 돌아가고, 모든 논리흐름은 프로세스의 전체 주소공간에 접근가능-> 흐름들 간에 데이터 공유를 쉽게해준다.
장점3 : 프로세스 기반 설계보다 효율적이고, 새로운 흐름을 스케줄하기 위해 문맥전환을 요구하지 않기 때문이다.
단점 : 코딩 복잡도가 중요함 -> 프로세스기반보다 코드가 3배 더 김
단점2: 멀티코어 프로세서를 완전히 활용 불가능
쓰레드를 이용한 동시성 프로그래밍
쓰레드 => 프로세스 컨텐스트 내에서 돌아가는 논리흐름
프로세스는 한개의 쓰레드 였지만 요즘은 멀티쓰레드가 됨
쓰레드는 커널에서 자동 스케줄되는데
각 쓰레드 고유는 정수 쓰레드 id가 있다. 스택, 스택 포인터, PC 범용 레지스터, 조건 코드를 포함하는 자신만의 쓰레드 컨텍스트를 가진다.
한 개의 프로세스에서 돌고 있는 모든 쓰레드는 이 프로세스의 전체 가상주소를 공유한다.
I/O 다중화에 기초한 흐름에서와 같이 다수의 쓰레드는 한 개의 프로세스의 컨텍스트에서 돌아가며, 프로세스 가상 주소공간의 전체 내용을 공유한다. -> 코드,데이터,힙,공유 라이브러리, 오픈한 파일 포함
쓰레드 실행모델
다중 쓰레드에 대한 실행 모델은 다중 프로세스를 위한 실행 모델과 비슷하다.
각 프로세스는 메인 쓰레드라고 부르는 한개의 쓰레드로 시작한다.
어떤 시점에서 메인 쓰레드는 피어 쓰레드를 생성하고, 이때부터 두 쓰레드가 동시에 돌아감.
제어는 문맥전환을 통해서 피어쓰레드로 전달되고, 이유는 메인 쓰레드가 read나 sleep같은 느린 시스템 콜을 실행하기 때문이거나 인터벌 타이머에 의해서 중단되었기 때문이다.
피어 쓰레드는 제어를 메인 쓰레드로 돌려주기 전에 잠시 동안 실행하는 식으로 진행된다.
쓰레드의 실행은 프로세스와는 살짝 다르다.
쓰레드 컨텍스트가 프로세스 컨텍스트보다 훨씬 작아서 더 빠르고 쓰레드는 부모-자식 계층구조가 아니기 때문에 하나의 연계된 쓰레드들은 피어들의 풀을 구성하고 쓰레드는 이들과 독립적으로
다른 쓰레드에 의해서 생성되었다.
메인쓰레드는 항상 프로세스에서 돌아가는 첫 번째 쓰레드라는 의미에서만 다른 쓰레드와 구별된다.
피어의 풀에 관한 개념의 주요 영향은 쓰레드가 자신의 피어 모두를 죽일 수 있거나 자신의 피어들이 종료하는 것을 기다릴 수 있다.
나아가서 피어는 동일한 고유 데이터를 읽고 쓸 수 있다.
쓰레드 프로그램에서 공유변수
쓰레드의 한가지 매력적인 측면은 다수의 쓰레드가 같은 프로그램 변수들을 공유하기가 쉽다.
공유는 다소 까다로운데
정확하게 쓰레드 프로그램을 작성하기 위해서는 공유한다는 것이 무슨의미인지 알아야한다.
어떤 변수가 공유되었는지 아닌지 이해하기 위해서 몇가지 기본적인 질문들에 대답해보자: 1. 쓰레드를 위한 하부 메모리 모델은 무엇인가? 2. 이 모델이 주어지면 변수들은 어떻게 메모리에 매핑되는가?
- 마지막으로 얼마나 많은 쓰레드들이 이 변수를 참조하는가?
변수는 다수의 쓰레드가 이 변수의 일부 인스턴스를 참조할 때만 공유된다.
쓰레드 메모리 모델
동시성 쓰레드의 풀은 한 개 프로세스의 컨텍스트에서 돌아간다.
각각의 쓰레드는 자신만의 별도의 쓰레드 컨텍스트를 가지며, 여기에는 쓰레드 ID, 스택, 스택포인터, 프로그램 카운터, 조건 코드, 범용 레지스터 값이 포함된다.
각 쓰레드는 나머지 프로세스 컨텍스트를 다른 쓰레드와 공유한다.
여기에는 가상 주소공간이 포함되며, 이것은 읽기 허용 텍스트, 읽기 쓰기 데이터, 힙, 공유 라이브러리 코드, 데이터영역으로 구성된다. 쓰레드 또한 동일한 파일들을 공유한다.
동작적인 측면에서 하나의 쓰레드가 다른 쓰레드의 레지스터를 읽거나 쓰는것은 불가능,
모든 쓰레드는 공유 가상메모리 내의 모든 위치에 접근가능하다.
만약 어떤 쓰레드가 한 메모리 위치를 수정하면 그 위치를 읽는 다른 모든 쓰레드는 결국 이 변수의 변경사항을 알 수 있게된다.
그래서 레지스터들은 절대 공유되지 않지만 가상 메모리는 항상공유된다.
별도의 쓰레드 스택을 윟나 메모리 모델은 깔끔하지 않다.
이 스택들은 가상 주소공간의 스택영역에 포함되어 있고, 대개 이들 각각의 쓰레드에 의해 독립적으로 접근된다.
항상은 아닌 이유는 서로 다른 쓰레드 스택이 다른 쓰레드로부터 보호되지 않기 때문이다.
그래서 만약 어떤 쓰레드가 어떻게든 다른 쓰레드의 스택을 가리키는 포인터를 획득하게 되면, 스택의 모든 부분을 읽고 쓸 수 있다.
변수들을 메모리로 매핑하기
쓰레드를 사용하는 C프로그램의 변수들은 이들의 저장 클래스에 따라 가상메모리에 매핑된다.
1.전역변수: 전역 변수는 함수 밖에서 선언된 변수를 의미하며 런타임에 가상메모리의 읽기/쓰기 영역은 쓰레드의 의해 참조될 수 있는 각각의 전역변수의 정확히 한 개의 인스턴스를 포함한다.
2.지역 자동변수 : 지역 자동변수는 함수내에 static 특성없이 선언된 변수 -> 런타임에 각 쓰레드의 스택은 자신만의 지역 자동 변수의 인스턴스를 가진다. 심지어 다수의 쓰레드가 동일한 쓰레드 투린을 사용하는 경우에도 그렇다.
3.지역 정적 변수 : 함수안에서 static쓴 변수 전역 변수처럼 가상메모리의 읽기/쓰기 영역은 프로그램에서 선언된 각 지역 정적변수의 정확히 한개의 인스턴스를 포함한다.
공유변수
어떤 변수 v는 자신의 인스턴스 중 한 개가 하나이상의 쓰레드에 의해 참조되는 경우에만 공유되어 있다고 한다.
예를 들어 cnt 변수가 공유되는데 하나의 런아팀 인스턴스를 가지고 있고, 이 인스턴스가 피어 쓰레드 모두에 의해서 참조되고 있다.
하지만 msgs 같은 지역 자동변수들도 공유될 수 도 있다는것을 인식하자
세마포어로 쓰레드 동기화하기
공유 변수들은 편리하지만 심각한 동기화 오류를 가져올 수 있다.
이 프로그램은 두개의 쓰레드를 만들고, 각각은 전역 공유 카운터 변수 cnt를 증가 시킨다.
각 쓰레드 카운터를 ninserts번 증가시키니 때문에 값이 2 * ninserts 일 것이라고 생각하지만 다른값이 나온다.
이는 어셈블리 코드를 보면 알수있는데
각각 동시성 실행은 일종의 두 쓰레드 내 인스터럭션의 전체 순서를 정의하는데 아쉽게도 이 연산의 일부는 정확한 결과를 만들지만 나머지가 꼭 그렇지 않다는것.
일반적으로 운여체제가 여러분의 쓰레드를 위해서 정확한순서를 잡을 방법은 없다.
진행 그래프
진행 그래프는 n개의 동시성 쓰레드를 n 차원 직교좌표 공간을 지나는 궤적으로 모델링한것을 말한다.
각각의 축 k는 쓰레드 k의 진행에 대응된다.
쓰레드 i에 대해서 공유변수의 내용을 조작하는 인스트럭션은 크리티컬 섹션(임계구역)을 형성한다.
각각의 쓰레드가 자신의 크리티컬 섹션 내의 인스터럭션들을 실행하는 동안 상호배타적으로 공유 변수를 접근하도록 보장하기를 원한다.
이 현상을 상호배제 라고 한다.
그러면 진행 그래프에서, 두 개의 크리티컬 섹션의 교차점은 위험 영역이라는 상태 공간의 구역을 정의한다.
그러면 변수 cnt에 대한 위험영역이 생기는데, 위험 영역은 둘레에 있는 상태들과 접해 있지만 포함하지 않는다.
모든 안전 궤적은 공유 카운터를 정확히 갱신해야함 -> 동기화를 해서 안전궤적을 가지게 해야함
세마포어
동시성 프로그래머의 개척자인 다익스트라는 서로 다른 실행 쓰레드를 동기화하는 문제에 대한 고전적인 해답을 세마포어라고 하는 특별한 타입의 변수에 기초해 제안했다.
세마포어 s는 비음수 정수값을 갖는 전역변수로 두 개의 특별한 연산인 P,V를 통해서만 조작가능하다.
P(s) = s가 0이 아니면 P는 s를 감소시키고 즉시 리턴한다. 만일 0이면 이 쓰레드는 s가 0이 아닌값을 가지고, 쓰레드가 V 연산에 의해 재시작 될때까지 정지된다. 재시작 후에 P연산은 s를 감소시키고 제어를 호출자에게 보냄
V(s) = V연산은 s를 1 증가시킨다. 만일 s가 0이 아닌 값이 되는 것을 기다리면서 P연산에서 멈춰있는 쓰레드가 있다면, V연산은 이중에서 정확히 한 개의 쓰레드를 시작하고 그 후에 s를 감소시켜서 자신의 P연산을 완료한다.
P에서 테스트와 감소 연산은 일단 세마포어 s가 0이 아니면 s의 감소가 중단없이 일어난다는 의미에서 개별적으로 일어남.
V에서 증가 연산 또한 개별적으로 일어나는데, 그것은 이연산이 세모포어를 중단 없이 로드하고, 증가하고 ,저장하기 때문이다.
V의 정의가 기다리고 있는 쓰레드들이 재시작되는 순서를 정의하지 않는다는 것에 주목해라.
유일한 요구사항은 V개 정확히 한 개의 대기하는 쓰레드를 재시작해야 한다는 것.
그래서 여러 개의 쓰레드가 하나의 세마포어를 기다리고 있을 때, 어떤 것이 V이 결과로 재시작되는지는 예측 불가능
P와 V의 정의를 돌고 있는 프로그램이 적절히 초기화된 세마포어가 음수 값을 가지는 상태로 절대 들어가지 못하는걸 보장해줌.
이것을 세마포어의 불변성이라고 하고, 동시성 프로그램의 궤적을 제어하기 위한 강력한 도구를 제공한다.
상호 배제를 위해 세마포어 이용하기
세마포어는 공유 변수들을 상호 배타적으로 접근하기 위한 편리한 방법을 제공
하나의 세마포어 s를 초기값 1로 싲가해서 각각의 공유 변수에 연계하고 그 후에 대응하는 크리티컬 섹션을 P(s)와 V(s)연산으로 둘러싸는것이다.
이런 방법으로 공유 변수들을 보호하기 위해 이용된 세마포어는 바이너리 세마포어라고 부름-> 값이 항상 0,1
상호배태성을 제공하는 목적의 바이너리 세마포어는 뮤텍스라고도 한다.
뮤텍스에서 P 연산을 수행하는 것은 뮤텍스를 잠근다(locking) 비슷하게, V 연산을 수행하는 것은 뮤텍스를 연다(unlocking)이라고 한다.
뮤텍스를 잠갔으나 아직 열지 못한 쓰레드는 뮤텍스를 소유하고 있다고 말한다.
가능한 자원들의 집합에 대한 카운터로 이용된 세마포어는 카운팅 세마포어라고 한다.
핵심 아이디어은 P와 V의 조합이 금지된 구역이라고 부르는 상태들의 집합을 생성한다.
세마포어 불변성으로 인해 금지된 구역의 상태를 하나라도 포함하는 가능한 궤적이 존재하지 않는다.
그리고 금지 구역이 완전히 위험 영역을 감싸고 있으므로 모든 가능한 궤적들은 위험 영역의 모든 부분을 지날 수 없다.
따라서 모든 가능한 궤적은 안전하고 런타임에 인스터럭션의 순서와 무관하게 정확하게 카운터를 증가시킨다.
세마포어를 이용한 공유 자원 스케줄링하기
세마포어의 또 다른 중요한 용도는 상호 배제를. 제공할 뿐만 아니라, 공유 자원으로의 접근을 스케줄링하는 것이다.
쓰레드는 세마포어 연산을 이용해서 프로그램 상태의 어떤 조건이 참이 되었다는 다른 쓰레드에 알려준다.
두 개의 고전적이고 유용한 사례는 생산자-소비자 문제다.
병렬성을 위해서 쓰레드 이용하기
지금 까지의 동시성에 관한 학습을 통해서 단일 프로세서 시스템에서 실행하는 동시성 쓰레드를 가정했다.
현대 머신들은 멀티코어 프로세서를 가지고 있다.
동시성 프로그램들은 종종 이런 머신에서 더 빨리 동작하고, 이유는 운영체제 커널이 동시성 쓰레드를 단일 코어에서 순차적으로 실행하는 대신 멀티코어에서 병렬로 스케줄하기 때문이다.
이런 병렬성을 활용하는 것은 바쁜 웹서버, 데이터베이스 서버, 큰 규모의 app에서 매우 중요하고, 웹 브라우저, 스프레드시트, 문서처리 같은 주요 app에서 점차 유용해지고 있다.
다수의 쓰레드들이 자신의 할당된 영역에서 병렬로 동작할 수 있는 여러가지 방법중 일부를 봐보자
직접적인 옵션은 쓰레드들이 하나의 뮤텍스에 의해 보호된공유된 전역 변수로 합을 계산하도록 하는 것이다.
중간에 과정은 매우 기니 결과만 보면 단일 쓰레드의 계산이 동기화하는 뮤텍스보다 빠르다. 왜냐하면 동기화하는 비용이 비싸기 때문이다.
그래서 동기화를 피해서 하는 편이 좋은데 각 피어 쓰레드가 다른 쓰레드와 공유되지 않게 사적 변수에 자신의 부분합을 계산하면 된다.
여기서 교훈은 병렬 프로그램 작성은 매우 까다롭고 조금만 수정해도 성능이 좌지 우지 된다.
병렬 프로그램 성능의 특성 분석
실행시간은 실제로 쓰레드수가 증가하면 약간 증가한다
동일코어에서 여러 쓰레드 문맥 전환하는데 걸리는 오버헤드 때문이다.
그래서 병렬 프로그램들은 종종 각각의 코어가 정확히 한 개의 쓰레드만 돌리도록 작성된다.
다른 동시성 이슈
공유된 데이터로의 접근을 동기화하라는 요구를 받게 되면 아마도 인생이 복잡해진다.
동기화는 원래 어려운 문제이고
보통 순차 프로그램에서는 일어나지 않는다.
쓰레드 안전성
쓰레드로 프로그램 할 때, 쓰레드 안정성이라고 부르는 특성을 가지는 함수를 작성하도록 유의해야한다.
어떤 함수는 다수의 동시성 쓰레드로부터 반복적으로 호출 될 때 항상 정확한 결과를 만드는 경우에만 쓰레드- 안전 이라고한다.
쓰레드 안전하지 못하면, 쓰레드-위험이라고한다.
쓰레드-위험 함수의 네가지 클래스는 다음과 같다.
클래스 1: 공유 변수를 보호하지 않는 함수들.
클래스2 : 다중 호출에 대해서 상태를 유지하는 함수들
클래스3 : 정적 변수를 가리키는 포인터를 리턴하는 함수
클래스 4: 쓰레드 - 위험 함수를 호출하는 함수들
만약 g가 다수의 호출에 걸쳐서 상태에 의존하는 클래스 2라면 f도 쓰레드-위험 다시 g 재작성 해야함
만일 g가 클래스 1 또는 3 함수라면 호출 위치와 다른 결과로 생성디는 공유 데이터를 뮤텍스로 보호한다면 f는 여전히 쓰레드-안전이다.
재진입성
재진입(Reentrancy) 가능한 함수라고 하는 쓰레드 - 안전 함수의 중요한 클래스가 있으며, 이들은 다수의 쓰레드에 의해 호출될 때 공유 데이터는 전혀 참조하지 않는 특성으로 규정된다.
이들은 다수의 쓰레드에 의해 호출될 때 공유 데이터는 전혀 참조하지 않는 특성으로 규정된다.
쓰레드 -안전 재진입은 둘이 다른거임
재진입 함수는 쓰레드-안전 의 부분집합이다.
재진입 가능 함수들은 재진입 불가능 쓰레드-안전 함수들보다 효율적이다. -> 동기화 연산을 필요로 하지 않기 때문에
클래스 2 쓰레드-위험 함수를 쓰레드-안전 함수로 바꾸는것은 무조건 함수 다시작성해서 재진입 가능하게 만들어야된다.
모든 데이터 참조가 지역 자동 스택 변수들로 이루어진다면 이 함수는 명시적 재진입 가능이고 이것은 우리가 함수의 재진입성을 어떻게 호출 되어쓴지에 관계없이 선언할 수 있다는 의미에서 그렇다.
가정을 완화하고 그렇지 않다면 명시적으로 재진입 가능한 함수에서 일부 매개변수들을 참조 형태로 전달되도록 해주며 그 후에 만일 호출하는 쓰레드들이 포인터를 공유되지않은 데이터로 조심스럽게 전달하면 유일하게 재진입가능하다는 의미에서 간접적 재진입 가능함수라고 한다.
경쟁상태
경쟁(race)은 프로그램의 정확성이 다른 쓰레드가 y 지점에 도착하기 전에 자신의 제어흐름에서 x 지점에 도착하는 하나의 쓰레드에 의존할 때 일어난다.
경쟁은 대개 프로그래머들이 쓰레드가 실행 상태 공간을 지나가는 어떤 특정 궤적을 따른다고 가정하며, 쓰레드 프로그램이 모든 가능한 궤적에 대해서도 정확하게 동작해야한다는 불문율을 잊어버리기 때문에 일어난다.
각각 피어 쓰레드와 메인 쓰레드 간에 경쟁 때문에 발생하는 동시성 오류
경쟁을 제거하기 위해 각각 정수 ID를 위한 별도의 블록을 동적으로 할당할 수 있다. 즉, 따로 동기화를 해줘서 경쟁상태를 없애주는것
교착 상태
세마포어는 교착상태라고 하는 런타임 에러를 유발하고, 이것은 다수의 쓰레드가 절대로 참이 될 수없는 조건을 기다리면서 정지된것.
진행 그래프는 교착상태를 이해하기 위한 소중한 도구이다.
대충 이해해보면 서로 임계구역이 겹치는 상황이 오면 deadlock state가 만들어지는데 여기에 들어오면 교착상태를 피할수 없다.
궤적들은 교착 구역에 진입할 수 는 있지만 떠날수가 없음.
예측 불가능해서 엄청 난해한 문제이다.
언제 나타날지 모르는……
이것은 뮤텍스를 사용해서 풀 수 있는데
모든 뮤텍스들의 전체 순서가 주어지면 프로그램은 만일 각 쓰레드가 자신의 뮤텍스를 순서대로 획득하고 이들을 역순으로 반환하면 데드락이 없어진다.
'정글' 카테고리의 다른 글
| WIL(7주차) Proxy 구현 (0) | 2023.05.25 |
|---|---|
| TIL(27일차) 네트워크 (0) | 2023.05.23 |
| WIL(6주차) Malloc-lab 구현 (1) | 2023.05.20 |
| (TIL 25일차) 가상 메모리1 (0) | 2023.05.18 |
| TIL(24일차) 프로세스 (0) | 2023.05.18 |
