학습기간

1주차 2024-10-14(월) ~ 2024-10-18(금)

강의 수강

• 학습내용 요약

• 알고리즘

• 섹션3-알고리즘

  • 삽입 정렬(Insertion Sort)

    <aside>

    • 선택정렬과 마찬가지로 배열을 두 영역으로 나누어 정렬을 진행함 (정렬된 영역, 정렬되지 않은 영역)

    • 정렬되지않은 영역에서 데이터를 하나씩 꺼내서 정렬영역의 적절한 위치에 삽입하여 정렬하는 것

       

    • 삽입 정렬의 성능도 버블,선택정렬과 같이 O(n^2)이다.

  • 병합 정렬(Merge Sort)

    <aside>

    • 반으로 나누고 또 반으로 나눠서 각 원소로 정렬 한 후 한단계 씩 병합해가면서 정렬

    • 재귀함수 호출 모양과 아주 비슷한 모양을 하고 있음

       

    • 분할된 배열을 병합할때는 N개의 데이터를 n번 비교하므로 n과 logn을 곱해서 O(nlogn)의 성능이 나옴

    • 장점 : 성능이 지금까지 배운 정렬보다 좋음

    • 단점 : 재귀적인 기법을 이용해 이해와 구현이 어려움

  • 퀵 정렬(Quick Sort)

    <aside>

    • 퀵정렬은 이전에 알아본 병합정렬과 같이 분할 정복 알고리즘에 속함

    • 그래서 재귀를 사용함

    • 퀵정렬은 정렬전 배열에 있는 수자중 하나를 피벗 으로 설정해줌

    • 피벗을 선택하는 방법은 여러가지 있으나, 여기서는 이해하기 쉽게 배열의 왼쪽에 있는 것으로 선택함

    • 퀵정렬은 이렇게 한번 진행될 때 마다 피벗이 정렬되고 정렬된 배열을 좌우로 나눠 같은 방식으로 재귀호출해 모든 배열을 정렬함

    • 성능

       

      • 피벗이 배열을 반으로 가르지않고 한쪽에 치우쳤을 경우 O(n^2)의 성능임

      • 대부분 피벗을 중간값으로 설정하므로 배열을 매번 반으로 가를 수 있어서 평균적인 성능은 ‘새타(nlogn)’의 성능을 가짐

      • 성능만 보면 병합정렬이 더 좋다고 볼 수 있는데, 실제로 병합정렬과 비교하면 퀵정렬이 더 적은비교와 더 적은메모리 공간을 차지하기 때문에 더 좋은 알고리즘으로 평가됨

        • 퀵정렬 : 새타(nlogn), O(n^2)

        • 병합정렬 : O(nlogn)

    • 장점 : 성능이 지금까지 배운 정렬보다 좋음

    • 단점 : 재귀적인 기법을 이용해 이해와 구현이 어려움 </aside>

  • 동적 프로그래밍-메모이제이션(memoization)

    <aside>

    • 재귀를 이용해 큰문제를 작은문제로 분할해서 해결했음 ⇒ 분할정복

      • 단점 : 재귀를 사용하면 함수가 호출되어 콜스택의 영역을 차지하는 단점 외에도 성능에 크게 영향을 미치는 단점이 있음

    • 피보나치 수열(하향식 문제)

      • 무한대 수열을 만듦….

      • 구현 시 성능이 좋지 못함

      • return 값인 fibonacci(n-2)가 재귀적으로 호출할 때 반복계산이 되는 경우가 있고, 중복호출도 있음, 시간이 낭비됨

        ⇒ 결과값을 저장해 함수호출수를 줄이고 성능이 향상됨

      • 메모이제이션으로 성능향상해보기

        • 계산하려는 데이터가 있는지 검색

        • 없다면 함수를 호출해 그결과를 저장

          ⇒ 해시테이블(데이터 검색,삽입이 빠른 장점이 있음)을 이용

          ⇒ 해시테이블의 키에 계산하려는 값을, 밸류에 계산결과를 저장함

    • 메모이제이션

      • 계산결과를 저장해서 여러번 계산하지 않도록 하는 기법

      • 장점 : 재귀적인 기법으로 어려운 문제를 단순히 풀 수 있고, 계산결과를 해시테이블에 저장하기 때문에 중복계산을 하지않아 속도가 빠름, 재귀가 더 직관적이라면 메모이제이션이 유리함

      • 단점 : 함수를 여러번 호출하는 재귀를 사용하기 때문에 함수를 하나 호출하는것보다 오버헤드가 더 들고, 함수호출로 메모리 공간에 스택을 차지하고 메모이제이션을 위한 해시테이블 공간까지 차지하기 때문에 메모리를 더 많이 사용함 </aside>

  • 동적 프로그래밍-타뷸레이션

    <aside>

    • 상향식 계산방식

    • 계산에 필요한 모든 값을 전부 계산후 테이블에 저장해둠

    • 재귀가 직관적이지 않을때는 타뷸레이션을 이용해 메모리도 절약하고 속도도 빠르게 해결할 수 있음 </aside>

