Study/TIL(Today I Learned)

24.02.19 CSAPP, 백준, Keyword

에린_1 2024. 2. 19. 23:34
728x90

CSAPP

12. 동시성 프로그램

  • 논리적 제어흐름은 이들이 시간적으로 중첩되면 동시적이다. 이와 같은 현상을 동시성이라고 한다.
  • 응용수준 동시성은 다양한 경우 유용하다.
    • 느린 I/O 디바이스 접근하기 : 응용프로그램은 유용한 작업을 I/O요청과 겹치게 한다.
    • 사람들과 상호 작용하기 : 사용자가 어떤 동작을 요청할 때 마다, 이 동작을 수행하기 위해 별도의 동시성의 논리 흐름이 생성된다.
    • 작업을 지연시켜서 시간지연 줄이기 : 다른 동작을 지연시키고 이들을 동시에 수행해서 특정 독작의 시간 지연을 축소하기 위해 동시성을 이용한다
    • 다수의 네트워크 클라이언트 처리 : 클라이언트마다 별도의 논리흐름을 생성하는 동시성 서버
    • 멀티코어 머신에서 병렬로 계산하기
  • 동시성 프로그램을 만들기 위한 세 개의 기본 접근방법
    • 프로세스 : 각 논리적 흐름은 커널이 스케줄하고 관리하는 프로세스이다. 프로세스가 별도의 가상 주소공간을 가지기 때문에, 서로 통신하기를 원하는 흐름들은 모종의 명시적 프로세스간 통신(IPC : interprocess Communication)메커니즘을 사용해야 한다.
    • I/O 다중화 : 동시성 프로그램의 한 형태로, 응용들은 명시적으로 자신의 논리흐름을 한 개의 프로세스 컨텍스트 내에서 스케줄한다. 논리적 흐름들은 파일 식별자에 도착하는 데이터로 인해 메인 프로그램이 명시적으로 하나의 상태에서 다른 상태로 전환하는 상태머신으로 모델할 수 있다. 프로그램이 한 개의 프로세스이므로 모든 흐름들은 동일한 주소공간을 공유한다.
    • 쓰레드 : 쓰레드는 한 개의 프로세스 컨텍스트에서 돌아가는 논리흐름으로 커널에 의해 스케줄된다. 쓰레드를 다른 두 개의 방식의 하이브리드 형태로 생각할 수 있다. 커널에 의해 스케줄되며 동일한 가상 주소공간을 공유한다.

12.1 프로세스를 사용한 동시성 프로그래밍

  • 동시성 프로그램을 만드는 가장 간단한 방법
    • ex) 동시성 서버를 구현하는 방법은 부모에서 클라이언트 연결 요청을 수락하는 것이며, 그 후에 새로운 자식 프로세스를 생성해서 새로운 각각의 클라이언트를 서비스한다.

12.1.1 프로세스 기반 동시성 서버

  • 서버를 만드는 데 중요한 몇 가지 사항이 있다.
    • 첫째, 서버들은 대개 장시간 동안 돌아가므로 좀비 자식을 청소하는 SIGCHLD핸들러를 포함 해야한다.
    • 둘째, 부모와 자식은 자신의 connfd사본을 닫아야 한다.
    • 마지막으로, 소켓의 파일 테이블 엔트리 내의 참조 횟수 때문에 클라이언트로의 연결은 부모와 자식의 connfd 사본이 모두 닫힐 때 까지 종료되지 않는다.

12.1.2 프로세스의 장단점

  • 프로세스는 부모와 자식 사이에 상태 정보를 공유하는 것에 대해서 깔끔한 모델을 가지고 있다.
    • 파일은 공유되고 사용자 주소공간은 공유되지 않는다.
  • 프로세스들이 분리된 주소공간을 가지는것은 장점이자 단점이다. 한 개의 프로세스가 우연히 다른 프로세스의 가상메모리에 쓰는 것은 불가능하며, 이로 인해서 많은 혼란스러운 오류들을 제거할 수 있다.
  • 반면에 별도의 주소공간은 프로세스가 상태정보를 공유하는 것을 어렵게 한다. 정보를 공유하기 위해서 명시적인 IPC 메커니즘을 사용해야 한다. 그리고 프로세스 제어와 IPC의 오버헤드가 크기 때문에 더 느려지는 경향이 있다.

12.2 I/O 다중화를 이용한 동시성 프로그래밍

  • 기본 아이디어는 select 함수를 사용해서 커널에게 이 프로세스를 정지할 것을 요구해서 한 개 이상의 I/O 이벤트가 발생한 후에만 응용에게 제어를 돌려준다.

