Algorithm

Recursion(재귀)

• 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 의미한다.

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

• 재귀함수는 콜스택이라는 메모리 가득차게 되는 경우 자동으로 종료된다.

• 기저 조건 : 재귀함수가 종료될 수 있는 탈출 조건

  • 기저 조건이 반드시 있어야 정상적으로 수행할 수 있다.

• 재귀함수는 함수를 호출할 때마다 Call Stack이라는 메모리 공간에 호출정보가 저장된다.
  → 재귀함수는 Loop문보다 더 많은 메모리 공간을 차지한다.

Call Stack(= Stack)

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

• 함수가 종료되면 콜스택에서 제거된다.

• FILO(First-In Last-Out)

재귀함수를 사용하는 이유

• Loop를 대신한다기 보다는 더 복잡한 문제를 쉽게 해결하기 위해 사용된다.
  ex) Factorial

재귀함수를 쉽게 작성하는 방법

• 재귀함수 내에서 자기 자신을 호출할 때 해당 함수가 벌써 구현이 되어있다고 가정한다.

재귀 사용하는 패턴

단순 반복문

• 반복문으로 구현했을 때보다 이점이 되는 부분이 없음

• Call Stack에 공간을 많이 차지해 성능이 반복문보다 좋지 않다.

하향식 계산

• 하향식 계산 : 하위문제의 결과를 기반으로 현재 문제를 계산하는 방식

  • 재귀가 반복문보다 성능이 좋은 경우

  • 큰 문제를 해결하기 위해 작은 재귀 함수를 호출한다.

  • 재귀를 사용해서만 구현이 가능하다.

• 상향식 계산 : 하위 문제를 모아서 현재 문제를 계산하는 방식

  • 반복문으로 구현한 것보다 성능이 좋지 않음

  • 반복문이나 재귀를 사용해서 구현할 수 있다.

  하노이의 탑

  • 하향식 계산 방식의 좋은 예시
    → 재귀함수의 좋은 예시

  제약 조건

  • 한 번에 하나의 원반을 움직일 수 있다.

  • 가장 위에 있는 원반만 옮길 수 있다.

  • 아래에 작은 원반이 올 수 없다.

     

  Bubble Sort

  • 인접한 두 원소를 비교하여 두 원소의 위치를 교환한다.

  과정

  • 배열을 처음부터 끝까지 순회하며 인접한 두 원소를 비교한다.

  • 왼쪽 원소가 오른쪽 원소보다 크면 두 원소를 교환한다.

  • 이 과정을 배열이 정렬될 때까지 반복한다.

  시간 복잡도

  • O(n^2)

  장점

  • 이해와 구현이 간단한다.

  단점

  • 성능이 좋지 않다.

  Selection Sort

  • 배열에서 최솟값을 찾아 맨 앞으로 이동시킨다.

  과정

  • 정렬되지 않은 부분에서 최솟값을 찾는다.

  • 찾은 최솟값을 정렬되지 않은 부분의 첫 번째 원소와 교환한다.

  • 정렬된 부분을 한 칸 늘리고, 정렬되지 않은 부분에서 위 과정을 반복한다.

  시간 복잡도

  • O(n^2)

  장점

  • 이해와 구현이 간단하다.

  단점

  • 성능이 좋지 않다.

• 참고 : https://visualgo.net/en/sorting

CPU Scheduling Algorithm

SJF(Shortest Job First)

• Burst Time이 짧은 작업부터 CPU를 할당한다.

문제점

• 어떤 프로세스가 얼마나 실행될지 예측하기 힘들다.
  → 예측하는 것이 거의 불가능하다.

• Burst Time이 긴 프로세스는 아주 오랫동안 실행되지 않을 수 있다.
  → Burst Time이 긴 프로세스는 Burst Time이 짧은 프로세스에게 계속해서 우선순위가 밀린다.
  ⇒ 사용되지 않는다.

RR(Round Robin)

• 하나의 프로세스에게 일정 시간만 CPU를 할당하고 할당된 시간이 지나면 강제로 다른 프로세스에게 일정시간만큼 CPU를 할당하는 방식
  → 강제로 CPU를 뺏긴 프로세스는 Queue의 가장 마지막으로 밀려난다.

• Time Slice(=Time Quantum) : 프로세스에게 할당하는 일정 시간

• Time Slice에 따라서 RR의 성능이 좌지우지된다.

  • Time Slice를 작게 만드는 경우 Context Switching이 빈번하게 발생된다.
    → Context Switching이 빈번하게 발생함에 따라 성능이 떨어진다.

  • Time Slice가 큰 경우 FIFO와 동일하게 동작한다.

