[인프런 워밍업클럽 CS 2기] 2주차 발자국

2주차 학습 내용

• '그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)' Section 3(Unit 1~5)

• '그림으로 쉽게 배우는 운영체제' Section 3(Unit 5~7), Section 4, 5, 7

'그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)' Section 3(Unit 1~5)

Section 3. 알고리즘

• 재귀

  • 재귀란?

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

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

  • 콜스택?

    • 함수가 호출되면서 올라가는 메모리 영역으로 스택이라고도 불림

    • 스택이기 때문에 First In Last Out 특성을 가짐

       

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

console.log(factorial(5));

• 재귀적으로 생각하기

  • 패턴 1. 반복실행 : 반복문에 비해 크게 이점이 되는 부분은 없음. 오히려 콜스택에 공간을 많이 차지해 성능은 for문 보다 좋지 않음.

    for(let i = 1; i < 11; i++) {
    	console.log(i);
    }
    
    function myFunction(number) {
    	if(number > 10) return;
    	console.log(number);
    	myFunction(number + 1);
    }
    myFunction(1);
    

  • 패턴 2. 하위 문제의 결과를 기반으로 현재 문제를 계산하는 것 : 팩토리얼 계산

    • 하향식 계산

      return number * factorial(number - 1);
      

    • 상향식 계산

      function factorial(number) {
      	let sum = 1;
      	for(let i = 1; i <= number; i++) {
      		sum *= i;
      	}
      	return sum;
      }
      

      function factorial2(number, i = 1, sum = 1) {
      	if(i > number) return sum;
      	return factorial2(number, i + 1, sum * i);
      }
      

    • 재귀함수를 위의 코드처럼 상향식으로 쓸 수도 있긴하지만의 진정한 위력은 하향식 계산에서 발휘됨

    • 하향식 계산 예제로 알아보기

      • 예제 1) 배열의 숫자 모두 더하기

        function sumArray(arr) {
        	if(arr.length == 1) return arr[0];
        	return sumArray(arr.slice(0, -1) + arr[arr.length - 1]);
        }
        
        let arr = [1,2,3,4,5];
        let sum = sumArray(arr);
        console.log(sum);
        

      • 예제 2) 문자열 길이 구하기

        function strLength(arr) {
        	if(arr[0] == null) return 0;
        	return strLength(arr.slice(0, -1)) + 1;
        }
        
        let str = "abcde";
        let len = strLength(str)
        console.log(len);
        

      • 예제 3) 지수함수 만들기

        function power(x, n) {
        	if(n == 0) return 1;
        	return power(x, n - 1) * x;
        }
        
        console.log(power(2, 5));
        

   

• 재귀 - 하노이 탑

  
  

  • 1883년 프랑스 수학자 에두아르드 뤼카가 발표한 게임

  • 기둥 A → 기둥 C 옮기기

    • 원반 1 → 기둥 C 이동, 원반 2→ 기둥 B, 원반 1 → 기둥 B 이동, 원반 3 → 기둥 C 이동, 원반 1 → 기둥 A 이동, 원반 2 → 기둥 C 이동, 원반 1 → 기둥 C 이동 → 성공

  • 하향식 재귀함수로 하노이 탑 게임 풀어보기

    • 기둥 A에 있는 원반 1, 2, 3을 기둥 C로 옮기려 함

    • 첫번째 목표로 원반 3을 기둥 C로 옮기는 것

      
      

      • 원반 1, 2를 목표 기둥이 아닌 기둥 B로 옮겨야 함

        • 원반 1이 기둥 C로 이동

      • 하위 문제가 없다면 스택에서 하나씩 꺼내서 문제를 해결할 수 있음

      

    • 두번째 목표로 원반 2를 기둥 C로 옮기는 것

      

      • 원반 1을 기둥 A로 옮김

      

  • 코드로 살펴보기

    

    • honoi(3, "A", "B", "C") : honoi(원반갯수, 시작기둥, 목표기둥, 임시기둥)

      function hanoi(count, from, to, temp) { // 3, A, C, B
      	if(count == 0) return;
      	hanoi(count - 1, from, temp, to); // 2, A, B, C
      	console.log(`원반 $(count)를 $(from)에서 $(to)로 이동`);
      	hanoi(count - 1, temp, to, from); // 2, B, C, A
      }
      

     

