인프런 워밍업 클럽 2기 - CS 전공지식 스터디 2주차 발자국

운영체제 2주차 학습 요약

CPU 스케쥴링 알고리즘

SJF (Shortest Job First)
- 짧은 작업 시간을 가진 프로세스에 먼저 CPU를 할당하는 방식
- 버스트 타임이 긴 프로세스는 계속 실행되지 않을 수 있고, 어떤 프로세스가 얼마나 실행될지 예측이 어려움
RR (Round Robin)
- 시간을 균등하게 분배하여 각 프로세스에 순차적으로 CPU를 할당하는 방식
- 컨텍스트 스위칭으로 인해 처리량이 늘어남
MLFQ (Multi Level Feedback Queue)
- 프로세스의 우선순위를 동적으로 조절하여 CPU를 효율적으로 할당하는 방식
- 오늘날 운영체제에서 가장 일반적으로 사용됨

프로세스 동기화

여러 프로세스가 공유 자원에 동시에 접근할 때 순서를 정하여 데이터의 일관성을 유지하는 것

프로세스간 통신의 종류

한 컴퓨터 내에서 프로세스간 통신하는 방법 : 파일 or 파이프를 이용
한 프로세스 내에서 쓰레드간 통신하는 방법 : 데이터 or 힙영역을 이용
네트워크를 이용하여 통신하는 방법 : 소켓통신, RPC

공유자원과 임계영역

공유자원은 프로세스 혹은 스레드간 통신할 때 공동으로 이용하는 변수나 파일 같은 것들
공유자원은 여러 프로세스가 공유하고 있기 때문에 각 프로세스의 접근 순서에따라 결과가 달라질 수 있음

임계영역은 프로세스 혹은 스레드가 동시에 사용하면 안되는 영역 (접근 순서등의 이유로 결과가 달라지는 영역)

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

임계구역 문제를 해결하기 위한 조건

상호배체
- 임계영역엔 하나의 프로세스만 접근해야 함
한정대기
- 기다리는 프로세스는 언제가는 임계영역에 접근 할 수 있어야함
진행의 융통성
- 한 프로세스가 다른 프로세스의 일을 방해해서는 안됨

세마포어 & 모니터

뮤텍스는 공유자원을 lock()과 unlock()을 이용하여 프로세스의 접근을 제어하는 메커니즘
여러 프로세스의 접근을 관리할 수 있으면 세마포어 (뮤텍스는 동기화 대상이 오직 하나임)

세마포어는 잘못된 사용으로 임계영역을 보호받지 못할 수 있음 (세마포어를 사용하지 않고 임계구역에 들어간 경우)
이를 해결한 방식이 모니터

모니터는 공유자원을 숨기고 접근에 대한 인터페이스만 제공하여 공유자원에 안전하게 접근하게 하는 메커니즘

운영체제가 처리하는게 아니라 프로그래밍 언어차원에서 지원하는 방법임

교착상태 (데드락)

두개 이상의 프로세스들이 서로가 가진 자원을 기다리다 아무도 작업을 진행하지 못하는 상태

데드락 필요조건

상호배제
비선점
점유대기
원형대기

은행원 알고리즘

총 자원의 양과 현재 할당한 자원의 양을 기준으로 안정 또는 불안정 상태로 나누고, 교착상태가 발생하지 않는 수준이 되도록 자원을 할당하는 알고리즘

검출 & 회복

교착상태는 어떻게 검출하지?

가벼운 교착상태 검출 (타이머)
- 일정시간마다 작업을 조작하고 교착상태가 발생하면 체크포인트로 롤백
무거운 교착상태 검출 (순환구조)
- 교착상태를 일으킨 프로세스를 강제 종료시키고 다시 실행 시킬때 체크포인트로 롤백
- 오버헤드가 발생하지만 억울하게 종료되는 프로세스는 발생하지않음

메모리

레지스터 (32bit 또는 64bit)
캐시
- CPU와 메인메모리 속도 차이 때문에 미리 데이터를 저장하는 임시공간
메인메모리 (RAM)
- 프로세스를 로드, 휘발성
보조기억장치 (SSD, HDD)
- 디스크 저장, 비휘발성

물리 주소 - 물리적인 메모리 주소
논리 주소 - 사용자 관점에서 본 상대적 주소, 사용자는 논리 주소를 통해 물리 주소로 접근

메모리 할당방식

가변분할방식

메모리에 연속해서 프로세스를 할당
단점으로 외부 단편화가 발생할 수 있음

고정분할방식

메모리를 정해진 크기로 나누어 프로세스를 할당
단점으로 내부 단편화가 발생할 수 있음

버디시스템

메모리를 2의 제곱 수로 분할하여 할당하는 방식
가변분할방식과 고정분할방식을 합친 방법

알고리즘 & 자료구조 2주차 학습 요약

재귀 & 재귀적으로 생각하기

재귀는 자기 자신을 다시 호출하는 함수를 말함

