그림으로 쉽게 배우는 자료구조와 알고리즘

재귀(recursion) : 어떠한 것을 정의할 때 자기 자신을 참조하는 것

콜스택

• 함수가 호출되면서 올라가는 메모리 영역, 스택이라고도 부름

• First In Last Out

  (그림을 보면 기억이 더 잘 날 것 같아서 캡쳐! FILO를 시각적으로 이해할 수 있어서 좋다💕)

재귀함수 예시 : 팩토리얼 함수

function factorial(number){
    if(number == 1 || number == 0){
        return 1;
    } else{
        return number * factorial(number - 1);
    }
}

(이게 어떻게 구현이 가능한 것인지 완벽히 이해되지는 않지만, 이렇게 간단히 표현 할 수 있다는 것이 놀랍다.)

재귀적으로 생각하기

• 하위 문제의 결과를 기반으로 현재 문제를 계산 -> 하향식 계산

• 재귀함수의 위력은 하향식 계산에서 발휘

   

• 배열의 합

   

function sumArray(arr){
    if(arr.length == 1) return arr[0];
    return sumArray(arr.slice(0, -1)) + arr[arr.length -1];
}

• 문자열의 길이를 계산

function strLength(arr){
    if(arr[0] == null) return 0;
    return strLength(arr.slice(0, -1)) + 1;
}

• 지수함수(밑 x, 지수 n)

function power(x, n){
    if(n == 0) return 1;
    retrun power(x, n-1) * x;
}

하노이 탑