12.2.1 I/O 다중화에 기초한 동시성 이벤트 기반서버

  • I/O 다중화는 동시성 이벤트 기반 프로그램을 위한 기초과정으로 사용될 수 있으며, 이 경우 흐름들은 특정 이벤트의 결과로 진행된다. 일반적인 아이디어는 논리 흐름을 상태머신으로 모델링 하는 것이다. 비공식적으로 상태 머신은 상태, 입력 이벤트, 상태와 입력이벤트를 상태로 매핑하는 전환의 집합이다. 각각의 전환은 한 개(입력상태, 입력 이벤트)의 쌍을 한 개의 출력 상태로 매핑한다. 자체 - 루프는 동일한 입력과 출력 상태 사이의 전환이다. 상태 머신들은 대개 방향성 그래프로 그리며, 이 경우 노드들은 상태를, 화살표는 전환을, 호의 이름은 입력 이벤트를 나타낸다. 상태머신은 초기 상태에서 실행을 시작한다. 각각의 입력 이벤트는 현재 상태에서 다음 상태로의 전환을 유발한다.

12.2.2 I/O 다중화의 장단점

  • 한 가지 장점은 이벤트기반 설계로 프로그래머가 프로세스 기반 설계보다 자신의 프로그램을 더 잘 제어할 수 있다는 점이다.
  • 또 다른 장점은 I/O 다중화에 기초한 이벤트 기반 서버는 단일 프로세스의 컨텍스트에서 돌아가며, 그래서 모든 논리흐름은 프로세스의 전체 주소공간에 접근할 수 있다. 이 흐름들 간에 데이터 공유를 쉽게 해준다. GDB같은 친숙한 디버깅 도구를 이용해서 순차 프로그램에서 하는 것처럼 동시성 서버를 디버그 할 수 있다.
  • 마지막으로 이벤트 기반 설계는 대개 프로세스 기반 설계보다 훨씬 더 효율적이며, 그 이유는 이들이 새로운 흐름을 스케줄하기 위해서 프로세스 문맥 전환을 요구하지 않기 때문이다.
  • 이벤트 기반 설계의 한 가지 중요한 단점은 코딩 복잡도다. 프로세스 기반 서버보다 세 배 더 많은 코드를 필요로 한다. 불행히도 동시성의 크기가 감소하면 할수록 복잡성은 증가한다. 크기라는 것은 각 논리흐름이 타임 슬라이스 동안에 각 논리흐름이 실행하는 인스트럭션의 수를 의미한다.
  • 또 다른 중요한 단점은 이들이 멀티코어 프로세서를 완전히 활용할 수 없다는 것이다.

12.3 쓰레드를 이용한 동시성 프로그래밍

  • 쓰레드는 프로세스의 컨텍스트 내에서 돌아가는 논리흐름이다.
  • 쓰레드는 커널에 의해서 자동으로 스케줄된다. 각 쓰레드는 고유의 정수 쓰레드 ID(TID), 스택, 스택 포인터, 프로그램 카운터, 범용레지스터, 조건 코드를 포함하는 자신만의 쓰레드 컨텍스트를 가진다. 한 개의 프로세스에서 돌고 있는 모든 쓰레드는 이 프로세스의 전체 가상주소를 공유한다.

12.3.1 쓰레드 실행모델

  • 각 쓰레드는 메인 쓰레드라고 부르는 한 개의 쓰레드로 생명을 시작한다. 어떤 시점에서 메인 쓰레드는 피어(Peer) 쓰레드를 생성하고, 이때부터 두 쓰레드가 동시에 돌아간다. 피어 쓰레드는 제어를 메인 쓰레드로 돌려주기 전에 잠시동안 실행하는 식으로 진행된다.
  • 쓰레드의 실행은 일부 중요한 부분에서 프로세스와 다르다. 쓰레드 컨텍스트가 프로세스 컨텍스트보다 훨씬 작기 때문에 쓰레드 문맥전환은 프로세스보다 빠르다. 또 프로세스와는 달리 쓰레드는 경직된 부모 - 자식 계층구조에서 구성되지 않았다. 하나의 프로세스에 연계된 쓰레드들은 피어들의 풀을 구성하고, 쓰레드는 이들과는 독립적으로 다른 쓰레드에 의해서 생성되었다. 메인 쓰레드는 항상 프로세스에서 돌아가는 첫 번째 쓰레드라는 의미에서만 다른 쓰레드와 구별된 피어의 풀에 관한 이 개념의 주요 영향은 쓰레드가 자신의 피어 모드를 죽일 수 있거나 자신의 피어들이 종료하는 것을 기다릴 수 있다는 것이다. 또, 각 피어는 동일한 공유 데이터를 읽고 쓸 수 있다.