어떤 문제를 해결하기 위해 문제의 부분 문제를 같은방식으로 해결하는 과정
하향식 풀이에서 활용됨 (하위 문제를 기반으로 해결)

하노이탑 구현하기

세개의 기둥과 서로 다른 크기의 원반들이 있을때 가장 큰 원반이 아래에 있고 위로 갈수록 작은 원반으로 이루어져있음
하나의 기둥에 있는 원반들을 다른 기둥으로 옮겨야 함
기둥 A에 있는 원반을 기둥 C로 옮기기 (하향식 접근으로 풀이)

처음 시작

그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편) 캡쳐

모두 옮김
그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편) 캡쳐

자바코드

public class HanoiTop {

  void hanoi(int count, String from, String to, String temp){
    if(count == 0) return;
    hanoi(count - 1, from, temp, to);
    System.out.printf("원반 %d를 %s에서 %s로 이동\n", count, from, to);
    hanoi(count - 1, temp, to, from);
  }

  public static void main(String[] args) {
    HanoiTop hanoiTop = new HanoiTop();
    hanoiTop.hanoi(3, "A", "C", "B");
  }

}

버블정렬

앞에 있는 숫자와 옆에 있는 숫자를 비교해서 자리를 바꾸는 알고리즘

자바코드

public class BubbleSort {

  void bubbleSort(int[] arr) {
    // 사이클 - 자리교체는 (배열의 갯수 - 1) 번 수행함
    for (int i = 0; i < arr.length - 1; i++) {
      // 횟수 - 정렬이 된 원소의 이전 원소보다 하나 이전의 원소까지 순회
      // 시작점이 (arr.length-i-1)번 임
      for (int j = 0; j < (arr.length - i - 1); j++) {
        // 앞의 데이터가 뒤에 데이터보다 더 크다면?
        if (arr[j] > arr[j + 1]) {
          // 데이터 자리변경
          int temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
        }
      }
    }
  }

  public static void main(String[] args) {
    int[] arr = {2, 3, 1, 4};

    // 정렬 전 - arr = [2, 3, 1, 4]
    System.out.println("정렬 전 - arr = " + Arrays.toString(arr));
    BubbleSort bubbleSort = new BubbleSort();
    bubbleSort.bubbleSort(arr);

    // 정렬 후 - arr = [1, 2, 3, 4]
    System.out.println("정렬 후 - arr = " + Arrays.toString(arr));
  }

}

선택정렬

정렬되지 않은 배열의 첫번째 원소를 시작으로 마지막 원소까지 탐색하여 가장 작은 값을 정렬되지 않은 첫번째 배열로 가져오는 알고리즘

자바코드

public class SelectionSort {

  void selectionSort(int[] arr) {
    // 1 사이클의 순회는(배열의 갯수 - 1) 번 수행됨
    for (int i = 0; i < arr.length - 1; i++) {
      int minValueIndex = i;

      // 가장 작은 값을 탐색하기위해 순회
      for (int j = i + 1; j < arr.length; j++) {
        if (arr[j] < arr[minValueIndex]) {
          // 작은값 저장
          minValueIndex = j;
        }
      }

      // 자리 변경
      int temp = arr[i];
      arr[i] = arr[minValueIndex];
      arr[minValueIndex] = temp;
    }
  }

  public static void main(String[] args) {
    int[] arr = {4, 2, 1, 3};

    // 정렬 전 - arr = [4, 2, 1, 3]
    System.out.println("정렬 전 - arr = " + Arrays.toString(arr));
    SelectionSort selectionSort = new SelectionSort();
    selectionSort.selectionSort(arr);

    // 정렬 후 - arr = [1, 2, 3, 4]
    System.out.println("정렬 후 - arr = " + Arrays.toString(arr));
  }
}

회고

2주차 스터디를 진행하면서 정해진 진도도 학습하면서, 스터디안에 발표스터디에 참여해서 복습도 하는 과정이었어요. 적어보였던 운영체제의 내용이 생각보다 많아서 정리하는데 은근 시간이 오래 걸리더라구요. 그래도 스터디안의 발표 스터디에 참여하여 정리내용을 발표하고 다른 스터디원들의 발표내용도 듣고 헷갈리는 부분도 토론해서 도움이 많이 되었던 한 주 였던것 같습니다.

스터디 발표 정리 자료 캡쳐

그리고 이번 알고리즘 강의에서는 항상 어렵게 느꼈던 재귀에 대해 조금은 이해한게 너무 좋았습니다.

어떤 문제를 해결하기 위해 문제의 부분 문제를 같은 방식으로 분해하여 해결한다.!! 재귀함수 내에서 자기 자신을 호출할 때 이 함수가 벌써 구현이 되어있다고 가정하고 재귀함수를 구현한다.!! 많이 연습해봐야겠지만 그래도 재귀적으로 생각하는 방법을 느낄 수 있었던 것 같습니다.

마지막 1주가 남았는데, 끝까지 열심히 해서 끝까지 완주해야겠네요. 화이팅