강의 내용 요약

운영체제

프로세스간 통신

1. 프로세스는 독립적으로 실행되는 경우도 있지만 다른 프로세스와 데이터를 주고 받으며 통신을 하는 경우도 있음

2. 프로세스는 한 컴퓨터 내에서 실행 중인 다른 프로세스와 통신하거나 네트워크로 연결된 다른 컴퓨터에 있는 프로세스와 통신할 수도 있음.

    

프로세스 간 통신의 종류

1. 한 컴퓨터 내에서 프로세스 간 통신

    

   • 파일 : 파일을 이용해 데이터를 주고 받으며 통신

   • 파이프 : 운영체제가 제공한 파이프를 통해 데이터를 주고 받으며 통신

      

     2. 하나의 프로세스 내에서 쓰레드를 이용한 통신

     • 쓰레드는 코드, 데이터, 힙영역을 공유하고 스택만 각자의 것을 가지고 있음

     • 데이터 영역의 전역 변수 or 힙을 이용하면 쓰레드 간 통신이 가능

     3. 원격의 컴퓨터의 프로세스 간 통신(네트워크 이용)

     • 운영체제가 제공하는 소켓통신

     4. 다른 컴퓨터에 있는 함수를 호출하는 RPC(Remote Procedure call : 원격 프로시저 호출)

공유자원과 임계구역

1. 공유자원과 동기화 문제

• 프로세스/쓰레드 간 통신을 할 때 여러 프로세스/쓰레드가 공동으로 이용하는 자원(메모리, 변수, 파일, 데이터 등…)을 공유자원이라함

• 공유자원은 여러 프로세스/쓰레드가 공유하고 있기 때문에 프로세스/쓰레드가 공유자원에 접근하는 순서에 따라 실행 결과가 달라질 수 있음

• 시분할처리, 멀티스레드 환경 등의 이유로 인해 프로세스/쓰레드의 실행 순서를 파악하기 어려움

  • 참고 사항

    • 운영체제는 프로세스의 실행 순서를 관리 및 결정하지만, 실행 결과에는 관여하지 않는다. → 실행만 하고 결과는 알 바가 아니다

  • 따라서 공유 자원에 대한 접근 순서가 올바르게 조정되지 않으면 예상치 못한 결과가 발생함

• 이 문제를 동기화 문제 라 부름

• 동기화 문제는 공유 자원에 대한 접근 순서가 잘못된 경우, 공유 자원에 동시 접근 등 공유 자원 사용과 관련된 모든 문제를 아우르는 개념

2. 동기화 문제의 예시

// 물약을 먹는 코드
int currentHealth = getHealth();
health = currentHealth + 50; // 체력 50 회복

// 공격받는 코드
int currentHealth = getHealth();
health = currentHealth - 10; // 체력 10 감소

• 공격받는 코드가 먼저 실행된다고 가정

• 공격받는 코드의 int currentHealth = getHealth(); 가 실행되어 currentHealth에 20이 저장

• 컨텍스트 스위칭이 발생 → 물약먹는 코드가 실행

• int currentHealth = getHealth();가 실행되어 currentHealth에 20이 저장되고 health = currentHealth + 50; 가 실행되어 health를 70으로 변경

• 다시 컨텍스트 스위칭이 발생 → 공격받는 코드가 실행

• health = currentHealth - 10; 가 실행되어 health를 10으로 변경

• 물약먹는 코드가 먼저 실행된다고 가정

• 물약먹는 코드의 int currentHealth = getHealth();가 실행되어 currentHealth에 20이 저장

• 컨텍스트 스위칭이 발생 → 공격받는 코드가 실행

• int currentHealth = getHealth();가 실행되어 currentHealth에 20이 저장되고 health = currentHealth - 10;가 실행되어 health를 10으로 변경

• 다시 컨텍스트 스위칭이 발생 → 물약먹는 코드가 실행

• health = currentHealth +50가 실행되어 health를 70으로 변경

• 예상 결과값으로는 health가 60이지만 health라는 공유자원에 여러 프로세스가 잘못된 순서로 접근하여 엉뚱한 값이 되어버림

3. 임계구역(Critical Section)과 경쟁 조건(Race Conditon)