• Time Slice 예시

  • Window Time Slice : 20ms

  • Unix Time Slice : 100ms

단점

• Context Switching이 존재한다.
  → 평균 대기시간이 FIFO와 동일하다면 FIFO가 더 성능이 좋다.

MLFQ(Multi Level Feedback Queue)

• RR의 업그레이드 버전

• 주로 사용되는 CPU 스케줄링 알고리즘

• CPU Bound Process : CPU를 할당받은 시간을 대부분 CPU 연산을 수행하는 프로세스

  • CPU 사용률과 처리량이 중요

• I/O Bound Process : 대부분의 시간을 I/O 작업에 수행하고 적은 시간만 CPU 연산을 하는 프로세스
  - 응답시간이 중요

• MLFQ는 기본적으로 CPU 사용률과 I/O 사용률이 좋게 나오는 작은 크기의 Time Slice를 사용한다.

• CPU Bound Process에게는 CPU 사용률을 높이기 위해 Time Slice를 높게 할당한다.

• I/O Bound Process에게는 I/O 사용률을 높이기 위해 Time Slice를 낮게 할당한다.

OS는 어떻게 CPU Bound Process와 I/O Bound Process를 구분할까?

• CPU를 사용하는 프로세스가 실행하다가 스스로 CPU를 반납하는 경우 CPU 사용률이 낮음
  → I/O Bound Process일 확률이 높음

• CPU를 사용하는 프로세스가 실행하다가 CPU 스케줄러에 의해 강제로 CPU를 뺏기는 상황인 경우 CPU 사용률이 높음
  → CPU Bound Process일 확률이 높음

구현 방법

• 우선순위를 갖는 큐를 여러개 준비한다.

• 우선순위가 높으면 Time Slice가 작다.

• 우선순위가 낮아질수록 Time Slice가 커진다.

Process간 통신

• 하나의 컴퓨터 내에서 프로세스간 통신하는 방법

Pipe

• 운영체제가 생성한 파이프를 이용해 데이터를 읽고 쓰는 방법

File

• 통신을 하려는 프로세스들이 하나의 파일을 이용해 읽고 쓰는 방법

Thread를 이용한 통신

• 하나의 프로세스 내에서 쓰레드간 통신하는 방법

• 쓰레드는 코드, 데이터, 힙 영역을 공유한다.
  (스택 영역만 별도로 갖는다.)

• 데이터 영역의 전역 변수나 힙 영역을 이용하여 통신할 수 있다.

Network

• OS가 제공하는 Socket 통신

• RPC(Remote Procedure Call)

  • 다른 컴퓨터의 함수를 호출하는 방법

공유자원과 임계구역

• 공유자원 : 프로세스간 통신을 할 때 공용으로 이용하는 변수나 파일

  • 여러 프로세스가 공유하기 때문에 각 프로세스의 접근 순서에 따라서 결과가 달라질 수 있다.

  • 컨텍스트 스위칭으로 시분할 처리를 하기 때문에 프로세스간의 실행 순서를 예측하기 어렵다.
    ⇒ 동기화 문제가 발생할 수 있다.

• 임계규역 : 여러 프로세스가 동시에 사용하면 안되는 영역

  • 상호배제 메커니즘을 통해 해결할 수 있다.

• 경쟁조건 : 공유자원을 사용하기 위해 서로 경쟁하는 것

상호배제 요구사항

1. 임계영역엔 동시에 하나의 프로세스만 접근한다.

2. 여러 요청에도 하나의 프로세스의 접근만 허용한다.

3. 임계구역에 들어간 프로세스는 빠르게 나와야한다.

Semaphore

• 상호배제 메커니즘의 한 종류

• Semaphore :  정수 값을 가지는 변수로, 공유 자원에 접근할 수 있는 프로세스/스레드의 수를 나타낸다.

• 세마포어를 갖고 있는 프로세스가 실행되고 세마포어를 반납한다.

기본 연산

• wait(S): 세마포어 값을 감소시킨다.

  • 값이 0이면 프로세스/스레드를 대기 상태로 만든다.

• signal(S): 세마포어 값을 증가시킵니다.

  • 대기 중인 프로세스/스레드가 있다면 깨운다.

종류

• 이진 세마포어: 0과 1 두 가지 값만 갖는다.
  (뮤텍스와 유사하게 사용한다.)

• 카운팅 세마포어: 0 이상의 정수 값을 갖는다.
  (여러 자원을 관리할 때 사용된다.)

장단점