• 정렬 - 버블정렬(Bubble Sort)

  • 배열에 숫자가 무작위로 들어가 있을 때, 데이터를 옆 데이터와 비교하면서 자리를 바꿈(반복에 따라 맨 마지막 원소는 큰 값이므로 범위에서 제외)

  • 코드 구현

    function BubbleSort(arr) {
    	for(let i = 0; i < arr.length - 1; i++) {
    		for(let j = 0; j < arr.length - -- 1; j++) {
    			if(arr[j] > arr[j + 1]) {
    				let temp = arr[j];
    				arr[j] = arr[j + 1];
    				arr[j + 1] = temp;
    			}
    		}
    	}
    }
    
    let arr = [4, 2, 3, 1];
    console.log("==== 정렬 전 ====");
    console.log(arr);
    
    BubbleSort(arr);
    
    console.log("==== 정렬 후 ====");
    console.log(arr);
    

  • 버블 정렬의 성능

    

  • 버블 정렬의 장단점

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

    • 단점 - 성능이 O(n^2)으로 좋지 않음

   

• 정렬 - 선택정렬(Selection Sort)

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

  • 코드 구현

    function SelectionSort(arr) {
    	for(let i = 0; i < arr.length - 1; i++) {
    		let minValueIndex = i;
    
    		for(let j = i + 1; j < arr.length; j++) {
    			if(arr[j] < arr[minValueIndex]) {
    				minValueIndex = j;
    			}
    		}
    
    		let temp = arr[i];
    		arr[j] = arr[minValueIndex];
    		arr[minValueIndex] = temp;
    	}
    }
    
    let arr = [4, 2, 1, 3];
    console.log("==== 정렬 전 ====");
    console.log(arr);
    
    SelectionSort(arr);
    
    console.log("==== 정렬 후 ====");
    console.log(arr);
    

  • 선택 정렬의 성능

    

  • 선택 정렬의 장단점

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

    • 단점 - 성능이 좋지 못함 (O(n^2))

'그림으로 쉽게 배우는 운영체제' Section 3(Unit 5~7), Section 4, 5, 7

Section 3. CPU 스케줄링(Unit 5~7)

• CPU스케줄링 개요

  • 컴퓨터 자원

    • 필수 장치 - CPU, 메모리

    • 주변 장치 - HDD, 키보드, 마우스

  • CPU스케줄링

    • 운영체제가 모든 프로세스에게 CPU를 할당/해제 하는 것

    • CPU가 스케줄링에서 고려할 사항

      • 어떤 프로세스에게 CPU 리소스를 줄 것인가?

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

    • CPU Burst

      • CPU를 할당받아 실행하는 작업

    • I/O Burst

      • 입출력 작업

• 다중큐

  • 프로세스 상태에서 준비상태, 대기상태는 큐(Queue)라는 자료구조로 관리됨

  • 실행 → 준비 상태가 될 때, 운영체제는 그에 맞는 준비 큐에 넣음

  • 실행 → 대기 상태가 될 때, I/O 작업 종류에 따라서 분류된 큐에 들어가게 됨 (ex, 하드디스크 작업 → HDD 큐)

  • 정확히는 프로세스 정보를 가지고 있는 PCB가 들어가게 됨

