운영체제

섹션 4. 프로세스 동기화

4-1. 프로세스간 통신

프로세스는 독립적으로 실행되기도 하지만, 다른 프로세스와 데이터를 주고받으며 통신을 하는 경우도 있음

프로세스 통신의 종류

파일과 파이프를 이용하는 방법(프로세스 간 통신 방법)
1. 파일: 통신하려는 프로세스들이 하나의 파일을 이용해 읽고 쓰는 방법
2. 파이프: 운영체제가 생성한 파이프를 이용해 데이터를 읽고 쓰는 방법
쓰레드를 이용하는 방법(프로세스 내 쓰레드 간 통신 방법)
1. 쓰레드는 코드, 데이터, 힙 영역을 공유하고 스택만 각자 지니고 있음
2. 데이터 영역의 전역변수나 힙을 이용하면 통신이 가능함
네트워크를 이용하는 방법
1. 운영체제가 제공하는 소켓 통신
2. RPC(원격 프로시저 호출)를 이용한 통신: 다른 컴퓨터에 있는 함수를 호출하는 방법

4-2. 공유자원과 임계구역

프로세스 간 통신을 할 때 공동으로 이용하는 변수나 파일들을 공유자원 이라고 일컬음

공유자원은 여러 프로세스가 공유하고 있기 때문에 각 프로세스의 접근 순서에 따라 결과가 달라질 수 있음. 또한 컨텍스트 스위칭으로 시분할 처리를 하기 때문에 어떤 프로세스가 먼저 실행되고 어떤 프로세스가 나중에 실행되는지 예측하기가 힘듦

따라서 연산결과를 예측하기가 힘들고, 여기서 발생한 문제를 동기화 문제라고 부름

따라서 여러 프로세스가 동시에 사용하면 안되는 영역이 임계 구역(Critical Section)임

공유자원을 서로 사용하기 위해 경쟁하는 것은 경쟁조건(Race Condition)

임계구역 문제를 해결하기 위해서는 상호 배제(Mutual Exclusion) 메커니즘이 필요함

상호 배제의 요구사항
- 임계구역엔 동시에 하나의 프로세스만 접근한다.
- 여러 요청에도 하나의 프로세스의 접근만 허용한다.
- 임계구역에 들어간 프로세스는 빠르게 나와야한다.

4-3. 세마포어

상호배제 메커니즘 중 하나. 여러 프로세스나 스레드의 공유 자원 접근을 제어하는 동기화 도구로써 정수형 변수로 이루어짐.

4-4. 모니터

세마포어의 단점을 해결한 상호배제 메커니즘

운영체제가 처리하는 것이 아닌 프로그래밍 언어 차원에서 지원하는 방법

모니터의 구현만 완벽하다면 프로그래머는 세마포어처럼 wait(), signal() 함수를 임계영역에 감싸지 않아도 돼서 편리하고 안전하게 코드를 작성할 수 있음

섹션 5. 데드락

5-1. 데드락이란?(feat. 식사하는 철학자)

교착상태(데드락) 이란 여러 프로세스가 서로 다른 작업이 끝나기를 기다렸다가 아무도 작업을 진행하지 못하는 상태

공유자원 때문에 교착상태가 발생함

교착상태의 필요조건 4가지

상호배제 - 어떤 프로세스가 한 리소스를 점유했다면, 그 리소스는 다른 프로세스에게 공유가 되면 안됨
비선점 - 프로세스 A가 리소스를 점유하고 있는데, 프로세스 B가 리소스를 뺏을 수 없어야함
점유와 대기 - 어떤 프로세스가 리소스A를 가지고 있는 상태에서 리소스 B를 원하는 상태여야 함
원형 대기 - 점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있음

이중에 한가지라도 충족하지 않는다면 교착상태는 발생하지 않음.

5-2. 데드락 해결(feat. 은행원 알고리즘)

교착상태 회피(Deadlock avoidance)란 프로세스들에게 자원을 할당할 때 어느정도 자원을 할당해야 교착상태가 발생하는지 파악해서 교착상태가 발생하지 않는 수준의 자원을 할당하는 것 교착상태 회피는 전체 자원의 수와 할당된 자원의 수를 기준으로 안정상태(Safe state), 불안정 상태(Unsafe state)로 나눔. 불안정상태에 있더라도 무작정 교착상태에 빠지는것이 아니라, 교착상태에 빠질 확률이 높아짐