• 장점: 여러 프로세스/스레드 간의 복잡한 동기화 문제를 해결할 수 있다.

• 단점

  • 잘못 사용하면 교착 상태나 기아 상태를 유발할 수 있다.
    ex) 세마포어를 획득하는 함수와 세마포어를 반납하는 함수의 위치 잘못 사용

Mutex(MUTual EXclusion)

• 뮤텍스는 이진 세마포어의 특수한 경우

• 여러 스레드가 공유 자원에 동시에 접근하는 것을 방지하는 기술

기본 연산

• Lock: 스레드가 임계 영역에 진입할 권한을 획득

• Unlock: 임계 영역 사용을 마치고 다른 스레드가 진입할 수 있게 한다.

뮤텍스와의 차이

• 세마포어는 여러 프로세스/스레드의 접근을 허용할 수 있지만, 뮤텍스는 하나의 프로세스/스레드만 접근을 허용한다.

Monitor

• 세마포어의 단점을 보완한 상호배제 메커니즘

• OS가 처리하는 것이 아니라 프로그래밍 언어단에서 지원하는 기능
  ex) Java : synchronized 키워드

• 한 번에 하나의 프로세스/스레드만 실행할 수 있다.

교착상태

• 여러 프로세스가 서로 다른 프로세스의 작업이 끝나길 기다리다가 아무 작업도 수행되지 않는 상태

발생 원인

• 상호 배제 : 공유 자원은 한 번에 하나의 프로세스만 사용할 수 있다.

• 비선점 : 다른 프로세스가 사용 중인 자원을 강제로 빼앗을 수 없다.

• 점유와 대기 : 프로세스가 이미 자원을 보유한 상태에서 다른 자원을 요청하며 대기한다.

• 원형 대기 : 점유와 대기를 하는 프로세스들의 관계가 원형이다.

• 하나라도 충족하지 않으면 교착상태가 발생하지 않는다.
  → 교착 상태를 예방하는 것을 구현하기는 매우 어려워서 교착 상태를 해결하는 방향으로 발전됐다.

해결방법

교착상태 회피

• 프로세스들에게 자원을 할당할 대 어느 정도 자원을 할당해야 교착상태가 발생하는지 파악해서 교착상태가 발생하지 않는 수준의 자원을 할당한다.

• 전체 자원의 수와 할당된 자원의 수를 기준으로 안정상태와 불안정 상태로 나뉜다.

• OS는 안정상태를 유지하려 한다.

  • 안전 상태: 모든 프로세스가 요구한 최대 자원을 할당받아 실행을 완료할 수 있는 상태

• 불안정상태에 있더라도 무조건 교착상태에 들어가는 것이 아니라 교착상태에 빠질 확률이 높아지는 것이다.

은행원 알고리즘

작동 원리

• 프로세스가 자원을 요청할 때, 그 요청이 시스템을 안전 상태로 유지할 수 있는지 확인한다.

• 안전 상태를 유지할 수 있는 요청만 수락하고, 불안정한 상태를 초래할 수 있는 요청은 거절한다.

주요 개념

• 최대 요구량(Max Need): 프로세스가 실행을 완료하기 위해 필요한 최대 자원 양

• 할당량(Allocation): 현재 프로세스에 할당된 자원 양

• 필요량(Need): 최대 요구량에서 현재 할당량을 뺀 값

• 가용량(= 시스템 총 자원, Available): 시스템에서 현재 사용 가능한 자원 양

단점

• 비용이 비싸고 비효율적이다.

교착상태 검출

가벼운 교착 상태 검출

• 타이머를 이용하는 방식

• 프로세스가 일정시간 동안 작업을 진행하지 않는다면 교착상태가 발생했다고 간주하고 교착상태를 해결한다.

교착상태 해결 방법

• 일정 시점마다 체크포인트를 만들어 작업을 저장하고 타임아웃으로 교착상태가 발생했다면 마지막으로 저장했던 체크포인트로 롤백한다.

무거운 교착 상태 검출

• 자원 할당 그래프를 이용하는 방식

  • OS가 자원 할당 그래프를 유지하고 검사해야 하기 때문에 오버헤드가 발생한다.
    But. 가벼운 교착 상태 검출에서 발생할 수 있는 억울하게 종료되는 프로세스가 발생하지 않는다.

• OS에서 프로세스가 어떤 작업을 사용하는지 지켜보고 교착상태가 발생했다면 해결한다.

Programming Language