• 여러 프로세스/쓰레드가 동시에 사용하면 안되는 영역을 임계 구역이라 함

• 공유자원을 수정하는 코드 부분이며 한 번에 하나의 프로세스/쓰레드만 접근해야 하는 영역

• 여러 프로세스/스레드가 동일한 공유 자원을 동시에 접근해 문제가 발생할 수 있는 상황을 경쟁 조건(Race Condition)이라고 부름

• 경쟁 조건은 동기화 문제의 한 가지 경우에 해당

4. 상호 배제(Mutual Exclusion) 매커니즘

• 임계 구역 문제를 해결하기 위한 원칙

• 상호 배제의 요구사항

  • 임계구역에는 동시에 하나의 프로세스만 접근해야 한다

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

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

세마포어(Semaphore)

1. 세마포어의 개념

• 직원 A와 직원 B가 프린터 이용을 하고 싶음

• 프린터 이용 시 작업물이 섞이는 것을 방지하기 위해 프린터실을 따로 만들고 프린트 작업을 원할 때마다 프린터실 열쇠 관리자에게 단 하나의 열쇠를 받아서 프린터실을 이용해야 함

• 한 직원이 프린터실에 들어가있는 동안에는 다른 직원은 절대 프린터실에 출입할 수 없으며 들어간 직원이 나올 때까지 대기해야 함

• 직원 A가 프린터 작업을 마치고 프린터실에서 나와서 열쇠를 열쇠 관리자에게 반납함

• 프린터를 사용하려는 직원 : 프로세스

• 프린터: 여러 프로세스/쓰레드가 같이 쓰고 있는 공유자원

• 프린터를 쓰기 위해 대기하는 공간: 대기큐

• 프린터실 열쇠 관리자: 운영체제

• 열쇠: 세마포어

2. 세마포어를 코드에 적용하기

// 세마포어 선언
int semaphore = 1;

// 물약을 먹는 코드
wait(semaphore); //열쇠를 요청해서 열쇠를 받고 문을 잠금

int currentHealth = getHealth();
health = currentHealth + 50; // 체력 50 증가

signal(semaphore); // 방에서 나와 열쇠 관리자에게 열쇠 반납

// 공격받는 코드
wait(sempahore); //열쇠를 요청해서 열쇠를 받고 문을 잠금

int currentHealth = getHealth();
health = currentHealth - 10; // 체력 10 감소

signal(semaphore); // 방에서 나와 열쇠 관리자에게 열쇠 반납

• 물약을 먹는 코드가 먼저 실행

• 세마포어 변수 semaphore를 가지고 wait() 함수 호출 → **wait()함수**는 세마포어(열쇠)를 획득할 때까지 기다렸다가 획득하면 방에 들어가 문을 잠구는 함수

• 현재 세마포어(열쇠)가 있으니 받아서 문을 잠굼

• 공격받는 코드로 컨텍스트 스위칭이 발생

• 공격받는 코드에서 wait()함수를 호출했지만 세마포어(열쇠)가 없으므로 세마포어(열쇠)를 받을 때까지 대기 → 다음 코드가 실행되지 않고 멈춰있음

• 시간이 지나 다시 물약을 먹는 코드로 컨텍스트 스위칭이 발생

• signal() 함수가 호출될 때까지 물약을 먹는 코드가 실행

• 물약을 먹는 코드가 signal() 함수를 호출하여 세마포어(열쇠)를 반납하였고 그제서야 공격받는 코드의 wait()함수가 종료됨

• 시간이 지나 다시 공격받는 코드로 컨텍스트 스위칭이 발생하면 health 값을 변경하고 signal() 함수로 세마포어(열쇠)를 반납함

• 초기 health값을 20이라고 하면 health는 20 → 70 → 60으로 변화

• 위 설명을 통해 세마포어를 이용하면 여러 프로세스/쓰레드가 공유자원에 동시에 접근하지 못하기 때문에 동기화 문제가 발생하지 않음

• 세마포어는 여러 개의 값을 가질 수 있음

  • 공유자원의 개수에 따라 세마포어의 값을 다르게 조정 가능

  • ex) 공유자원이 3개 → 세마포어의 값은 3

3. 세마포어의 단점

wait(s);
// 임계 구역
wait(s);

wait(s);
// 임계 구역
signal(s);