운영체제는 프로세스들에게 자원을 할당하기 전에 자기가 가지고 있는 전체 자원의 수를 알고 있어야함. 이가 시스템의 총 자원.

그리고 프로세스들은 각자 자기가 필요한 자원의 최대숫자를 운영체제에게 알려줘야 함.

이가 최대 요구 자원.

불안정 상태에 있더라도 모든 프로세스가 최대 자원을 요청하지 않는다면 교착상태에 빠지지 않을 수도 있지만 불안정상태에 빠지지 않도록 유지하는게 좋음

은행원 알고리즘은 교착상태를 피하는 좋은 방법이지만 비용이 비싸고, 비효율적임

그래서 교착상태는 허용하지만, 발생했을때 이를 해결하는 방식을 연구함

교착상태 검출 방식

가벼운 교착 상태 검출
1. 타이머를 이용하는 방식. 프로세스가 일정시간 동안 작업을 진행하지 않는다면 교착상태가 발생했다고 간주하고 교착상태를 해결함
2. 해결법 - 일정 시점마다 체크포인트를 만들어 작업을 저장하고 타임아웃으로 교착상태가 발생했다면 마지막으로 저장한 체크포인트로 롤백함
무거운 교착 상태 검출
1. 자원 할당 그래프를 이용하는 방식. 현재 운영체제에서 프로세스가 어떤 자원을 사용하는지 지켜보고 교착상태가 발생하면 해결함
2. 해결법 - 교착상태가 검출되면 교착상태를 일으킨 프로세스를 강제종료 시킴. 그리고, 다시 실행시킬 때 체크포인트로 롤백 시킴. 이 방식은 운영체제가 지속적으로 “자원 할당 그래프”를 유지하고 검사해야 하기에 오버헤드가 발생함. 하지만 가벼운 교착 상태 검출에서 발생할 수 있는 억울하게 종료되는 프로세스가 발생되지 않음

섹션 6. 쉬어가기

6-1. 컴파일과 프로세스

컴파일 언어: 컴파일 과정에서 개발자가 문법 오류를 일으켰는지 검사를 하고, CPU에서 처리 가능한 기계어로 실행파일을 만들어 놓기에 속도가 빠름
인터프리터 언어: 인터프리터 언어는 개발자가 작성한 코드를 미리 기계어로 만들지 않고, 실행 시 코드를 한 줄씩 해석해 실행하는 언어. 미리 검사하지 않기 때문에 실행할 때 오류가 날 수도 있고, 속도도 컴파일 언어와 비교하면 느림

컴파일 과정

전처리 단계: 전처리 구문 처리
컴파일러 단계: 기계어에 가까운 어셈블리어로 변환
어셈블러 단계: 오브젝트 파일로 변환. 0과 1로 된 기계어로 구성
링커 단계: 모든 오브젝트 파일을 하나의 코드영역과 데이터영역으로 묶음. 실제로 실행될 주소를 매핑시킴. 링커까지 거친 후 .exe 실행 파일 생성

섹션 7. 메모리

7-1. 메모리 종류

레지스터: 가장 빠른 기억장소로 CPU 내에 존재하고 있음. 컴퓨터의 전원이 꺼지면 데이터가 사라지기에 휘발성 메모리로 불림. 32bit, 64bit는 레지스트리의 크기를 말함. CPU는 계산을 할 때 메인메모리에 있는 값을 레지스터로 가져와 계산함. 계산 결과는 다시 메인메모리에 저장
캐시: 휘발성 메모리. 미리 가져온 데이터들을 저장. 캐시는 성능의 이유로 여러 개 두고 사용함. CPU가 값을 요청해 레지스터로 값을 옮겨야 한다면 단계에 따라 가장 속도가 빠른 L1 → L2 → 메인 메모리 순으로 참조함. 즉 빠른 캐시에 있는 값을 먼저 찾으려고 함
메인 메모리(RAM): 실제 운영체제와 다른 프로세스들이 올라가는 공간. 전원이 공급되지 않으면 데이터가 지워지기에 휘발성임. HDD, SDD 보다 속도는 빠르지만 가격이 비싸기에 데이터를 저장하기보다는 실행중인 프로그램만 올림
보조저장장치(HDD, SSD): 다른 메모리에 비해 비교적 가격이 저렴하고, 전원이 공급되지 않아도 데이터가 지워지지 않는 비휘발성 메모리.

