운영체제

섹션 3

- SJF

FIFO는 Burst Time이 짧은 것과 관계없이 실행되어서 효율적이지 않다.

그로 인해 Burst Time이 짧은 것부터 실행시키는 Shortest Job First가 생겼다.

이론상 FIFO보다 성능이 좋지만 프로세스의 작동시간을 예측하기 힘든다는 점과 실행시간이 너무 긴 프로세스는 너무 늦게 실행된다는 단점이 있다.

이러한 이유로 사용되지 않는다.

- RR

사람들은 생각한 결과 FIFO에서 단점만 해결해보자고 생각이 들었다.

운영체제가 프로세스에게 시간을 부여하고 그 시간을 넘으면 강제로 다음 프로세스를 작동시키는 구조로 되었다.

프로세스에게 할당하는 시간은 "타임 슬라이스" 혹은 "타임 퀀텀"이라고 부른다.

물론 상황에 따라 FIFO가 더 좋은 경우도 있기에 무조건적으로 좋은 것은 아니다.

- MLFQ

Multi Level Feedback Queue

RR의 업그레이드 버전이다.

프러세스마다 CPU를 더 사용하는지 I/O를 더 사용하는지에 따라 "CPU Bound Process"와 "I/O Bound Process"로 나누어진다.

"CPU Bound Process"는 CPU사용률과 처리량을 중요하게 생각하고 "I/O Bound Process"는 응답속도를 중요하게 여긴다.

작동 구조는 프로세스의 종류에 따라 타임 슬라이스를 다르게 주는 것이다.

둘의 구분법은 CPU를 반납하는지 혹은 CPU를 뺏기는 지에 따라 구분한다.

섹션 4

- 프로세스 간 통신

프로세스틑 다른 프로세스와 협업하는 경우도 있다.

통신은 같은 컴퓨터나 다른 방식으로 연결된 프로세스와 할 수도 있다.

통신의 종류

• 파일와 파이프 이용

  • 프로세스들이 하나의 파일을 읽고 쓰는 방식

  • 파이프를 이용해 주고받는 방식

• 쓰레드 이용

  • 프로세스 간 통신이 아닌 쓰레드 간 통신 방법

  • 데이터, 힙에 있는 정보를 공유해서 사용

• 네트워크 이용

  • 소켓통신

  • RPC를 통해 통신

- 공유자원과 임계구역

프로세스 간 통신할 때 공동으로 사용하는 파일들이 있다.

이런 파일들을 공유자원이라고 한다.

프로세스의 접근 순서에 따라 값이 다를 수 있다.

시분할 처리로 인해 뭐가 먼저 실행되는지 예측하기 힘들다.

위와 같은 문제를 동기화 문제라고 한다.

동기화 문제를 일으키기 때문에 동시에 이용하면 안되는 영역을 임계구역이라고 한다.

문제를 해결하기 위해서는 상호배제 매커니즘이 필요하다.

요구사항

• 주어진 시간에 하나의 프로세스만 접근이 가능해야 한다

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

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

- 세마포어

상호배제 메커니즘 중 한가지이다.

예시로는 강의에서 프린터실,열쇠관리자,직원 등으로 예시를 들었다.

int s

wait(s)

int currentHealth = GetHealth();
health = currentHealth + 50;

signal(s);

wait(s)

int currentHealth = GetHealth();
health = currentHealth - 10;

signal(s);

여기서는 예시가 1가지이지만 실제로는 여러가지의 열괴를 가질 수 있다.

단점

• wait과 signal을 잘못 사용하면 꼬일 가능성도 있다.

- 모니터

세마포어의 단점을 해결한 상호배제 알고리즘

운영체제가 아니라 사용하는 언어 차원에서 해결하는 것

예 : java의 synchronized, 이 함수를 사용하면 겹쳐서 사용되지 않는다.

섹션 5

- 데드락이란?

프로세스간에 서로 자원을 가지려고 하다가 아무도 사용하지 못하는 상태를 교착상태라고 한다.

이런 상태가 일어나는 것은 공유자원 때문이다.