signal(s);
// 임계 구역
wait(s);

• 위 그림과 같이 wait()과 signal()의 순서를 이상하게 호출하여 세마포어를 잘못 사용할 가능성이 있음.

  • 반납을 안해서 다른 프로세스가 임계 구역에 접근이 불가능하다 등..

• 위 문제는 모니터라는 기법을 통해 해결 가능

4. 모니터

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

• 운영체제가 아닌 프로그래밍 언어 차원에서 지원하는 방법

  • ex) 자바의 synchronized

public class Health{
	private int health = 100;
	
	synchronized void increase(int amount){
		health += amount
	}
	
	synchronized void decrease(int amount){
		health -= amount
	}
}

// synchornized 키워드가 붙은 함수들은 동시에 여러 프로세스/쓰레드에서 실행 불가능
// ex)(동일한 객체에 속한) increase 함수가 프로세스/쓰레드 A에서 실행 중이면
// 프로세스/쓰레드 B에서는 increase, decrease 모두 실행 불가능

데드락(Deadlock)

1. 교착상태(데드락)이란?

• 여러 프로세스/쓰레드가 서로 다른 프로세스/쓰레드의 작업이 끝나기를 기다리다가 아무도 작업을 진행하지 못하는 상태

• 일상생활 속 교착 상태 → 교차로에서의 교통 마비 상태

• 교착 상태의 발생 이유는 공유자원 때문임

  • 어떤 자원을 여러 프로세스/쓰레드가 공유하지 않는다면 교착상태는 발생하지 않음

2. 식사하는 철학자

• 원형으로 된 탁자에 음식이 준비되어 있고 철학자들은 각자 의자에 앉아서 음식을 먹는 상황

• 각 철학자는 포크를 1개씩 가지고 있으며 음식을 먹기 위해서는 포크를 2개 사용해야 함

• 철학자 3명이 동시에 자신의 오른쪽에 있는 포크를 집음

• 모든 철학자가 포크가 1개 더 필요한 상황이지만 아무도 양보를 하지 않음

• 아무도 식사가 불가능한 교착상태에 빠짐

3. 교착상태의 필요조건

• 아래의 4가지 필요조건 중 하나라도 충족되지 않는다면 교착상태는 발생하지 않는다.

• 상호 배제

  • 어떤 프로세스/쓰레드가 한 리소스를 점유했다면 그 리소스를 사용하는 동안 다른 프로세스에게 공유되면 안됨

     

  • 식사하는 철학자에서 포크가 리소스에 해당

  • 먼저 포크를 집었다면 그 포크는 다른 사람이 사용할 수 없는 리소스

   

• 비선점

  • 프로세스/쓰레드 A가 리소스를 점유하고 있는데 프로세스/쓰레드 B가 그 리소스를 빼앗을 수 없어야 함

  • 식사하는 철학자에서 철학자 A가 들고 있는 포크를 철학자 B가 뺏을 수 없는 상황

   

• 점유와 대기

  • 어떤 프로세스/쓰레드가 리소스를 가지고 있는 상태에서 추가적인 리소스를 원하지만 추가 리소스를 사용할 수 없어 대기하는 상태

  • 식사하는 철학자에서 오른쪽 포크를 손에 쥔 채로 왼쪽 포크를 기다리는 상태

   

• 원형 대기

  • 점유와 대기를 하는 프로세스/쓰레들의 관계가 원형(순환 구조)을 이루며, 각 프로세스가 다음 프로세스가 보유한 리소스를 기다리는 상황.

     

  • 식사하는 철학자에서 서로가 서로의 포크를 원하는 상황이 원형(순환구조)을 이룸

   

4. 교착상태의 예방(Prevention)

• 아예 교착상태 자체가 일어나지 않도록 방지하는 방법

• 운영체제 연구자들은 앞의 4가지 필요조건을 통해 교착상태를 예방하려고 했으나 제약이 많고 비효율적이기 때문에 예방이 아닌 교착상태를 해결하는 방법을 연구하기 시작함

5. 교착상태 회피(Avoidance)

• 운영체제가 프로세스들에게 자원을 할당할 때 어느 정도의 자원을 할당해야 교착상태가 발생하는지 파악하여 교착상태가 발생하지 않는 수준의 자원을 할당하는 방식