12.3.2 POSIX 쓰레드

  • POSIX 쓰레드는 C프로그램에서 쓰레드를 조작하는 표준 인터페이스다 pthreads는 데이터를 피어 쓰레드와 안전하게 공유하기 위해서, 시스템 상태의 변화를 피어들에게 알리기 위해 프로그램이 쓰레드를 생성하고, 죽이고, 청소하도록하는 약 60개의 함수를 정의한다.

12.3.6 쓰레드 분리하기

  • 언제나 쓰레드는 연결가능 joinable하거나 분리되어detached있다. 연결 가능한 쓰레드는 다른 쓰레드에 의해 청소되고 종료될 수 있다. 자신의 메모리 자원들은 다른 쓰레드에 의해 청소될 때 까지는 반환되지 않는다. 반대로, 분리된 쓰레드는 다른 쓰레드에 의해서 청소되거나 종료 될 수 없다. 자신의 메모리 자원들은 이 쓰레드가 종료할 때 시스템에 의해 자동으로 반환된다.
  • 기본적으로 쓰레드는 연결 가능하게 생성된다.

백준

2566 최댓값

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int row = 9, col = 9 ,max =0, idi=0, idj=0;
	vector<vector<int>> ij_arr(row, vector<int>(col));
	for (int i = 0; i < row; ++i)
	{
		for (int j = 0; j < col; ++j)
		{
			int input_num;
			cin >> input_num;
			if (input_num > max)
			{
				max = input_num;
				idi = i;
				idj = j;
			}
		}
	}
	cout << max << "\\n" << idi+1 <<" "<< idj + 1;
	return 0;
}
  • 2차원 배열을 만들고, 순회해서 큰 값을 찾은 다음 풀려고 접근했던 문제이다.
  • 갑자기 그렇게 안하고 값을 배열에 넣을 때, MAX체크를 하면 안될까? 하고 생각을 했고, 코드를 수정해서 진행해봤다.
  • 한번 틀렸었는데 모든 숫자가 0으로 들어왔을때, index row,column초기화를 안시켜줘서 그 부분에서 틀렸다고 생각해서 초기값을 넣어주었다.

10798 세로읽기

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	vector<string> str_arr(5);
	string input_string;
	for (int i = 0; i < 5; ++i)
	{
		cin >> input_string;
		str_arr[i] = input_string;
	}
	for (int j = 0; j < 15; ++j)
	{
		for (int i = 0; i < 5; ++i)
		{
			if (str_arr[i].size()-1 < j)
				continue;
			cout << str_arr[i][j];
		}
	}
	return 0;
}
  • row과 column 접근을 반대로 해보자 하고 문제에 접근해보았다.
  • vector에 사용에 아직 익숙하지 않아서 그 부분에서 애를 먹었다.

2563 색종이

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int test_case, row = 100, column = 100, ans = 0;
	vector<vector<int>> int_arr(row,vector<int>(column));
	cin >> test_case;
	for (int i = 0; i < test_case; ++i)
	{
		int witdh, height;
		cin >> witdh >> height;
		for (int x = witdh; x < witdh + 10; ++x)
		{
			for (int y = height; y < height + 10; ++y)
			{
				if (0 == int_arr[x][y])
				{
					int_arr[x][y] = 1;
					ans++;
				}
			}
		}
	}
	cout << ans;
	return 0;
}
  • 2차원 배열 0,1을 이용해서 색칠한 부분을 나타내도록 했다.
  • 넓이라는 것은 1의 개수를 세면 되는것이기 때문에, 색칠할 때, 1씩 증가시키는 형식으로 코드를 작성했다.

5086 배수와 약수

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	while (true)
	{
		int a, b;
		cin >> a >> b;
		if (0 == a && 0 == b)
			break;
		if (0 == b % a)
			cout << "factor" << "\\n";
		else if (0 == a % b)
			cout << "multiple" << "\\n";
		else
			cout << "neither" << "\\n";
	}
	return 0;
}
  • 약수 체크, 배수 체크 그리고 나머지는 아무것도 속하지 않는다는것을 파악하면 빠르게 풀 수 있다.