7-2. 메모리와 주소

운영체제는 메모리를 관리하기 위해서 1바이트 크기로 구역을 나누고 숫자를 매김.

이 숫자는 곧 “주소”. 각 CPU의 bit는 레지스터 크기, ALU, 버스의 크기가 동일함.

물리주소와 논리주소

0x0번지부터 시작하는 주소공간 = 물리 주소 공간

사용자 관점에서 바라본 주소공간 = 논리 주소 공간

사용자는 물리 주소를 몰라도 논리 주소로 물리 주소에 접근할 수 있음.

운영체제는 특별하기에 메모리에 따로 공간을 마련해둠.

그래서 하드웨어적으로 운영체제 공간과 사용자 공간을 나누는 경계 레지스터를 만듦.

경계 레지스터는 CPU내에 존재하는 레지스터로 메모리 관리자가 사용자 프로세스가 경계 레지스터의 값을 벗어났는지 검사하고 만약 벗어났다면 그 프로세스를 종료 시킴.

절대주소와 상대주소

개발자는 프로그램을 만들 때 프로그램이 실행될 주소를 신경쓰지 않고 개발함. 이는 컴파일러가 컴파일을 할 때 메모리 0번지에서 실행한다고 “가정”하기 때문.

7-3. 메모리 할당방식

메모리 오버레이란? 유니프로그래밍 환경에서 메모리보다 더 큰 프로그램을 실행시키기 위해 큰 프로그램을 메모리에 올릴 수 있도록 잘라 당장 실행시켜야 할 부분만 메모리에 올리고, 나머지는 하드디스크에 저장하는 기법.

현대의 멀티프로그래밍 환경에서 메모리를 나누는 방식

가변 분할 방식: 가변 분할 방식이란 프로세스의 크기에 따라 메모리를 나누는 방식
고정 분할 방식: 프로세스 크기와 상관없이 메모리를 할당

가변 분할 방식

한 프로세스가 메모리에 연속된 공간에 할당되기에 연속 메모리 할당이라고 함

가변 분할 방식은 프로세스의 크기에 딱 맞게 할당되기에 낭비되는 공간인 “내부 단편화”가 없음

단점으로는 “외부 단편화”가 발생함

고정 분할 방식

프로세스가 쪼개져 할당되어 여러곳에 할당됨

고정 분할 방식의 장점은 구현이 간단하고 오버헤드가 적음

단점으로는 작은 프로세스도 큰 영역에 할당돼서 공간이 낭비되는 “내부 단편화”가 발생

버디 시스템

가변 분할 방식과 고정 분할 방식을 혼합해 단점을 최소화함

버디 시스템은 2의 승수로 메모리를 분할해 메모리를 할당하는 방식

프로세스가 종료후 해제되도, 근접한 메모리 공간을 합치기 쉬움

알고리즘&자료구조

섹션 3. 알고리즘

재귀(Recursion)

함수가 자기 자신을 호출하는 프로그래밍 방식
큰 문제를 동일한 형태의 작은 문제로 나누어 해결

재귀 함수를 사용하기 위해서는 기저 조건(탈출 조건)이 필요함

팩토리얼(Factorial)

n!로 표시
1부터 n까지의 모든 양의 정수를 곱한 값

하향식 계산

큰 문제 → 작은 문제로 분할
가장 작은 문제(기저 조건)까지 내려감
결과를 다시 위로 올라가며 조합

버블정렬(Bubble Sort)

앞에 있는 숫자와 옆에 숫자를 비교해 자리를 바꾸는 알고리즘

장점: 이해와 구현이 간단함
단점: 성능이 좋지 않음

시간복잡도

O(n²)

선택정렬(Selection Sort)

배열에서 최솟값을 찾아 맨 앞으로 이동하는 정렬. 정렬되지 않은 부분에서 가장 작은 요소를 선택하여 정렬된 부분의 끝에 추가함

장점: 이해와 구현이 간단함
단점: 성능이 좋지 않음