• 교착상태가 발생할 수 있지만 최대한 발생하지 않도록 미리 대비하는 방법

• 교착상태 회피는 전체 자원의 수와 할당된 자원의 수를 기준으로 안정상태와 불안정 상태로 나눔

• 운영체제는 최대한 안정 상태를 유지하는 방향으로 자원을 할당함

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

• 은행원 알고리즘(Banker’s Algorithm)

  • 은행(운영체제)이 사업가들(프로세스/쓰레드)에게 돈(리소스)을 빌려줄 때 은행의 여윳돈(시스템의 총 자원)과 사업가들에게 빌려준 돈들(현재 할당된 자원)을 보고 대출 가능한 상황(안전상태)인지 확인하고 빌려주는 원리의 알고리즘

     

  • 안정 상태

    • 안정상태의 경우 P2 혹은 P3이 추가 자원을 요청할 경우 사용 가능한 자원 2개를 사용하여 할당해줄 수 있음.

    • 추가 자원이 할당된 P2 혹은 P3의 작업이 끝나면 자원을 반납받아 P1의 추가 자원 요청에도 대응할 수 있음

       

  • 불안정 상태

    • 현재 운영체제가 사용 가능한 자원이 1개임

    • 이 자원으로는 P1, P2, P3가 요청할 수 있는 최대 요청인 2개를 충족하지 못함

    • 불안정 상태에 있더라도 프로세스가 추가로 최대 자원을 요청하지 않는다면 교착상태에 빠지지 않을 수도 있지만 안정 상태에 비해 확률이 높음

• 은행원 알고리즘은 교착상태를 회피하는 좋은 방법이지만 비용이 비싸고 비효율적

5. 교착상태 검출

• 가벼운 교착 상태 검출

  • 타이머를 이용하는 방식 → 프로세스가 일정시간 동안 작업을 진행하지 않는다면 교착상태가 발생했다고 간주하고 교착상태를 해결(프로세스 종료)

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

• 무거운 교착 상태 검출

  • 자원할당 그래프를 이용하는 방식 → 현재 운영체제에서 프로세스가 어떤 자원을 사용하는지 지켜보고 교착상태가 발생했다면 해결(프로세스 종료)

     

  • 프로세스는 각자 자원을 차지하고 있고 화살표를 통해 추가로 다른 자원을 요청하고 있음

  • 왼쪽 그래프 : 순환 구조가 생기지 않음 → 교착상태가 없는 그래프

  • 오른쪽 그래프: 순환 구조가 발생 → 교착상태가 있는 그래프

  • 그래프를 통해 교착 상태를 검출했다면 교착상태를 일으킨 프로세스를 강제종료시키고 다시 실행될 때 체크포인트로 롤백시킴

  • 이 방식은 운영체제가 지속적으로 자원 할당 그래프를 유지하고 검사해야 하므로 큰 오버헤드가 발생

  • 하지만 가벼운 교착 상태보다 정확한 교착상태 검출 가능(타이머에 의한 강제 종료가 아니라 그래프를 근거로 판단하기 때문)

컴파일과 프로세스

1. 프로그래밍 언어의 종류

• 컴파일 언어

  • 작성한 코드를 컴파일이라는 과정을 거쳐 0과 1로 이루어진 기계어로 실행파일을 만드는 언어

  • 컴파일 과정에서 문법 오류를 검사하고 CPU에서 바로 처리 가능한 기계어로 실행파일을 만들어두기 때문에 속도가 빠름

  • 번역가가 원고를 읽고 통째로 번역한 다음 전달해주는 느낌

  • C, C++, C# 등의 언어가 이에 해당

• 인터프리터 언어

  • 작성한 코드를 미리 기계어로 만들지 않고 실행 시 코드를 1줄씩 해석해 실행하는 언어

  • 컴파일 과정이 없기 때문에 오류가 발생할 수 있고 컴파일 언어에 비해 속도도 느림

  • 동시통역사가 중간에서 즉석으로 통역해주는 느낌

  • Javascript, Python, Ruby등의 언어가 이에 해당

   

2. 컴파일 과정

• 가장 먼저 전처리기에서 전처리 과정이 진행됨

• 전처리 구문이 처리됨

