[인프런 워밍업클럽 CS 2기] 3주차 발자국👣
3주차 학습내용
운영체제
가상메모리
가상 메모리를 사용하면 프로세스는 운영체제 영역이 어디 있는지, 물리 메모리의 크기가 얼마나 큰지 몰라도 됨
프로그래머는 물리 메모리의 크기와 프로세스가 메모리의 어느 위치에 올라가는지 신경 쓰지 않고 0x0번지에서 시작된다고 생각하고 프로그래밍
프로세스는 메모리 관리자를 통해 메모리에 접근 -> 물리 메모리에 직접 접근할 일이 없고 메모리 관리자(MMU)에게 요청만 하면 됨
메모리 관리자는 물리 메모리와 스왑 영역을 합쳐 프로세스가 사용하는 가상 주소를 물리 주소로 변환 => 동적 주소 변환(Dynamic Address Translation)
물리 메모리 내용의 일부를 하드 디스크의 스왑 영역으로 옮긴 뒤 처리가 필요할 때 물리 메모리로 가져와 실행
세그멘테이션(배치정책)
가변분할 방식으로, 프로세스의 메모리를 다양한 크기의 논리적 단위인 세그먼트로 나누어 관리하는 메모리 관리 전략
Base Address와 Bound Address정보가 담긴 세그멘테이션 테이블을 가지고 있어 이를 통해 물리 메모리 주소를 계산
Base Address: 세그먼트가 물리 메모리 내에서 시작하는 위치
Bound Address: 세그먼트 크기
논리 주소를 MMU에 전달 => MMU는 이 논리주소가 몇 번 세그먼트 인지 알아냄 => MMU 내의 Segment Table Base Register를 이용해 물리 메모리 내에 있는 세그먼트 테이블을 찾음 => 세그먼트 테이블 내 세그먼트 번호를 인덱스로 Base Address와 Bound Address를 찾음
MMU는 논리주소와 Bound Address의 크기를 비교
논리주소 < Bound Address : 물리주소 = 논리주소 + Base Address
논리주소 > Bound Address : 메모리 침범으로 간주하고 에러 발생
장점
메모리를 가변적으로 분할 가능
코드, 데이터, 스택, 힙 영역을 모듈로 처리할 수 있어 메모리 보호 및 공유 기능 향상
단점
외부 단편화 발생
페이징(배치정책)
고정 분할 방식으로, 물리 메모리를 고정 크기의 블록(페이지 프레임)으로 나누고, 프로세스의 가상 메모리 역시 같은 크기의 페이지로 분할하여, 각 가상 페이지를 필요에 따라 물리 메모리의 페이지 프레임에 동적으로 매핑하는 방식
페이지 : 논리 주소 공간에서 같은 크기로 나눈 블록
프레임 : 물리 주소 공간에서 같은 크기로 나눈 블록
CPU가 논리 주소를 전달 => MMU는 그 주소에 해당하는 페이지와 오프셋을 알아냄 => MMU 내의 PTBR(Page Table Base Register)를 이용해 물리 메모리에 있는 페이지 테이블을 찾음 => 페이지 번호를 인덱스로 해 프레임 번호를 알아낸 뒤 오프셋을 이용해 물리주소로 변환
페이지 넘버 = 논리주소 / 페이지 크기
오프셋 = 논리주소 % 페이지 크기
물리주소 = 프레임값 + 오프셋
장점
외부 단편화 문제 해결
논리 메모리는 물리 메모리에 저장될 때 연속되어 저장될 필요 없음
단점
내부 단편화 발생
페이지 테이블의 크기를 적절히 유지해야 함
페이지드 세그멘테이션(배치정책)
메모리 관리의 두 가지 기본 접근 방식인 세그멘테이션과 페이징의 장점을 결합한 메모리 관리 전략
프로그램의 메모리 공간을 논리적인 단위인 세그먼트로 나눈 다음, 각 세그먼트를 다시 고정 크기의 페이지로 분할하여 관리하는 방식
메모리 접근 권한
code 영역: 읽기, 실행
data 영역: 읽기, (쓰기)
heap 영역: 읽기, 쓰기
stack: 읽기, 쓰기
가상 주소에서 물리 주소로 변환될 때마다 메모리 접근 권한에 대한 검사 => 권한 위반 시 에러 발생시킴
가상 주소가 들어오면 몇 번 세그먼트인지 알아냄 => 물리 메모리에 있는 페이지 테이블 찾음 => 그먼트 번호에 따라 인덱스를 참조하여 먼저 해당 세그먼트가 메모리 접근 권한을 위반하는지 검사 => 접근 권한 위반시 프로세스를 종료, 접근 권한에 부합할시 페이지 넘버와 페이지 개수를 가져옴 => 페이지 테이블에서 페이지 넘버에 따라 인덱스를 참조하여 프레임 알아냄
장점
각각의 세그먼트는 논리적 영역별로 나누어 독립적으로 관리 가능
메모리를 효율적으로 관리
단점
물리 메모리에 접근하기 위해 메모리에 두 번 접근해야
디맨드 페이징(가져오기 정책)
프로그램 실행 시 모든 코드와 데이터를 메모리에 적재하는 것이 아닌, 필요로 하는 데이터만을 메모리로 가져오고 쓰이지 않을 것 같은 데이터는 스왑 영역으로 이동 시키는 방식
지역성 이론
goto문을 사용하지 않는 이유가 되는 이론
공간의 지역성 : 현재 위치와 가까운 데이터에 접근할 확률이 높다.
시간의 지역성 : 최근 접근했던 데이터가 오래 전에 접근했던 데이터보다 접근할 확률이 높다.
지역성 이론에 따라 조만간 쓰일 데이터만 메모리에 올리고 당분간 필요하지 않을 것 같은 데이터는 스왑 영역으로 보내 성능 향상
메모리 계층 구조
레지스터: CPU 1 사이클
캐시(L1, L2): CPU n~nn사이클
메인 메모리: CPU nnn사이클
보조 저장 장치: CPU nnnnnnn사이클
메모리에 접근하는 시간은 보조 저장 장치로 갈수록 느려짐
디맨드 페이징은 스왑 영역을 보조 저장 장치에 저장하는데, 성능 향상을 위해서는 스왑 영역으로 데이터 이동시키는 것을 최소화해야 함
가상 메모리 크기 = 메인메모리 + 스왑 영역
스왑 인 : 스왑 영역에서 물리 메모리로 데이터 가져오는 것
스왑 아웃 : 물리 메모리에서 스왑영역으로 데이터 내보내는 것
PTE : 페이지 테이블 엔트리, 페이지 테이블을 이루는 한 행
페이지 교체정책
page fault가 생겼고, 현재 메모리가 가득 차있을 때 메모리에서 스왑 영역으로 페이지를 넣고 가져와야 하는데, 이 과정에서 어떤 페이지를 스왑영역으로 옮길지를 결정하는 것
random
무작위로 페이지를 선택해 교체하는 방식
지역성을 고려하지 않아 성능이 좋지 않음
FIFO(First In First Out)
메모리에 가장 먼저 적재된 페이지를 선택해 교체하는 방식
하드웨어적으로 접근비트를 지원하지 않는 시스템에서 사용
장점
구현이 간단함
단점
자주 사용되는 페이지도 교체되므로 낮은 성능
Optimum
앞으로 가장 오랫동안 쓰이지 않을 페이지를 선택해 교체하는 방식
가장 오랫동안 쓰이지 않을 페이지를 알 수 없으므로 이론적으로만 존재하는 방식이며 다른 정책과 성능을 비교하기 위한 참조용으로만 쓰임
LRU(Least Recently Used)
최근 가장 사용이 적은 페이지를 선택해 교체하는 방식
지역성 이론의 시간 지역성에 따른 방식
장점
FIFO에 비해 효율적
단점
프로그램이 지역성을 띄지 않을 때 성능 저하
시간을 기록하기 위한 많은 bit 필요하며 시간이 오래되면 오버플로우 발생
접근 시간을 기록하기 위한 추가적 메커니즘 필요
Clock Algorithm
LRU와 비슷
모든 페이지에 접근 비트를 하나만 사용하여 일정 시간 간격마다 모든 페이지의 접근 비트를 0으로 초기화하며 페이지가 참조될 때 접근 비트를 1로 설정, 클락 핸드가 시계방향으로 페이지들을 순환하며 사용 비트가 0인 페이지를 선택해 교체하는 방식
Enhanced Clock Algorithm
접근 비트와 변경 비트를 동시에 두고 교체할 페이지를 선택하는 방식
교체 1순위: 접근 비트 0 / 변경 비트 0
교체 2순위: 접근 비트 0 / 변경 비트 1
교체 3순위: 접근 비트 1 / 변경 비트 0
교체 4순위: 접근 비트 1 / 변경 비트 1
2차 기회 페이지 교체 알고리즘
하드웨어적으로 접근비트를 지원하지 않는 시스템에서 사용되어야 하는 FIFO의 단점이었던 자주 사용되는 페이지의 교체 문제를 개선한 방식
먼저 들어왔지만 Page Fault 없이 페이지 접근에 성공한 경우 자주 사용되는 페이지이므로 해당 페이지를 큐의 맨 뒤로 이동시켜 수명을 연장시키는 알고리즘
성능 : FIFO < 2차 기회 페이지 교체 알고리즘 < LRU
스레싱
운영체제는 CPU사용량을 늘리려 함 => 사용량을 늘리려고 멀티프로그래밍 정도를 늘리려고 하는데 무작정 늘려버리면 오히려 스왑작업이 많아져서 사용량이 줄어들게 됨 => 해당 상황이 스레싱
원인 : 물리메모리의 크기가 작은 것
해결 방법
메모리 크기 증가
프로세스에 적절한 페이지의 수 할당
한 프로세스에 많은 페이지 할당시 다른 프로세스의 페이지가 줄어들어 낮은 효율
한 프로세스에 적은 페이지 할당시 빈번한 Page Fault 발생으로 스래싱 발생
프로세스에 맞게 유지할 페이지 결정
워킹셋 : 현재 사용중인 페이지들은 자주 사용될 확률이 높기 때문에 이를 통째로 메모리에 올리는 것
주변장치(I/O 디바이스, 저장장치)
그래픽 카드, 하드디스크, SSD, 키보드, 마우스 등
주변 장치 분류
캐릭터 디바이스
데이터 전송단위가 character로, 상대적으로 크기가 작다.
마우스, 키보드, 사운드카드, 직렬/병렬 포트
블록 디바이스
데이터 전송단위가 block으로, 상대적으로 크기가 작다.
하드디스크, SSD, 그래픽카드 등
입출력 버스 구조
초기 : 버스 하나에 주변 장치를 모두 연결
CPU가 작업을 진행하다가 입출력 명령을 만나면 직접 입출력장치에서 데이터를 가져오는 폴링 방식 이용 => CPU 사용률이 낮아짐
현재 : 입출력 제어기(I/O Controller)와 여러개의 버스 추가
CPU는 I/O 작업 발생 시 입출력 제어기에 이를 맡기고 다른 작업 진행
메모리가 입출력 제어기에 직접 연결하기 위해 DMA(Direct Memory Access)를 추가하고 사용하는데 이를 Memory Mapped I/O라고 부름
마우스/키보드
광학 마우스 작동 원리
마우스 밑면에 작은 카메라 탑재, 초당 1500회가 넘는 사진을 찍어 디바이스 컨트롤러 내 DSP로 보냄
DSP는 사진을 분석해 마우스의 x축 좌표와 y축 좌표 움직임 분석
디바이스 컨트롤러는 CPU에게 인터럽트를 보내고 마우스 드라이버가 동작해 데이터 읽음
마우스 드라이버는 운영체제에게 이벤트 신호를 보내고 운영체제는 이 이벤트를 Foreground 애플리케이션으로 전달
해당 애플리케이션은 받은 마우스 이벤트 처리, 해당 동작 수행
키보드 작동 원리
사용자가 키 입력
디바이스 컨트롤러가 어떤 키를 입력 받았는지 알아냄
CPU에게 인터럽트 보냄
키보드 드라이버는 운영체제에 이벤트를 보내고 운영체제는 이 이벤트를 Foreground 애플리케이션으로 전달
해당 애플리케이션은 받은 키보드 이벤트 처리, 해당 동작 수행
하드디스크/Flash Memory(SSD)
블록 디바이스의 한 종류
하드 디스크 구조
spindle이라고 하는 막대가 있고 그곳에는 platter라는 원판들이 붙어 있음. disk arm이 platter의 값을 읽음.
platter > track > sector구조
하드 디스크 작동 원리
유저 프로세스가 하드디스크의 특정 섹터에 접근 요청(실린더 C로 가서 트랙 B에 있는 섹터 D를 읽어라)
seek: 디스크암은 헤드를 실린더 C로 이동.
seek Time: 헤드를 실린더로 이동시키는 시간으로, 하드디스크가 느린 이유
트랙 B의 섹터D가 헤드에 닿을때까지 스핀들 회전
헤드에 섹터D가 읽히면 작업 종료
단점
속도 느리고 소음 발생
자석을 대면 데이터 손상
충격에 약함
Flash Memory
장점
전기적으로 데이터를 읽어 속도가 빠르고 조용하다
자석을 대도 데이터 보존
충격에 강함
단점
특정 부분에 데이터를 쓴 경우 덮어쓰기 불가 및 데이터 삭제 횟수가 정해져있어 같은 부분에 데이터 삽입과 삭제를 반복할 경우 망가져 사용 불가
파일과 파일시스템
파일들은 하드디스크나 SSD같은 저장 장치에 저장되는데, 사용자가 직접 저장하면 손상시킬 수 있어 운영체제가 안전하게 저장
파일 시스템 기능
파일과 디렉토리 생성
파일과 디렉토리 수정/삭제
파일 권한 관리
무결성 보장
백업과 복구
암호화
파일 제어 블록 = 파일 디스크립터
모든 파일마다 있고 오픈되면 메모리로 이동
운영체제가 관리하고 사용자는 접근할 수 없음
파일의 분류
순차파일구조
카세트테이프
들어온 순서대로 작동하기에 공간의 낭비가 없고 구조가 단순
특정지점으로 바로 이동이 어려움
직접파일구조
해시 함수를 통해 저장 위치를 정하는 방식(json도 이 방식 사용)
데이터 접근이 매우 빠름
해시함수를 잘 골라야 하며 저장공간이 낭비될 수 있음
인덱스 파일구조
앞선 두 가지 방식을 합친 것
노래 재생목록
디렉토리
파일과 다른 디렉토리를 포함할 수 있는 컨테이너
파일을 주제나 유형별로 그룹화하여 조직화할 수 있음
디렉토리도 하나의 파일로, 파일이 데이터를 저장한다면 디렉토리는 파일 정보를 저장
디렉토리 구조
계층적 구조 : 최상위에 루트 디렉토리(/) 존재
초기 : 루트 디렉토리에만 디렉토리가 존재할 수 있고 다른 디렉토리에서는 하위 디렉토리를 만들 수 없는 구조
현재 : 다단계 디렉토리 구조로, 모든 디렉토리가 하위 디렉토리를 만들 수 있는 트리구조
파일과 디스크
디스크는 블록(1~8kB)으로 나뉘어있음.
파일시스템은 파일정보를 파일 테이블로 관리하고, 파일이 시작하는 블록 위치 정보도 기록되어있음.
파일 할당 방식
연속 할당
블록들을 디스크에 연속적으로 저장하는 방식
시작블록만 알면 나머지도 알 수 있으나 내부단편화가 발생 -> 그래서 사용하지 않음
불연속 할당
디스크의 비어있는 공간에 집어넣고 파일시스템이 두가지 방식으로 관리
연결 할당
파일에 속한 데이터를 연결리스트로 관리
파일 테이블에는 시작 블록에 대한 정보만 저장하고 다른 블록은 연결리스트를 통해 접근
인덱스 할당(i-node 방식)
파일 테이블의 블록 포인터가 데이터 블록에 직접 연결하는것이 아닌, 데이터들의 인덱스를 가지고 있는 인덱스 블록에 연결
데이터가 많아 테이블이 꽉 찬 경우 인덱스 블록을 더 만들어 연결하기 때문에 테이블 확장 가능
파일 크기가 작다면 데이터를 바로 참조하는 블록 포인터 이용, 파일 크기가 크다면 간접 포인터를 이용해 많은 데이터에 접근 가능
디스크를 구성하는 블록의 크기가 너무 작으면 공간 낭비는 줄지만 관리해야 할 블록의 수가 많아지고, 블록의 크기가 너무 크면 관리해야하는 블록의 수는 적지만 내부단편화로 낭비되는 공간이 많아짐
빈공간을 찾을 때 항상 모든 공간을 찾는것보다는 빈공간 리스트를 만들고 삭제한 후에 리스트에 빈 공간의 주소를 추가하는 방식이 좋음
알고리즘
정렬 - 삽입정렬
장점 : 간단한 이해와 구현
단점 : 낮은 성능
A = [34, 58, 13, 94, 29]
# 이미 정렬된 부분이라고 가정하는 0번째 요소를 제외한 나머지 부분 순회
for i in range(1, len(A)):
# 이미 정렬된 부분(0번째~i-1번째)에서 자리 찾기
# 뒤에서부터 훑으면서 큰 원소들을 만날 때마다 교환
for j in range(i-1, 0, -1):
if A[j+1] > A[j]:
break
A[j], A[j+1] = A[j+1], A[j]
정렬 - 병합정렬
정렬해야 할 것을 아주 잘게 나눈 다음 정렬하고 병합하는 것을 반복하는 정렬 방법
장점 : O(nlogn)의 좋은 성능
단점 : 이해와 구현 어려움, 시스템의 스택 크기가 큰 데이터를 정렬할 때 제한적
def merge_sort(unsorted_list):
# 리스트를 더 이상 나눌 수 없으면 해당 리스트를 그대로 리턴
if len(unsorted_list) <= 1:
return unsorted_list
# 리스트를 반으로 나누기
mid = len(unsorted_list)//2
# 왼쪽 부분을 재귀적으로 정렬
left = merge_sort(unsorted_list[:mid])
# 오른쪽 부분을 재귀적으로 정렬
right = merge_sort(unsorted_list[mid:])
# left, right 리스트를 처음부터 순회하기 위한 인덱스 초기화
left_idx = right_idx = 0
# 정렬된 left, right 두 리스트를 병합한 결과를 저장할 리스트 초기화
merged = []
# 왼쪽과 오른쪽 리스트의 앞부분 부터 비교해가며 병합
while (left_idx < len(left) and right_idx < len(right)):
# 현재 가리키고 있는 왼쪽 값이 오른쪽 값보다 작으면 왼쪽 값을 병합리스트에 추가하고, 왼쪽 인덱스에 1 더하기
if right[right_idx] > left[left_idx]:
merged.append(left[left_idx])
left_idx += 1
# 현재 가리키고 있는 오른쪽 값이 왼쪽 값보다 작으면 왼쪽 값을 병합리스트에 추가하고, 왼쪽 인덱스에 1 더하기
else:
merged.append(right[right_idx])
right_idx += 1
# 왼쪽 리스트에 남은 값이 있으면 병합 리스트에 추가
while (left_idx < len(left)):
merged.append(left[left_idx])
left_idx += 1
# 오른쪽 리스트에 남은 값이 있으면 병합 리스트에 추가
while (right_idx < len(right)):
merged.append(right[right_idx])
right_idx += 1
# 병합된 결과 리턴
return merged
A = [34, 58, 13, 94, 29]
A = merge_sort(A)
정렬 - 퀵정렬
배열의 값 중 한가지를 피벗으로 설정 (피벗 설정 방법은 여러가지)
맨 왼쪽, 맨 오른쪽, 양쪽 이동 값을 만든다
장점 : O(nlogn)의 좋은 성능
단점 : 이해와 구현 어려움, 최악의 경우 시간복잡도가 O(n^2)
A = [34, 58, 13, 94, 29]
def quick_sort(low, high):
if low < high:
# pivot을 가장 큰 값으로 임의로 선택
pivot = A[high]
# 현재 pivot보다 작은 부분의 마지막 요소의 인덱스
# 주어진 리스트 안에서 pivot보다 작은 요소의 개수 - 1
i = low - 1
# 분할 과정
for j in range(low, high): # low부터 high-1까지 순회
# pivot보다 작은지 확인
if A[j] <= pivot:
i = i + 1
A[i], A[j] = A[j], A[i] # 작은 부분(왼쪽 부분)으로 옮기기
# 작은 부분의 마지막 요소의 바로 뒤 요소와 pivot을 교환
# pivot을 기준으로 pivot보다 작은 원소는 왼쪽으로, 큰 원소는 오른 쪽으로 배치
A[i+1], A[high] = A[high], A[i+1]
# 분할 과정 이후 pivot의 최종 위치
pivot_idx = i + 1
# 재귀적 정렬 - 왼쪽 부분 정렬
quicksort(low, pivot_idx - 1)
# 재귀적 정렬 - 오른쪽 부분 정렬
quick_sort(pivot_idx + 1, high)
# 초기 호출
quick_sort(0, len(A)-1)
동적 프로그래밍 - 메모이제이션
계산 결과를 저장해서 여러번 계산하지 않도록 하는 기법
계산 결과를 해시 테이블에 저장하고 재사용해 속도가 빠르다 .
하향식 계산 방식으로 문제를 해결
동적 프로그래밍 - 타뷸레이션
계산에 필요한 모든 값을 전부 계산 후 테이블에 저장하는 기법
상향식 계산 방식으로 문제를 해결
회고
3주간의 워밍업클럽 2기가 마무리되었다. 끝나고 회고를 작성하면서 드는 생각은 이것저것 챙기려고 하다보니, 3주간 약간은 쫓기면서 수업을 수강하진 않았는가 하는 아쉬움도 들고, 그럼에도 혼자 수강했다면 절대 완강하지 못했을 거란 생각이 들어서 참여하길 잘했다고 생각한다!
알고리즘 공부는 개인적으로도 필요성을 많이 느껴서 블로그에 정리도 해보고, 따로 이런저런 글도 많이 읽어서 익숙했는데 운영체제는 사실 예전에 CS 면접 준비를 위해 잠깐 슥 겉핥기로 훑어본게 전부였고, 그때도 제대로 이해하진 못해서 좀 걱정되는 부분도 있었다. 다행히 친절한 난이도의 강의와 설명 덕분에 큰 무리없이 강의를 수강할 수 있었다. 기회가 된다면 다시 강의를 한바퀴 돌리면서 좀 더 개념을 확실히 익히고 추가적으로 궁금한 점이 생기는 부분을 더 깊게 파고들어보고 싶다. 일단은 기초 개념을 잡았다는 것에 만족:-)
이제 워밍업 클럽은 끝났지만, 이걸로 공부를 완전히 끝내서는 당연히 안될 것이다. 인프런에 올린 발자국의 배운 내용 요약은 내가 강의를 들으면서 휘갈겼던(..) 노트를 그대로 옮긴거라, 추후엔 내 블로그에 이해한 내용을 나만의 방식으로 정리한 것과 강의를 들으면서 생겼던 의문, 그리고 그 의문에 대한 답 등등..을 정리하며 추가적으로 공부할 예정이다. (제발 하길...)
워밍업 클럽 2기 안녕👋
댓글을 작성해보세요.