• 스케줄링 목표

  • 리소스 사용률

    • CPU 사용률 높이기, I/O 디바이스의 사용률 높이기 등등

  • 오버헤드 최소화

    • 스케줄링을 하기 위한 계산이 너무 복잡해지거나, 컨텍스트 스위칭을 너무 자주하지 않도록

  • 공평성

    • 모든 프로세스에게 공평하게 CPU가 할당되어야 함

    • 공평의 의미는 시스템에 따라 달라질 수 있음

  • 처리량

    • 같은 시간 내에 더 많은 처리를 할 수 있는 방법

  • 대기 시간

    • 작업을 요청하고 실제 작업이 이루어지기 전까지 대기 시간이 짧은 것을 목표로 함

  • 응답 시간

    • 대화형 시스템에서 사용자의 요청이 얼마나 빨리 반응하는지가 중요하기 때문에 응답시간이 짧은 것을 목표로 함

  • 목표간에 서로 상반되는 상황이 있는데, 이 때는 사용자가 사용하는 시스템에 따라 목표를 다르게 설정하게 됨 (ex, 터치스크린 → 응답시간 짧도록, 과학 계산 → 처리량이 높도록 초점 맞춤)

• FIFO(First In First Out)

  • 스케줄링 큐에 들어온 순서대로 CPU를 할당받는 방식

  • 먼저 들어온 프로세스가 완전히 끝나야만 다음 프로세스가 실행될 수 있음

  • 장점

    • 단순하고 직관적

  • 단점

    • 한 프로세스가 완전히 끝나야 다음 프로세스가 시작되기 때문에 실행시간이 짧고 늦게 도착한 프로세스가 실행시간이 길고 빨리 도착한 프로세스의 작업을 기다려야 함

    • I/O 작업이 있다면 끝날 때까지 쉬고있기 때문에 CPU 사용률이 떨어지게 됨

  • 스케줄링의 성능 → 평균 대기 시간으로 평가함

    • 프로세스의 실행 순서만 바꿔도 평균 대기 시간의 차이가 많이 남

    • FIFO 알고리즘은 프로세스의 Burst Time에 따라 성능의 차이가 심하게 나기 때문에 현대 운영체제에서 잘 쓰이지 않고, 일괄처리시스템에 쓰임

• SJF(Shortest Job First)

  • 작업의 순서에 따라 평균 대기 시간이 달라지는 FIFO에서 Burst Time이 짧은 프로세스를 먼저 실행했을 때 평균대기시간이 짧아지는 알고리즘을 만들기로 함 → SJF

  • FIFO보다 이론적으로 성능이 좋음

  • 실제 구현 시 두 가지 문제 발생

    • 첫번째 문제

      • 어떤 프로세스가 얼마나 실행될지 예측하기 어려움 (유저의 사용시간에 따라 달라짐)

    • 두번째 문제

      • Burst Time이 긴 프로세스는 아주 오랫동안 실행되지 않을 수도 있다는 것

• RR(Round Robin)

  • FIFO 알고리즘은 일괄처리 시스템에 적절하기 때문에 시분할 처리 시스템에서는 사용하기 힘들고, SJF 알고리즘은 프로세스의 종료시간을 예측하기 힘듦

  • FIFO 알고리즘의 단점을 해결해보기로 함

    • 문제점 - 한 프로세스가 그 다음 프로세스가 실행됨

    • 한 프로세스에게 일정 시간만큼 CPU를 할당하고 강제로 다른 프로세스에게 일정시간만큼 CPU를 할당함 → 강제로 CPU를 뺏긴 프로세스는 큐의 가장 뒷부분으로 밀려남

    • 프로세스에게 할당하는 일정 시간은 ‘타임 슬라이스’ 또는 ‘타임 퀀텀’이라고 부름

  • 작업에 따라 RR 알고리즘과 FIFO 알고리즘의 평균 대기 시간이 비슷할 수도 있는데, 이 때는 RR 알고리즘이 더 비효율적인 방식임

    • 컨텍스트 스위칭이 있기 때문에 컨텍스트 스위칭 시간이 더 추가되기 때문

    • RR 알고리즘 성능은 타임 슬라이스의 값에 따라 크게 달라짐

      • 타임 슬라이스가 큰 경우 : 먼저 들어온 프로세스의 작업이 종료될 때까지 실행하니 FIFO 알고리즘과 동일해짐

      • 타임 슬라이스가 작은 경우 : 컨텍스트 스위칭이 너무 자주 일어나게 되고, 타임 슬라이스에서 실행되는 프로세스의 처리량보다 컨텍스트 스위칭을 처리하는 양이 훨씬 커져서 오버헤드가 너무 커지게 됨

    • 최적의 타임 슬라이스를 결정하는 방법 → 유저가 느끼기에 여러 프로세스를 사용하기에 동시에 실행되는 것처럼 버벅이지 않고 오버헤드가 너무 크지 않은 값을 찾아야 하는 것

