2주차 학습 내용

운영체제

• CPU 스케줄링 알고리즘 - SJF(Shortest Job First)

  • Burst Time이 짧은 프로세스를 먼저 실행하는 알고리즘

  • 이론적으론 FIFO보다 성능이 좋지만, 구현에 문제가 발생할 수 있음

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

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

• CPU 스케줄링 알고리즘 - Round Robin

  • 한 프로세스에게 일정 시간만큼 CPU를 할당하고, 할당 시간이 지나면 강제로 다른 프로세스에게 일정 시만큼 CPU를 할당하는 알고리즘

  • 프로세스에게 할당하는 일정 시간 => 타임 슬라이스, 타임 퀀텀

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

    • 타임 슬라이스가 큰 경우(무한대라고 가정)

      • 먼저 들어온 프로세스의 작업이 종료될 때까지 실행 => FIFO 알고리즘이 됨

    • 타임 슬라이스가 작은 경우(1ms라고 가정)

      • 컨텍스트 스위칭이 너무 자주 일어남

      • 프로세스 처리량보다 컨텍스트 스위칭을 처리하는 양이 더 커짐 => 오버헤드가 너무 큼

    • 최적의 타임 슬라이스 : 사용자가 느끼기에 여러 프로세스가 버벅거리지 않고, 동시에 실행되는 것처럼 느껴지면서 오버헤드가 너무 크지 않는 값

      • Windows는 20ms, Unix는 100ms 정도

         

• CPU 스케줄링 알고리즘 - MLFQ(Multi Level Feedback Queue)

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

  • 기본적으로 CPU 사용률과 I/O 사용률이 좋게 나오는 작은 크기의 타임 슬라이스를 선택하되, CPU Bound Process들에게는 타임 슬라이스를 크게 줌

    • CPU를 사용하는 프로세스가 스스로 CPU를 반납하면 I/O Bound Process일 확률이 높고, 실행 도중 CPU 스케줄러에 의해 강제로 CPU를 뺏기는 상황이 발생하면 CPU Bound Process일 확률이 높음

  • 우선순위 큐를 여러 개 준비하여, 우선순위가 높으면 타임 슬라이스 크기가 작고, 우선순위가 낮으면 타임 슬라이스 크기가 커짐

    • 처음엔 타임 슬라이스가 작게 할당되어있다가, CPU가 강제로 뺏기면 좀 더 큰 타임 슬라이스를 할당받게 됨

• 프로세스 간 통신

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

  • 한 컴퓨터 내에서 프로세스 간 통신하는 방법

    • 파일을 이용하는 방법

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

    • 파이프를 이용하는 방법

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

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

    • 데이터 영역의 전역 변수나 힙을 이용해 통신

  • 네트워크를 이용한 방법

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

  • 공유자원과 임계구역

    • 공유자원

      • 프로세스가 통신할 때 공동으로 이용하는 변수, 파일 등

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

    • 임계 구역(Critical Section)

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

      • 경쟁 조건(Race Condition) : 공유 자원을 서로 사용하기 위해 경쟁하는 것

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

        • 상호 배제(Mutual Exclusion) 메커니즘 필요

          • 임계 구역엔 주어진 시간에 항상 하나의 프로세스만 접근할 수 있어야 한다

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

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

• 세마포어

  • 프로세스들은 대기 큐에서 공유 자원을 사용하기 위해 대기하고, 운영 체제가 관리하는 열쇠를 가진 프로세스만 공유 자원을 사용할 수 있음 => 이때 이 열쇠를 세마포어(정수형 변수)라고 함

  • 공유 자원의 개수에 따라 세마포어의 값 또한 달라짐

  • wait() : 열쇠를 요청해서 열쇠를 받고 문을 잠금. 열쇠가 없으면 기다림

  • signal() : 방에서 나와 문지키는 직원에게 열쇠 반납

  • 단점 : wait() 함수, signal() 함수의 순서를 이상하게 호출해서 세마포어를 잘 못 사용할 가능성이 있음 => 모니터로 해결!

• 모니터

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

  • Java에서 synchronized라는 키워드가 붙으면, 이 키워드가 붙은 함수들은 동시에 여러 프로세스에서 실행시킬 수 없음 = 상호배제가 완벽하게 이루어짐

  • 만약 프로세스 A에서 increase() 함수를 실행하면, 프로세스 B는 synchronized 키워드가 붙은 decrease() 함수도 실행할 수 없음

• 교착상태(데드락)

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

  • 교착상태의 필요 조건 (한가지라도 충족하지 않으면 교착상태 발생 X)

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

       

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

       

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

       

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

       

  • 교착 상태의 네가지 조건을 이용해서 교착상태를 예방하는 방법을 연구해보고자 했으나, 제약이 많고 비효율적이라 해결하는 방법을 연구함

• 교착상태 회피(Deadlock avoidance)

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

  • 전체 자원의 수와 할당된 자원의 수를 기준으로 안정 상태, 불안정 상태로 나눔

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

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

  • 운영체제에서 은행원 알고리즘 구현하기

    • 안정상태

      • 은행원 알고리즘은 각 프로세스가 현재 요구할 수 있는 요청이 예상되는 자원을 구함

         

         

        
        

      • P1에서 4개를 요청하면 현재 사용 가능 자원이 2개뿐이므로 거절

      • P2에서 2개를 요청하면 2개 모두 P2에 할당, P2는 작업을 마치고 6개를 반납

      • 사용 가능한 자원이 6개가 되어, P1, P3 모두에 필요한 만큼 할당 가능

    • 불안정 상태

      • 사용 가능한 자원이 1개

        

      • 현재 사용 가능한 자원 개수로는 P1, P2, P3가 요청할 수 있는 최대 요청인 2개를 충족하지 못함 => 불안정 상태

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