2501 약수 구하기

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int num, index;
	vector<int> num_arr;
	cin >> num >> index;
	for (int i = 1; i <= num; ++i)
	{
		if (0 == num % i)
			num_arr.push_back(i);
	}
	if (num_arr.size() < index)
		cout << "0";
	else
		cout << num_arr.at(index - 1);
	return 0;
}
  • 간단하게 배열을 하나 만들어서 약수일 때, 그 배열에 값을 넣고 인덱스 접근으로 해결해주었다.
  • index가 size보다 크게 오는 경우가 있기 때문에 예외처리를 해주어야 한다.

9506 약수들의 합

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	while (true)
	{
		int num;
		int check_num = 0;
		vector<int> num_arr;
		cin >> num;
		if (-1 == num)
			break;
		for (int i = 1; i <= num; ++i)
		{
			if (0 == num % i)
			{
				num_arr.push_back(i);
				check_num += i;
			}
		}
		if (check_num - num_arr.back() == num)
		{
			cout << num << " = ";
			for (int idx = 0; idx < num_arr.size() - 1; ++idx)
			{
				if (idx == num_arr.size() - 2)
					cout << num_arr[idx] << "\\n";
				else
					cout << num_arr[idx] << " + ";
			}
		}
		else
			cout << num << " is NOT perfect." << "\\n";

	}
	return 0;
}
  • 약수문제를 풀었다면 똑같이 접근해서 풀 수 있다.

KEYWORD

가상메모리(Virtual Memory)

  • 주기억장치의 부족한 물리적 저장공간을 보조기억장치를 이용해서 가상으로 늘려주는 기술이다.
  • 프로세스 전체게 메모리 내에 올라오지 않더라도 실행이 가능하도록 하는 기법이다.
    • 실행에 필요한 부분만 메모리에 올려 실행한다.
  • CPU는 TLB, MMU를 사용하여 가상 메모리 주소에 접근한다.
  • Paging 또는 Segmentation을 사용한다

장점

  • 실제 메모리보다 더 큰 프로그램을 실행할 수 있다.
  • 한정된 메모리 내에서 더 많은 프로그램을 동시에 실행할 수 있다.

단점

  • 가상 메모리로 실행하는 것은 물리 메모리로 실행하는 것보다 느리다.

페이징(Paging)

  • 물리 메모리를 일정한 크기인 Frame으로 나누고, 논리 메모리를 frame과 동일한 크기의 page로 나눈다. 이후 필요한 page를 frame에 적재하고 실행한다.
  • 각 page는 연속적이지 않은 공간에 존재할 수 있다
  • .각 프로세스는 각자의 page table을 가진다.

장점

  • 가상메모리 사용의 장점을 가진다
  • 외부단편화가 발생하지 는다

단점

  • 내부단편화가 발생한다.

요구페이징(Demand Paging) 기법

  • 실행 중 필요한 시점에 필요한 데이터만 물리 메모리에 적재하는 방법
  • 페이지 교체 알고리즘이 필요하다
  • 한정된 메모리 활용에 효율적이다
  • Locality of Reference로 인해 page fault 확률이 줄어든다.

페이지 폴트(Page Fault)

  • 필요한 페이지가 물리 메모리에 없을 때 발생하는 인터럽트를 말한다.
    1. CPU는 물리 메모리를 확인하여 페이지가 없으면 trap을 발생하여 운영체제에 알린다.
    2. 운영체제는 CPU의 동작을 잠시 멈춘다.
    3. 운영체제는 페이지 테이블을 확인하여 가상메모리에 페이지가 존재하는지 확인하고, 없으면 프로세스를 중단한다.
    4. Page Fault면, 현재 물리 메모리에 비어있는 프레임(Free Frame)이 있는지 찾는다.
      1. page fault가 발생하면 os가 해당 페이지를 저장공간에서 가져온다
    5. 비어있는 프레임에 해당 페이지를 로드하고, 페이지 테이블을 최신화 한다.
      1. 비어있는 프레임이 없다면 희생 프레임을 골라야 하는데, 이 과정에서 페이지 교체 알고리즘이 사용된다.
    6. 중단되었던 CPU를 다시 시작한다.
728x90

'Study > TIL(Today I Learned)' 카테고리의 다른 글

24.02.21 CSAPP, TCP/IP, 백준, C++  (1) 2024.02.22
24.02.20 퀴즈, CSAPP, 백준  (1) 2024.02.20
24.02.18 CSAPP 11, Keyword  (0) 2024.02.18
24.02.17 묵시적 리스트, 백준, C++  (1) 2024.02.18
24.02.16 간단한 정리, 코드리뷰에 대해, 백준, C++  (0) 2024.02.17

'Study/TIL(Today I Learned)'의 다른글

  • 현재글24.02.19 CSAPP, 백준, Keyword

관련글

티스토리툴바