• Compile Language

  • 개발자가 코드를 작성하고 컴파일을 수행하여 0과 1로된 기계어로 실행파일을 만든다.
    → 기계어로 되어 있어 실행 속도가 인터프리터 언어에 비해 빠르다.

  • 컴파일 과정에서 개발자의 문법오류를 체크한다.
    ex) C, C++, C#

• Interpreter Language

  • 개발자가 작성한 코드를 미리 기계어로 만들어 놓지 않고 실행시 코드를 한줄씩 해석해 실행하는 언어
    → 미리 검사를 하지 않기 때문에 실행할 때 오류가 발생할 수 있고, 컴파일 언어보다 느리다.
    ex) Javascript, Python, Ruby

프로세스의 영역

• 코드 영역

  • 실행해야 할 코드가 들어간다.

• 데이터 영역

  • 전역 변수나 배열이 들어가는 영역

• 스택 / 힙

  • 프로세스가 실행될 때 할당되는 메모리

  • 스택 : 지역변수와 함수 관련 값들이 저장

  • 힙 : 실행 중에 메모리 공간을 할당할 수 있는 유동적인 공간

Compile 언어가 Process가 되는 방법

1. 개발자가 코드 작성

2. 전처리 단계 실행

   • 개발자가 작성한 코드를 확인하고 전처리 구문을 처리한다.

   • C에서는 #이라는 키워드로 선언된다.
     ex) #include<stdio.h>, #define MY_NUMBER 100

   • 코드에 있는 모든 주석은 삭제된다.

   • 결과물로 .i 파일이 생성된다.

3. 전처리기에서 나온 결과파일을 컴파일러가 처리한다.

   • 컴파일러는 .i 파일을 기계어에 가까운 어셈블리어로 변환시킨다.

   • 결과물로 .s 파일이 생성된다.

4. 어셈블러 작업이 수행된다.

   • 오브젝트 파일.o로 변환된다.

   • 오브젝트 파일은 0과 1로 구성되어 있다.

   • 코드영역과 데이터 영역이 나뉘어져 있다.

5. 링커 작업이 수행된다.

   • 모든 오브젝트 파일을 하나의 코드 영역과 데이터 영역으로 묶어준다.

   • 실제로 실행될 주소를 매핑시켜준다.

   • 결과물로 .exe 파일이 생성된다.

6. 사용자가 .exe파일을 실행시키면 OS가 프로세스를 생성한다.

   • OS는 파일에 있는 코드 영역과 데이터 영역을 가져와 프로세스의 코드 영역과 데이터 영역에 넣어주고, 빈 상태의 스택과 힙을 할당한다.

   • PCB를 만들어 프로세스를 관리가 가능하게 한다.

   • PC(프로그램 카운터)에 다음 실행할 명령어의 주소를 생성한 프로세스의 코드영역의 첫번째 주소로 설정한다.
     → OS의 CPU 스케줄링에 따라서 프로세스가 실행되다가 작업을 마친다.

메모리 종류

레지스터

• 가장 빠른 기억장소, CPU 내에 존재한다.

• 휘발성 메모리

• CPU를 나타내는 값에서 32bit, 64bit를 의미하는 것이 레지스터의 크기이다.

• CPU는 계산을 수행할 때 메인 메모리에 있는 값을 레지스터로 가져와서 계산한다.

  • 계산 결과는 메인 메모리에 저장한다.

캐시

• 휘발성 메모리

• 속도가 매우 빠른 레지스터와 레지스터에 비해 상대적으로 느린 메인 메모리 사이의 속도 간극을 메우기 위해 필요한 데이터를 미리 가져와 저장하는 저장소

• 성능의 이유로 여러 개가 존재한다.

  • L1, L2, L3
    → 숫자가 커질 수록 느린 캐시

• CPU가 값을 요청해 레지스터로 값을 옮겨야 한다면 빠른 캐시를 순차적으로 확인하고, 캐시에 데이터가 없으면 메인 메모리를 조회한다.
  ex) L1 → L2 → L3 → 메인 메모리

보조 저장장치(HDD, SSD)

• 비휘발성 메모리

메인 메모리

• 실제 운영체제와 다른 프로세스들이 올라가는 공간

• 휘발성 메모리

• 데이터를 저장하기 보다는 실행중인 프로그램만 저장한다.

• OS는 메모리를 관리하기 위해서 1Byte 크기로 구역을 나누고 숫자(주소)를 매긴다.

32bit CPU, 64bit CPU

• 32bit CPU

  • 레지스터, ALU, Data Bus : 32bit

  • 메모리 : 2^32 = 4GB

• 64bit CPU

  • 레지스터, ALU, Data Bus : 64bit

  • 메모리 : 2^64 = 16384PiB