• MLFQ(Multi Level Feedback Queue)

  • 오늘날 운영체제에서 가장 일반적으로 쓰이는 CPU 스케줄링 기법

  • RR의 업그레이드 된 알고리즘

  • MLFQ 설명 예시

    • P1 (CPU Bound Process)

      • I/O 작업 없이 CPU 연산만 하는 프로세스

      • CPU 사용률과 처리량을 가장 중요하게 생각

    • P2 (I/O Bound Process)

      • 1초 CPU 작업을 하고 10초 I/O 작업을 함

      • 응답속도를 가장 중요하게 생각

    • 두 프로세스로 두 가지 상황에 따라 성능을 비교해 봄

      

      • 타임 슬라이스가 100초인 경우

      • 타임 슬라이스가 1초인 경우

        • I/O 사용률을 봤을 때 더 좋음

        • P1 입장에서는 CPU 사용율은 100초일 때와 비교했을 때 손해가 없지만, 컨텍스트 스위칭이 있기 때문에 오버헤드가 생겨서 손해를 봄

        • P2 입장에서는 I/O 사용률이 많이 높아졌기 때문에 이득을 봄

        • 손해를 보는 프로세스의 문제를 해결하기 위해 MLFQ가 나오게 됨

    • MLFQ는 기본적으로 CPU 사용률과 I/O 사용률이 좋게 나오는 작은 크기의 타임 슬라이스를 선택함. 그리고 P1과 같은 CPU Bound Process들에게는 타임 슬라이스를 크게 줌

    • 운영체제가 프로세스가 I/O Bound Process인지, CPU Bound Process인지 구분하는 방법

      • I/O Bound Process

        • CPU를 사용하는 프로세스가 실행하다가 스스로 CPU를 반납하면 CPU 사용이 적은 것이니 I/O Bound Process일 확률이 높음

      • CPU Bound Process

        • CPU를 사용하는 프로세스가 타임 슬라이스 크기를 오버해서 CPU 스케줄러에 의해 강제로 CPU를 뺏기는 상황이면 CPU 사용이 많은 것이니 CPU Bound Process일 확률이 높음

    • 위의 아이디어를 가지고 우선순위를 가진 큐를 여러개 준비함 → 우선순위가 높으면 타임 슬라이스가 작고, 우선순위가 낮을수록 타임 슬라이스 크기가 커짐

      

  • MLFQ 외에도 HRN, SRT, MLQ, Priority 등 다양한 알고리즘이 있지만, MLFQ가 주류임

Section 4. 프로세스 동기화

• 프로세스 간 통신

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

  • 네트워크로 연결된 다른 프로세스와 통신할 수도 있음

  • 통신 방법

    • 한 컴퓨터 내에서 통신하는 방법

      • 파일과 파이프 이용

        • 파일

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

        • 파이프

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

      • 쓰레드를 이용한 방법

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

        • 코드, 데이터, 힙 영역을 공유, 스택만 따로 가짐

        • 여기서 데이터 영역에 있는 전역변수나 힙을 이용

    • 네트워크를 이용한 방법

      • 운영체제가 제공하는 소켓통신이나 다른 컴퓨터에 있는 함수를 호출하는 RPC(원격 프로시저 호출)를 이용해 통신하는 방법이 있음