• 전처리 구문: #으로 시작하는 구문

  • #include, #define …

• 코드에 있는 모든 주석은 제거됨

• printf()함수의 원형을 가져옴

• 매크로 값인 MY_NUMBER가 100으로 치환 됨

   

• 컴파일러는 C언어 작성된 파일(.i)을 기계어에 가까운 어셈블리어로 변환시킴

   

• 어셈블리어로 변환된 파일은 어셈블러를 통해 오브젝트파일(.o)파일로 변환됨

• 오브젝트 파일은 0과 1로 된 기계어로 구성되어 있기 때문에 일반적인 텍스트 에디터로는 내용을 확인할 수 없음

• 오브젝트 파일은 코드 영역과 데이터 영역이 분리되어 있음

   

• 링커는 여러 개의 오브젝트 파일을 하나의 코드영역과 데이터영역으로 묶음

• 실제로 실행될 주소를 매핑시켜줌

• 링커까지 거치면 실행파일(.exe)파일이 생성됨

   

• 사용자가 프로그램을 실행시키면 운영체제가 프로세스를 생성

• 운영체제는 exe파일에 있는 코드영역과 데이터영역을 가져와 프로세스의 코드영역과 데이터영역에 넣어주고 빈 상태의 스택과 힙을 할당

• PCB를 만들어 프로세스 관리가 가능하도록 만듦

• PCB의 프로그램 카운터를 생성한 프로세스의 코드영역의 첫번째 주소로 설정

• 운영체제의 CPU 스케줄링에 따라 프로세스가 실행되다가 작업을 마치고 종료됨

메모리

1. 메모리 종류

• 레지스터

  • 가장 빠른 기억장소로 CPU내에 존재

  • 전원이 공급되지 않으면 데이터가 사라지는 휘발성 메모리

  • 32bit 크기의 레지스터를 가짐 → 32bit CPU

  • 64bit 크기의 레지스터를 가짐 → 64bit CPU

  • cpu는 계산을 할 때 메인메모리에 있는 값을 레지스터로 가져와서 계산

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

• 캐시

  • 레지스터와 메모리의 중간 다리 역할을 하는 메모리

  • 레지스터가 필요로 할 것 같은 데이터를 메인메모리에서 미리 가져와서 저장해두는 장소

  • 휘발성 메모리

  • 캐시는 성능의 이유로 L1, L2, L3등 여러 개가 존재

  • CPU가 값을 요청해 레지스터로 값을 옮겨야 할 때 가장 속도가 빠른 L1 → L2 → L3 → 메인메모리의 순서대로 참조하여 값을 가져옴 (값이 없으면 하위 단계를 참조하는 방식)

• 메인메모리

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

  • 전원이 공급되지 않으면 데이터가 사라지는 휘발성 메모리

  • 보조저장장치보다 가격이 비싸고 휘발성이기 때문에 실행중인 프로그램만 올림

• 보조저장장치(HDD/SSD)

  • 가격이 저렴하고 전원이 공급되지 않아도 데이터가 지워지지 않는 비휘발성 메모리

2. 메모리와 주소

• 유니프로그래밍 환경에서는 하나의 프로세스만 메모리에 올라오기 때문에 메모리 관리가 어렵지 않았음

• 멀티프로그래밍 환경에서는 여러 프로세스가 메모리에 올라오기 때문에 메모리 복잡하고 어려워졌음

  • 주소 변환 필요

  • 프로세스 간 메모리 침범 방지 대책 필요

  • 동적 메모리 할당 및 해제가 복잡

  • 프로세스 간 메모리 공유 및 보호 문제

• 32bit CPU와 64bit CPU

  • 32bit CPU

    • 레지스터 크기, ALU, 버스의 크기가 모두 32bit

    • 최대 메모리의 크기: 2^32 = 4GB

  • 64bit CPU

    • 레지스터 크기, ALU, 버스의 크기가 모두 64bit

    • 최대 메모리의 크기: 2^64 = 거의 무한대

  • 64bit CPU가 1번에 처리할 수 있는 양이 더 많으므로 속도가 더 빠름

