CS 전공지식 스터디 발자국 02

운영체제

Ch4

01 프로세스 간 통신

(1) 같은 컴퓨터 내의 프로세스끼리

파이프 이용 - 운영체제가 생성한 파이프를 이용해 데이터를 읽고 씀
쓰레드 이용 - 데이터나 힙 영역을 이용한 통신 (한 프로세스 내에서)

(2) 다른 컴퓨터의 프로세스끼리

네트워크 이용 - 소켓 통신, RPC(Remote Procedure Call)

02 공유자원과 임계구역

공유자원 - 프로세스 간 통신을 할 때 공동으로 이용하는 파일 - 동기화 문제 발생 (동시에 실행됐을 때 발생)

임계구역(Critical Section) - 여러 프로세스가 동시에 사용해서는 안 되는 영역

Race Condition - 공유자원을 사용하기 위해 경쟁하는 것

임계구역의 상호배제 메커니즘

(1) 임계영역에는 동시에 하나의 프로세스만 접근

(2) 여러 요청에도 하나의 프로세스 접근만 허용

(3) 임계구역에 들어간 프로세스는 최대한 빠르게 나올 것

03 세마포어(Semaphore)

대기 큐 - 공유자원을 쓰기 위한 프로세스들이 대기하는 공간

열쇠관리자 - 운영체제, 열쇠 - 세마포어(정수형 변수), 여러 개 가질 수 있음

int s = 1; // semaphore
wait(s) // lock

int currentHP = GetHealth();
health = currentHP - 10;

signal(s); // return

세마포어의 단점 - 잘못 사용할 가능성이 있음 (wait - signal 짝이 아닌 wait-wait, signal-signal 등)

04 모니터

세마포어의 단점을 보완한 상호배제 메카니즘: 프로그래밍 언어 차원에서 지원하는 방법

ex) java의 synchronized

Ch5

데드락

여러 프로세스가 서로 작업이 끝나는 상태를 기다리다가 아무런 프로세스도 작업을 진행하지 못하는 상태

(ex) 식사하는 철학자

교착상태의 필요조건 (모두 충족해야 교착상태 발생)

(1) 상호배제 - 어떤 프로세스가 리소스를 차지하였다면 그 리소스는 다른 프로세스에 공유되어서는 안 됨

(2) 비선점 - 다른 프로세스가 리소스를 빼앗을 수 없어야 함

(3) 점유와 대기

(4) 원형대기 - 점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있음

교착상태 해결 방법

교착상태 회피

전체 자원, 할당 자원의 수를 기준으로 안정 / 불안정 상태를 가짐

불안정(교착 상태에 빠질 확률이 높아짐)

(ex) 은행원 알고리즘 - 누구에게도 돈을 빌려주지도 못하고 받지도 못하는 교착상태를 방지하기 위함

자원을 할당하기 전, 전체 자원의 수 파악 (시스템의 총 자원)

프로세스가 필요한 자원 (최대 요구 자원)

→ 요청이 예상되는 자원을 파악하여 자원을 빌려 줌 (안정 상태)

→ 현재 사용 가능한 자원이 요청 예상 자원보다 적음 (불안정 상태)

비싸고, 비효율적인 알고리즘 ⇒ 교착상태를 해결하는 방식을 연구 (먼저 교착상태 여부를 파악)

(1) 가벼운 교착상태 검출 - 일정시간 작업을 진행하지 않을 때, 교착상태로 간주 → 마지막 체크포인트로 롤백

(2) 무거운 교착상태 검출 - 자원할당 그래프를 통해 교착상태를 일으킨 프로세스 강제종료, 체크포인트로 롤백

Ch7

메모리 종류

(1) 레지스터

휘발성 메모리, 32bit / 64bit (레지스터의 크기),

(2) 메인메모리

실제 프로세스들이 올라가는 공간

(3) 캐시

메인메모리에 있는 값을 옮길 때, 미리 저장 (L1, L2 캐시 등 속도에 따라)

(4) 보조저장장치(HDD, SSD)

비휘발성메모리, 저장장치

메모리와 주소

주소 (메모리 관리를 위해 설정)

(1) 물리주소와 논리주소

사용자가 인식하는 것(논리주소)

(2) 경계레지스터

운영체제 보호를 위해 설정

(3) 절대주소와 상대주소

컴파일러(상대주소), 실제 메모리 관리자가 확인하는 공간(절대주소)

재배치 레지스터(메모리 관리자)

메모리 할당 방식

메모리보다 더 큰 프로그램을 실행시키는 방법?

필요한 부분만 잘라서 실행, 일부는 하드디스크에 저장 - 오버레이

가변분할방식(세그멘테이션)

프로세스의 크기에 따라 메모리를 할당

내부단편화는 없으나 외부단편화(연속되지 않은 공간) 발생

고정분할방식(페이징)

고정된 크기에 따라 메모리를 할당

오버헤드 X, 작은 프로세스도 큰 영역에 할당돼서 공간이 낭비

내부단편화 발생(연속되지 않은 공간, 내부에서 발생하는 공간 낭비)

버디시스템

2의 승수로 메모리를 할당(내부단편화 최소화)

조립하기 쉬움(외부단편화 최소화)

알고리즘

재귀(Recursion)

재귀: 어떤 것을 정의할 때 자기 자신을 참조하는 것

재귀함수: 재귀적으로 정의된 함수

function myFunction(number){
if(number >10) return; // 기저조건
console.log(number);
myFunction(number+1);
}

myFunction(1) // 메모리가 꽉 찰 때까지 출력

탈출조건(기저조건)이 있어야 사용할 수 있음

콜스택 (FILO)

함수 A 호출 - A 내부에서 B 호출 - B 실행 (콜스택에서 제거) - A 끝 (콜스택에서 제거)

(ex)

function factorial(nubmer){
if(number ==1 || number == 0){
return 1}; else {
return number* factorial(number-1)
}
}

재귀적으로 생각하기

재귀의 패턴 (1) 반복실행 (반복문에 비해 이점이 없음)

재귀의 패턴 (2) 하위 문제의 결과를 기반으로 현재를 개선 (ex) 팩토리얼 함수 구현 (하향식 계산)

상향식 계산 (반복문으로도 가능)

Q1. 배열의 합

(1) 하위문제 파악 (2) 바탕으로 현재 구현식 작성 (3) 기저조건 추가

function sumArray(arr){
if(arr.length ==1) return arr[0]
return sumArray(arr.slice(0, -1)) + arr[arr.length -1];
}

Q2. 문자열의 길이

function strLength(arr){
if(arr[0]==null) return 0;
return strLength(arr.slice(0, -1))+1;
}

Q3. 지수함수

function power(x, n){
if(n==0) return 1;
return power(x, n-1)*x;
}

Q4. 하노이 탑

(1) 하위문제 파악 (2) 바탕으로 현재 구현식 작성 (3) 기저조건 추가

목표: 가장 큰 원판을 기둥 C로 옮기기 - 다른 원판들을 기둥 B로 옮기기 (하향식 접근)

function hanoi(count, from, to, temp){
if(count ==0) return;
hanoi(count -1, from, temp, to) // 기둥 B로 나머지를 옮기는 부분
hanoi(count -1, temp, to, from) // 나머지를 다시 기둥 C로 옮기는 부분
}

hanoi(3, "A", "C", "B")