예시 : 식사하는 철학자 예시

교착상태의 필요조건 4가지

• 상호배제

  • 자원을 한 프로세스가 가져갔다면 다른 프로세스에게 공유되서는 안된다.

• 비선점

  • 리소스를 강제로 빼앗을 수 없다

• 점유와 대기

  • 프로세스가 자원A를 가지고 있는 상태에서 자원 B를 원하는 상태여야 한다.

• 원형 대기

  • 점우와 대기를 하는 관계가 원형이어야 한다.

• 이 중 한가지라도 만족되지 않으면 생기지 않는다.

연구자들은 예방을 하려고 하였으나 너무 복잡해져서 대신 해결하는 방법을 연구하였다.

- 데드락 해결

교착상태 회피

자원을 할당할 때 교착상태가 생기지 않을 정도만 주는 것을 말한다.

은행원 알고리즘

자신의 자원 상태에 따라 할당을 적절하게 주는 것

1. 운영체제는 자신의 자원 수를 파악한다

2. 프로세스는 자신의 최대 요구 자원을 운영체제에게 알려준다

3. 현재 자원 요구량에 따라 프로세스에게 자원을 나눠준다

4. 그 이후 요구량에 따라서 적절한 순으로 할당과 회수를 반복한다

이런 방식은 불편하고 비싸기 때문에 해결 방법을 생각했다.

그 이후 교착상태를 검출하는 방법을 고민했다.

2가지 방법을 알아냈다.

1. 가벼운 교착 상태 검출

   1. 특정 시간 동안 프로세스가 일을 안하면 교착상태로 판단

   2. 교착상태가 아니었던 일정 시간 전으로 바꾸기

2. 무거운 교착 상태 검출

   1. 프로세스의 자원 사용량을 보고 판단

       

   2. 이 방법은 정확성은 좋지만 지속적으로 확인해야해서 힘들다

섹션 7

- 메모리 종류

컴퓨터에서는 메모리가 여러 종류가 있다

• 레지스터

  • 휘발성 메모리

  • 컴퓨터의 bit는 레지스터의 크기를 말한다

  • 메인메모리의 값을 가져와서 레지스터에서 연산 후 다시 메인메모리로 저장

• 캐시

  • 레지스터와 메인메모리 속도 차이 때문에 미리 데이터를 가져오는 곳

  • 여러개이다

• 메인메모리(RAM)

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

  • 휘발성 메모리

  • 가격이 비싸다

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

  • 파일 저장 공간

  • 비휘발성 메모리

- 메모리와 주소

• 주소

현대의 컴퓨터는 폰 노이만 구조에 따라 모든 프로그램을 메모리에 올려서 실행시킨다

운영체제는 멀티프로그래밍 환경 때문에 1바이트 크기로 메모리를 나누고 관리한다.

한칸마다 숫자를 지정하는데 그것이 주소이다.

주소에서 0x0대로 시작하는 주소가 있는데 그곳을 물리 주소라고 부른다.

사용자 관점에서 바라본 주소 공간은 논리 주소라고 부른다.

• 경계 레지스터

주소 처음에는 운영체제를 두는 공간이 있는데 만약 사용자가 악의적은 프로세스를 넣어서 침범한다면 위험하다

이런 이유로 물리적으로 분리하는 경계 레지스터를 만들었다.

경계 레지스터는 프로세스가 할당받지 않은 주소를 침범했다면 종료시킨다.

• 절대주소와 상대주소

메모리에는 절대주소와 상대주소가 존재한다.

프로그램이 실행되면 컴파일러는 0번지에서 시작한다고 알고있지만 절대주소로는 다른 주소에서 시작한다.

만약 사용자가 10번지의 데이터를 가져오라고 한다면 절대주소+10번지의 데이터를 가져온다.

- 메모리 할당방식

• 메모리 오버레이

유니프로그래밍 환경에서 메모리보다 더 큰 프로램을 실행시키는 방법은 사용되는 곳만 메모리에 넣고 나머지는 하드디스크에 넣는 방식이다

• 현대의 메모리를 나누는 방식

