[워밍업클럽3기] CS전공지식 2주차
기본편 - Section 03 알고리즘
재귀 (recursion)
사전적 정의: 어떠한 것을 정의할 때 자기 자신을 참조하는 것.
탈출조건(=기저조건)이 필수적으로 있어야함.
콜스택
함수가 호출되면서 올라가는 메모리 영역
FILO의 조건을 가짐
스택자료구조를 잘 활용한 대표적 사례
재귀함수는, 호출할 때마다 콜스택영역을 차지함
탈출조건이 없으면 콜스택에 계속 쌓이기만함-> 메모리부족->자동stop
for문 대신 사용하기보다는, 팩토리얼과 같이 더 쉽게 함수구현을 위한것임.
재귀함수내에서 자기자신을 호출할때, 이미 함수가 구현되어있다고 가정함.
재귀함수: 나 자신을 호출, 구현할때는 이미 구현된 것을 부르는 것처럼 구현하면 쉬움
재귀적으로 생각하기
pattern 01:
단순 반복실행
반복문으로 구현했을때보다 성능이 떨어짐
pattern 02:
하위 문제 결과를 기반으로 현재문제 계산
팩토리얼을 예를 들으면, return number*factorial(number -1);여기에서 하위문제(=factorial(number-1);)를 기반으로, 현재문제(number*factorial(number-1);)를 해결함
for문이용은 상향식 계산, 재귀함수를 이용하는 것은 하향식 계산
모든 재귀가 하향식은 아님
상향식: for문, 재귀함수 구현가능
(상향식에서 재귀함수는 매리트없음)
하향식: only 재귀함수만 가능
재귀 - 하노이탑
재귀함수의 대표적인 예
하향식 계산법의 대표적인 예임!
순서대로 예상 스택을 쌓아보면 알수 있음
1st stack
원반 3 -> 기둥 C
원반 2, 1 -> 기둥 B
원반 1 -> 기둥 C
위에서 1번째를 스택 제일 아래에 놓으면,원반 1 -> 기둥 C 부터 실행하게됨
2nd stack
원반 2 -> 기둥 C
원반 1 -> 기둥 A
버블정렬(Bubble sort)
배열에 무작위로 섞인 숫자 정렬 방법 중 1개
그 중 가장 쉽게 생각 할 수 있는 알고리즘
구현 쉬움, but 성능 안좋음
[4,2,3,1] -> [2,4,3,1] ->[2,3,4,1]->[2,3,1,4]->[2,3,1,4]->[2,1,3,4]->[2,1,3,4]->[1,2,3,4]
버블정렬의 성능
알고리즘의 빅오 표기법으로 할때, 숫자로 바꾸어보면 쉬움
버블 정렬은 (n-1)+(n-2) ... +2+1 = n(n-1)/2 =(n^2-n)/2b 결과적으로 O(n^2)
for문 두개가 중첩되어있으니 O(n^2)이라고 예측이 가능하기도함.
버블 정렬의 장단점
장점: 이해와 구현이 간단함
단점: 성능이 O(n^2)으로 좋지만은 않음.
선택정렬(Selection Sort)
버블정렬처럼 간단한 정렬에 속함
정렬되지 않은 영역의 첫번째 원소를 시작으로 마지막 원소까지 비교후 가장 작은값을 첫번째 원소로 가져옴
정렬이 되지 않은 영역에서 가장 작은수와 가장 큰수 위치 바꿔치기!
선택정렬의 성능
바깥 for문이 실행될수록 안쪽 for문이 줄어듦 -> 선택 정렬의 성능도 버블정렬과 동일한 O(n^2)
선택정렬의 장단점은 버블정렬의 장단점과 동일함.
그림으로 배우는 운영체제 Section 04
프로세스간 통신
프로세스: 독립적이기도 데이터를 주고받기도함
한 컴퓨터내의 다른 프로세스 or 네트워크로 연결된 다른 프로세스와 데이터를 주고받기도함
종류
한컴퓨터 내에서 데이터 주고받음
파일을 이용: 여러개의 프로세스가 하나의 파일을 읽고씀
파이프 이용: 운영체제가 생성한 파이프를 이용함
쓰레드를 이용함: 한프로세스내에서 쓰레드가 주고받음
네트워크를 이용함
소켓통신
RPC(원격 프로시져호출)
공유자원: 프로세스가 통신할때 공동으로 이용하는 파일이나 변수
각프로세스의 접근 순서에 따라 결과가 달라질 수 있음.
컨텍스트 스위칭으로 시분할 처리: 어떤 프로세스가 먼저 실행되는지 예측어려움
연산결과 예측 어려움 -> 동기화 문
컨텍스트 스위칭(Context Switching): 운영체제(OS)가 여러 개의 프로세스를 실행해야 할 때, 현재 실행 중인 작업을 멈추고 다른 작업으로 전환하는 과정
임계구역(Critical Section): 여러 프로세스가 동시에 사용하면 안되는 구역!
임계구역 문제 해결을 위한 조건
상호배제 메커니즘: 임계영역엔 동시에 하나의 프로세스만 접근, 여러 요청에 도 하나의 프로세스 접근만 허용, 임계구역에 들어간 프로세스는 빠르게 나와야함.
세마포어: 상호배제 메커니즘 중 한가지
경쟁조건(Race Condition): 공유자원을 차지하기 위한 프로세스의 경쟁?
동기화에서 가장 중요한 개념
프로세스가 공유자원에 접근하기 위해서 운영체제가 세마포어를 우선순위가 높은 프로세스에게 먼저주고, 프로세스가 일을 다하면 운영체제에게 세마포어를 주고, 다시 운영체제는 세마포어를 대기큐에있던 다른 프로세스에게 전달해주는 식임.
쉽게 생각해서 은행줄 같은느낌?
손님 = 프로세스, 은행원 = 공유자원, 번호표 기계 = 운영체제, 세마포어 = 번호표
세마포어를 이용하면, 공유자원에 여러 프로세스가 동시에 접근하지 않기 때문에 동기화문제가 일어나지 않음.
세마포어: 정수형 변수임
단점: 함수 순서가 중요함 (모니터를 통해 커버가능)
모니터: 세마포어의 단점을 해결하기 위한 상호배제메카니점
프로그래밍 언어 차원에서 지원하는 방법
synchronized: 자바에서 이것이 붙으면 동시에 여러 프로세스에서 실행할 수 없음!
상호배제가 완벽하게 이루어짐
이런 것을 제지해주는 것이 모니터의 역할임
실제 모니터아니고 지켜본다의 모니터인듯?
Section 05
데드락(교착상태)
여러 프로세스가 서로 다른 프로세스의 작업이 끝나기를 기다리다가 아무 작업이 이루어지지않는 상태
약간 고집센 상태?
교착상태 발생이유: 공유자원을 서로 차지하려다 발생함.
교착상태의 필요조건
상호배제: 먼저 차지하면 다른 프로세스가 사용할 수 없는 리소스임.
비선점: 프로세스가 이미 사용하고 있는 것을 다른 프로세스가 뺒을 수 없음.
점유와 대기: 프로세스가 다른 리소스를 기다리는 상태
원형대기: 점유와 대기를 하는 프로세스의 관계가 원형을 이룸
예로 프로세스 A는 프로세스 B의 리소스를, 프로세스 B는 프로세스 C의 리소스를, 프로세스 C는 프로세스 A 의 리소스를 원하는 상태.
교착상태 해결
교착상태 회피(Deadlock avoidance)
프로세스에 자원을 할당할 때 교착상태가 발생하지 않는 수준의 자원을 할당하는 것.
전체 자원과 할당된 자원을 기반으로 안정상태를 유지하려 하는것.
불안정 상태 =/= 교착상태. 그저 가능성이 높을 뿐.
은행원 알고리즘: 전체자원의 수를 알고 있지 않은 채로 자원을 잘못나눠주면 교착상태가됨
최대요구자원: 프로세스가 원하는 자원의 수
교착상태 검출 방법
가벼운 교착상태 검출: 타이머이용
일정시간동안 프로세스가 일을 안함 = 교착상태
해결법: 중간저장해서 교착상태되면 중간저장한데로 가는것
무거운 교착상태 검출: 자원할당 그래프 이용
운영체제가 어떠한 자원을 프로세스가 사용하는지 관찰
순환구조가 생기는 그래프 = 교착상태
교착상태 발생 -> 강제종료
강제 종료된 프로세스를 체크포인트에서 롤업
오버헤드가 발생하기도함.
Section 06
컴파일과 프로세스
프로그래밍언어
컴파일 언어: 개발자가 코드작성 -> 컴파일을 이용하여 기계어로 변환
컴파일 과정: 문법 오류 검증 및 기계어로 변환함.
C, C++, C#등이 이에 속함
인터프리터언어: 개발자가 작성한 코드를 한줄씩 해석해 기계어로 변환
미리 검사하지 않아 실행 시 오류가 발생할 수 있음.
컴파일 대비 느림
JS, Python, Ruby가 이에 속함
프로세스: code, data, stack, heap영역
code: 말그대로 코드가 들어감
data: 전역변수 or 배열
stack: 지역변수나 함수 매개변수, 함수의 리턴 주소저장.
heap: 동적 메모리 할당.
<컴파일 과정>
test.c: 개발자가 C언어로 코딩함.
전처리기: 개발자 코딩보고, 전처리부분(C언어에서 #부분)을 코드에 치환시킨 후 주석제거
test.i: 전처리 된것 저장
컴파일러: C언어 파일을 어셈블리어로 저장함.
test.s: 어셈블리어 파일
어셈블러: 어셈블리어를 오브젝트 파일로 변환
test.o: 0과 1로 된 기계어로 구성된 오브젝트 파일 (코드영역과 데이터 영역이 나누어있음)
링커: 오브젝트 파일을 실행파일로 변환.
모든 오브젝트 파일을 하나의 데이터영역과 코드영역으로 바꿈
실제 실행될 주소 매핑
test.exe: 운영체제가 프로세스를 만들어줌. 완벽한 상태의 코드영역과 데이터 영역으로 나누어짐.
이후...
운영체제 ->exe파일의 코드영역과 데이터영역을 프로세스의 코드영역과 데이터영역에 넣어줌-> 빈상태의 스택과 힙을 할당 ->PCB를 만들어 관리가 가능하게 만들어줌 -> 프로그램 카운터(다음 실행할 명령어의 주소를 생성한 프로세스의 코드를 첫번째 주소로 설정) -> CPU 스케줄링에 맞추어 프로세스 실행후 작업을 마침
Section 07
메모리의 종류 (1번이 가장 속도가 빠르고 용량이 작으며 비쌈)
레지스터: 가장빠른 기억장소, CPU내에 존재
휘발성 메모리
레지스터의 크기= 32bit, 64 bit
메인메모리의 값을 레지스터로 가져와 계산 후 메인 메모리로 옮김
캐시: 메인메모리에서 레지스터로 옮길때 미리 가져오는 데이터를 캐시에 옮겨둔다.
캐시는 여러개를 둠. 가장 빠른 캐시 = L1.
RAM(매인 메모리): 실제 운영체제와 여러 프로세스를 사용
실행중인 프로그램만 돌림
보조저장장치(HDD, SSD)
비휘발성 메모리
메인메모리
폰노이만 구조는 모든 프로그램을 메모리에서 실행시킴
멀티프로그래밍 환경에서 여러개가 한번에 진행하여야 하기 때문에 복잡하고 어려워짐
운영체제 : 1바이트 크기의 주소를 만들어 관리
32bit= 레지스터, ALU, 데이터 이동버스 , 사용가능 메모리도 2^34=4Gb
64bit = 레지스터, ALU, 데이터 이동버스, 사용가능 메모리는 2^64로 거의 무한대
즉, 32bit보다 64bit ram이 더빠름
메모리에는 운영체제 영역이 따로있음.
악의적이 프로그램이 운영체제를 침범하면 위험하기 때문에 경계레지스터( CPU내에 존재)를 통하여 보호함.
절대주소: 실제 프로그램이 올라가는 주소, 물리 주소공간이라고도함.
상대주소: 사용자가 바라보는 주소, 논리 주소라고 하기도함.
메모리 할당방식
메모리보다 더큰 프로그램은!!!
프로그램을 메모리만큼 자른뒤 필요한거 일부 실행, 나머지 일부는 하드디스크내 스왑영역에 두었다가 사용함. = memory overlay
멀티 프로그램 환경에서는,
가변분할 방식 사용
프로세스 크기에 따라 메모리는 나눔
한프로세스가 메모리의 연속된 공간에 할당: 연속 메모리 할당
단점: 외부단편화 발생
장점: 빈공간 없음.
고정 분할 방식
프로세스 크기 상관없이 메모리 나눔
비연속 메모리할당: 메모리가 잘라서 나누어 들어가기도 하기때문
장점: 구현이 간단하고 오버헤드가 적음
단점: 내부단편화 발생
외부단편화
세그멘테이션 = 가변분할방식
일부 프로세스가 종료되어 그만큼의 메모리(50+10MB)를 다른 프로세스(60MB필요)가 사용할때, 메모리가 연속으로 붙어있지 않으면 다른 프로세스에 할당이 어려운 것을 외부단편화라 함.
해결방법: 조각모음,
단점: 사용중 메모리 전부 중단, 메모리 이동해야함 -> 오버헤드 발생
내부단편화
페이징 = 고정분할 방식
일정하게 분할된 메모리(20MB)이지만, 프로세스가 더 많은 메모리(50MB)가 필요하면 불할된 메모리를 프로세스가 필요한 메모리보다 많은 메모리(60MB)를 제공함
버디시스템
2의 승스로 메모리 분할해 할당함
내부단편화가 발생하지만, 크기가작음
동일하게 나누었기 때문에 조립하기 쉬움 (조각모음보다 간단함)
2주차 후 소감...
확실히, 한글로 배우니까 너무 좋음.
자세히 그림으로 설명해주시는것도 너무 좋음...
이해 쏙쏙되어서 너무 좋다.
학기 시작할때 알고 시작했으면 더 좋았을걸 하는 아쉬움
남은 2주 화이팅 :)
댓글을 작성해보세요.
