[인프런 워밍업 클럽 스터디 3기] 3주차 발자국

운영체제

가상메모리

메모리 공간이 부족해서 프로그램을 실행하지 못하는 문제를 해결
물리 메모리 크기랑 위치를 생각하지 않고 0번지에서 시작한다고 생각하면 됨

프로세스(사용자) > 가상 메모리 (메모리 관리자) > 물리 메모리

가상 메모리의 크기: 물리 메모리의 크기와 CPU 비트 수에 따라 결정됨

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

프로세스가 메모리 접근을 시도 할 때마다 발생

CPU가 가상 주소 생성 > MMU(Memory Management Unit)가 변환 작업 시작 
> 페이지 테이블 참조 > 물리적 주소로 변환 > 실제 메모리 접근

메모리 부족 상황에서는 Swap 영역으로 페이지를 이동 (Swap Out)

스왑 대상 페이지 선정 > 페이지 테이블 엔트리 수정 > 수정된 페이지라면 디스크 쓰기 > 물리 메모리에서 해제

이런 메모리 할당/비할당을 어떻게 관리하는지는 아래의 정책 별로 나뉨

Segmentation (가변 분할 방식)

메모리를 어떻게 구분하나: 메모리의 역할에 따라 구분(코드, 데이터, 라이브러리, 스택, 힙)
어떻게 바꾸나: 세그멘테이션 테이블을 이용해서 변환
- CPU에서 받은 논리주소와 Bound Address의 크기를 비교
  - 논리주소 < Bound Address > 논리주소 + Base Address = 물리주소
  - 논리주소 > Bound Address > 메모리 침범 에러 발생

Paging (고정 분할 방식)

메모리를 어떻게 구분하나: 구분하지 않음
어떻게 바꾸나: 정해진 크기의 페이지로 나눠둠
- 논리주소 공간 = 페이지 / 물리주소 공간 = 프레임
- 페이지, 오프셋을 통해서 프레임 번호를 알아내서 물리주소로 변환

Paged Segmentation (Segmentation + Paging)

위 2개의 장점을 취한 방식
현대의 운영체제는 페이징과 페이지드 세그멘테이션을 적절히 섞어서 사용

Demand Paging (가져오기)

필요한 모듈만 메모리에 올라가서 실행
조만간 쓸 것 같은 데이터만 메모리에 두고 안 쓰는 거 같은 거는 스왑에 저장해둔다
스왑영역 = 보조저장장치
- 어떻게 안쓰는거 같은거를 구분하나?
  - 접근비트/변경비트/유효비트를 통해 구분
  - 페이지 교체 알고리즘을 이용

Page Fault > 스왑영역에서 메모리로 불러들이기 (= 공간을 만들어줘야 함) 
> 교체정책을 통해 어떤 애를 스왑으로 옮길지 결정

Random
FIFO
Optimum: 앞으로 가장 오랫동안 쓰이지 않을 페이지 선택 > 구현 불가
LRU: 최근 가장 사용 적은 페이지 (실제로 Optimum과 성능 비슷)
2차 기회 페이지 교체 알고리즘: 자주 사용하는 페이지한테 기회를 한 번 더 줌

입출력장치

주변장치: 그래픽카드, HDD, SSD, 키보드, 마우스 등

이 주변장치들은 메인보드에 있는 버스로 연결된다.

레지스터를 이용해서 장치의 상태와 데이터를 보관해서 저장하고, CPU가 이 값을 사용하기도 한다

캐릭터 디바이스

데이터의 전송 단위가 캐릭터(글자)
마우스/키보드/직병렬포트/사운드카드
상대적 크기가 작음

블록 디바이스

데이터의 전송 단위가 블록
하드디스크/SSD/그래픽카드
크기가 큼

파일시스템

파일은 하드디스크/SSD 같은 저장장치에 저장

파일관리자가 파일테이블을 이용해서 파일 정리

운영체제는 파일을 관리하기 위헤 정보를 관리하는 파일 디스크럽터를 갖고 있음

자료구조와 알고리즘

선택정렬

1번째 원소부터 마지막 원소까지 비교 후 가장 작은 값을 1번째 원소로 가져옴

삽입정렬

정렬되지 않은 영역에서 하나씩 빼서 정렬된 영역의 적절한 위치에 원소 삽입

병합정렬

Divide and Conquer(분할 정복) 사용
배열의 원소를 1개가 될 때까지 배열을 반으로 쪼갠 다음 거기서부터 하나씩 정렬을 하며 병합 하는 것
재귀를 사용

퀵정렬

Divide and Conquer(분할 정복) 사용
재귀를 사용
정렬하기 전에 배열에 있는 숫자 중 하나를 피벗으로 설정
각각 왼쪽 오른쪽에서 이동하면서 피벗보다 큰/작은 수를 만나면 멈추고 둘을 스왑

성능만 보면 병합정렬이 더 좋다고 생각할 수 있지만 퀵정렬이 메모리 공간을 덜 차지해서 더 좋다고 평가됨

추가적인 배열을 생성하지 않음 (제자리 정렬)

동적프로그래밍

메모이제이션

피보나치 수열
재귀로 구현했더니 중복계산이 많이 발생
이를 해결하기 위해 계산 결과를 저장해서 여러번 같은 계산을 하지 않도록 하는 기법 == 메모이제이션

타뷸레이션

메모이제이션 = 하향식 / 타뷸레이션 = 상향식
미리 계산에 필요한 모든 값을 계산 후 테이블에 저장

12586269025
fibonacci 함수 실행 시간 : 86590ms
12586269025
enhanced fibonacci 함수 실행 시간 : 0ms
12586269025
tabulation Fibonacci fibonacci 함수 실행 시간 : 1ms

재귀가 더 직관적이라면 메모이제이션을 사용하는 것이 유리
아니라면 타뷸레이션 사용

회고

👏 칭찬하고 싶은 점

일이 정말 더 바빴는데 한번도 강의를 밀리지 않았다

😅 아쉬웠던 점

너무 일이 바빠서 강의 들면서 졸거나 해서 대충 넘어간 부분이 있는거 같다..