• 공유자원과 임계구역

  • 공유자원

    • 공동으로 이용하는 변수나 파일들

    • 문제점

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

      • 컨텍스트 스위칭으로 시분할 처리를 하기 때문에 프로세스의 실행 순서를 예측하기 어려움

      • 그에 따라 실행 결과를 예측하기 힘들고, 여기서 발생한 문제를 ‘동기화 문제’라고 부름

      • 이 문제를 해결하기 위해 여러 프로세스가 동시에 사용하면 안되는 영역을 ‘임계구역(Critical Section)’이라고 함

      • 공유자원을 서로 사용하기 위해 경쟁하는 것을 ‘경쟁조건(Race Condition)’이라고 함

    • 임계구역의 문제를 해결하기 위한 방법

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

        • 상호 배제 매커니즘의 요구사항

          1. 주어진 시간에 항상 하나의 프로세스만 접근할 수 있음

          2. 동시에 여러개의 요청이 있더라도 하나의 프로세스의 접근만 허용함

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

• 세마포어

  • 상호배제 매커니즘의 한가지

  • 예시

    • 직원 A, 직원 B가 공유자원인 프린터를 사용하는 상황

    • 동시에 프린터 요청 시, 경쟁 조건이 됨

    • 직원 A, 직원 B의 결과물이 섞여서 나오게 되는 오류 발생

    • 프린터실과 프린터실 열쇠 관리자를 두어 프린터 사용 시, 프린터실 열쇠를 받아 프린터 이용하게 됨. 프린터실 열쇠 관리자에게 열쇠가 없다면 누군가 프린터실 사용중이므로 기다려야 함

    • 위의 예시는 세마포어 매커니즘

    • 동기화에서 중요한 개념

  • 예시를 현실 프로세스 매커니즘으로 생각

    • 직원들 → 프로세스

    • 프린터 → 공유자원

    • 프로세스가 기다리는 공간 → 대기큐

    • 열쇠 관리자 → 운영체제

    • 열쇠 → 세마포어(semaphore)

      • 세마포어 - 정수형 변수

  • 코드 예시

    • 예시) 게임에서 물약 먹어서 체력 회복 / 공격받아서 체력 줄어드는 상황이 동시에 진행됨

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

      // 물약 먹는 코드
      
      wait(s); // 열쇠를 요청해서 열쇠를 받고 문을 잠금
      
      int currentHealth = GetHealth();
      health = currentHealth + 50;
      
      signal(s); // 방에서 나와 문지키는 직원에게 열쇠 반납
      

      // 공격받는 코드
      
      wait(s); // 열쇠를 요청해서 열쇠를 받고 문을 잠금
      
      int currentHealth = GetHealth();
      health = currentHealth - 10;
      
      signal(s); // 방에서 나와 문지키는 직원에게 열쇠 반납
      

    • 세마포어를 이용하면 공유자원에 여러 프로세스가 동시에 접근하지 못하기 때문에 동기화 문제가 발생하지 않음

  • 세마포어의 문제점

    • wait() 함수와 signal() 함수를 이상하게 호출하여 세마포어를 잘못사용할 가능성이 있음

      

    • 이 문제를 해결한 방법 → 모니터

• 모니터

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

  • 모니터는 따로 운영체제가 처리하는 것이 아니라 프로그래밍 언어 차원에서 지원하는 방법

  • 자바 예시

    • synchronized가 붙으면 동시에 여러 프로세스에서 실행시킬 수 없음 → 상호배제가 완벽하게 됨

    • increase() 뿐만 아니라 synchronized가 붙은 decrease()도 실행할 수 없음

      

  • 모니터의 구현만 완벽하다면, 프로그래머는 세마포어처럼 wait(), signal() 함수를 임계영역에 감싸지 않아도 되서 편리하고 안전하게 코드 작성 가능함

Section 5. 데드락