• 운영체제

• 섹션8-가상메모리

  • 가상메모리 개요

    <aside>

    • 운영체제나 프로세스보다 큰 프로그램이 실행되지 못할 때, 가상메모리를 이용해 실행 할 수 있음

    • 프로세스(사용자)는 메모리 관리자(가상메모리)를 통해서 메모리(메인메모리)에 접근함

    • 프로세스 입장에서는 물리메모리에 직접 접근할일이 없고, 메모리 관리자에게 요청만 하면됨

    • 메모리 관리자는 프로세스의 요청이 있으면 그에맞는 물리 메모리로 연결시켜줌

    • 가상메모리의 크기는 이론적으론 무한대지만, 실제론 메모리의 크기와 CPU의 비트수로 결정됨

      ex) 만약 32비트의 경우, 표현할 수 있는 주소값은 2^32승으로 대략 4GB정도 되고, 가상 메모리의 크기도 똑같이 4GB임

    • 가상메모리 할당

      • 운영체제가 사용하는 0번지를 제외

      • 가상메모리 시스템에서는 운영체제 영역을 제외한 나머지영역을 일정한 크기로 나누어서 프로세스에게 할당함

      • 메모리 분할방식과 동일하게 가변분할방식(세그멘테이션)과 고정분할방식(페이징)으로 나뉨

      • 각각 단점을 보완한 세그멘테이션-페이징 혼용기법을 사용함

    • 가상메모리시스템-가상주소

      • 가상주소는 메모리나 스왑영역 중 한 곳에 위치함

      • 메모리 관리자는 가상주소와 물리주소를 일대일 매핑 테이블로 관리함

       

    • 동적 주소 변환(DAT, Dynamic Address Translation)

      • 메모리 관리자는 물리메모리+스왑영역을 합쳐서 프로세스가 사용하는 가상주소를 물리주소로 변환함

      • 동적주소변환을 거치면 프로세스는 마음대로 사용자 데이터를 물리 메모리에 배치할 수 있음 </aside>

  • 세그멘테이션(배치정책)

    <aside>

    • 세그멘테이션에서 프로그램은 함수나 모듈등으로 세그먼트를 구성함

      • 데이터, 코드, 힙, 스택, 라이브러리 등

         

    • 장점 : 메모리를 가변적으로 분할 할 수 있고,각 영역을 모듈로 처리할 수 있기 때문에 공유와 각 영역에 대한 메모리 접근보호가 편리함

    • 단점 : 가변분할 방식의 단점인 외부단편화가 발생함

    • 논리주소

      • 사용자, 프로세스, CPU가 바라보는 주소

      • 메모리 관리자(MMU)가 중간에서 세그멘테이션 테이블에 저장된 Base Address와 Bound Address 정보를 이용해 물리주소로 변환 해줌

      • CPU에서 논리주소가 전달되면, 메모리관리자는 이 논리주소가 몇번 세그먼트인지 알아내서 메모리관리자 내의 segment table base register에서 물리 매모리내에 있는 세그멘테이션 테이블을 찾고 세그먼트 번호를 인덱스로, base address와 bound address를 찾음

        cf) 운영체제는 컨텍스트 스위칭을 할 때 마다 메모리 관리자 내에 있는 segment table base register를 해당 프로세스의 것으로 값을 바꿔줘야 하기 때문에 컨텍스트 스위칭은 굉장히 무거운 동작임

         

    • 논리주소 → 물리주소 변환 예시

      • CPU에서 세그먼트 1번이 0x632번지로 접근한다고 가정해보자

      • 메모리 관리자는 CPU의 요청을 받고 세그먼트가 1번인 것을 알아내고, 메모리 관리자 내에 있는 segment table base register를 이용해서 세그멘테이션 테이블을 찾아냄

      • 세그멘테이션 테이블을 찾은다음, 세그먼트 1번이 위치한 1번 인덱스를 참조하고, 논리주소 632와 bound address 1000을 비교해보면 논리주소가 더 작음

        ⇒ 더 작은 논리주소 632와 base address 5200을 더해 물리주소 5832가 됨

    </aside>

  • 페이징(배치정책)

    <aside>

    • 메모리를 할당할 때 정해진 크기의 페이지로 나눔

    • 모든 페이지는 크기가 같기때문에 관리가 쉬워지고, 외부단편화 현상이 발생하지 않음

    • 물리주소 공간도 논리주소공간(페이지)과 같이 동일하게 나뉘는데 이걸 프레임 이라고 부름

    • 페이징의 주소변환 방법

      • 세그멘테이션과 마찬가지로 메모리관리자는 테이블을 갖고 있고, 이를 페이지 테이블 이라고 부름

      • CPU에서 논리주소를 전달해주면, 메모리 관리자는 이 논리주소가 몇번 페이지 인지, 오프셋은 얼마인지 알아냄

      • 메모리 관리자 내 page table base register(PTBR)를 이용해서 물리 메모리에 있는 페이지 테이블을 찾고, 페이지 번호를 인덱스로 프레임 번호를 알아내고 오프셋을 이용해 물리주소로 변환함

    • 오프셋의 계산

      • 페이지 테이블에 invalid로 표시되어있으면 스왑영역, 즉 하드디스크에 저장되어 있다는 의미임

    • 세그멘테이션과 페이징의 차이

      • 페이지의 크기이다.

      • 세그멘테이션은 프로세스마다 크기가 달라 bound address를 가지고 있지만,

        페이징은 모든 페이지의 크기가 동일해서 크기를 표현하는 bound address는 필요하지 않음

      • 세그멘테이션 (외부단편화 발생), 페이징 (내부단편화 발생-정해진 크기의 페이징보다 프로세스의 정보가 작으면 그만큼 공간이 낭비됨)

      • 페이징은 페이지의 크기가 고정되어있기때문에 공유하거나 권한을 부여하는게 어려움

      • 페이징에서 가장 신경써야하는것은 페이지 테이블의 크기임

        • 각 프로세스마다 페이지 테이블을 가지고 있는데, 프로세스가 많아질수록 테이블도 많아지기 대문에 프로세스가 실제로 사용할 수 있는 메모리 영역이 줄어듦

        • 실제로 메모리 관리자가 참조하는 페이지 테이블도, 물리메모리의 운영체제 영역에 저장되어 있기 때문에 페이지 테이블의 크기가 너무 크면 사용자 영역이 부족하게 됨 </aside>

  • 페이지드 세그멘테이션(배치정책)

    <aside>

    • 세그멘테이션과 페이징의 장점을 취한 방식

    • 메모리 접근권한은 메모리의 특정 번지에 부여된 권한으로 읽기(Read), 쓰기(Write), 실행(Execute) 3가지로 나뉨

      ex) 0x0 ~ 0x1000까지는 읽기 권한, 0x1000~0x2000까지는 읽기,쓰기 권한 설정 .ᐟ

    • 프로세스의 각 영역의 메모리 권한 알아보기

      • CODE : 프로그램 그 자체이므로 수정되면 안됨 → 읽기/실행 권한

      • DATA : 일반변수, 전역변수, 상수로 선언한 변수 저장 → 읽기 /(쓰기)권한

      • HEAP : 읽기/쓰기 권한

      • STACK : 읽기/쓰기 권한

    • 메모리 접근 권한 검사

      • 가상주소→물리주소 변환 될 때마다 일어남

      • 권한 위반 시 에러발생 및 종료

    • 페이지드 세그멘테이션

      • 세그멘테이션 테이블과 페이지 테이블이 혼합된 것

      • 세그멘테이션 테이블에는 권한 비트를 추가하고, base address는 페이지 넘버로 바뀌고, bound address는 이 세그멘트의 페이지 개수로 바뀜(이름만 달라졌을 뿐 본질은 달라지지 않음)

      • 단점 : 물리메모리에 접근하기 위해서 메모리에 접근을 2번 해야됨(1. 세그멘테이션 테이블 참조, 2.페이지 테이블 참조)

        ⇒ 오늘날에는 이러한 단점때문에 페이징과 페이지드 세그먼테이션 기법을 적절히 섞어서 사용함

    </aside>

  • 디맨드 페이징(가져오기 정책)

     

    • 조만간 필요할 것 같은 데이터를 메모리로 가져오고, 쓰이지 않을 것 같은 데이터는 스왑영역으로 이동시키는 정책임

    • 스왑영역으로 데이터를 이동시키는 것을 최소화 시켜야 함(CPU의 수백개가 넘는 사이클이 걸리기 때문에 성능이 안좋아짐)

      • 페이지 테이블을 이루고 있는 한 행을 페이지 테이블 엔트리(PTE) 라고 함

    • 페이지 테이블 엔트리(PTE)

      • 접근비트

        • 페이지가 메모리에 올라온 후 데이터에 접근이 있었는지 알려줌

        • 메모리에 읽기나 실행 작업을 했다면 1 로 바뀜

      • 변경비트

        • 페이지가 메모리에 올라온 후 데이터에 변경이 있었는지 알려줌

        • 메모리에 쓰기 작업을 했다면 1 로 바뀜

      • 유효비트

        • 페이지가 물리메모리에 있는지 알려줌

        • 유효비트가 1이라면 스왑영역에 있고, 0이라면 물리메모리에 있음

      • 읽기/쓰기/실행 비트

        • 해당 메모리에 접근권한이 있는지 검사하는 권한비트

    •  

  • 페이지 교체정책

    <aside>

    • 프로세스는 데이터 접근을 위해 메모리를 참조하는데, 해당 데이터가 메모리에 없으면 Page Fault가 발생함

    • Page Fault가 발생하면 해당 페이지를 스왑영역에서 메모리로 불러들여야하는데 메모리가 꽉차서 공간이 없다면 메모리에 있는 페이지 중 하나를 선택헤서 스왑영역으로 옮겨야 함

    • 메모리에 있는 페이지를 스왑영역으로 옮길때 어떤 페이지를 선택할지 결정하는 정책을 페이지 교체정책이라고 함

    • 페이지 교체정책의 종류

      • 무작위 선택 방법

        • 무작위로 선택해서 교체하는 이 방법은 지역성을 고려하지 않기때문에 자주사용되는 페이지가 선택될 수 있어 성능이 별로 좋지 않음

        • 그래서 거의 사용되지 않음

      • FIFO(First In First Out, 메모리에 들어온지 가장오래된 페이지를 선택하는 방법)

        • 페이지 1이 먼저 들어왔으면 먼저 교체함

        • 단점 : 자주쓰는 페이지가 먼제 교체되는 단점이 있음

        • 구현이 간단하고 성능도 꽤 괜찮아서 조금 변형해서 많이 쓰임

      • Optimum(앞으로 가장 오랫동안 쓰이지 않을 페이지를 선택하는 방법)

        • 사실상 구현이 불가능한 이론적인 선택 방법

          (앞으로 누가 가장 사용되지않을지 모르니까)

        • 다른 알고리즘과 성능비교를 할 때 참조용으로 쓰임

      • LRU(Least Recently Used, 최근에 가장 사용이 적은 페이지 선택 방법)

        • 지역성 이론의 시간의 지역성에 따르면 최근 사용한 데이터가 앞으로도 사용할 확률이 높기 때문에, 최근에 가장 사용을 적게한 페이지가 앞으로도 사용될 확률이 적다는 결론이 나옴

        • 실제로도 Optimum 알고리즘에 근접한 성능을 보임

        • 하지만 프로그램이 지역성을 띄지 않을 땐 성능이 떨어짐

       

    • LRU의 유사 구현 - 클락 알고리즘(Clock Algorithm)

      • 접근 비트 하나만 이용함

      • 일정 시간 간격마다 모든 페이지의 접근비트를 0으로 초기화함

      • 만약 페이지가 참조되었다면 접근비트는 1로 설정 됨

      • 일정 시간 간격마다 페이지가 참조되었는지 여부를 확인 할 수 있음

    • 향상된 클락 알고리즘(Enhanced Clock Algorithm)

      • 이 알고리즘은 접근비트만 이용하는 것이 아니라 변경비트까지 봄

      • 스왑영역으로 보내지는 것 중 순위가 높은거슨 접근비트가 0이고, 변경비트도 0인 페이지임

      • 그다음으로 접근비트0, 변경비트1 → 접근비트1, 변경비트0 → 접근비트1, 변경비트 1 인페이지 순으로 교체됨

    • LRU만 사용되고 FIFO는 사용되지 않는 것 처럼 보이나, 부득이하게 FIFO를 사용할 때가 있음

      • 하드웨어적으로 접근비트를 지원하지 않는 시스템에선 FIFO를 이용함

        ⇒ 어쩔수없이 FIFO의 성능을 높일 수 있는 방법 고안 (2차 기회 페이지 교체 알고리즘)

      • 2차 기회 페이지 교체 알고리즘

        • FIFO방식에서 자주 사용하는 페이지에게 또 한번의 기회를 주는 것

        • FIFO방식과 동일하게 동작하지만, 만약 Page Fault 없이 페이지 접근에 성공했다면 해당 페이지를 큐의 맨 뒤로 이동시켜 수명을 연장시켜주는 방식

        • 성능 : LRU > 2차 기회 페이지 교체 알고리즘 > FIFO 순 </aside>

           

  • 스레싱과 워킹셋

    <aside>

    • CPU 스케쥴링의 목표 : CPU 사용률을 높임

      • 방법 : 동시에 실행하는 프로세스의 수 (멀티프로그래밍 정도, Degree of Multiprogramming)를 올림

        ⇒ 어떤 프로세스가 I/O 작업으로 CPU를 사용할 수 없을 때, 다른 프로세스로 컨텍스트 스위칭을 해서 CPU 사용율을 높일 수 있음

        ⇒ CPU 사용율을 높이기 위해 멀티프로그래밍 정도를 늘렸으면, 이 프로세스들이 필요로 하는 공간이 있기 때문에 물리메모리에 프레임을 할당해야함

        ⇒ 하지만, 물리메모리에 할계가 있기때문에 모든 프로세스의 모든 프레임을 물리메모리에 올릴 수 없고, 일부는 스왑영역에 저장됨

         

      • 스레싱

        • 발생 원인 : 근본적인 원인은 물리메모리의 크기가 부족한 것

           

        • 해결방법 : 프로세스가 실행되면 일정량의 페이지를 할당하고, Page Fault가 발생하면 더 많은 페이지를 할당함

           

           

      • 워킹셋

        • 현재 메모리에 올라온 페이지는 다시 사용할 확률이 높기 때문에 하나의 세트로 묶어서 메모리에 올림

           

        • 프로세스가 준비상태에서 실행상태가되는 컨텍스트 스위칭을 할 때 사용됨

     

    • 회고

      • 처음시작할땐 프로그래밍 언어와 SQL정도 공부한 상태라 자료구조, 알고리즘, 운영체제 모두 용어가 겁나고 두려웠었는데 감자님 인강을 통해 그림으로 배우고 많은 예시, 직접 구현등을 해보니까 자신감이 생긴 것 같다.

      • 독학하다보니 이렇게 스케쥴을 가지고 공부해본적이 드문데 인강을 뽀개는 법을 배운것 같고, 정처기 실기에서도 LRU 페이지 교체가 나와서 신기했다.. 엮여 있는 것 같아서 앞으로의 내 공부에 많은 영향이 있을 것 같다. 기대된다!