function hanoi(count, from, to, temp){
    if(count == 0) return;
    hanoi(count - 1, from, temp, to);
    console.log({"원반 ${count}를 ${from}에서 ${to}로 이동");
    hanoi(count -1, temp, to, from);
}

hanoi(3, "A", "C", "B");

정렬 - 버블 정렬(Bubble Sort)

• 데이터를 옆 데이터와 비교하면서 자리를 바꿈

function BubbleSort(arr){
    for(let i = 0; i < arr.length - 1; i++){
        for(let j = 0; j < (arr.length - i - 1); j++){
            if(arr[j] > arr[j + 1]){
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

• 버블정렬의 성능 : Ο(n²)

• 장점 : 이해와 구현이 간단함

• 단점 : 성능이 좋지 않음

 정렬 - 선택 정렬(Selection Sort)

• 배열의 정렬되지 않은 영역의 첫 번째 원소를 시작으로 마지막 원소까지 비교 후 가장 작은 값을 첫번째 원소로 가져옴

function SelectionSort(arr){
    for(let i = 0; i < arr.length - 1; i++){
        let minValueIndex = i;

        for(let j = i + 1; i < arr.length; j++){
            if(arr[j] < arr[minValueIndex]){
                minValueIndex = j;
            }
        }

        let temp = arr[i];
        arr[i] = arr[minValueIndex];
        arr[minValueIndex] = temp;
    }
}
 

• 선택 정렬의 성능 : Ο(n²)

• 장점 : 이해와 구현이 간단함

• 단점 : 성능이 좋지 않음

   

그림으로 쉽게 배우는 운영체제

CPU 스케줄링

• 운영체제는 모든 프로세스에게 CPU를 할당/해제하는데 이를 CPU 스케줄링이라고 한다.

• CPU 스케줄링에서 스케줄러(운영체제)가 고려해야 할 사항

   

  • 첫번째, 어떤 프로세스에게 CPU 리소스를 줘야하는가?

  • 두번째, CPU를 할당받은 프로세스가 얼마의 시간동안 CPU를 사용해야하는가?

• 스케줄링 목표

   

  • 리소스 사용률

  • 오버헤드 최소화

  • 공평성

     

  • 처리량

  • 대기시간

  • 응답시간

• 스케줄링 알고리즘

   

  • FIFO(First In First Out)

     

    • Burst Time이 짧은게 먼저 실행되면 평균 대기 시간이 짧아진다.

  • SJF(Shortest Job First)

     

    • 문제1 : 어떤 프로세스가 얼마나 실행될지 예측 어려움

    • 문제2 : Burst Time이 긴 프로세스는 오랫동안 실행되지 않을 수도 있다

  • RR(Round Robin)

     

    • 한 프로세스에 일정 시간만큼 CPU 할당(타임 슬라이스)

    • 타임 슬라이스가 작을 경우 컨텍스트 스위칭이 너무 자주 일어나게 되어 오버헤드 발생

    • 여러 프로세스가 동시에 실행되는 것처럼 느껴지면서 오버헤드가 너무 크지 않은 값을 찾아야 함

    • Windows는 20ms, Unix는 100ms

  • MLFQ(Multi Level Feedback Queue)

     

    • 오늘날 운영체제에서 가장 일반적으로 사용

    • RR의 업그레이드 버전

    • CPU Bound Process들에게는 타임 슬라이스를 크게 준다.

      
      

 프로세스 동기화

 프로세스 간 통신의 종류

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

   

  • 파일과 파이프 이용

  • 쓰레드 이용(한 프로세스 내에서 쓰레드 간 통신)

  • 네트워크 이용(소켓통신, RPC(원격 프로시저 호출))

공유자원과 임계구역

• 공유자원

   

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

  • "동기화 문제" 발생

• 임계구역

   

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

  • 상호 배제 메커니즘 필요

     

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

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

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

세마포어(상호베제 메커니즘의 한 가지)

• 프린터실(공유자원) 열쇠관리자(운영체제) 예시 -> "열쇠 = 세마포어"

• 단점 : wait()함수와 signal()함수의 순서를 이상하게 호출해서 세마포어를 잘못 사용할 가능성이 있음

모니터

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

• 프로그래밍 언어 차원에서 지원하는 방법

• 자바 : synchronized

  ---

  교착상태(데드락)

  교착상태의 필요조건

• 상호배제

• 비선점

• 점유와 대기

• 원형 대기

교착상태 해결 방법

• 교착상태 회피

   

  • 교착상태가 발생하지 않는 수준의 자원 할당

  • 전체 자원과 할당된 자원의 수를 기준으로 안정상태와 불안정상태 구분

  • 은행원 알고리즘

   

• 교착상태 검출

   

  • 가벼운 교착 상태 검출

     

    • 타이머 이용

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

    • 일정 시점마다 체크포인트를 만들어 작업 저장, 교착상태 발생했다면 마지막으로 저장했던 체크포인트로 롤백

  • 무거운 교착 상태 검출

     

    • 자원 할당 그래프 이용

    • 프로세스가 어떤 자원을 사용하는지 지켜보고 교착상태가 발생했다면 해결

    • 교착상태를 일으킨 프로세스 강제 종료, 다시 실행할 때 체크포인트로 롤백

    • 자원 할당 그래프를 유지하고 검사해야 하기 때문에 오버헤드 발생

       

메모리

메모리 종류

• 레지스터

   

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

  • 휘발성 메모리

  • 32bit 64bit

• 캐시

   

  • 메인메모리에 있는 값을 레지스터로 옮기려면 한참 걸리기 때문에 필요할 것 같은 데이터 미리 가져와 저장

• 메인메모리(RAM)

   

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

  • 휘발성 메모리

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

   

  • 비휘발성 메모리

메모리와 주소

 메모리 = 메인메모리(RAM)

• 물리주소와 논리주소 - 사용자

• 절대주소와 상대주소 - 메모리 관리자

메모리 할당 방식

•  메모리 오버레이(memory overlay)

   

  • 프로그램을 잘라서 실행시켜야 할 부분만 메모리에 올리고 나머지는 하드디스크(스왑영역)에 저장

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

   

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

  • 연속 메모리 할당

  • 장점 : 낭비되는 공간인 '내부 단편화'가 없음

  • 단점 : 외부 단편화 발생(조각모음으로 해결, but 실행되고 있는 프로세스 중지해야 함 오버헤드 발생)

• 고정 분할 방식(페이징)

   

  • 프로세스 크기와 상관없이 메모리를 할당

  • 비연속 메모리 할당

  • 장점 : 구현이 간단, 오버헤드가 적음

  • 단점 : 내부 단편화 발생

• 버디 시스템(가변 + 고정 혼합)

   

  • 2의 승수로 메모리 분할

  • 각 단점 최소화