• 64bit CPU가 32bit CPU 보다 한번에 처리할 수 있는 양이 많기 때문에 속도가 더 빠르다.

물리 주소 & 논리 주소

• 물리 주소 공간 : 0x0부터 시작하는 주소 공간

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

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

• OS를 위한 공간은 따로 확보한다.

경계 레지스터

• H/W적으로 OS 공간과 사용자 공간을 나누는 레지스터

• CPU 내에 존재하는 레지스터

• 메모리 관리자가 사용자 프로세스가 경계 레지스터의 값을 벗어났다면 검사하고, 벗어났다면 해당 프로세스를 종료시킨다.

절대 주소 & 상대 주소

• 개발자가 프로그램이 실행될 주소를 신경쓰지 않고 개발할 수 있는 이유
  → 컴파일러가 컴파일을 할 때 메모리 0번지에서 실행한다고 가정하기 때문

• 절대 주소 : 메모리 관리자가 바라본 프로세스가 올라간 물리 주소

• 상대 주소 : 사용자가 바라보는 논리 주소

재배치 레지스터

• 프로그램의 시작 주소가 저장되어 있다.

• 사용자가 요청한 논리 주소의 데이터를 물리 주소로 치환해준다.

• 사용자가 메모리에 접근할 때마다 논리 주소를 물리 주소로 치환해준다.

메모리 할당 방식

메모리 오버레이

• 메모리보다 용량이 큰 프로그램을 실행시키는 방법

• 큰 프로그램을 메모리에 올릴 수 있을 정도로 분할하여 일부만 실행하고, 실행되지 않은 프로그램은 HDD의 스왑 영역에 저장하는 방식

Swap

• 스왑영역에 있는 데이터 일부를 메모리로 가져오고 메모리에 있는 데이터를 스왑영역으로 옮기는 것

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

• 프로세스의 크기에 따라 메모리를 나누는 방식

• 하나의 프로세스가 메모리에 연속된 공간에 할당된다.
  → 연속 메모리 할당이라고 한다.

장점

• 메모리에 연속된 공간에 할당된다.
  → 내부 단편화가 없다.

단점

• 외부 단편화가 발생한다.

고정 분할 방식(= Paging, 페이징)

• 프로세스의 크기와는 상관없이 정해진 크기로 나누는 방식

• 하나의 프로세스가 메모리에 분산되어 할단된다.
  → 비연속 메모리 할당이라고 한다.

장점

• 구현이 간단하고 오버헤드가 적다.

단점

• 작은 프로세스도 큰 영역에 할당되어 내부 단편화가 발생한다.

내부 단편화

• 프로세스에 필요한 메모리보다 더 큰 고정 크기의 메모리 블록이 할당될 때 발생한다.

• 할당된 메모리와 실제 사용된 메모리 사이의 차이로 인해 메모리 공간이 낭비된다.

• 고정 크기 분할 방식에서 주로 발생한다.

• 해결 방법은 딱히 없고, 분할되는 크기를 조절하여 내부 단편화를 최소화한다.

외부 단편화

• 메모리 할당과 해제를 반복하면서 작은 빈 공간들이 메모리 곳곳에 흩어져 생기는 현상

• 전체 가용 메모리는 충분하지만, 연속된 큰 블록을 할당할 수 없는 상황을 만든다.

• 가변 분할 방식에서 주로 발생한다.

조각모음

• 외부 단편화가 발생한 공간을 합쳐주는 작업

• 현재 메모리에서 실행되고 있는 프로세스들의 작업을 일시 주징하고, 메모리 공간을 이동시켜야 한다.
  → 오버헤드가 발생한다.

버디 시스템

• 가변 분할 방식 + 고정 분할 방식

• 오늘날의 OS가 채택한 메모리 할당 방식

• 2의 제곱으로 메모리를 분할하여 할당하는 방식
  → 근접한 메모리 공간을 합치기 쉽다.
  → 조각 모음보다 훨씬 간단하다.

장점

• 가변 분할 방식처럼 프로세스 크기에 따라 할당되는 메모리 크기가 달라지고, 외부 단편화를 방지하기 위해 메모리 공간을 확보하는 것이 간단하다.

• 내부 단편화가 발생할 수 있지만 고정 분할 방식에 비해 많은 공간이 낭비되지는 않는다.

Retrospect

잘한 점

• 매일매일 빠지지 않고 강의를 들은 점

• 매일 들은 강의 내용을 요약/정리하고 그 주차의 내용들을 하나의 게시글로 정리한 것