![[워밍업 클럽 3기 CS 전공지식] 2주차 회고](https://cdn.inflearn.com/public/files/blogs/8cefe2aa-1067-4482-9aad-4b066478c570/인프런 워밍업클럽 스터디 3기.png)
[워밍업 클럽 3기 CS 전공지식] 2주차 회고
[2 주차 시작하기 전 다짐]
아침에 일어나서 주어진 강의 분량을 다 듣기
틈날 때 강의 듣기
저녁에 집에 와서 다시 듣기 또는 실습 진행
강의 들으면서 강의 노트도 실시간으로 작성하기!
[2 주차 회고]
칭찬할 점
2 주차 다짐을 모두 지켰다!
=> 꾸준히 하는 걸 힘들어하는 나에게 칭찬하고 싶다.
아쉬운 점
강의 노트를 적는 동안은 생각을 안 하고 따라 치기만 한 것 같다.
=> 강의를 듣고 그 날 강의 노트를 정리하는 시간을 가지자.
[강의 내용 정리]
[운영체제]
[프로세스 동기화]
프로세스 간 통신
프로세스는 독립적으로 실행되기도 하지만 다른 프로세스와 데이터를 주고받으며 통신을 하는 경우도 있다.
종류
한 컴퓨터 내에서 프로세스 간 통신
파일을 이용한 방법
통신을 하려는 프로세스들이 하나의 파일을 이용해 읽고 쓰는 방법
파이프를 이용한 방법
운영체제가 생성한 파이프를 이용해 데이터를 읽고 쓰는 방법
한 프로세스 내에서 쓰레드 간 통신
쓰레드는 코드, 데이터, 힙 영역을 공유하고 스택만 자기의 것을 가진다.
데이터 영역에 있는 전역변수나 힙을 이용하면 통신이 가능하다.
네트워크를 이용한 통신
운영체제가 제공하는 소켓 통신하는 방법
다른 컴퓨터에 있는 함수를 호출하는 RPC(원격 프로시저 호출)를 이용해 통신하는 방법
공유자원과 임계구역
공유자원
프로세스 간 통신을 할 때 공동으로 이용하는 변수나 파일들
문제
여러 프로세스가 공유하고 있어서 각 프로세스의 접근 순서에 따라 결과가 달라진다.
컨텍스트 스위칭으로 시분할 처리를 하기 때문에 어떤 프로세스가 먼저 실행될 지 예측하기 어렵다.
연산 결과를 예측하기 힘들다. 여기서 발생한 문제가 '동기화 문제' 이다.
그러니 예측 불가능하고 손 댈 수 없는 운영체제 보다는 예측 가능하고 손 댈 수 있는 코드를 수정하는 게 최선이다.
동기화 문제
여러 프로세스 또는 여러 쓰레드가 공유 자원에 동시에 접근할 때 발생하는 문제이다.
적절한 제어 없이 데이터가 동시에 수정되면 경쟁 조건(Race Condition)이 발생하여 예측 불가능한 결과나 데이터 불일치가 일어난다.
해결 방법으로는 세마포어, 모니터 등의 동기화 기법을 사용한다.
임계구역(Critical Section)
여러 프로세스가 동시에 사용하면 안되는 영역
임계구역 문제를 해결하기 위해서는 '상호 배제(Mutual Exclusion)' 메커니즘'이 필요하다.
상호 배제(Mutual Exclusion) 요구사항 세가지
임계영역에는 동시에 하나의 프로세스만 접근한다.
(동시에) 여러 요청에도 하나의 프로세스의 접근만 허용한다.
임계구역에 들어간 프로세스는 빠르게 나와야 한다.
그렇지 않으면 다른 프로세스들이 오래 기다려야 한다.
세마포어(Semaphore)
상포배제 메커니즘의 한 가지이다.
정수형 변수이다.
공유되는 자원의 개수에 따라 세마포어의 초기값 숫자를 설정한다.
wait() 함수로 시작하고 signal() 함수로 끝나야 한다. 사이에 코드 작성
세마포어를 이용하면 공유자원에 여러 프로세스가 동시에 접근하지 못하기 때문에 동기화 문제가 발생하지 않는다.
단점
wait(), signal() 함수의 순서를 이상하게 호출해서 잘못 사용할 경우가 있다.
=> 이것을 해결한 방법은 '모니터'이다.
모니터(Monitor)
세마포어의 단점을 해결한 상호배제 메커니즘
운영체제가 처리하는 것이 아닌 프로그래밍 언어 차원에서 지원하는 방법
대표적으로 Java 에서 모니터를 지원
synchronized 키워드
해당 키워드가 붙은 함수들은 동시에 여러 프로세스에서 실행시킬 수 없다.
상호배제가 완벽하게 이루어진다.
[데드락]
교착 상태(데드락)
여러 프로세스가 서로 다른 프로세스의 작업이 끝나기를 기다리다가 아무도 작업을 진행하지 못하는 상태
발생 이유
여러 프로세스가 공유하는 자원 때문이다.
자원을 공유하지 않으면 교착 상태가 발생하지 않는다.
유명한 예시
식사하는 철학자
교착 상태의 필요조건
교착상태가 발생하기 위해서는 4가지 필요 조건이 모두 충족되어야 한다.
상호배제
프로세스A가 한 자원을 점유했다면 그 자원은 프로세스B에게 공유가 되면 안된다.
비선점
프로세스A가 자원을 점유하고 있는데 프로세스B가 자원을 빼앗을 수 없어야 한다.
점유와 대기
어떤 프로세스가 자원A를 가지고 있는 상태에서 자원B를 원하는 상태여야 한다.
원형 대기
점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있다.
해결
교착 상태 회피(Deadlock avoidance)
프로세스들에게 자원을 할당할 때 어느 정도 자원을 할당 했을 때 교착 상태가 발생하는지 파악해서 교착 상태가 발생하지 않는 수준의 자원을 할당한다.
전체 자원의 수와 할당된 자원의 수를 기준으로 안정 상태(Safe state)와 불안정 상태(Unsafe state)로 나뉜다.
운영체제가 최대한 안정 상태를 유지하려고 한다.
불안정 상태에 있더라도 무조건 교착 상태에 빠지는 건 아니고 교착 상태에 빠질 확률이 높아진다.
은행원 알고리즘
돈을 빌려줄 때 사업가들의 상환 능력도 보면서 빌려준다.
교착 상태 발생했을 때 해결
교착 상태를 막지 못한다. 그래서 교착 상태가 발생했을 때 해결하는 방법을 알아보자.
가벼운 교착 상태 검출
타이머를 이용한 방식
프로세스가 일정 시간 동안 작업을 진행하지 않는다면 교착상태가 발생한 걸로 간주하고 해결한다.
교착 상태 해결
일정 시점마다 체크포인트를 만들어 작업을 저장한다.
타임아웃으로 교착상태가 발생했다면 마지막으로 저장했던 체크포인트로 롤백한다.
무거운 교착 상태 검출
자원 할당 그래프를 이용
현재 운영체제에서 프로세스가 어떤 자원을 사용하는지 지켜보고 교착상태가 발생했다면 해결한다.
프로세스들 간 자원 점유와 대기가 순환구조가 생긴다면 교착상태가 생긴 그래프이다.
교착상태를 검출했다면 교착상태를 일으킨 프로세스를 강제종료 시킨다.
그리고 다시 실행시킬 때 체크포인트로 롤백을 시킨다.
운영체제가 지속적으로 자원 할당 그래프를 유지하고 검사해야 하기 때문에 오버헤드가 발생한다.
가벼운 교착상태 검출에서 발생할 수 있는 억울하게 종료되는 프로세스는 발생하지 않는다.
[프로그래밍 언어, 프로세스]
프로그래밍 언어
컴파일 언어
개발자가 코드를 작성하고 컴파일 과정을 거쳐서 0과 1로된 기계어로 실행파일을 만든다.
컴파일 과정에서 문법 오류를 검사하고 CPU에서 처리가능한 기계어로 실행파일을 만들어 놓기 때문에 속도가 빠르다.
C, C++, C# 등이 이에 속한다.
인터프리터 언어
개발자가 작성한 코드를 미리 기계어로 만들지 않고 실행 시 코드를 한 줄씩 해석해 실행하는 언어이다.
미리 검사를 하지 않기 때문에 실행할 때 오류가 날 수 있고 속도도 컴파일 언어와 비교하면 느리다.
JavaScript, Python, Ruby 등이 이에 속한다.
프로세스의 메모리 구조
코드 영역, 데이터 영역, 스택 영역, 힙 영역으로 나뉜다.
코드 영역
말 그대로 실행해야 할 코드가 들어가는 영역
데이터 영역
전역변수나 배열이 들어가는 영역
스택과 힙은 프로세스가 실행될 때 할당되는 메모리
스택 영역
지역변수와 함수 관련 값들
힙 영역
실행중에 메모리 공간을 할당할 수 있는 유동적인 공간
프로그램을 실행 시켰을 때
사용자가 프로그램을 실행시키면 운영체제가 프로세스를 만든다.
운영체제는 exe 파일에 있는 코드 영역과 데이터 영역을 가져온다.
프로세스의 코드 영역과 데이터 영역에 넣어준다.
빈 상태의 스택과 힙을 할당한다.
PCB(Process Control Block)를 만들어 관리가 가능하도록 만든다.
프로그램 카운터 즉, 다음 실행할 명령어의 주소를 생성한 프로세스의 코드 영역의 첫 번째 주소로 설정한다.
운영체제의 CPU 스케줄링에 따라서 프로세스가 실행되다기 작업을 마친다.
[메모리]
메모리 종류
레지스터, 캐시, 메인메모리(RAM), 보조저장장치(하드디스크(이하 HDD), SSD)
오른쪽으로 갈수록 가격은 싸지고 용량은 커진다. 속도는 느려진다.
레지스터
가장 빠른 기억 장소로 CPU 내에 존재한다.
컴퓨터 전원이 꺼지면 데이터가 사라진다. 휘발성 메모리라고 부른다.
32bit 레지스터를 가지고 있으면 32bit CPU라고 말한다.
64bit 레지스터를 가지고 있으면 64bit CPU라고 말한다.
CPU는 계산 할 때 메인메모리에 있는 값을 레지스터로 가져와서 계산한다. 계산 결과는 다시 메인메모리에 저장시킨다.
캐시
레지스터와 메인메모리에서 중간 단계 역할을 한다.
레지스터는 CPU가 사용하는 메모리로 굉장히 빠르다. 그에 비해 메인메모리는 너무나 느리다.
메인메모리에 있는 값을 레지스터로 옮기려면 한참 걸린다. 그래서 필요할 것 같은 데이터를 미리 가져오기로 한다.
미리 가져온 데이터를 저장하는 곳이 바로 캐시이다.
메인메모리(RAM)
운영체제와 다른 프로세스들이 올라가는 공간이다.
전원이 공급되지 않으면 데이터가 지워져 휘발성 메모리이다.
HDD나 SSD 보다는 속도는 빠르지만 가격이 비싸기 때문에 데이터를 저장하기 보다 실행중인 프로그램만 올린다.
보조저장장치인 HDD와 SSD
가격이 저렴하고 전원이 공급되지 않아도 데이터가 지워지지 않는 비휘발성 메모리이다.
저장 작업하기에 좋다.
메모리와 주소
운영체제는 메모리를 관리하기 위해 1바이트 크기로 구역을 나누고 숫자를 매긴다.
이 숫자를 '주소'라고 부른다. - 1바이트(8비트)마다 주소를 가지고 있다.
물리 주소와 논리 주소
물리 주소
메모리 0x0번지부터 시작하는 주소 공간
논리 주소
사용자 관점에서 바라본 주소 공간
사용자는 물리 주소를 몰라도 논리 주소로 물리 주소에 접근할 수 있다.
경계 레지스터
하드웨어적으로 운영체제 공간과 사용자 공간을 나누는 경계 레지스터
절대 주소와 상대 주소
절대 주소
실제 프로그램이 올라간 주소는 0x4000번지로 메모리 관리자가 바라본 주소이다.
상대 주소
컴파일러는 0x0번지라고 가정해서 프로그램 만든다.
사용자가 바라본 주소인 '상대 주소'는 '논리 주소 공간'이라고 부른다.
메모리 관리자가 바라본 주소인 '절대 주소'는 '물리 주소 공간'이라고 부른다.
메모리 관리자
CPU가 요청한 상대 주소와 재배치 레지스터에 있는 절대 주소를 더해서 데이터에 접근한다.
재배치 레지스터
프로그램의 시작 주소가 저장되어 있다.
시작 영역이 바뀌면 재배치 레지스터만 변경해주면 된다. 그래서 굉장히 유연하다.
메모리 할당방식
유니프로그래밍 환경에서 메모리보다 더 큰 프로그램을 실행시키는 방법
메모리 오버레이(memory overlay)
큰 프로그램을 작게 나누어 일부만 실행하고 일부는 HDD의 스왑 영역에 저장된다.
스왑(swap)
스왑 영역에 있는 데이터 일부를 메모리로 가져오고 메모리에 있는 데이터를 스왑 영역으로 옮긴다.
멀티프로그래밍 환경에서 메모리 관리
가변 분할 방식
프로세스의 크기에 따라 메모리를 나누는 방식
프로세스가 크면 메모리도 크게 할당
한 프로세스가 메모리에 연속된 공간에 할당되서 '연속 메모리 할당'이라고 한다.
장점
메모리에 낭비되는 공간이 없다. - 내부 단편화가 없다.
단점
외부 단편화가 발생한다.
외부 단편화
메모리 할당 해제 된 자리를 더하면 새로운 프로그램을 올릴 수 있는데 따로 따로 자리가 있어서 다른 프로그램을 올릴 수 없다.
해결
외부 단편화가 발생한 공간을 합쳐주는 조각모음을 하면된다.
고정 분할 방식
프로세스의 크기와는 상관없이 메모리를 정해진 크기로 나누는 방식
프로세스 크기와 상관없이 메모리를 할당
한 프로세스가 메모리에 분산되어 할당되어서 '비연속 메모리 할당'이라고 한다.
장점
구현이 간단하고 오버헤드가 적다.
단점
메모리에 낭비되는 공간이 있다. - 내부 단편화가 발생한다.
가상 메모리에서 가변 분할 방식은 '세그멘테이션', 고정 분할 방식은 '페이징'이라고 부른다.
버디 시스템
가변 분할 방식과 고정 분할 방식의 단점을 최소화한 시스템
2의 승수로 메모리를 분할해 메모리를 할당하는 방식
프로세스가 사용을 마치고 메모리에서 나가도 근접한 메모리 공간을 합치기 쉽다.
장점
가변 분할 방식처럼 프로세스 크기에 따라 할당되는 메모리 크기가 달라진다.
외부 단편화를 방지하기 위해 메모리 공간을 확보하는 것이 간단하다.
고정 분할 방식처럼 내부 단편화가 발생하기는 하지만 많은 공간의 낭비가 발생하지 않는다.
[자료구조와 알고리즘]
재귀
사전적 정의 : 어떠한 것을 정의할 때 자기 자신을 참조하는 것
재귀 함수
재귀적으로 정의된 함수
기저 조건(탈출 조건)이 반드시 있어야 한다.
if() 로 함수를 종료하지 않으면 콜스택에 메모리 공간이 가득 차서 자동으로 종료된다.
=> java.lang.StackOverflowError 에러 발생콜스택
함수가 호출되면서 올라가는 메모리 영역으로 스택이라고 부른다.
스택의 특성처럼 먼저 들어온 데이터가 나중에 나간다. (FILO : First In Last Out)
함수를 호출하면 해당 함수는 콜스택에 올라가게 되고 함수가 종료되면 콜스택에서 제거된다.
public class Recursion {
public static void main(String[] args) {
myFunction(1);
}
public static void myFunction(int number) {
if (number > 10) return;
System.out.println(number);
myFunction(number + 1);
}
}재귀 함수 - 팩토리얼
n이 주어질 때 1부터 n까지 모든 수의 곱을 말한다.
예시) 5! => 5*4*3*2*1 => 120
재귀 함수 쉽게 작성하는 방법
재귀 함수 내에서 자기 자신을 호출할 때 이 함수가 벌써 구현이 되어 있다고 가정하자.
5! 구현하기
5 * 4!(4*3*2*1) => 하위 4 * 3!(3*2*1) => 하위 3 * 2!(2*1) => 하위 2 * 1!(1)
factorial() 함수가 이미 구현되었다고 가정하면 5 * factorial(4)를 호출하면 된다.
이를 일반화 하면 number * factorial(number-1)
그리고 중요한 기저 조건을 만들어야 한다.
1이 되면 팩토리얼은 종료된다.
0! 은 1이기 때문에 같이 기저 조건에 넣겠다.
public class Factorial {
public static void main(String[] args) {
System.out.println(factorial(5)); // 120
}
public static int factorial(int number) {
if (number == 1 || number == 0) {
return 1;
} else {
return number * factorial(number - 1);
}
}
}재귀적으로 생각하기
패턴1
단순히 반복 실행
콜스택 공간을 많이 차치해 성능은 for문보다 좋지 않다.
패턴2
하위 문제의 결과를 기반으로 현재 문제를 계산하는 것
재귀를 이용해 하위 문제의 결과를 기반으로 현재 문제를 계산하는 방식 - 하향식 계산
재귀를 이용해서 상향식 계산도 가능하다.
재귀 함수의 진정한 위력은 하향식 계산에서 발휘된다.
재귀 - 하노이탑 (정리 한번하기)
재귀 함수의 대표적인 예시
하향식 계산 방식을 보여줄 수 있는 좋은 예시이다.
세 개의 기둥과 서로 다른 크기의 원반들이 있다.
가장 큰 원반이 아래에 있고 위로 갈수록 작은 원반으로 이루어져 있다.
현재 기둥에서 다른 기둥으로 옮겨야 한다.
규칙
한 번에 하나의 원반을 움직일 수 있다.
가장 위에 있는 원반만 옮길 수 있다.
아래에 작은 원반이 올 수 없다.
하위 문제 찾기 (재귀함수를 이용해서 하향식으로 접근)
[깃허브 코드]
이미 해결을 한 상황을 예상해보기 (하위 문제)
첫 번째 목표 : 원반3을 기둥A에서 기둥C로 옮긴다.
하위 문제1 : 원반3 위에 있는 원반1,2를 기둥A에서 기둥B로 옮겨야 한다.
hanoi(count - 1, from, temp, to);
하위 문제2 : (하위 문제1) 이 해결되었다면 출력
System.out.printf("원반 %d을/를 %s에서 %s로 이동%n", count, from, to);
=> 원반 3을 A에서 C로 이동
하위 문제3 : (하위 문제2) 가 해결되었다면
=> 두 번째 목표 : 원반1,2를 기둥 B에서 기둥C로 옮겨야 한다.hanoi(count - 1, temp, to, from);
기저 조건(탈출 조건)
원반이 없는 경우, 옮길 원반이 없을 때
if (count == 0) return;
정렬 - 버블정렬
가장 쉽게 생각할 수 있는 정렬 중 하나이다.
구현하기 쉽지만, 성능은 좋지 않다.
앞에 있는 숫자와 옆에 숫자를 비교해서 자리를 바꾸는 알고리즘이다.
방식
앞에서부터 요소들을 하나씩 비교한다.
가장 큰 숫자는 자기 위치를 찾아 가장 끝에 정렬된다.
이미 정렬된 마지막 원소를 제외하고 앞에서부터 다시 요소를 검사한다.
남은 원소가 하나이면 더이상 정렬을 할 필요가 없다.
성능
반복 횟수 for문 * 원소비교 for문 => O(n제곱)
성능이 좋지 않다.
장점
가장 쉽게 생각할 수 있는 정렬 방법으로 이해와 구현이 간단하다.
단점
성능이 O(n제곱)으로 좋지 않다.
정렬 - 선택정렬
버블정렬과 마찬가지로 구현이 쉬운 알고리즘
이해와 구현이 간단하지만 성능이 아쉽다.
방식
정렬된 영역과 정렬되지 않은 영역을 나눠서 정렬되지 않은 영역을 비교한다.
정렬되지 않은 첫 번째 원소를 시작으로 마지막 원소까지 비교 후 가장 작은 값을 첫 번째 원소로 가져온다.
첫 번째 원소는 정렬된 영역으로 제외하고 다시 정렬되지 않은 영역을 비교한다.
정렬되지 않은 영역에 요소가 한 개 남으면 정렬할 필요없이 끝이난다.
성능
반복 횟수 for문 * 원소비교 for문 => O(n제곱)
성능이 좋지 않다.
장점
이해하기 쉽고 구현이 간단하다.
단점
성능이 O(n제곱)으로 좋지 않다.
※ '강의 내용 정리' 출처
[인프런 / 그림으로 쉽게 배우는 운영체제 (감자) / 섹션 4~7]
[인프런 / 그림으로 쉽게 배우는 자료구조와 알고리즘 (감자) / 섹션 3 (유닛 1~5)]
댓글을 작성해보세요.