• 데드락이란?(feat.식사하는 철학자)

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

  • 일상생활 예시

    • 교통상황

      

  • 교착상태가 발생하는 이유

    • 공유자원 때문. 만약 어떤 자원을 여러 개의 프로세스가 공유하지 않는다면 교착상태는 발생하지않음

  • 식사하는 철학자 예시

    

    • 포크가 2개 있어야 식사가 가능한데, 우연히 모든 철학자가 자신의 오른쪽의 포크를 동시에 사용할 때 → 교착상태

  • 교착상태의 필요조건

    • 필요조건에는 네 가지가 있는데, 모두 충족되어야 교착상태 발생함

      • 상호배제

        • 어떤 프로세스가 한 리소스를 점유했다면, 그 리소스는 다른 프로세스에게 공유가 되면 안됨

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

      • 비선점

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

        • 식사하는 철학자 예시에서 철학자 A의 포크를 철학자 B가 뺏을 수 없음

      • 점유와 대기

        • 어떤 프로세스가 리소스 A를 가지고 있는 상태에서 리소스 B를 원하는 상태여야 함

        • 식사하는 철학자에서 오른쪽 포크를 든 상태에서 왼쪽 포크를 기다리고 있는 상태

      • 원형 대기

        • 점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있음

        • 식사하는 철학자에서 서로가 서로의 포크를 원하는 상황이 원형을 이룸

  • 교착상태를 예방하는 방법을 고려했으나, 제약이 많고 비효율적이라 다른 방식 연구 → 교착상태에 빠졌을 때 해결하는 방법 연구

• 데드락 해결(feat. 은행원 알고리즘)

  • 교착상태 해결방법으로 ‘교착상태 회피(Deadlock avoidance)’라는 방법이 있음

  • 교착상태 회피(Deadlock avoidance)

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

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

    • 운영체제가 최대한 안정상태를 유지하려고 자원할당을 함

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

  • 교착상태 회피를 표한한 알고리즘 → 은행원 알고리즘

    • 은행이 1000만원을 가지고 있다고 가정하고, 사업가 A에게 500만원, 사업가 B에게 400만원을 빌려줌(은행 잔고 100만원) → 이후 사업가 A가 은행에게 200만원을 더 빌려주면 빌린돈을 상환할 수 있다고 함 → 은행이 B에게 상환을 요청할 때, B도 200만원을 더 빌려주면 상환가능하다고 함 → 은행은 대출해줄 수도, 상환받을 수도 없는 교착상태에 빠지게 됨

    • 은행이 사업가들에게 돈을 빌려줄 때, 은행의 여윳돈과 사업가들에게 빌려준 돈들을 보고 대출 가능한 상황(안전상태)인지 확인하고 빌려줌

  • 운영체제에서 은행원 알고리즘을 구현하는 방법

    • 운영체제는 프로세스에게 자원을 할당하기 전에 자기가 가지고 있는 전체 자원의 수를 알고 있어야 함 → 시스템의 총 자원

    • 프로세스들은 각자 자기가 필요한 자원의 최대 숫자를 운영체제에게 알려줘야 함 → 최대 요구자원

    • 안정상태

      • 모든 프로세스에게 자원할당 후, 요청이 예상되는 자원이 맞는 프로세스에게 먼저 할당 함 그 후에 자원을 반납 받고 다른 프로세스에게 또 다시 할당할 수 있게 됨

      

    • 불안정상태

      • 현재 사용 가능한 자원이 1개이기 때문에 P1, P2, P3 모두 자원 추가할당이 안됨

      • 불안정상태에 있더라도 모든 프로세스가 최대자원을 요청하지 않는다면, 교착상태에 빠지지 않을수도 있지만 불안정상태에 빠지지 않도록 유지하는게 좋음

        

  • 은행원 알고리즘은 교착상태를 피하는 좋은 방법이지만, 비용이 비싸고 비효율적임 → 그래서 알고리즘 연구자들은 교착상태가 발생하지만, 교착상태가 발생했을 때 이를 해결하는 방식을 연구함

  • 교착상태를 검출하는 방법을 연구(두가지)

    • 가벼운 교착상태 검출 → 타이머 이용

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

      • 해결방법 - 일정 시점마다 체크포인트를 만들어 작업을 저장하고 타임아웃으로 교착상태 발생 시, 마지막으로 저장했던 체크포인트로 롤백하는 것

    • 무거운 교착상태 검출 → 자원 할당 그래프 이용

      • 현재 운영체제에서 프로세스가 어떤 자원을 사용하는지 지켜보고, 교착상태 발생 시 이를 해결함

      • 해결방법 - 운영체제가 자원 할당 그래프를 계속 지켜보고 교착상태 검출 시, 교착상태를 일으킨 프로세스를 강제 종료 시킴 그 후 다시 실행시킬 때 체크포인트로 롤백을 시킴

      • 이 방법은 운영체제가 지속적으로 ‘자원 할당 그래프’를 유지하고 검사해야 하기때문에 오버헤드가 발생함

      • 그러나 가벼운 교착상태 검출에서 발생할 수 있는 억울하게 종료되는 프로세스는 발생하지 않음

    

