![[인프런 워밍업 클럽 CS 2기] 3주차 발자국](https://cdn.inflearn.com/public/files/blogs/2df02128-2cf6-4ce3-a736-bcdfb78396b8/KakaoTalk_20240930_194345309.png)
[인프런 워밍업 클럽 CS 2기] 3주차 발자국
자료구조와 알고리즘
삽입 정렬(Insertion Sort)
자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하는 정렬 방식
삽입 정렬의 원리
다음과 같은 배열이 있다고 할 때, 삽입 정렬이 진행되는 과정을 알아보자.
array = [4, 1, 5, 3, 2, 6]
path 1
첫 번째 원소인 4는 이미 정렬되어 있다고 가정하고 정렬 되지 않은 뒤의 영역중 첫 번째 원소인 1을 정렬된 부분의 마지막 원소인 4와 비교한다.
4가 더 크므로 원래의 원소 1이 있던 위치에 덮어 쓴다.
[4, 4, 5, 3, 2, 6]
1은 4의 위치로 삽입한다.
[1, 4, 5, 3, 2, 6]
정렬되지 않은 부분의 첫 번째 원소 1을 삽입했으므로 path 1을 끝낸다.
path 2
현재 정렬된 부분은 [1, 4]로, 정렬되지 않은 부분의 첫 번째 원소 5를 삽입 정렬한다.
먼저 5를 정렬된 부분인 [1, 4]의 마지막 원소인 4와 비교한다.
5는 4보다 크므로 그 자리에 그대로 있는 것으로 정렬을 마친다.
[1, 4, 5, 3, 2, 6]
정렬되지 않은 부분의 첫 번째 원소 5를 삽입했으므로 path 2을 끝낸다.
path 3
현재 정렬된 부분은 [1, 4, 5]로, 정렬되지 않은 부분의 첫 번째 원소 3을 삽입 정렬한다.
먼저 3을 정렬된 부분인 [1, 4, 5]의 마지막 원소인 5와 비교한다.
3은 5보다 작으므로 3의 자리에 5를 덮어 쓴다.
[1, 4, 5, 5, 2, 6]
그다음 3을 정렬된 부분의 두 번째 원소인 4와 비교한다.
3은 4보다 작으므로 4를 오른쪽 인덱스에 덮어 쓴다.
[1, 4, 4, 5, 2, 6]
그다음 3을 정렬된 부분의 첫 번재 원소인 1과 비교한다.
3은 1보다 크므로 3을 1의 다음 인덱스에 덮어 쓴다.
[1, 3, 4, 5, 2, 6]
정렬되지 않은 부분의 첫 번째 원소 3을 삽입했으므로 path 3을 끝낸다.
path 4
현재 정렬된 부분은 [1, 3, 4, 5]로, 정렬되지 않은 부분의 첫 번째 원소 2를 삽입 정렬한다.
먼저 2를 정렬된 부분인 [1, 3, 4, 5]의 마지막 원소인 5와 비교한다.
2는 5보다 작으므로 2의 자리에 5를 덮어 쓴다.
[1, 3, 4, 5, 5, 6]
그다음 2를 정렬된 부분의 세 번째 원소인 4와 비교한다.
2는 4보다 작으므로 그 다음 인덱스에 4를 덮어 쓴다.
[1, 3, 4, 4, 5, 6]
그 다음 2를 정렬된 부분의 두 번째 원소인 3과 비교한다.
2는 3보다 작으므로 그 다음 인덱스에 3을 덮어 쓴다.
[1, 3, 3, 4, 5, 6]
그 다음 2를 정렬된 부분의 첫 번째 원소인 1과 비교한다.
2는 1보다 크므로 그 다음 인덱스에 2를 덮어 쓴다.
[1, 2, 3, 4, 5, 6]
정렬되지 않은 부분의 첫 번째 원소 2를 삽입했으므로 path 4를 끝낸다.
path 5
현재 정렬된 부분은 [1, 2, 3, 4, 5]로, 정렬되지 않은 부분의 첫 번째 원소이자 마지막 원소 6을 삽입 정렬한다.
먼저 6을 정렬된 부분인 [1, 2, 3, 4, 5]의 마지막 원소인 5와 비교한다.
6은 5보다 크므로 그 자리에 그대로 있는 것으로 정렬을 마친다.
[1, 2, 3, 4, 5, 6]
정렬되지 않은 부분의 마지막 원소 6을 삽입했으므로 path 5를 끝낸다.
모든 원소가 정렬된 상태로 배열되었으므로 정렬을 마친다.
삽입 정렬의 성능
삽입 정렬은 이해와 구현이 간단하다. 그렇다면 성능은 어떨까?
배열의 개수가 n개일 경우 정렬을 해야하는 횟수는 (n-1)+(n-2)+(n-3)+...+2+1로, 이를 식으로 표현하면 n(n-1)/2 즉, (n²-n)/2가 된다.
이를 빅 오로 표기하면 O(n²)의 성능을 갖는다고 할 수 있다.
삽입 정렬의 장단점
삽입 정렬의 장점
간단한 이해와 구현이 가능
삽입 정렬의 단점
O(n²)의 낮은 성능
병합 정렬(Merge Sort)
분할 정복(Divide and Conquer) 알고리즘의 대표적인 예 중 하나로, 큰 문제를 작은 문제로 나눈 뒤 각각 해결한 다음 결과를 합쳐 전체 문제의 답을 얻는 방법이다.
병합 정렬의 과정
분할(Divide) - 정복(Conquer) - 결합(Merge)의 과정으로 진행된다.
배열 [3, 5, 2, 4, 1, 7, 8, 6]를 병합 정렬 해 보자.
1. 분할(Divide): 정렬되지 않은 리스트를 계속해서 절반으로 나누어, 각 부분 리스트의 크기가 1이 될 때까지 분할한다.
2. 정복(Conquer): 그 후 가장 작은 단위가 된 리스트부터 재귀적으로 정렬을 하며 문제를 해결해 나간다.
3. 결합(Merge): 정렬된 부분 리스트들을 하나의 정렬된 리스트로 합친다.
성능
병합 정렬에서 성능을 평가하는 부분은 흩어진 배열을 합치는 부분이다.
하나의 데이터와 하나의 데이터가 두 개로 합쳐질 때 비교 연산 두 번 수행,
두개의 데이터와 두개의 데이터가 네 개로 합쳐질 때 비교 연산 네 번 수행.
각 단계를 거칠 때 마다 영역의 수가 반으로 줄기 때문에 logn
분할된 데이터를 병합시 n개의 데이터를 n번 비교하므로
성능 = n x logn = O(nlogn)
장단점
장점
O(nlogn)의 좋은 성능
단점
이해와 구현의 어려움
시스템의 스택 크기가 큰 데이터를 정렬할 때 제한적
퀵 정렬(Quick Sort)
병합 정렬과 같이 분할 정복 방식을 이용하는데, 피벗(pivot)을 이용한다는 특징이 있다.
퀵 정렬의 과정
피벗 선택 - 분할(Divide) - 정복(Conquer)의 과정으로 진행된다.
배열 [5, 3, 7, 2, 6, 4, 9, 1, 8]를 퀵 정렬 해 보자.
피벗 선택: 배열에서 하나의 요소를 피벗으로 선택한다. 선택 방법으로는 첫 번째 요소, 마지막 요소, 중간 요소 또는 무작위 요소 선택 등이 있다.
여기에서는 첫 번째 요소인 5를 피벗으로 선택한다.분할(Divide): 선택된 피벗을 기준으로 배열을 두 부분으로 나눠 피벗보다 작은 요소들은 피벗 왼쪽에, 피벗보다 큰 요소들은 피벗 오른쪽에 오도록 한다. 이 과정에서 피벗은 자신의 위치에 맞게 정렬된다.
규칙은 다음과 같다.
1) leftStartIndex와 rightStartIndex를 선언해 준비를 마친다.
2) leftStartIndex는 오른쪽으로 이동하며 피벗보다 큰 값을 만나면 멈춘다.
3) rightStartIndex는 왼쪽으로 이동하며 피벗보다 작은 값을 만나면 멈춘다.
4) leftStartIndex와 rightStartIndex가 둘 다 멈췄을 때 서로의 요소를 교환한다.
5) 위를 반복해 나아가다가 leftStartIndex와 rightStartIndex가 서로 지나쳐 leftStartIndex가 rightStartIndex의 오른쪽에, rightStartIndex가 leftStartIndex의 왼쪽에 위치하게 될 때 진행을 멈춘다.
6) 피벗과 rightStartIndex의 값을 교환한다.
아래는 준비를 모두 마친 상태이다.
leftStartIndex를 오른쪽으로 이동시키다 피벗인 5보다 큰 수 7을 만나면 멈춘 뒤 rightStartIndex를 왼쪽으로 이동시키다 피벗인 5보다 작은 수 1을 만나면 멈춘다.
각각 멈춘 자리에서 요소의 자리를 바꾼다.
다시 leftStartIndex를 오른쪽으로 이동시키다 피벗인 5보다 큰 수 6을 만나면 멈춘 뒤 rightStartIndex를 왼쪽으로 이동시키다 피벗인 5보다 작은 수 4를 만나면 멈춘다.
각각 멈춘 자리에서 요소의 자리를 바꾼다.
다시 leftStartIndex를 오른쪽으로 이동시키다 피벗인 5보다 큰 수 6을 만나면 멈춘 뒤 rightStartIndex를 왼쪽으로 이동시키다 피벗인 5보다 작은 수 4를 만나면 멈춘다.
이 때 leftStartIndex와 rightStartIndex가 자리를 바꾸게 되는데, 여기에서 이동을 종료한다.
최종으로 rightStartIndex가 위치한 자리의 요소 4와 피벗의 요소 5를 교환한다.
피벗이었던 요소 5의 위치가 정렬된 상태가 된다.
정복(Conquer): 피벗을 제외한 왼쪽 부분과 오른쪽 부분 각각에 대해 재귀적으로 위의 과정을 반복한다.
결합(Merge): 퀵 정렬은 분할 시 요소들이 이미 정렬되어 별도의 결합 과정이 없다.
성능
최악의 경우는 피벗이 배열을 반으로 가르지 않고 한쪽으로 치우친 경우로, O(n²)의 성능을 보인다. 하지만 보통 중간값의 좋은 피벗을 선택해 성능이 안 좋게 나올 경우가 극히 드물다.
평균적인 성능은 다음과 같다.
데이터가 한 개가 될 때까지 반으로 나누므로 logn
이 작업을 데이터의 개수 n개만큼 반복
성능 = n x logn = O(nlogn)
장단점
장점
O(nlogn)의 좋은 성능
단점
이해와 구현의 어려움
최악의 경우 시간 복잡도가 O(n²)까지 증가
다이나믹 프로그래밍(Dynamic Programming)
다이나믹 프로그래밍(Dynamic Programming)이란?
다이나믹 프로그래밍(Dynamic Programming)은 문제를 여러 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다. 큰 문제를 작은 문제로 분할하여 각 하위 문제의 해를 계산하고, 이를 이용하여 상위 문제의 해를 구하는 방식으로 동작한다.
메모이제이션(Memoization)
메모이제이션(Memoization)이란?
메모이제이션(Memoization)이란 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다.
예시
피보나치 수열과 같은 하향식 문제에선 중복된 계산이 많아져 낮은 성능을 보이는데, 이렇게 중복된 계산이 많을 때 메모이제이션을 통해 계산 결과를 저장, 검색함으로써 중복된 계산을 줄여 성능을 높일 수 있다.
아래는 fibonacci 함수를 생성하고 실행한 결과이다.
fibonacci1 함수: 재귀함수
fibonacci2 함수: 재귀함수에 메모이제이션 기술 적용
n=5 일 때의 결과
n=40 일 때의 결과
성능
fibonacci1: O(n²)
fibonacci2: O(n)
메모이제이션을 사용했을 때 성능이 더 좋다.
장점
빠른 속도
재귀를 이용해 어려운 문제를 단순하게 해결 가능
단점
메모리 사용
타뷸레이션(Tabluation)
타뷸레이션(Tabluation)이란?
타뷸레이션(Tabluation)이란 상향식 계산 방식으로, 계산에 필요하지 않을 수도 있는 값도 미리 계산해 테이블에 저장해 두고 값이 필요할 때 빠르게 가져다 쓰는 방식
다음은 위의 fibonacci1과 fibonacci2 함수에 더해 타뷸레이션 방식으로 생성한 fibonacci3 함수의 실행시간을 비교한 결과이다.
fibonacci1, fibonacci2, fibonacci3 함수 비교
fibonacci1
여러 번의 함수 호출로 메모리 공간에 스택 차지, 느린 속도fibonacci2
여러 번의 함수 호출로 메모리 공간에 스택 차지, 메모이제이션을 위한 테이블 공간 차지로 더 많은 메모리 사용, 빠른 속도fibonacci3
적은 메모리 사용, 빠른 속도
결론
동적 프로그래밍이 필요한 분할 정복 문제를 해결할 때 재귀가 더 직관적이라면 메모이제이션을, 아닐 시엔 상향식 계산 방식인 타뷸레이션을 이용하는 것이 유리하다.
운영체제
가상 메모리
가상 메모리란?
컴퓨터 운영 체제의 메모리 관리 기술 중 하나로, 소프트웨어와 하드웨어의 협력을 통해 프로그램에게 실제 물리적 메모리(RAM)보다 더 큰 메모리 공간을 사용할 수 있게 해주는 시스템
가상 메모리를 사용하면 프로세스는 운영체제 영역이 어디 있는지, 물리 메모리의 크기가 얼마나 큰지 몰라도 된다.
프로그래머는 물리 메모리의 크기와 프로세스가 메모리의 어느 위치에 올라가는지 신경 쓰지 않고 0x0번지에서 시작된다고 생각하고 프로그래밍을 하면 된다.
프로세스는 메모리 관리자를 통해 메모리에 접근한다. 프로세스 입장에서는 물리 메모리에 직접 접근할 일이 없고 메모리 관리자(MMU)에게 요청만 하면 된다. 프로세스가 메모리 관리자에게 요청하면 그에 맞는 물리 메모리로 연결 시켜준다.
동작 방식
물리 메모리 내용의 일부를 하드 디스크의 스왑 영역으로 옮긴 뒤 처리가 필요할 때 물리 메모리로 가져와 실행 한다.
동적 주소 변환(Dynamic Address Translation)
메모리 관리자는 물리메모리와 스왑영역을 합쳐 프로세스가 사용하는 가상 주소를 물리주소로 변환한다.
세그멘테이션(segmentation)
가변 분할 방식
세그멘테이션(segmentation) 기법은 프로세스의 메모리를 다양한 크기의 논리적 단위인 세그먼트로 나누어 관리하는 메모리 관리 전략으로, 각각 독립적인 주소 공간을 가진다.
동작 원리
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일 때메모리를 침범한 것으로 간주하고 에러 발생
예시
아래와 같이 세그먼트 테이블이 존재한다.
예시 1)
CPU에서 세그먼트 1번이 0x632번지로 접근
MMU는 내부의 Segment Table Base Register를 이용해 세그먼트 테이블을 찾은 뒤 세그먼트 1번이 위치한 1번 인덱스 참조.
논리주소가 632이고 1번 인덱스의 Bound Address가 1000이므로 논리주소 < Bound Address 가 성립한다.
물리주소 = 632 + 5200 = 5832
예시 2)
CPU에서 세그먼트 3번이 0x750번지로 접근
MMU는 내부의 Segment Table Base Register를 이용해 세그먼트 테이블을 찾은 뒤 세그먼트 3번이 위치한 3번 인덱스 참조.
논리주소가 750이고 3번 인덱스의 Bound Address가 500이므로 논리주소 > Bound Address 가 성립한다.
메모리를 침범한 것으로 판단하고 인터럽트를 발생시켜 프로세스를 종료시킨다.
장점
메모리를 가변적으로 분할 가능
코드, 데이터, 스택, 힙 영역을 모듈로 처리할 수 있어 메모리 보호 및 공유 기능 향상
단점
외부 단편화 발생
페이징
고정 분할 방식으로, 물리 메모리를 고정 크기의 블록(페이지 프레임)으로 나누고, 프로세스의 가상 메모리 역시 같은 크기의 페이지로 분할하여, 각 가상 페이지를 필요에 따라 물리 메모리의 페이지 프레임에 동적으로 매핑하는 방식
페이지와 프레임
논리 주소 공간에서 같은 크기로 나눈 블록을 페이지라고 하며
물리 주소 공간에서 같은 크기로 나눈 블록을 프레임이라고 한다
동작 원리
CPU가 논리 주소를 전달하면 MMU는 그 주소에 해당하는 페이지와 오프셋을 알아내고 MMU 내의 PTBR(Page Table Base Register)를 이용해 물리 메모리에 있는 페이지 테이블을 찾는다. 페이지 번호를 인덱스로 해 프레임 번호를 알아낸 뒤 오프셋을 이용해 물리주소로 변환한다.
페이지 테이블에 Invalid로 표시되어 있다면 스왑영역(하드디스크)에 저장되어 있는 것.
페이지 넘버 = 논리주소 / 페이지 크기
오프셋 = 논리주소 % 페이지 크기
물리주소 = 프레임 값 + 오프셋
예시
아래와 같이 세그먼트 테이블이 존재한다.
예시 1)
논리 주소 공간의 페이지 크기가 2²⁴(16,777,216)일 때 CPU가 논리주소 0x1000번지에 접근한다고 가정
페이지 넘버 = 1000 / 16,777,216 = 0
오프셋 = 1000 % 16,777,216 = 1000
페이지 넘버 0을 페이지 테이블의 인덱스로 참조하여 프레임을 구하면 3이다.
물리주소 = 프레임 3번 + 1000
예시 2)
CPU가 논리주소 0x31554432번지에 접근한다고 가정
페이지 넘버 = 31554432 / 16777216 = 1
오프셋 = 31554432 % 16777216 = 14777216
페이지 넘버 1을 페이지 테이블의 인덱스로 참조하여 프레임을 구하면 1이다.
물리주소 = 프레임 1번 + 31554432
장점
외부 단편화 문제 해결
논리 메모리는 물리 메모리에 저장될 때 연속되어 저장될 필요가 없고
단점
내부 단편화 발생
페이지 테이블의 크기를 적절히 유지
세그멘테이션과 페이징의 차이
세그멘테이션은 프로세스마다 크기가 달라 Bound Address를 가지고 있다.
세그멘테이션은 논리적인 영역별로 세그먼트를 나눕니다.
페이징은 모든 페이징의 크기가 동일해 Bound Address를 가지지 않는다.
페이징은 논리적 영역으로 나눌 수 없어 특정 부분만 떼어내 공유, 권한 부여 어려움
페이지드 세그멘테이션(segmentation with paging)
메모리 관리의 두 가지 기본 접근 방식인 세그멘테이션과 페이징의 장점을 결합한 메모리 관리 전략으로, 프로그램의 메모리 공간을 논리적인 단위인 세그먼트로 나눈 다음, 각 세그먼트를 다시 고정 크기의 페이지로 분할하여 관리하는 방식
메모리 접근 권한
메모리의 특정 번지에 부여된 권한으로 읽기(Read), 쓰기(Write), 실행(Execute) 세 가지
Code영역: 읽기, 실행 권한
Data영역: 읽기, (쓰기) 권한
Heap영역: 읽기, 쓰기 권한
Stack: 읽기, 쓰기 권한
메모리 접근 권한에 대한 검사는 가상주소에서 물리주소로 변환될 때마다 일어나며 권한 위반 시 에러를 발생시킨다.
동작 원리
가상 주소가 들어오면 몇 번 세그먼트인지 알아낸뒤 물리 메모리에 있는 페이지 테이블을 찾는다. 세그먼트 번호에 따라 인덱스를 참조하여 먼저 해당 세그먼트가 메모리 접근 권한을 위반하는지 검사한다. 접근 권한 위반시 프로세스를 종료 시키고, 접근 권한에 부합할시 페이지 넘버와 페이지 개수를 가져온다. 페이지 테이블에서 페이지 넘버에 따라 인덱스를 참조하여 프레임을 알아낸다.
예시
다음과 같이 세그멘테이션 테이블과 페이지 테이블이 존재한다.
세그멘테이션 테이블
페이지 테이블
예시 1)
CPU가 논리주소 0x12300번지에 접근한다고 가정
1번 세그먼트를 따라 RE 권한이 부여된 것을 확인, 들어온 요청이 부여된 권한에 부합하면 페이지 넘버 0을 얻는다.
페이지 테이블에서 페이지 넘버 0에 따른 인덱스 0을 참조하여 프레임 3을 얻는다.
물리 메모리에 접근해 프레임 3번에 페이지 개수 1000을 더하여 물리주소를 구한다. 만약 물리 메모리에 해당 프레임이 없다면 스왑 영역에서 가져온다.
장점
각각의 세그먼트는 논리적 영역별로 나누어 독립적으로 관리가 가능
메모리 효율적 관리
단점
0 물리 메모리에 접근하기 위해 메모리에 두 번 접근해야 한다. (세그멘테이션 테이블과 페이지 테이블에 접근 시 각각 한 번 씩 두번)
가상메모리 시스템에서 데이터와 코드의 적재 방식은 메모리의 효율적 사용과 시스템 성능 최적화를 목표로
가상메모리를 물리적 메모리에 어떻게 매핑하고 적재할지에 대한 전략
디맨드 페이징(Demand Paging)
프로그램 실행 시 모든 코드와 데이터를 메모리에 적재하는 것이 아닌, 필요로 하는 데이터만을 메모리로 가져오고 쓰이지 않을 것 같은 데이터는 스왑 영역으로 이동 시키는 방식
지역성 이론
goto문 사용을 하지 않는 이유가 되는 이론이다.
공간의 지역성
현재 위치와 가까운 데이터에 접근할 확률이 높다.시간의 지역성
최근 접근했던 데이터가 오래 전에 접근했던 데이터보다 접근할 확률이 높다.
지역성 이론에 따라 조만간 쓰일 데이터만 메모리에 올리고 당분간 필요하지 않을 것 같은 데이터는 스왑 영역으로 보내 성능 향상
메모리 계층구조
레지스터: CPU 1 사이클
캐시(L1, L2): CPU n~nn사이클
메인 메모리: CPU nnn사이클
보조 저장 장치: CPU nnnnnnn사이클
메모리에 접근하는 시간이 보조 저장 장치로 갈수록 느려진다.
디맨드 페이징은 스왑 영역을 보조 저장 장치에 저장하는데, 성능 향상을 위해서는 스왑 영역으로 데이터를 이동 시키는 것을 최소화 해야 한다.
가상 메모리 크기 = 메인 메모리 크기 + 스왑 영역 크기
스왑 인: 스왑영역에서 물리 메모리로 데이터를 가져오는 것
스왑 아웃: 물리메모리에서 스왑영역으로 데이터를 보내는 것
가상 주소가 주어지면 MMU는 페이지 테이블을 참조하여 물리 메모리가 있는 프레임을 알아내거나 스왑 영역의 위치를 알아내야 한다. 이는 페이지 테이블의 비트를 이용한다. 페이지 테이블을 이루는 한 행을 페이지 테이블 엔트리(PTE)라 부른다.
PTE
접근비트: 페이지가 메모리에 올라온 후 데이터에 접근이 있었는지 알려주는 비트로, 메모리에 읽기/실행 작업 시 1로 바뀐다.
변경비트: 페이지가 메모리에 올라온 후 데이터에 변경이 있었는지 알려주는 비트로, 메모리에 쓰기 작업 시 1로 바뀐다.
유효비트: 페이지가 물리메모리에 있는지 알려주는 비트로, 페이지가 스왑영역에 있으면 1, 페이지가 물리메모리에 있으면 0
읽기/쓰기/실행 비트: 권한 비트로, 해당 메모리에 접근 권한이 있는지 검사하는 비트
페이지 테이블에서 프레임을 찾아 물리 메모리의 프레임을 찾아내는데, 만약 물리 메모리에 해당 프레임이 없다면 'Page Fault' 인터럽트를 발생시킨다. 보조 저장장치의 스왑영역에 접근해 스왑영역에서 물리 메모리로 데이터를 올리는 작업을 한다. 이 때 프로세스는 중지상태. 물리 메모리에 데이터가 올라가면 대기 상태의 프로세스는 다시 실행된다.
가상 메모리 주소가 물리메모리와 스왑영역에서 참조되는 과정
1) 스왑이 필요 없는 경우
프로세스가 페이지 0 요청시
페이지 테이블에서 0번 인덱스에 따른 유효비트와 프레임 값 확인
유효비트가 0이므로 물리 메모리에 데이터가 있다는 것을 확인
프레임 값은 1이므로 물리 메모리의 1번 프레임 참조.
2) 스왑영역에 있는 데이터를 참조하는 경우
프로세스가 페이지 2 요청시
페이지 테이블에서 2번 인덱스에 따른 유효비트와 프레임 값 확인
유효비트가 1이므로 스왑 영역에 데이터가 있다는 것을 확인
프레임 값은 2이므로 스왑영역의 2번 프레임 확인.
물리 메모리의 빈 공간에 스왑영역 2번 프레임에 있는 C를 스왑 인
페이지 테이블에서 해당 엔트리의 유효비트를 0, 프레임을 스왑 인 한 빈 공간의 프레임 번호로 변경
프로세스에 해당 물리 메모리의 프레임 참조
3) 물리메모리가 꽉 찼을 때 스왑영역의 데이터 참조
프로세스가 페이지 1 요청시
페이지 테이블에서 1번 인덱스에 따른 유효비트와 프레임 값 확인
유효비트가 1이므로 스왑 영역에 데이터가 있다는 것을 확인프레임 값은 2이므로 프레임 값은 0이므로 스왑영역의 0번 프레임 확인.
물리 메모리의 빈 공간을 찾지만 빈 공간이 없음
물리 메모리에서 현재 필요하지 않다고 판단하는 영역을 스왑 영역으로 스왑 아웃(ex. 물리메모리 1번 프레임의 A를 스왑영역의 3번 프레임으로)
페이지 테이블에서 스왑아웃 한 데이터의 유효비트를 1, 프레임 넘버를 해당 스왑영역의 프레임 번호(3)로 변경
빈 공간으로 남은 물리 메모리의 1번 프레임으로 스왑영역의 0번 프레임 데이터 B를 스왑 인
페이지 테이블에서 스왑인 한 데이터의 유효비트를 0, 프레임 넘버를 1로 변경
프로세스에 해당 물리 메모리의 프레임 참조
장점
효율적인 메모리 사용
프로그램 시작 시간 단축
페이지 교체 정책
페이지 교체는 물리 메모리에 적재된 페이지 중 하나를 선택하여 보조 저장소(스왑 영역)로 이동 시키고, 그 자리에 새로운 페이지를 적재하는 과정으로, 주로 물리적 메모리가 가득 차 더 이상 새로운 페이지를 적재할 공간이 없을 때 필요하다.
1) Random
무작위로 페이지를 선택해 교체하는 방식으로, 지역성을 고려하지 않아 성능이 좋지 않다.
2) FIFO(First In First Out)
메모리에 가장 먼저 적재된 페이지를 선택해 교체하는 방식
하드웨어적으로 접근비트를 지원하지 않는 시스템에서 사용
장점
구현이 간단
단점
자주 사용되는 페이지도 교체되므로 낮은 성능
빌레이디의 역설(Belady's Anomaly): Page Fault를 줄이기 위해 메모리를 더 늘려 프레임 수를 늘렸는데 오히려 Page Fault가 더 많이 발생하는 현상
3) Optimum
앞으로 가장 오랫동안 쓰이지 않을 페이지를 선택해 교체하는 방식
가장 오랫동안 쓰이지 않을 페이지를 알 수 없으므로 이론적으로만 존재하는 방식이며 다른 정책과 성능을 비교하기 위한 참조용으로만 쓰인다.
4) LRU(Least Recently Used)
최근 가장 사용이 적은 페이지를 선택해 교체하는 방식
지역성 이론의 시간 지역성(최근 사용한 데이터가 앞으로 사용할 확률이 높다)에 따른 방식
장점
FIFO에 비해 효율적
단점
프로그램이 지역성을 띄지 않을 때 성능 저하
시간을 기록하기 위한 많은 bit 필요하며 시간이 오래되면 오버플로우 발생
접근 시간을 기록하기 위한 추가적 메커니즘 필요
5) Clock Algorithm
LRU와 비슷한 알고리즘으로, 모든 페이지에 접근 비트를 하나만 사용하여 일정 시간 간격마다 모든 페이지의 접근 비트를 0으로 초기화하며 페이지가 참조될 때 접근 비트를 1로 설정한다. 클락 핸드가 시계방향으로 페이지들을 순환하며 사용 비트가 0인 페이지를 선택해 교체하는 방식
6) Enhanced Clock Algorithm
접근 비트와 변경 비트를 동시에 두고 교체할 페이지를 선택하는 방식
교체 1순위: 접근 비트 0 / 변경 비트 0
교체 2순위: 접근 비트 0 / 변경 비트 1
교체 3순위: 접근 비트 1 / 변경 비트 0
교체 4순위: 접근 비트 1 / 변경 비트 1
7) 2차 기회 페이지 교체 알고리즘
하드웨어적으로 접근비트를 지원하지 않는 시스템에서 사용되어야 하는 FIFO의 단점이었던 자주 사용되는 페이지의 교체 문제를 개선한 방식으로, 먼저 들어왔지만 Page Fault 없이 페이지 접근에 성공한 경우 자주 사용되는 페이지이므로 해당 페이지를 큐의 맨 뒤로 이동시켜 수명을 연장시키는 알고리즘
성능은 FIFO보다는 좋으며 LRU보다 좋지 않다.
스레싱과 워킹셋
스래싱(Thrashing)이란?
컴퓨터 운영 체제에서 발생하는 현상으로, CPU 사용률을 높이기 위해 멀티 프로그래밍 정도를 늘리다보면 한정된 메모리 공간에 모든 프로세스를 올릴 수 없어 스왑 영역에 저장된다. 이로 인해 Page Fault를 처리하는 데 대부분의 시간을 소요해 CPU 사용률이 오히려 낮아지며 작업이 멈춘 것 같은 상태를 뜻한다.
영향
성능 저하
응답 시간 증가
해결 방법
메모리 크기 증가
프로세스에 적절한 페이지의 수 할당
한 프로세스에 많은 페이지 할당시 다른 프로세스의 페이지가 줄어들어 낮은 효율
한 프로세스에 적은 페이지 할당시 빈번한 Page Fault 발생으로 스래싱 발생
프로세스에 맞게 유지할 페이지 결정
지역성 이론에 따라 현재 메모리에 올라온 페이지는 다시 사용할 확률이 높다는 가정 하에 현재 메모리에 올라 온 페이지를 하나로 묶어 워킹셋으로 만든다. 워킹셋은 준비 상태에서 실행 상태로 되는 컨텍스트 스위칭시 사용
입출력 장치
주변 장치그래픽 카드, 하드디스크, SSD, 키보드, 마우스 등
주변장치의 내부 구조
각 하드웨어에 맞게 외부 인터페이스 존재
각종 레지스터: 입출력 작업 시 데이터를 저장하며 CPU가 필요로 할 때 메모리로 이동
메인보드에 있는 버스를 통해 연결
하나의 버스는 Address Bus, Data Bus, Control Bus로 이루어짐
따라서 I/O 디바이스는 이 세 가지 버스를 따로 받을 수 있다.
주변장치의 분류
데이터 전송 단위에 따라 캐릭터 디바이스와 블록 디바이스로 나뉜다.
캐릭터 디바이스
데이터 전송단위가 character로, 상대적으로 크기가 작다.
마우스, 키보드, 사운드카드, 직렬/병렬 포트
블록 디바이스
데이터 전송단위가 block으로, 상대적으로 크기가 작다.
하드디스크, SSD, 그래픽카드 등
입출력 버스 구조
초기의 입출력 버스
버스 하나에 주변 장치를 모두 연결해 사용
CPU가 작업을 진행하다가 입출력 명령을 만나면 직접 입출력장치에서 데이터를 가져오는 폴링방식 이용 → CPU 사용률 ↓
현재의 입출력 버스
위의 문제를 해결하기 위해 입출력 제어기(I/O Controller)와 여러 개의 버스 추가
CPU는 I/O 작업 발생 시 입출력 제어기에 이를 맡기고 다른 작업을 진행한다.
버스는 시스템 버스와 입출력 버스 두 개의 채널로 나뉜다.시스템 버스: 고속으로 작동하는 CPU와 메모리가 사용 + 그래픽 카드의 경우 고속 주변장치임에도 대용량 데이터를 다루기 때문에 시스템 버스 사용
입출력 버스: 주변장치가 사용
입출력 버스의 분리
입출력 제어기 사용으로 작업 효율을 높일 수 있지만, 저속 주변장치로 인해 고속 주변장치의 데이터 전송이 느려지는 문제를 해결하기 위해 고안저속 입출력 버스: 저속 주변장치(마우스, 키보드 등) 연결
고속 입출력 버스: 고속 주변장치(하드디스크 등) 연결
입출력 제어기의 역할
입출력 버스에서 온 데이터를 메모리로 옮긴다. CPU의 도움 없이 메모리에 접근할 수 있도록하는 DMA(Direct Memory Access) 제어기를 통해 데이터를 직접 메모리에 저장하거나 가져온다. CPU가 사용하는 메모리 영역과 DMA가 사용하는 메모리 영역을 구분해 Memory Mapped I/O라고 부른다.마우스와 키보드
마우스
광학 마우스의 작동 원리
마우스 밑면에 작은 카메라 탑재, 초당 1500회가 넘는 사진을 찍어 디바이스 컨트롤러 내 DSP로 보낸다.
DSP는 사진을 분석해 마우스의 x축 좌표와 y축 좌표 움직임 분석
디바이스 컨트롤러는 CPU에게 인터럽트를 보내고 마우스 드라이버가 동작해 데이터 읽음
마우스 드라이버는 운영체제에게 이벤트 신호를 보내고 운영체제는 이 이벤트를 Foreground 애플리케이션으로 전달
해당 애플리케이션은 받은 마우스 이벤트 처리, 해당 동작 수행키보드
키보드의 작동원리
사용자가 키 입력
디바이스 컨트롤러가 어떤 키를 입력 받았는지 알아냄
CPU에게 인터럽트를 보냄
키보드 드라이버는 운영체제에 이벤트를 보내고 운영체제는 이 이벤트를 Foreground 애플리케이션으로 전달
해당 애플리케이션은 받은 키보드 이벤트 처리, 해당 동작 수행하드디스크
블록 디바이스의 한 종류
하드디스크의 구조
스핀들(spindle): 플래터의 중심 축 막대
플래터(platter): 자기화된 원판으로 구성. 여러개의 트랙(track)으로 구성되어 있으며 표면에 자성이 있어 표면이 N극을 띄면 0, S극을 띄면 1로 인식
디스크암(Disk Arm): 플래터쪽을 향한 끝부분에 있는 읽기/쓰기 헤드(read/write head)로 플래터의 표면을 읽는다. 이 헤드들은 항상 같이 움직인다.
실린더(cylinder): 여러 개의 플래터에 있는 같은 트랙의 집합\
섹터(sector): 하드디스크의 가장 작은 단위
하드디스크 작동 원리
하드디스크에서 데이터를 읽어오는 과정은 다음과 같다.
유저 프로세스가 하드디스크의 특정 섹터에 접근 원함
"실린더 C로 가서 트랙 B에 있는 섹터 D를 읽어라"
seek: 디스크암은 헤드를 실린더 C로 이동.
seek Time: 헤드를 실린더로 이동시키는 시간으로, 하드디스크가 느린 이유
트랙 B의 섹터D가 헤드에 닿을때까지 스핀들 회전
헤드에 섹터D가 읽히면 작업 종료단점
속도 느리고 소음 발생
자석을 대면 데이터 손상
충격에 약함
Flash Memory
장점
전기적으로 데이터를 읽어 속도가 빠르고 조용하다
자석을 대도 데이터 보존
충격에 강함
단점
특정 부분에 데이터를 쓴 경우 덮어쓰기 불가 및 데이터 삭제 횟수가 정해져있어 같은 부분에 데이터 삽입과 삭제를 반복할 경우 망가져 사용 불가
파일과 파일시스템
파일들은 하드디스크나 SSD같은 저장 장치에 저장되는데, 사용자가 직접 저장하면 손상시킬 수 있어 운영체제가 안전하게 저장한다.
파일시스템이란?
운영체제가 파일을 관리하기 위해 둔 파일 관리자로, 파일 테이블을 이용한다.
파일시스템 기능
파일과 디렉토리 생성
파일과 디렉토리 수정/삭제
파일 권한 관리(다중 사용자 환경)
무결성 보장
백업 및 복구
파일 암호화로 파일 보호
파일은 하드디스크나 Flash Memory같은 블록 디바이스에 저장되기 때문에 전송 단위가 블록
저장장치의 전송 단위: 블록
바이트 단위로 접근해야하는 사용자를 위해 파일 시스템이 중간에서 바이트 단위로 변환
파일의 구조
헤더: 파일의 속성(파일 이름, 식별자, 유형, 크기, 시간, 저장 위치, 접근 권한, 소유자)
데이터
파일 디스크립터(File Descriptor)
운영체제는 파일을 관리하기 위해 정보를 보관하는 파일 제어 블록(File Control Block)을 가지는데, 이를 파일 디스크립터라고 한다. 각 파일마다 독립적으로 존재하고, 저장장치에 존재하다 파일이 오픈되면 메모리로 이동한다.
사용자는 직접 참조할 수 없고, 파일시스템이 건내준 파일 디스크립터로 파일에 접근할 수 있다.
파일은 데이터의 집합으로 이루어지는데, 이 집합을 어떻게 구성하느냐에 따라 종류가 나뉨
파일의 분류
1) 순차파일구조
파일의 내용이 연속적으로 이어지는 구조
작동 원리
사용자가 파일을 열기 위해 open()함수를 사용하면 파일 시스템은 파일 디스크립터를 사용자에게 전달한다. 파일 디스크립터는 파일의 맨 앞에 위치해 사용자가 읽기/쓰기를 시작하면 처음부터 진행한다. 다른 영역으로 가고싶다면 lseek() 함수를 이용해 파일디스크립터의 위치를 옮김
장점
모든 데이터가 순서대로 기록되어 공간의 낭비가 없고 구조가 단순
단점
특정지점으로의 이동이 어려워 데이터 삽입, 삭제를 위한 탐색 시간 소요
2) 직접파일구조
저장하려는 데이터를 해시함수를 통해 저장 위치를 결정하는 구조
예) 해시 테이블 자료구조, json
장점
해시함수 이용으로 데이터 접근 속도 빠름
단점
알맞은 해시함수를 잘 골라야하고 저장공간이 낭비될 가능성 존재
인덱스 파일구조
순차접근과 직접접근 방식의 장점을 취해 두 가지 모두 가능하게 한 구조
예) 재생목록
재생목록은 전부 순차 데이터로 저장되어있으며, 재생을 누르면 앞에서부터 뒤로 순차적 재생을 한다. 사용자가 듣고 싶은 노래를 클릭하면 인덱스 테이블의 해당 노래가 저장된 행에 접근해 블록 번호를 알아낸다. 순차 데이터의 해당 블록번호로 이동해 클릭한 노래가 재생될 수 있도록 함
디렉토리
디렉토리는 파일과 다른 디렉토리를 포함할 수 있는 컨테이너로, 파일을 주제나 유형별로 그룹화하여 조직화할 수 있다. 디렉토리도 하나의 파일로, 파일이 데이터를 저장한다면 디렉토리는 파일 정보를 저장한다.
디렉토리 구조
계층적 구조: 최상위에 루트 디렉토리(/)가 존재
초기
루트 디렉토리에만 디렉토리가 존재할 수 있고 다른 디렉토리에서는 하위 디렉토리를 만들 수 없는 구조
현재
다단계 디렉토리 구조로, 모든 디렉토리가 하위 디렉토리를 만들 수 있는 트리구조
파일과 디스크
디스크는 블록(1~8kB)으로 나뉘어있다.
파일시스템은 파일정보를 파일 테이블로 관리. 여기엔 파일이 시작하는 블록 위치 정보도 기록되어있다.
파일의 할당 방식
하나의 파일은 여러 개의 블록으로 이루어지는데, 이 블록들을 연결하는 방식에 따라 할당 방식 결정
연속 할당
파일을 구성하는 블록들을 디스크에 연속적으로 저장
파일의 시작 부분만 알면 파일의 전체를 찾을 수 있다.
외부 단편화가 발생해 실제로 쓰이지 않는다.
불연속 할당
파일을 구성하는 블록들을 디스크의 비어있는 공간에 분산 저장
이 분산된 블록은 파일시스템이 관리
1) 연결 할당
파일에 속한 데이터를 연결리스트로 관리
파일 테이블에는 시작 블록에 대한 정보만 저장하고 다른 블록은 연결리스트를 통해 접근
2) 인덱스 할당(i-node 방식)
파일 테이블의 블록 포인터가 데이터 블록에 직접 연결하는것이 아닌, 데이터들의 인덱스를 가지고 있는 인덱스 블록에 연결
데이터가 많아 테이블이 꽉 찬 경우 인덱스 블록을 더 만들어 연결하기 때문에 테이블 확장 가능
파일 크기가 작다면 데이터를 바로 참조하는 블록 포인터 이용, 파일 크기가 크다면 간접 포인터를 이용해 많은 데이터에 접근 가능
블록 크기에 따른 문제점
디스크를 구성하는 블록의 크기가 너무 작으면
공간 낭비는 줄지만 관리해야 할 블록의 수가 많아진다.
디스크를 구성하는 블록의 크기가 너무 크다면
관리해야하는 블록의 수는 적지만 내부단편화로 낭비되는 공간이 많아진다.
파일 저장, 삭제 방식
블록을 저장하려 할 때 마다 디스크의 빈 공간을 찾는 방식은 비효율적
파일 시스템은 효율적 관리를 위해 빈 공간을 모아둔 free block list 가짐
파일 삭제 시 파일 시스템은 파일의 모든 정보를 지우는 것이 아닌, 파일 테이블의 헤더를 삭제하고 블럭을 free block list에 추가
사용자는 파일이 삭제된 것처럼 느끼지만 사용했던 블록의 데이터는 그대로 남아 있어 포렌식을 통해 데이터를 복구할 수 있다.
회고
3주간의 스터디가 끝났다. 개념으로만 생각했던 문제들을 코드로 직접 구현해보는 시간을 가짐으로써 이론적인 공부 뿐만 아니라 코드를 작성할 수 있어서 도움이 많이 됐다고 생각한다. 초반에는 매일 강의 시간을 보며 이번에는 구현하는 시간이 얼마 쯤 될까, 이번에는 쉬웠으면 좋겠다 생각하며 두려운 마음이 앞서기도 했다. 하지만 스터디 마지막 주가 되니, 오히려 재미있게 느껴지기도 하고 마음만 먹으면 어떤 상황이든 코드로 구현할 수 있지 않을까? 생각하는 계기가 되기도 했다.
운영체제는 강의를 들으며 외부 지식과 자료도 참고하면서 참 재밌게 배웠다. 강의 자체가 영상으로 자세하게 설명되어있어 작동 원리나 과정을 배울 때 이해가 쏙쏙 됐다는 점이다. 책으로 공부했다면 같은 내용을 이해하기 위해 몇 번을 되감아 읽어봐야 했을지 모른다. 이 강의의 가장 좋았던 점이라고 할 수 있다. 비전공자도 이해할 수 있게끔 했다는 배려가 많이 느껴지는 강의였다.
또한 미션과 블로그를 작성하며 한번 듣고 끝낼 수 있었던 공부를 반복 학습하게 하는 강제성이 있어 하고자 하는 의지가 있는 사람에게 도움이 되는 활동이었다. 앞으로 배운 부분을 반복해 완전히 내 것으로 만드는 것 까지가 내 최종 미션이다. 화이팅!
댓글을 작성해보세요.