• 물리주소와 논리주소

   

  • 물리 주소 공간: 메모리의 실제 주소공간

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

     

  • 경계 레지스터

    • 사용자 프로세스가 운영체제의 영역에 함부로 접근하지 못하도록 하드웨어적으로 운영체제 공간과 사용자 공간을 나누는 역할을 하는 레지스터

    • CPU내에 존재하는 레지스터로 메모리 관리자가 사용자 프로세스가 경계 레지스터의 값을 벗어났는지 검사하고 만약 벗어났다면 그 프로세스를 종료시킴

       

• 절대주소와 상대주소

   

  • 실제 프로그램은 4000번지에서 시작되지만 컴파일러는 0번지에서 시작한다고 생각함

  • 절대 주소(물리 주소)

    • 메모리 내에서 프로세스가 실행되는 실제 주소 공간

    • 메모리 관리자 관점으로 바라본 주소

    • 그림에서는 실제 프로그램이 올라간 4000번지

  • 상대 주소(논리주소)

    • 사용자 관점으로 바라본 주소

    • 그림에서는 컴파일러가 생각한 0번지

       

  • CPU가 100번지의 값을 요청하면 재배치 레지스터 저장된 값인 4000번지의 값을 더한 4100번지의 값에 접근하여 데이터를 가져옴

  • 재배치 레지스터에는 프로그램의 시작주소가 저장되어 있음

  • 메모리 관리자는 사용자 접근 시마다 위의 방식대로 계산

  • 메모리 관리자 덕분에 주소에 대해 크게 신경쓰지 않아도 프로그램을 만들 수 있고 시작영역이 변경되더라도 재배치 레지스터의 값만 변경하면 되기에 굉장히 유연함

3. 메모리 할당방식

• 메모리 오버레이

  • 메모리의 크기보다 더 큰 프로그램을 실행시키는 방법

  • 큰 프로그램을 작게 나누어 일부만 메모리에서 실행하고 나머지는 하드디스크의 스왑영역에 저장

     

  • 하지만 스왑영역도 하드디스크의 일부 영역이고 스왑영역의 데이터와 메모리의 데이터를 교체하는 작업이 필요하므로 실제 메모리보다는 느리게 동작함

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

   

  • 한 프로세스가 메모리의 연속된 공간에 할당되므로 연속 메모리 할당 이라고도 부름

     

  • 한 프로세스가 메모리에 분산되어 할당되기 때문에 비연속 메모리 할당 이라고도 부름

  • 가변 분할 방식의 장/단점

  장점 단점 프로세스의 크기에 딱 맞게 할당됨 → 내부 단편화가 없음 외부 단편화가 발생

  • 고정 분할 방식의 장/단점

  장점 단점 같은 크기로 나누기 때문에 단순함 → 구현이 간단하고 오버헤드가 적음 작은 프로세스가 큰 공간에 할당되어 낭비되는 공간이 발생 → 내부 단편화가 발생

  • 외부 단편화

    • 충분한 메모리 공간이 있음에도, 연속된 빈 공간의 크기가 부족하여 프로세스를 메모리에 할당할 수 없는 상태

       

    • 조각 모음을 통해 외부 단편화가 발생한 공간을 합칠 수 있지만 실행중인 프로세스들을 일시 중지해야하고 메모리 공간을 이동시키는 작업을 수행해야 하므로 오버헤드 발생

  • 내부 단편화

    • 분할 메모리의 크기가 프로세스가 필요한 크기보다 크게 할당되어 내부에 빈 공간이 생겨 낭비되는 현상

       

    • 낭비되는 공간을 해결할 뚜렷한 방법은 없으나, 분할 메모리의 크기를 조절하여 내부단편화를 최소화하는 전략을 취함

• 버디 시스템

  • 2의 제곱수로 메모리를 분할하여 메모리를 할당하는 방식

     

  • 메모리를 2의 제곱수로 나누어 프로세스가 필요로 하는 크기보다 작을 때까지 나눔

    • 위 그림에서는 500이므로 256까지 메모리를 나눔

  • 나눴을 때 가장 작은 단위보다 한 단계 위의 공간에 프로세스를 할당

    • 256에는 할당할 수 없으므로 512에 할당

  • 여기서도 내부 단편화가 발생하지만 그 값을 최소화할 수 있음

  • 프로세스가 종료되어 메모리가 다시 확보되었을 때 비슷한 크기 혹은 같은 크기의 분할 공간이기에 메모리를 다시 합치기도 용이함

   

  • 버디 시스템 방식

    • 가변 분할 방식처럼 프로세스의 크기에 따라 유동적으로 메모리를 할당 가능

    • 외부 단편화 방지를 위해 메모리 공간을 확보하는 것이 용이

    • 외부고정 분할 방식처럼 내부 단편화가 발생하지만 많은 공간 낭비가 발생하지 않음

     