Section 7. 메모리

• 메모리 종류

  • 왜 여러종류의 메모리가 필요한가

    

    • 레지스터

      • 가장 빠른 기억장소로 CPU 내에 존재하고 있음

      • 컴퓨터 전원이 꺼지면, 데이터 사라짐 - 휘발성 메모리

      • 32bit, 64bit - 레지스터 크기

      • CPU는 계산을 할 때 메인메모리에 있는 값을 레지스터로 가져와 계산을 함 → 계산 결과는 다시 메인메모리에 저장

    • 캐시

      • 휘발성 메모리

      • 레지스터는 CPU가 사용하는 메모리로 빠름, 그에 비해 메인메모리는 너무 느린편 → 메인메모리에 있는 데이터를 레지스터에 옮기려면 한참 걸리기 때문에 필요할 것 같은 데이터를 미리 가져와서 저장함 → 캐시

      • 캐시는 성능의 이유로 여러개를 둠

      • 만약, CPU가 값을 요청해 레지스터로 값을 옮겨야한다면, 단계에 따라 가장 속도가 빠른 L1캐시를 보고 → 여기 없다면 L2캐시를 확인 → 여기도 없으면 메인 메모리에서 값을 가져옴

        

    • 메인 메모리

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

      • 전원이 공급되지 않으면 데이터가 지워짐 → 휘발성 메모리

      • 하드디스크나 SSD보다 속도는 빠르지만 가격이 비쌈 → 데이터 저장보다는 실행중인 프로그램만 올림

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

      • 사무용 프로그램 게임과 같은 파일들을 저장

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

• 메모리와 주소

  • 메인메모리

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

      

    • 멀티프로그램 - 여러개의 프로그램이 올라오게 되어 관리가 복잡해짐

      

    • 운영체제는 관리를 위해 1바이트(8bit) 크기로 구역을 나누고 숫자를 매김 → 주소

    • 32bit CPU vs 64bit CPU

      • 32bit CPU

        • 레지스터 크기가 32bit이고, CPU가 처리하는 ALU도, 데이터가 이동하는 버스도 32bit임.

        • CPU가 다룰 수 있는 메모리도 2^32로 4GB임

      • 32bit CPU

        • 레지스터 크기가 64bit이고, CPU가 처리하는 ALU도, 데이터가 이동하는 버스도 64bit임.

        • CPU가 다룰 수 있는 메모리도 2^64로 거의 무한대에 가까움

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

    • 물리주소, 논리주소

      • 물리주소 공간 - 메모리를 컴퓨터에 연결하면 0x0번지부터 시작하는 주소공간

        

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

      • 사용자 프로세스가 운영체제를 침범하지 않도록 하드웨어적으로 운영체제 공간과 사용자 공간을 나누는 ‘경계 레지스터’를 만듦

      • 경계 레지스터

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

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

    • 절대주소, 상대주소

      

      • 상대주소(논리 주소 공간) - 컴파일러가 컴파일을 할 때, 메모리 0번지에서 실행한다고 가정함

      • 절대주소(물리 주소 공간) - 실제 프로그램이 올라간 주소는 4000번지(메모리 관리자가 바라본 주소)

      • 예를 들어 0x100번지 데이터를 가져올 때, 메모리 관리자는 CPU가 요청한 0x100번지와 재배치 레지스터에 있는 0x4000번지의 값을 더한 0x4100(절대 주소, 물리 주소)에 접근해서 데이터를 가져옴

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

      • 메모리 관리자는 사용자가 메모리에 접근할 때마다 위의 예시처럼 계산함