1. 가변 분할 방식

   1. 메모리에 연속해서 프로세스를 집어넣는 것

   2. 연속 메모리 할당

   3. 장점

      1. 낭비되는 공간 없음

   4. 단점

      1. 외부 단편화

         1. 만약 프로세스가 끝나면 빈 공간이 생긴다

         2. 빈 공간이 여러개일 때 합치면 프로세스에게 줄 크기더라도 연속돼있지 않으면 사용이 불가능하다

         3. 합칠 수는 있지만 다른 프로세스들을 정지키시고 해야 하기 때문에 힘들다

2. 고정 분할 방식

   1. 프로세스의 크기에 상관없이 메모리를 정해진 크기로 나눈다.

   2. 프로세스도 그 크기에 맞춰서 넣는다

   3. 비연속 메모리 할당

   4. 장점

      1. 구현이 간단하다

      2. 오버헤드가 적다

   5. 단점

      1. 공간이 남는 상황이 있다

          

3. 버디 시스템

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

   2. 남는 공간이 최소화되고 사라진 이후에도 붙어있는 공간과 합치기 편리하다

알고리즘

https://github.com/asdf1596/cs_inflearn_club

섹션 3

- 재귀

재귀란?

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

• 프로그래밍에서는 함수를 정의할 때 재귀를 사용하는데 그것이 재귀함수이다

프로그래밍

function myFunction(number) {
    if (number > 10) return;
    console.log(number);
    myFunction(number);
}

myFunction(1);

기초적인 재귀함수

콜스택

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

FILO의 특징을 가지고 있다

위쪽 코드에서 return이 없을 경우 콜스택이 꽉 찰 때까지 실행된다.

콜스택은 함수가 실행되면 콜스택에 올라오고 실행된다, 실행된 후 만약 끝난다면 사라진다.

하지만 종료되지 않고 함수 내에서 다시 호출되면 사라지지 않고 스택에 남아 있는다.

그로 인해 콜스택의 크기가 꽉 차게 되고 끝난다.

앞선 내용만 보면 재귀보다 그냥 for문을 쓰는 것이 좋아보이지만 재귀함수를 이용하면 해결하기 힘든 문제를 쉽게 해결할 수 있다. - 예 : 팩토리얼

팩토리얼 구현

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

- 재귀적으로 생각하기

1.단순반복실행

ㄴ 단순반복은 오히려 for문보다 좋지 않다

2.하위문제를 기반으로 현재 문제 해결

ㄴfor문은 처음부터 쭉 올라가서 상향식 계산이라고 한다

ㄴ재귀의 경우 하향식 계산이다

ㄴ재귀를 쓴다고 다 하향식을 아니다

ㄴ쓸모없다

배열의 합 계산

하향식 계산 -> 1~5 계산 -> 1~4의 합 + 5 -> 1~4의 합은 1~3의 합에 4를 더한 값이다 -> ...반복

구현

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);

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

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

- 하노이 탑

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");

- 버블정렬

가장 쉬운 정렬이지만 성능이 좋지 않다

바로 옆의 숫자와 비교해서 정렬하는 방식

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

걸리는 시간은 O(n^2)이다.

간단하지만 확실히 시간이 오래 걸린다.

활용 : https://acmicpc.net/problem/23969

장점

• 이해와 구현이 간단하다

단점

• O(n^2)로 성능이 그리 좋지 않다

- 선택 정렬

이해와 구현이 간단하지만 역시 성능이 아쉽다

배열의 모드 값을 비교 후 가장 작은 값을 첫번째 원소로 가져온다

그 이후 정렬된 영역 뒤부터 다시 가장 작은 원소를 첫번째로 가져온다

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

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

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

let arr = [4, 2, 1, 3];
console.log("=====정렬 전=====");
console.log(arr);
SelectionSort(arr);
console.log("======정렬 후=====");
console.log(arr);

걸리는 시간 또한 O(n^2)이다.

버블정렬과 같 시간이 오래 걸린다.

장점

• 이해와 구현이 간단하다

단점

• O(n^2)로 성능이 그리 좋지 않다