기본편 - Section 03 알고리즘

재귀 (recursion)

• 사전적 정의: 어떠한 것을 정의할 때 자기 자신을 참조하는 것.

• 탈출조건(=기저조건)이 필수적으로 있어야함.

콜스택

• 함수가 호출되면서 올라가는 메모리 영역

• FILO의 조건을 가짐

• 스택자료구조를 잘 활용한 대표적 사례

재귀함수는, 호출할 때마다 콜스택영역을 차지함

• 탈출조건이 없으면 콜스택에 계속 쌓이기만함-> 메모리부족->자동stop

• for문 대신 사용하기보다는, 팩토리얼과 같이 더 쉽게 함수구현을 위한것임.

• 재귀함수내에서 자기자신을 호출할때, 이미 함수가 구현되어있다고 가정함.

재귀함수: 나 자신을 호출, 구현할때는 이미 구현된 것을 부르는 것처럼 구현하면 쉬움

재귀적으로 생각하기

1. pattern 01:

   단순 반복실행

   1. 반복문으로 구현했을때보다 성능이 떨어짐

2. pattern 02:

   하위 문제 결과를 기반으로 현재문제 계산

   1. 팩토리얼을 예를 들으면, return number*factorial(number -1);여기에서 하위문제(=factorial(number-1);)를 기반으로, 현재문제(number*factorial(number-1);)를 해결함

   2. for문이용은 상향식 계산, 재귀함수를 이용하는 것은 하향식 계산

      1. 모든 재귀가 하향식은 아님

상향식: 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)이라고 예측이 가능하기도함.

버블 정렬의 장단점

1. 장점: 이해와 구현이 간단함

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)

  • 프로세스에 자원을 할당할 때 교착상태가 발생하지 않는 수준의 자원을 할당하는 것.

  • 전체 자원과 할당된 자원을 기반으로 안정상태를 유지하려 하는것.

  • 불안정 상태 =/= 교착상태. 그저 가능성이 높을 뿐.

• 은행원 알고리즘: 전체자원의 수를 알고 있지 않은 채로 자원을 잘못나눠주면 교착상태가됨

  • 최대요구자원: 프로세스가 원하는 자원의 수

교착상태 검출 방법

1. 가벼운 교착상태 검출: 타이머이용

   1. 일정시간동안 프로세스가 일을 안함 = 교착상태

   2. 해결법: 중간저장해서 교착상태되면 중간저장한데로 가는것

2. 무거운 교착상태 검출: 자원할당 그래프 이용

   1. 운영체제가 어떠한 자원을 프로세스가 사용하는지 관찰

   2. 순환구조가 생기는 그래프 = 교착상태

   3. 교착상태 발생 -> 강제종료

   4. 강제 종료된 프로세스를 체크포인트에서 롤업

   5. 오버헤드가 발생하기도함.

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번이 가장 속도가 빠르고 용량이 작으며 비쌈)

1. 레지스터: 가장빠른 기억장소, CPU내에 존재

   1. 휘발성 메모리

   2. 레지스터의 크기= 32bit, 64 bit

   3. 메인메모리의 값을 레지스터로 가져와 계산 후 메인 메모리로 옮김

2. 캐시: 메인메모리에서 레지스터로 옮길때 미리 가져오는 데이터를 캐시에 옮겨둔다.

   1. 캐시는 여러개를 둠. 가장 빠른 캐시 = L1.

3. RAM(매인 메모리): 실제 운영체제와 여러 프로세스를 사용

   1. 실행중인 프로그램만 돌림

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

   1. 비휘발성 메모리

       

메인메모리

• 폰노이만 구조는 모든 프로그램을 메모리에서 실행시킴

• 멀티프로그래밍 환경에서 여러개가 한번에 진행하여야 하기 때문에 복잡하고 어려워짐

운영체제 : 1바이트 크기의 주소를 만들어 관리

32bit= 레지스터, ALU, 데이터 이동버스 , 사용가능 메모리도 2^34=4Gb

64bit = 레지스터, ALU, 데이터 이동버스, 사용가능 메모리는 2^64로 거의 무한대

즉, 32bit보다 64bit ram이 더빠름

메모리에는 운영체제 영역이 따로있음.

• 악의적이 프로그램이 운영체제를 침범하면 위험하기 때문에 경계레지스터( CPU내에 존재)를 통하여 보호함.

절대주소: 실제 프로그램이 올라가는 주소, 물리 주소공간이라고도함.

상대주소: 사용자가 바라보는 주소, 논리 주소라고 하기도함.

메모리 할당방식

메모리보다 더큰 프로그램은!!!

• 프로그램을 메모리만큼 자른뒤 필요한거 일부 실행, 나머지 일부는 하드디스크내 스왑영역에 두었다가 사용함. = memory overlay

멀티 프로그램 환경에서는,

1. 가변분할 방식 사용

   1. 프로세스 크기에 따라 메모리는 나눔

   2. 한프로세스가 메모리의 연속된 공간에 할당: 연속 메모리 할당

   3. 단점: 외부단편화 발생

   4. 장점: 빈공간 없음.

2. 고정 분할 방식

   1. 프로세스 크기 상관없이 메모리 나눔

       

   2. 비연속 메모리할당: 메모리가 잘라서 나누어 들어가기도 하기때문

   3. 장점: 구현이 간단하고 오버헤드가 적음

   4. 단점: 내부단편화 발생

외부단편화

• 세그멘테이션 = 가변분할방식

• 일부 프로세스가 종료되어 그만큼의 메모리(50+10MB)를 다른 프로세스(60MB필요)가 사용할때, 메모리가 연속으로 붙어있지 않으면 다른 프로세스에 할당이 어려운 것을 외부단편화라 함.

• 해결방법: 조각모음,

  • 단점: 사용중 메모리 전부 중단, 메모리 이동해야함 -> 오버헤드 발생

내부단편화

• 페이징 = 고정분할 방식

• 일정하게 분할된 메모리(20MB)이지만, 프로세스가 더 많은 메모리(50MB)가 필요하면 불할된 메모리를 프로세스가 필요한 메모리보다 많은 메모리(60MB)를 제공함

버디시스템

• 2의 승스로 메모리 분할해 할당함

• 내부단편화가 발생하지만, 크기가작음

• 동일하게 나누었기 때문에 조립하기 쉬움 (조각모음보다 간단함)

   

2주차 후 소감...

확실히, 한글로 배우니까 너무 좋음.

자세히 그림으로 설명해주시는것도 너무 좋음...

이해 쏙쏙되어서 너무 좋다.

학기 시작할때 알고 시작했으면 더 좋았을걸 하는 아쉬움

남은 2주 화이팅 :)