• 메모리 할당방식

  • 유니프로그래밍에서 메모리의 크기보다 큰 프로그램을 실행시키는 방법

    

    • 큰 프로그램을 메모리에 올릴 수 있도록 잘라서 당장 실행시켜야할 부분만 메모리에 올리고, 나머지는 용량이 큰 하드디스크(하드디스크 내 스왑영역)에 저장시키는 기법 → 메모리 오버레이(memory overlay)

  • 멀티프로그래밍에서 메모리의 크기보다 큰 프로그램을 실행시키는 방법(두가지)

    • 가변 분할 방식(가상 메모리 관점 - 세그멘테이션)

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

      • 한 프로세스가 메모리에 연속된 공간에 할당되기 때문에 ‘연속 메모리 할당’이라고 함

        

      • 장단점

        • 장점 - 메모리에 연속된 공간에 할당되기 때문에 더 크게 할당되서 낭비되는 공간인 ‘내부 단편화’가 없음

        • 단점 - ‘외부 단편화’ 발생

          

          • 메모리 공간이 쪼개져있어서 용량을 합쳐 계산하면 프로세스에게 할당을 할 수 있을 것 같지만,
            사실 할당할 수 없음 → 외부 단편화

          • 해결방법

            • 외부 단편화가 발생한 공간을 합쳐주는 조각모음을 함

            • 그러나 조각모음을 하려면 현재 메모리에서 실행되고 있는 프로세스들의 작업을 일시 중지해야하고, 메모리공간을 이동시키는 작업을 해야하기 때문에 오버헤드가 발생함

    • 고정 분할 방식(가상 메모리 관점 - 페이징)

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

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

        

      • 장단점

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

        • 단점 - 작은 프로세스도 큰 영역에 할당되서 공간이 낭비되는 ‘내부 단편화’가 발생

          • 내부 단편화

            

            • 따로 해결방법은 없고, 분할되는 크기를 조절해서 내부단편화를 최소화 함

    • 버디 시스템

      • 오늘날의 운영체제는 가변분할 방식과 고정분할방식을 혼합하여 단점을 줄임

      • 2의 승수로 메모리를 분할해 메모리를 할당하는 방식

        

      • 여기서도 내부 단편화가 발생하지만, 적은 용량으로 발생

      • 또한 프로세스가 사용을 마치고 메모리에서 나가도 근접한 메모리 공간을 합치기 쉬움 → 2의 승수로 동일하게 나눠서 반대로 조립만 하면 큰 공간이 만들어지기 때문 (조각모음보다 간단)

      • 장단점

         

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

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

회고

• 일주일 동안 스스로 칭찬하고 싶은 점, 아쉬웠던 점, 보완하고 싶은 점

  • 칭찬하고 싶은 점 : 이번주 강의를 매일 집중해서 잘 학습한 점

  • 아쉬웠던 점 : 어제 들었던 강의 내용이 오늘 다시보면 잘 기억이 안난다는 점

  • 보완하고 싶은 점 : 기억력 이슈라 반복할 수밖에 없을 것 같습니다🥲

• 다음주에는 어떤 식으로 학습하겠다는 스스로의 목표

  • 다음주에도 이번주처럼 오늘 범위의 강의를 듣기 전에 어제 범위의 강의를 머릿속으로 다시 생각하고 정리하는 시간을 갖겠습니다.