자료구조

재귀(Recursion)

1. 재귀란?

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

• 재귀적으로 정의된 함수를 재귀함수라고 부름

2. 재귀 함수의 간단한 예시

// 잘못된 방식의 재귀함수

function myFunction(number){
	console.log(number);
	myFunction(number + 1);
}

myFunction(1);

// 이 함수를 실행하면 정확한 종료 조건(기저 조건)이 없기 때문에
// 콜스택이 쌓여 계속 메모리 공간이 가득 차서 자동으로 종료됨

// 올바른 형식의 재귀함수

function myFunction(number){
	if (number > 3) return;
	console.log(number);
	myFunction(number + 1);
}

myFunction(1);

// 이 함수는 1 ~ 3까지는 재귀적으로 자신을 호출하다가
// 종료 조건(기저 조건)인 number > 3에 걸리게 되면 함수를 종료

3. 콜스택

• 스택의 영역의 일부 중 함수가 호출되면서 올라가는 영역

• 재귀 함수 호출 시 플로우 차트

   

• 위 그림처럼 함수를 호출할 때마다 위와 같이 콜스택에 쌓이게 됨

• 재귀를 사용하는 이유 : 더 복잡한 문제를 쉽게 해결하기 위해

  • 팩토리얼, 피보나치 수열문제 등

4. 재귀적으로 생각하기 (재귀로 풀 수 있는 유형 알아보기)

• 단순 반복 → 반복문을 재귀로 변경하기

  • 반복문을 재귀로 변경하면 성능 상 이점이 크게 없음 (메모리 문제 때문에 오히려 감소할 수도…)

• 하위 문제의 결과를 상위 문제의 해결에 사용하는 경우 (하향식 계산) ⭐⭐⭐

  • 배열의 합, 문자열의 길이, power 함수 …

5. 하노이의 탑 ⭐⭐⭐

• 하향식 접근을 통한 하노이의 탑 풀이

• 하노이의 탑 코드

  
  /**
   * @param {*} ringCount  원반 개수
   * @param {*} from 출발지 기둥
   * @param {*} to 임시 기둥
   * @param {*} temp 목적지 기둥
   * @returns 
   */
  function hanoi(ringCount, from, to, temp) {
    /* 종료(기저) 조건 */
    if (ringCount == 0) return;
  
    /* 재귀 조건 */
    // 기둥 A에 있는 원반 1,2를 B로 옮김
    hanoi(ringCount - 1, from, temp, to);
    // 기둥 A에 있는 원반 3을 C로 옮김
    console.log(`원반 ${ringCount}을(를) ${from}에서 ${to}로 이동`);
  
    // 기둥 B에 있는 원반 1,2을 C로 옮김
    hanoi(ringCount - 1, temp, to, from);
  }
  
  hanoi(3, 'A', 'C', 'B');

일주일 간의 회고

🍷칭찬하고 싶은 점

• 절대적 시간이 부족했지만 포기하지 않고 운영체제 강의는 끝까지 완주한 점

• 배운 내용까지 최대한 디테일하게 정리한 점

😅아쉬웠던 점

• 자료구조 및 알고리즘의 재귀까지는 제대로 강의를 들었지만 정렬 부분은 아직 정리를 못했습니다. ㅠㅠㅠ

• 예비군 2박3일 일정을 알고 있었는데도 시간 관리를 제대로 하지 못한 점이 아쉽습니다.

🛠보완하고 싶은 점

• 시간에 쫒겨서 제대로 정리하지 못한 부분을 제대로 정리하고 마지막 주차 잘 준비했으면 합니다.

• 일단 이해가 가지 않더라도 중간에 끊지 않고 먼저 1번 듣고 그 다음에 정리하는 습관을 몸에 들여야겠습니다.