학습 했던 내용 요약

• 자료구조 및 알고리즘

   

   

  •  버블정렬

    • 장점 : 이해와 구현이 간단하다.

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

    • 시간 복잡도 : O(n²)

  • 선택 정렬

    • 장점 : 이해와 구현이 간단하다.

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

    • 시간 복잡도 : O(n²)

  • 삽입 정렬

    • 장점 : 이해와 구현이 간단하다.

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

    • 시간 복잡도 : O(n²)

  • 병합 정렬

    • 장점 : O(nlog n) 성능으로 버블, 선택 , 삽입 정렬보다 성능이 훨씬 좋다.

    • 단점 : 재귀적인 기법으로 이해하기 어렵고, 구현하기 어렵다.

    • 시간 복잡도 : O(n logn)

  • 퀵 정렬

    • 장점 : 성능이 좋고, 병합 정렬보다도 적은 메모리 공간을 차지해 더 좋은 알고리즘으로 평가 받는다.

    • 단점 : 재귀적인 기법으로 이해하기 어렵고, 구현하기 어렵다.

    • 시간복잡도 : O(n logn)

  • 메모이제이션

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

    • 계산 결과를 해시 테이블에 저장하고 재사용해 속도가 빠르다 .

    • 하향식 계산 방식으로 문제를 해결한다.

  • 타뷸레이션

    • 계산에 필요한 모든 값을 전부 계산 후 테이블에 저장하는 기법

    • 상향식 계산 방식으로 문제를 해결한다.

• 운영체제

  • 가상메모리

    • 컴퓨터의 물리적 메모리의 크기를 확장하기 위해 사용되는 기술

       

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

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

  • 가변분할 방식을 이용하는 세그멘테이션 기법

    • 메모리 관리자내에 있는 Segment Table Base Register를 이용해 세그멘테이션 테이블 찾아내고, 이를 이용해 논리 주소를 물리 주소로 변환한다.

    • 메모리를 가변적으로 분할 할 수 있지만, 가변 분할의 단점인 외부 단편화가 발생한다 .

  • 고정분할 방식을 이용한 페이징 기법

    • 메모리를 할당 할 때 정해진 크기의 페이지의 나누는 기법으로

    • 메모리 관리자 내에 Page Table Base Register를 이용해서 물리 메모리에 있는 페이지 테이블을 찾고 , 이를 이용해 논리 주소를 물리 주소로 변환한다.

    • 페이징은 외부 단편화가 발생하지 않는 대신, 내부 단편화가 발생한다.

  • 페이지드 세그멘테이션

    • 세그멘테이션과 페이징을 혼합해 장점을 취한 방식으로

    • 물리 메모리에 접근하기 위해서 메모리에 접근을 두 번 해야 한다는 단점이 있다.

      • 1. 세그멘테이션 테이블을 참조할 때

        2. 페이지 테이블을 참조할 때

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

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

  • 페이지 테이블 엔트리 PTE

    • 페이지 테이블을 이루고 있는 한 행

    • 페이지 테이블 엔트리는 프레임 넘버로 구성되어 있는데, 실제로는 접근 비트, 변경 비트, 유효 비트, 읽기-쓰기-실행 비트 등 더 많은 비트 들이 있다.

  • Page Fault

     

    • Page Fault는 프로세스가 가상 메모리에 있는 페이지에 접근하려고 할 때, MMU가 페이지 테이블을 참조하여 해당 페이지가 물리 메모리에 존재하는지 확인하는 과정에서, 물리 메모리에 해당 페이지가 없는 경우 발생하는 인터럽트다.

  • 페이지 교체 정책

    • 페이지 교체 정책은 메모리에 빈 공간이 없을 때, 어떤 페이지를 선택해서 스왑 영역으로 보낼지(스왑 아웃)를 결정하는 운영체제의 정책이다.

    • 스왑 인은 스왑 영역에서 물리 메모리로 페이지를 가져오는 것이고,

    • 스왑 아웃은 물리 메모리에서 스왑 영역으로 페이지를 보내는 것이다.

    • 이러한 스왑 인과 스왑 아웃의 적절성은 운영체제가 판단한다.

      • Random 무작위로 선택하는 방법

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

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

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

      • Clock 알고리즘 : 접근비트 하나만 이용하고, 일정 시간 간격마다 모든 페이지의 접근비트를 0으로 초기화 한다.

      • Enhanced Clock Algorithm : 변경 비트까지 보는 향상된 Clock 알고리즘

      • 2차 기회 페이지 교체 알고리즘 : FIFO 방식에서 자주 사용되는 페이지에게는 또 한 번의 기회를 주는 것.

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

  • 스레싱

    • CPU 사용률을 높이려 했지만 오히려 더 떨어지는 상황이 나오는 것

  • 워킹셋

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

    • 워킹셋은 프로세스가 준비 상태에서 실행 상태가 되는 컨텍스트 스위칭을 할 때 사용된다.

회고

• 일주일 동안 스스로 칭찬하고 싶은 점

  • 일주일치 진도대로 인강을 다 수강하고, 미션과 발자국도 기한내에 진행한 점.

     

• 아쉬웠던 점

  • 며칠은 복습이 잘 되었고, 며칠은 복습은 잘 하지 못한 점 

• 보완하고 싶은 점

   

  • 이해가 어려웠던 부분들은 더 찾아보면서 이해해보기

     

• 다음주 학습 목표

  • 한번 배웠다고 끝내는 것이 아니라 계속해서 복습을 진행하기

출처 : 그림으로 쉽게 배우는 운영체제 - 감자 , 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)- 감자