• 교착상태의 검출 방식

  • 가벼운 교착 상태 검출

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

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

  • 무거운 교착 상태 검출

    • 자원 할당 그래프 이용

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

    • 그래프에 순환 구조가 생긴다면 교착 상태가 생긴 그래프

    • 교착 상태를 검출하면 교착 상태를 일으킨 프로세스를 강제 종료시키고, 다시 실행시킬 때 체크포인트로 롤백

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

    • 장점 : 가벼운 교착상태에서 발생하는 억울하게 종료되는 프로세스는 발생하지 않음

• 메모리 종류

  • 레지스터

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

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

    • CPU를 구분할 때 말하는 32bit, 64bit는 레지스터의 크기를 말함

    • CPU는 계산을 할 때, 메인메모리에 있는 값을 레지스터로 가져와 계산하고, 결과는 메인메모리에 저장

  • 캐시

    • 휘발성 메모리

    • 레지스터는 굉장히 빠르고, 메인메모리는 너무 느림 => 메인 메모리에 있는 값을 레지스터로 옮기려면 한참 걸리므로 필요할 것 같은 데이터를 미리 가져와서 캐시에 저장

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

  • 메인메모리(RAM)

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

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

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

       

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

    • 사무용 프로그램, 게임, 작업한 파일 등을 저장할 필요가 있는데, 비싸고, 휘발성인 메모리에 저장할 순 없음

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

       

• 메인메모리

  • 오늘날의 컴퓨터 구조인 폰 노이만 구조는 모든 프로그램을 메모리에 올려 실행시킴

  • 운영체제는 메모리를 관리하기 위해 1바이트 크기로 구역을 나누고 숫자를 매김 => 이 숫자는 "주소"라고 부름

  • 물리 주소와 논리 주소

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

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

    • 사용자는 물리 주소를 몰라도 논리 주소로 물리 주소에 접근할 수 있음

  • 경계 레지스터

    • 메모리에는 수많은 프로세스가 올라오는데, 운영체제를 위한 공간은 따로 마련해둠. 이때,

      하드웨어적으로 운영체제 공간과 사용자 공간을 나누는 경계 레지스터를 만듦

• 메모리 할당 방식

  • 유니 프로그래밍

    • 메모리 오버레이

      • 유니프로그램 방식에서 메모리보다 더 큰 프로그램을 실행시키는 방법

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

  • 멀티프로그래밍

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

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

      • 장점 : 내부 단편화 없음

      • 단점 : 외부 단편화 발생

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

      • 프로세스의 크기와 상관 없이 메모리를 정해진 크기로 나누는 방식

         

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

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

    • 버디 시스템

      • 오늘날 가변 분할 방식과 고정 분할 방식을 혼합하여 단점을 줄인 방식

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

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

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

알고리즘

• 재귀(recursion)

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

  • 재귀 함수

    • 탈출 조건이 없으면 콜스택이라는 메모리 공간이 가득차서 자동으로 종료

    • 언제 종료될지 예측할 수 있게 하기 위해 탈출 조건, 즉 기저 조건이 반드시 필

  • 콜스택

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

    • FILO(먼저 들어온 데이터가 나중에 나감) 특성을 가짐

    • 함수를 호출하면 함수는 콜스택에 올라가고, 종료되면 콜스택에서 제거됨

• 버블 정렬(Bubble Sort)

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

  • 데이터를 옆 데이터와 비교하면서 자리를 바꾸는게 버블이 일어나는 것 같아서 붙여진 이름

  • 시간복잡도 : O(n^2)

  • 장점 : 이해와 구현이 쉽다

  • 단점 : 성능이 좋지 않다.

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

• 선택 정렬 (Sellection Sort)

  • 배열의 정렬되지 않은 영역을 순회하며 가장 작은 값을 탐색 후 교체하는 방법

  • 시간복잡도 : O(n^2)

  • 장점 : 이해와 구현이 쉽다

  • 단점 : 성능이 좋지 않다

  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[i] = arr[minValueIndex];
          arr[minValueIndex] = temp;
      }
  }

회고

칭찬하고 싶은 점

이번 주부터 알고리즘 스터디를 시작하고, 또 매일 출근도 하면서 오늘 있었던 코딩테스트까지 일주일 간 이것저것 할일이 많았는데 포기하지 않고 이번주차 진도를 따라잡았다. CS 중에서도 운영체제는 개념이 잘 잡혀있지 않았는데, 공부를 하면서 운영체제에서 가장 중요한 개념인 프로세스와 CPU 스케줄링에 대해 어느정도 개념을 이해할 수 있는 일주일이었다.

아쉬웠던 점

이번주에도 역시나 매일매일 정해진 분량을 학습하기보다는 시간이 남는 타임에 몰아들은 경우가 더 많았던 것 같다.

보완해야할 점

남은 일주일도 바쁠 예정이기 때문에..현실적으로 매일매일 정해진 분량을 지켜서 노트까지 정리해가며 학습하기엔 벅차더라도, 지난 주처럼 너무 한번에 몰아서 하지 말고 출퇴근 시간을 이용해서 강의를 가볍게 보고 추후에 다시 복습하는 개념으로 노트를 정리하면 좋을 것 같다.