[인프런 워밍업 클럽 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의 크기를 비교한다.논리주소 물리주소 = 논리주소 + Base Address논리주소 > Bound Address일 때메모리를 침범한 것으로 간주하고 에러 발생예시아래와 같이 세그먼트 테이블이 존재한다.예시 1)CPU에서 세그먼트 1번이 0x632번지로 접근MMU는 내부의 Segment Table Base Register를 이용해 세그먼트 테이블을 찾은 뒤 세그먼트 1번이 위치한 1번 인덱스 참조.논리주소가 632이고 1번 인덱스의 Bound Address가 1000이므로 논리주소 물리주소 = 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 AlgorithmLRU와 비슷한 알고리즘으로, 모든 페이지에 접근 비트를 하나만 사용하여 일정 시간 간격마다 모든 페이지의 접근 비트를 0으로 초기화하며 페이지가 참조될 때 접근 비트를 1로 설정한다. 클락 핸드가 시계방향으로 페이지들을 순환하며 사용 비트가 0인 페이지를 선택해 교체하는 방식6) Enhanced Clock Algorithm접근 비트와 변경 비트를 동시에 두고 교체할 페이지를 선택하는 방식교체 1순위: 접근 비트 0 / 변경 비트 0교체 2순위: 접근 비트 0 / 변경 비트 1교체 3순위: 접근 비트 1 / 변경 비트 0교체 4순위: 접근 비트 1 / 변경 비트 17) 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주간의 스터디가 끝났다. 개념으로만 생각했던 문제들을 코드로 직접 구현해보는 시간을 가짐으로써 이론적인 공부 뿐만 아니라 코드를 작성할 수 있어서 도움이 많이 됐다고 생각한다. 초반에는 매일 강의 시간을 보며 이번에는 구현하는 시간이 얼마 쯤 될까, 이번에는 쉬웠으면 좋겠다 생각하며 두려운 마음이 앞서기도 했다. 하지만 스터디 마지막 주가 되니, 오히려 재미있게 느껴지기도 하고 마음만 먹으면 어떤 상황이든 코드로 구현할 수 있지 않을까? 생각하는 계기가 되기도 했다.운영체제는 강의를 들으며 외부 지식과 자료도 참고하면서 참 재밌게 배웠다. 강의 자체가 영상으로 자세하게 설명되어있어 작동 원리나 과정을 배울 때 이해가 쏙쏙 됐다는 점이다. 책으로 공부했다면 같은 내용을 이해하기 위해 몇 번을 되감아 읽어봐야 했을지 모른다. 이 강의의 가장 좋았던 점이라고 할 수 있다. 비전공자도 이해할 수 있게끔 했다는 배려가 많이 느껴지는 강의였다.또한 미션과 블로그를 작성하며 한번 듣고 끝낼 수 있었던 공부를 반복 학습하게 하는 강제성이 있어 하고자 하는 의지가 있는 사람에게 도움이 되는 활동이었다. 앞으로 배운 부분을 반복해 완전히 내 것으로 만드는 것 까지가 내 최종 미션이다. 화이팅!

[인프런 워밍업 클럽 CS 2기] 3주차 미션

운영체제메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.레지스터가장 빠른 기억 장소로, CPU 내에 위치한다. 프로그램 실행 중 임시로 데이터나 명령어를 저장하며 컴퓨터가 꺼지면 데이터가 사라지는 휘발성 메모리입니다.캐시CPU 내에서 레지스터와 메인 메모리 사이에 존재하는 휘발성 메모리로, 자주 사용하는 데이터나 값을 미리 복사해 놓음으로써 데이터에 대한 액세스를 빠르게 할 수 있도록 돕는다.메인 메모리실제 운영체제와 다른 프로세스들이 올라가는 공간으로 휘발성 메모리입니다.보조 저장장치: 비휘발성 메모리로, 위의 메모리들에 비해 가격이 저렴합니다. SSD: 속도가 빠르고 조용하며 충격에 강하지만 특정 부분에 데이터를 쓴 경우 덮어쓰기가 불가능하고 데이터 삭제 횟수가 정해져 있어 같은 부분에 데이터 삽입과 삭제를 반복할 경우 망가져 사용할 수 없게 됩니다.하드디스크: 속도가 느리고 소음이 발생하며 충격에 약합니다. 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?경계 레지스터는 CPU 내에 존재하는 레지스터로, 하드웨어적으로 운영체제 공간과 사용자 공간을 나눠 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 합니다. 메모리 관리자는 사용자 프로세스가 경계 레지스터 값을 벗어났는지 검사하고 만약 벗어났다면 그 프로그램을 강제 종료합니다. 메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?가변 분할 할당 장점: 내부 단편화가 없습니다.단점: 외부 단편화가 발생하고 오버헤드가 발생합니다. 고정 분할 할당 장점: 구현이 간단하며 오버헤드가 적습니다.단점: 내부 단편화가 발생합니다. 4. CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?스래싱(Thrashing)이라고 하며 성능 저하 및 응답 시간 지연을 초래합니다.해결 방법은 다음과 같습니다.메모리 크기 증가프로세스에 적절한 페이지 수 할당프로세스에 맞게 유지할 페이지를 결정해 워킹셋 생성 HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요?HDD나 SSD가 없다면 컴퓨터는 운영 체제를 저장할 수 없기 때문에 부팅할 수 없습니다. 그러므로 컴퓨터를 실행시키는데 반드시 필요하다고 생각합니다. 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?파일 시스템의 블록 관리 방식에 그 이유가 있습니다.파일을 삭제하면 파일 시스템은 파일 테이블의 헤더만 삭제하고, 파일의 정보는 그대로 남아 있습니다. 그렇기 때문에 사용자는 파일이 삭제된 것처럼 느끼지만 블록의 데이터는 그대로 남아 있어 포렌식으로 파일을 복구할 수 있습니다. 자료구조와 알고리즘지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.버블 정렬(Bubble Sort)장점간단한 이해와 구현 가능단점낮은 성능시간 복잡도O(n²) 선택 정렬(Selection Sort)장점간단한 이해와 구현 가능단점낮은 성능시간 복잡도O(n²) 삽입 정렬(Insertion Sort)장점간단한 이해와 구현 가능단점낮은 성능시간 복잡도O(n²) 병합 정렬(Merge Sort)장점좋은 성능단점이해와 구현의 어려움시스템의 스택 크기가 큰 데이터를 정렬할 때 제한적시간 복잡도O(nlogn) 퀵 정렬(Quick Sort)장점좋은 성능단점이해와 구현의 어려움최악의 경우 시간 복잡도가 O(n²)까지 증가시간 복잡도O(nlogn) 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.메모이제이션은 재귀로 쉽게 구현할 수 있을 것 같을 때 사용하면 좋은 방법이지만 메모리를 많이 차지합니다. 메모리가 부족한 시스템에서 메모이제이션을 사용하다 스택 오버플로우가 발생할 수 있기 때문에 조금 시간을 들이더라도 적은 메모리로 빠른 성능을 낼 수 있는 타뷸레이션을 이용해 문제 해결을 위한 코드를 구현할 것 같습니다.

[인프런 워밍업 클럽 CS 2기] 2주차 미션

운영체제 FIFO 스케줄링의 장단점이 뭔가요?장점단순하며 직관적입니다.단점한 프로세스가 완전히 끝나야만 다음 프로세스 진행이 가능하다는 점에서 실행 시간이 짧고 늦게 도착한 프로세스가 실행 시간이 길고 빨리 도착한 프로세스의 작업을 기다려야 합니다.I/O 작업이 있을 시 CPU는 작업이 끝날 때 까지 쉬기 때문에 효율성이 낮습니다. SJF를 사용하기 어려운 이유가 뭔가요?두 가지의 이유가 있습니다.어떤 프로세스가 얼마나 실행될지 예측이 어렵습니다.Burst Time이 긴 프로세스는 Burst Time이 짧은 프로세스 작업이 계속 들어올 시 순서가 계속 밀려나 아주 오랜 시간 동안 실행되지 못할 수 있습니다. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요? 타임 슬라이스 값이 아주 작을 경우, 잦은 컨텍스트 스위칭 발생으로 오버헤드가 커집니다. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?CPU Bound Process는 CPU 사용 시간이 길기 때문에 CPU를 스스로 반납 하는 경우가 적고 타임 슬라이스 크기를 오버해 CPU를 강제로 빼앗기는 상황이 많습니다I/O Bound Process는 CPU 사용 시간이 짧기 때문에 CPU를 스스로 반납 하는 경우가 많습니다. 공유자원이란무엇인가요? 프로세스 간 통신(IPC)을 할 때 공동으로 이용하는 변수나 파일을 뜻합니다. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?교착상태가 발생하려면 다음의 네 가지 조건을 모두 충족해야 합니다.상호 배제: 어떤 프로세스가 리소스를 점유 했다면 다른 프로세스에게 해당 리소스는 공유 되면 안된다.비선점: 어떤 프로세스가 리소스를 점유 했다면 다른 프로세스는 해당 리소스를 빼앗을 수 없다.점유와 대기: 어떤 프로세스가 리소스를 가지고 있는 상태에서 다른 리소스를 원하는 상태원형 대기: 점유와 대기를 이루는 프로세스들이 원형을 이루는 형태 자료구조와 알고리즘 재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?자기 자신을 계속 호출하며 메모리가 가득 찰 때까지 반복합니다. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n){ if (n

[인프런 워밍업 클럽 CS 2기] 2주차 발자국

자료구조와 알고리즘 재귀(Recursion)재귀(Recursion)란 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다.재귀 함수는 말 그대로 자기 자신을 계속 호출하는 함수이다. 아래의 예시를 보자.function myFunction(number){ console.log(number); myFunction(number + 1); } myFunction(1);재귀 함수는 위의 결과처럼 자기 자신을 계속 호출해 메모리가 가득 찰 때까지 반복한다.이런 재귀 함수를 쓰임새 있게 만들려면 함수를 종료하는 탈출 조건(=기저 조건)이 반드시 있어야 한다.위의 코드에서 1~10까지의 데이터만 얻기 위해 기저 조건을 삽입 했을 때 비로소 원하는 데이터를 얻을 수 있다.function myFunction(number){ if(number > 10) return; console.log(number); myFunction(number + 1); } myFunction(1);재귀 함수의 이해콜스택함수가 호출되면서 올라가는 메모리 영역으로, 스택으로도 부른다. 스택이 가지는 특성인 FILO(First In Last Out)를 따라 먼저 들어온 데이터가 나중에 나간다.재귀 함수의 경우 함수 안에서 호출한 자신의 함수를 계속 스택 위로 쌓아 올리게 된다. 위의 코드를 그림으로 보면 다음과 같다. 그러므로 가장 위에 실행된 함수를 먼저 처리하고 먼저 실행한 단계 별로 내려가며 실행을 완료해 나가면 된다. 재귀적으로 생각하기반복적 실행반복문으로 구현했을 때보다 크게 이점이 되는 부분이 없고 오히려 메모리 공간을 많이 차지해 for문보다 성능이 낮다.하향식 계산하위 문제의 결과를 기반으로 현재 문제를 계산하는 방식인데, 이 계산 방법은 오직 재귀 함수로만 가능하며 재귀 함수를 사용하는 이유라고 할 수 있다.배열의 합, 문자열의 길이, 지수 함수를 모두 재귀 함수를 이용해 구현 해봤는데, 이전의 문제가 이미 해결됐다고 가정하는 식으로 코드를 작성하면 좀 더 쉽게 재귀 함수를 이용할 수 있다. 하노이의 탑재귀 함수를 배울 때 가장 기본으로 나오는 문제로, 규칙은 다음과 같다. 문제: 기둥 A에 꽃혀있는 3개의 크기가 다른 원반1,2,3을 기둥 B로 옮기기기둥은 A, B, C 세 가지가 존재한다.크기가 작은 순으로 원반1, 원반2, 원반3이 존재한다.규칙1. 한 번에 한 개의 원반만 옮길 수 있다.규칙2. 가장 위에 있는 원반만 옮길 수 있다.규칙3. 작은 원반 위에 큰 원반이 올 수 없다.위의 문제를 해결하기 위한 과정은 다음과 같다.path1기둥C로 원반3을 옮겨야 하므로 먼저 기둥B로 원반 1, 2를 옮겨야 한다.그런데 기둥B로 원반 1, 2를 옮기기 위해 먼저 기둥C로 원반 1을 옮겨야 한다.이를 콜스택에 넣는다고 생각하면 아래와 같고, 맨 위부터 수행하면 된다.path2기둥 B에 남아 있는 원반1,2를 기둥C로 옮겨야 한다.그런데 기둥C로 원반 1,2를 기둥C로 옮기기 위해 먼저 기둥A로 원반 1을 옮겨야 한다.이를 콜스택에 넣는다고 생각하면 아래와 같고, 맨 위부터 수행하면 된다.위의 흐름을 토대로 매개변수로 count, from, to, temp를 이용해 코드로 구현할 수 있다.시작(From): A목표(To): C임시(Temp): B 버블 정렬(Bubble Sort)왼쪽의 원소부터 인접한 원소와의 대소를 비교하여 더 큰 원소를 뒤쪽으로 보내며 자리를 바꾸는 정렬 방식버블 정렬의 원리다음과 같은 배열이 있다고 할 때, 버블 정렬이 진행되는 과정을 알아보자.array = [4,2,3,1]path 11-1. 4와 2를 비교해 더 큰 숫자가 앞에 있으니 둘의 자리를 바꾼다.[2, 4, 3, 1]1-2. 4와 3을 비교해 더 큰 숫자가 앞에 있으니 둘의 자리를 바꾼다.[2, 3, 4, 1]1-3. 4와 1을 비교해 더 큰 숫자가 앞에 있으니 둘의 자리를 바꾼다.[2, 3, 1, 4]차례대로 모든 원소를 한 번 지났으므로 path 1을 끝낸다.가장 큰 숫자인 4가 마지막에 위치했으므로 다음 path에서는 4를 제외하고 정렬을 수행한다.path 24를 제외하고 다시 맨 앞의 원소부터 비교해 나가기 시작한다.2-1. 2와 3을 비교했지만 규칙에 맞으니 넘어간다.[2, 3, 1, 4]2-2. 3과 1을 비교해 더 큰 숫자가 앞에 있으니 둘의 자리를 바꾼다.[2, 1, 3, 4]차례대로 모든 원소를 한 번 지났으므로 path 2를 끝낸다.다음으로 큰 수인 3이 세번 째에 잘 위치했으므로 다음 path에서는 3 또한 제외하고 정렬을 수행한다.path 3다시 맨 앞의 원소부터 비교해 나가기 시작한다.2-2. [1, 2, 3, 4]2와 1을 비교해 더 큰 숫자가 앞에 있으니 둘의 자리를 바꾼다.모든 원소가 작은 원소부터 큰 원소 순서대로 잘 자리했으니 정렬을 마친다. 버블 정렬의 성능버블정렬은 이해와 구현이 간단하다. 그렇다면 성능은 어떨까?배열의 개수가 n개일 경우 정렬을 해야하는 횟수는 (n-1)+(n-2)+(n-3)+...+2+1로, 이를 식으로 표현하면 n(n-1)/2 즉, (n²-n)/2가 된다.이를 빅 오로 표기하면 O(n²)의 성능을 갖는다고 할 수 있다. 이는 입력량에 따른 계산량이 급격하게 상승하여 좋은 성능이 아니다.버블 정렬의 장단점버블 정렬의 장점간단한 이해와 구현이 가능버블 정렬의 단점O(n²)의 낮은 성능 선택 정렬(Selection Sotr)배열의 정렬되지 않은 영역의 첫 번째 원소를 시작으로 마지막 원소까지 비교 후 가장 작은 값을 첫 번째 원소로 가져오는 정렬 방식 선택 정렬의 원리다음과 같은 배열이 있다고 할 때, 선택 정렬이 진행되는 과정을 알아보자.array = [6, 3, 4, 1, 2, 5]path 1첫 번째 원소인 6을 시작으로 한 칸씩 옆으로 이동하며 가장 작은 원소를 찾아 첫 번째 원소와 자리를 교체한다.[1, 3, 4, 6, 2, 5]차례대로 모든 원소를 한 번 지났으므로 path 1을 끝낸다.가장 작은 원소인 1이 첫번째에 위치했으므로 다음 path에서는 1을 제외한 부분에서 다시 정렬을 수행한다.path 21을 제외하고 두 번째 원소부터 비교해 나아가기 시작한다.두 번째 원소인 3을 시작으로 한 칸씩 옆으로 이동하며 가장 작은 원소를 찾아 3과 자리를 교체한다.[1, 2, 4, 6, 3, 5]차례대로 모든 원소를 한 번 지났으므로 path 2를 끝낸다.두 번째로 작은 원소인 2가 두 번째에 위치했으므로 다음 path에서는 1과 2를 제외한 부분에서 다시 정렬을 수행한다.path 31과 2를 제외하고 세 번째 원소부터 비교해 나아가기 시작한다.세 번째 원소인 4를 시작으로 한 칸씩 옆으로 이동하며 가장 작은 원소를 찾아 4와 자리를 교체한다.[1, 2, 3, 6, 4, 5]차례대로 모든 원소를 한 번 지났으므로 path 3을 끝낸다.세 번째로 작은 원소인 3이 세 번째에 위치했으므로 다음 path에서는 1, 2, 3을 제외한 부분에서 다시 정렬을 수행한다.path 41, 2, 3을 제외하고 네 번째 원소부터 비교해 나아가기 시작한다.네 번째 원소인 6을 시작으로 한 칸씩 옆으로 이동하며 가장 작은 원소를 찾아 6과 자리를 교체한다.[1, 2, 3, 4, 6, 5]차례대로 모든 원소를 한 번 지났으므로 path 4를 끝낸다.네 번째로 작은 원소인 4가 네 번째에 위치했으므로 다음 path에서는 1, 2, 3, 4를 제외한 부분에서 다시 정렬을 수행한다.path 51, 2, 3, 4를 제외하고 다섯 번째 원소부터 비교해 나아가기 시작한다.다섯 번째 원소인 6을 시작으로 한 칸씩 옆으로 이동하며 가장 작은 원소를 찾아 6과 자리를 교체한다.[1, 2, 3, 4, 5, 6]차례대로 모든 원소를 한 번 지났으므로 path 5를 끝낸다.다섯 번째로 작은 원소인 5가 다섯 번째에 위치했으며 하나 남은 원소 6은 자동으로 정렬되어 모든 원소가 작은 원소부터 큰 원소 순서대로 잘 자리했다.정렬을 마친다. 선택 정렬의 성능선택 정렬은 이해와 구현이 간단하다. 그렇다면 성능은 어떨까?배열의 개수가 n개일 경우 정렬을 해야하는 횟수는 (n-1)+(n-2)+(n-3)+...+2+1로, 이를 식으로 표현하면 n(n-1)/2 즉, (n²-n)/2가 된다.이를 빅 오로 표기하면 O(n²)의 성능을 갖는다고 할 수 있다. 버블 정렬과 같은 성능이라고 할 수 있다. 선택 정렬의 장단점선택 정렬의 장점간단한 이해와 구현이 가능선택 정렬의 단점O(n²)의 낮은 성능 운영체제(Operating System) CPU 스케줄링스케줄링의 성능 평가CPU 스케줄링의 성능을 평가하는 기준은 다음과 같다.평균 대기 시간프로세스 여러 개 실행시 모든 프로세스가 실행되기까지의 대기 시간의 평균 CPU 스케줄링의 종류FIFO(First In First Out)스케줄링 큐에 들어온 순서대로 CPU를 할당 받는 방식으로, 먼저 들어온 프로세스의 실행이 완전히 끝나야만 다음 프로세스 실행이 가능하다. ex) 마트 계산대장점단순하며 직관적단점한 프로세스가 완전히 끝나야만 다음 프로세스 진행이 가능하다는 점에서 실행 시간이 짧고 늦게 도착한 프로세스가 실행 시간이 길고 빨리 도착한 프로세스의 작업을 기다려야 한다는 것I/O 작업이 있을 시 CPU는 작업이 끝날 때 까지 쉬기 때문에 낮은 효율성평균 대기 시간Burst Time이 짧은 프로세스 먼저 실행시 평균 대기 시간이 짧다.Burst Time이 긴 프로세스 먼저 실행시 평균 대기 시간이 길다.프로세스의 Burst Time에 따라 평균 대기 시간의 차이가 크기 때문에 잘 쓰이지 않고, 일괄처리 시스템에 사용된다. SJF(Shortest Job First)FIFO 스케줄링에서 발견한 특징에 의해 고안된 스케줄링 방법으로, Burst Time이 짧은 프로세스를 먼저 실행하는 방식이다.이는 이론적으로는 FIFO보다 성능이 더 좋지만 문제점이 있다.어떤 프로세스가 얼마나 실행될지 예측 불가Burst Time이 긴 프로세스는 Burst Time이 짧은 프로세스 작업이 계속 들어올 시 순서가 계속 밀려나 아주 오랜 시간 동안 실행되지 못할 수 있다. RR(Round Robin)FIFO 스케줄링의 단점을 해결하기 위해 고안된 스케줄링 방법으로, 각 프로세스에게 일정 시간만큼 할당하여, 실행 중이던 프로세스의 할당 시간이 끝나면 CPU 할당을 끝내고 큐의 가장 뒤로 위치 시킨 뒤 다음의 프로세스를 실행하는 방식이다.타임 슬라이스(타임 퀀텀)프로세스에게 할당하는 일정 시간평균 대기 시간타임 슬라이스 값에 따라 크게 달라진다.타임 슬라이스 값이 아주 클 경우, FIFO 알고리즘과 같은 평균 대기 시간을 가진다.타임 슬라이스 값이 아주 작을 경우, 잦은 컨텍스트 스위칭 발생으로 오버헤드가 커진다.그러므로 사용자가 프로세스가 끊기지 않고 동시에 실행되는 것처럼 느끼면서 가장 큰 타임 슬라이스 값을 찾아야 한다. MLFQ(Multi Level Feedback Queue)RR 스케줄링을 기반으로 만들어졌으며 운영체제는 CPU Bound Process와 I/O Bound Process를 구분하며 CPU Bound Process는 타임 슬라이스를 크게, I/O Bound Process는 타임 슬라이스를 작게 주는 방식으로, 오늘날 운영체제에서 가장 일반적으로 쓰이는 스케줄링 기법이다.타임 슬라이스 선택 방식우선순위가 낮을수록 타임 슬라이스 크기가 커지고, 우선순위가 높을수록 타임 슬라이스 크기가 작은 큐 여러 개가 존재.모든 프로세스는 높은 우선순위의 큐에서 시작해 점점 큰 타임 슬라이스를 가진 낮은 우선순위의 큐까지 한칸씩 내려가며 만족하는 타임슬라이스를 가지는 우선순위 큐에 위치한다. CPU 사용률이 높은 프로세스의 경우 타임 슬라이스가 크므로 낮은 우선순위 큐에 많이 위치하게 되고, I/O 사용률이 높은 프로세스의 경우 타임 슬라이스가 작으므로 높은 우선순위 큐에 많이 위치한다.프로세스 동기화독립 프로세스와 협력 프로세스운영체제 내에서 프로세스들이 상호작용하는 방식에 따라 독립 프로세스(Independent Processes)와 협력 프로세스(Cooperating Processes)로 구분한다. 독립 프로세스(Independent Processes)독립 프로세스는 다른 프로세스의 실행에 영향을 받지 않으며, 다른 프로세스에 영향을 주지도 않는 프로세스이다.독립 프로세스의 특징자원의 독립성: 자신의 메모리 공간과 시스템 자원 독립적 사용실행의 독립성: 프로세스의 실행이 다른 프로세스의 상태나 실행에 비의존통신의 부재: 프로세스 사이에 명시적인 데이터 공유 또는 통신 부재협력 프로세스(Cooperating Processes)협력 프로세스는 다른 프로세스와 데이터를 공유하거나, 어떤 방식으로든 서로 영향을 주고받는 프로세스협력 프로세스의 특징데이터 공유: 프로세스간 데이터 또는 자원의 공유동기화: 프로세스 작업의 진행 속도에 따라 서로 동기화 가능통신: 프로세스 간 통신을 통해 서로 정보 교환그렇다면 협력 프로세스는 데이터를 공유하고, 작업을 조율하기 위해 어떻게 통신할까? 프로세스의 통신 종류스레드 간 통신(Thread Communication) 한 프로세스 내에서의 통신 프로세스 내의 쓰레드는 코드, 데이터, 힙영역 공유하고 스택은 자기 것을 소유하는데 이 중 데이터 영역에 있는 전역변수나 힙을 통해 통신프로세스 간 통신(Inter-Process Communication, IPC) 한 컴퓨터 내에서의 프로세스 간 통신 파일을 이용한 읽고 쓰기 운영체제가 생성한 파이프를 이용해 데이터를 읽고 쓰기 다른 컴퓨터의 다른 프로세스 간 통신 운영체제가 제공하는 소켓을 통한 통신 다른 컴퓨터에 있는 함수를 호출하는 RPC(원격 프로시저 호출)를 이용해 통신 공유자원과 임계구역공유자원이란?프로세스 간 통신(IPC)을 할 때 공동으로 이용하는 변수나 파일이 공유자원에 여러 프로세스가 동시에 접근할 때 발생할 수 있는 상황을 경쟁조건(Racing Condition)이라고 하며 그 상황에서 발생할 수 있는 문제는 다음과 같다.여러 프로세스가 공유하기 때문에 각 프로세스의 접근 순서에 따라 결과가 달라질 수 있다.컨텍스트 스위칭으로 시분할 처리를 하기 때문에 어떤 프로세스가 언제 처리될지 모른다.연산 결과를 예측하기 힘들다.위와 같은 문제들로 인해 임계구역 관리가 필요하다.임계구역(Critical Section)이란?여러 프로세스가 동시에 사용하면 안되는 영역으로, 임계구역 내의 코드를 실행하는 동안 해당 자원에 대한 독점적인 접근이 보장되어야 한다. 이는 동시 실행되는 프로세스나 스레드 사이에서 데이터의 일관성과 무결성을 유지한다. 임계구역 문제 해결을 위한 조건상호 배제(Mutual Exclusion) 메커니즘상호 배제 매커니즘의 요구사항 3가지임계영역엔 동시에 하나의 프로세스만 접근동시에 여러 요청이 있을 경우에도 하나의 프로세스 접근만 허용임계구역에 들어간 프로세스는 빠르게 다시 나옴 임계구역 문제 해결 기법1. 세마포어(Semaphore)공유자원을 필요로 하는 프로세스들은 대기 큐에 순서대로 대기 하고 먼저 온 프로세스에게 세마포어(정수형 변수=공유 변수의 개수, 예를 들어 공유 변수가 한 개일 때 s = 1)를 부여한다. 해당 프로세스의 실행이 끝나고 부여된 세마포어가 반납될 때 까지 다음의 프로세스는 이 세마포어를 받기 위해 기다려야 하는 방식예를 들어 코드로 살펴보자면 아래와 같다.먼저 온 프로세스는 wait() 함수로 세마포어를 부여 받고, 코드를 실행해 나간다. 이후에 온 프로세스는 세마포어를 부여 받기 위해 기다렸다가 이전의 프로세스가 코드 실행을 마치고 signal() 함수로 세마포어를 반납하면 그 때 세마포어를 부여 받을 수 있다. wait(변수); 실행 코드; signal(변수); 세마포어의 단점wait() 함수와 signal() 함수의 위치를 실수로 바꿔 잘못 사용할 가능성 존재 2. 모니터(Monitor)세마포어의 단점을 해결한 상호 배제 메커니즘으로, 운영체제가 아닌 프로그래밍 언어 차원에서 지원하는 방법wait() 함수와 signal() 함수로 해당 코드를 감쌀 필요 없이 프로그래밍 언어가 지원하는 언어로 간편하고 안전하게 상호 배제 메커니즘을 실현할 수 있다.예를 들어 JAVA에서는 임계구역을 표시하기 위해 동기화된 메서드 'synchronized method'를 사용한다. synchronized 구문이 실행되는 동안 여러 프로세스에서 모니터를 점유하려고 시도해도 할 수 없으며 해당 구문이 끝날 때까지 대기해야 한다. 교착상태(Deadlock)여러 프로세스가 서로 다른 프로세스의 작업이 끝나기를 기다리다 어떤 프로세스도 작업을 진행하지 못하는 상태로, 시스템의 자원을 비효율적으로 사용하게 만들며 최악의 경우 시스템의 정지를 초래할 수 있다.발생 이유공유 자원을 통해 여러 개의 프로세스가 자원을 공유하기 때문필요 조건교착상태가 발생하려면 다음의 네 가지 조건을 모두 충족해야 한다.상호 배제: 어떤 프로세스가 리소스를 점유 했다면 다른 프로세스에게 해당 리소스는 공유 되면 안된다.비선점: 어떤 프로세스가 리소스를 점유 했다면 다른 프로세스는 해당 리소스를 빼앗을 수 없다.점유와 대기: 어떤 프로세스가 리소스를 가지고 있는 상태에서 다른 리소스를 원하는 상태원형 대기: 점유와 대기를 이루는 프로세스들이 원형을 이루는 형태교착 상태 해결교착 상태 회피(Deadlock Avoidance)프로세스에 자원을 할당할 때 어느 정도 할당해야 교착 상태가 발생하는지 파악하여 교착 상태가 발생하지 않는 수준의 자원을 할당하는 방법전체 자원의 수와 할당된 자원의 수를 기준으로 안정 상태와 불안정 상태로 나눈다.안전 상태는 시스템이 프로세스의 모든 추가 요구를 충족시킬 수 있는 충분한 자원을 가지고 있어서, 모든 프로세스가 교착 상태 없이 실행을 완료할 수 있는 상태이며 불안전 상태는 교착 상태에 빠질 확률이 높아진 상태이다.운영체제는 최대한 안정 상태를 유지하기 위해 자원을 할당 은행원 알고리즘(Banker's Algorithm)다익스트라(Edsger W. Dijkstra)에 의해 고안된 교착 상태 회피 알고리즘 중 하나운영체제는 프로세스에 자원을 할당하기 전에 자신이 가지는 총 자원의 수(시스템 총 자원의 수)를 미리 알고 있어야 하며 각 프로세스는 자신이 필요한 최대 자원의 수(최대 요구 자원)를 운영체제에 미리 알린다. 위의 안정 상태에서 P1이 자원 요청을 할 경우 예상 자원이 사용 가능한 자원인 2보다 크기 때문에 자원을 할당하지 않는다.P2가 자원 요청을 하면 예상 자원이 사용 가능한 자원으로 할당 가능하기 때문에 P2에게 자원 2개를 할당 하고, P2는 2개의 자원을 더 받아 작업을 마치고 총 6개의 자원을 반납한다.사용 가능한 자원이 6개가 됐으므로 P1에 자원을 할당 할 수 있게 되어 자원 4개를 할당한다.반면 위와 같은 불안정 상태에서는 사용 가능한 자원이 1개뿐인데 반해 모든 프로세스의 요청 예상 자원이 2개로, 어떤 프로세스에게도 자원을 할당해 주지 못한다.하지만 프로세스가 최대 자원을 요청하지 않는다면 교착 상태에 빠지지 않을 수도 있다. 그래도 불안정 상태에 빠지지 않도록 유지하는 것이 좋다. 은행원 알고리즘의 단점높은 비용비효율적 위의 단점으로 인해 교착 상태의 발생은 허용하고, 교착 상태가 발생했을 때 해결하는 방식을 연구했다.교착상태 검출 방식1. 가벼운 교착 상태 검출타이머를 이용해 프로세스가 일정 시간 동안 작업을 진행하지 않는 상태 검출교착 상태 해결일정 시점마다 체크포인트를 만들어 작업 저장해놓은 뒤 타임 아웃으로 교착상태가 발생할 시 마지막으로 저장했던 체크포인트로 롤백 2. 무거운 교착 상태 검출자원 할당 그래프(Resource Allocation Graph)를 이용해 운영체제는 프로세스가 어떤 자원을 사용하는지 지켜보다가 교착 상태가 발생 시 검출이 그래프에서 교착 상태는 순환 대기(circular wait) 조건을 만족하는 사이클로 나타난다.교착 상태 해결교착 상태를 일으킨 프로세스 강제 종료 시킨 뒤 다시 실행시킬 때 체크포인트로 롤백 시킨다.단점운영체제가 지속적으로 자원 할당 그래프를 유지하고 검사해야해 오버헤드 발생 메모리의 종류레지스터가장 빠른 기억 장소로, CPU 내 위치. 컴퓨터가 꺼지면 데이터가 사라져 휘발성 메모리라고 부른다. 32bit, 64bit 등으로 크기를 구분해 32bit 레지스터를 가지는 CPU를 32bit CPU, 64bit 레지스터를 가지고 있으면 64bit CPU라고 한다.CPU는 계산을 할 때 메인 메모리에 있는 값을 레지스터로 가져와 계산, 계산 결과는 다시 메인 메모리에 저장한다.어셈블리 코드를 보면 기계어와 1:1 매칭이 되어 실제로 레지스터를 사용하는 것을 볼 수 있다. 캐시레지스터와 메인 메모리 사이에 존재하는 휘발성 메모리.레지스터는 속도가 매우 빠른 반면 메인 메모리는 속도가 느린 편이다. 메인 메모리에 있는 데이터를 레지스터로 옮기려면 오랜 시간이 걸리기 때문에 필요 할 것 같은 데이터를 미리 저장해 두는 역할을 한다. 성능의 이유로 여러개(L1, L2, L3..)를 둔다. 메인 메모리실제 운영체제와 다른 프로세스들이 올라가는 공간으로, 전원이 공급되지 않으면 데이터가 지워지는 휘발성 메모리.하드디스크나 SSD보다 속도는 빠르지만 가격이 비싸 데이터 저장보단 실행 중인 프로그램만 올리는 용도 보조 저장장치(SSD, 하드디스크)가격이 저렴하고 전원이 공급되지 않아도 데이터를 저장하는 비휘발성 메모리 메모리의 구조오늘날의 컴퓨터는 CPU와 메인 메모리가 함께 사용되어 모든 프로그램을 메모리 위로 올려 실행하는 폰 노이만 구조로, 하나의 프로그램만 메모리에 올라가던 예전에 비해 관리하기가 복잡해졌다.메모리는 1Byte(8bit)마다 주소를 가진다.32bit CPU는 레지스터 크기, ALU(산술논리연산장치), 버스의 크기가 32bit이며 CPU가 다룰 수 있는 메모리도 2³²으로 4GB이다.64bit CPU도 레지스터 크기, ALU(산술논리연산장치), 버스의 크기가 64bit이며 CPU가 다룰 수 있는 메모리도 2⁶⁴으로 거의 무한대에 가깝다.메모리를 컴퓨터에 연결하면 0번지부터 주소가 있다. 이를 물리 주소 공간이라 한다.사용자 관점에서의 공간은 논리 주소 공간이며, 이를 통해 물리 주소 공간에 접근한다. 메모리는 운영체제 영역을 따로 가지고 있어 이 영역이 침범 되면 위험할 수 있다.경계 레지스터CPU 내에 존재하는 레지스터로, 하드웨어적으로 운영체제 공간과 사용자 공간을 나눈다. 메모리 관리자가 사용자 프로세스가 경계 레지스터 값을 벗어났는지 검사하고 만약 벗어났다면 그 프로그램을 강제 종료한다. 절대주소와 상대주소사용자가 상대주소(논리주소)로 접근 시 메모리 관리자는 재배치 레지스터에 있는 프로그램의 시작 주소를 가지고 있어, 이 시작 주소에 상대주소를 더한 절대 주소(물리 주소)를 찾는다.메모리 관리자를 통해 모든 사용자 프로세스는 0x0번지부터 시작한다는 가정으로 편리하게 프로그램을 만들 수 있다. 메모리 할당 방식유니 프로그래밍 환경메모리 오버레이메모리보다 큰 프로그램을 실행하면 당장 필요한 부분만 먼저 메모리에 올리고 나머지 부분은 하드디스크의 스왑 영역에 저장하는 기법하지만 이는 스왑 영역에 있는 데이터 일부를 메모리로 옮기고, 메모리에 있는 데이터를 스왑 영역으로 옮기는 과정이 필요하기 때문에 동작이 느리다. 멀티 프로그래밍 환경1. 가변 분할 할당(Dynamic-Partition Allocation, 세그멘테이션)프로세스의 크기에 따라 메모리를 할당하는 방식장점프로세스 크기에 맞게 메모리가 할당되어 내부 단편화가 없다내부 단편화란?프로세스의 크기가 할당된 메모리 크기보다 작을 경우 발생되는 메모리 낭비 공간단점메모리의 할당과 회수 과정에서 작은 메모리 공간이 여러 곳에 분산될 수 있다. 이 공간을 합친 총 메모리 공간이 충분함에도 연속된 공간이 아니기 때문에 크기가 큰 프로세스가 들어갈 수 없어 낭비되는 외부 단편화 발생가변 분할 방식에서 외부 단편화가 생기는 경우 그 공간들을 합쳐주는 조각 모음을 실행하면 문제가 해결되지만 실행중인 다른 프로세스들을 중지하고 위치를 옮기는 과정이 필요해 오버헤드 발생 2. 고정분할 할당 (Fixed-Partition Allocation, 비연속 메모리 할당, 페이징)프로세스 크기와 상관없이 고정된 크기의 메모리를 할당하는 방식장점구현이 간단하고 오버헤드가 적다단점프로세스의 크기가 할당된 고정 메모리 크기보다 작을 경우 내부 단편화 발생분할되는 크기를 조절해 내부 단편화를 최소화 해줘야 한다. 3. 버디 시스템2의 승수로 메모리를 분할해 메모리 할당하는 방식으로, 가변 분할 할당 방식과 고정분할 할당 방식을 혼합해 단점을 줄임장점프로세스 크기에 따라 할당되는 메모리 크기가 달라지며 외부 단편화를 방지하기 위해 메모리 공간을 확보하는 것이 간단하다.내부 단편화가 발생하긴 하지만 공간 낭비가 적다. 회고 지난 주에 이어 알고리즘 같은 경우에는 강의를 보며 따라하기 전에 내가 미리 구현 해보는 시간을 가짐으로써 지난 주에 가졌던 아쉬움을 타파해보려고 노력한 점을 칭찬해주고 싶다. 보고 따라 치는 것만 하는 것 보다 먼저 구현해 봄으로써 내가 어떻게 사고하고 있고, 잘 안 됐던 부분에서는 어떤 지점에서 사고가 부족했는지 확실히 알 수 있었다.운영체제의 경우 강의를 토대로 다른 자료들도 함께 봄으로써 조금 더 폭넓게 이해하려고 노력했다. 그러다보니 생각보다 시간이 많이 소요되기도 한다. 정해진 시간 안에 조금 더 효율적으로 공부할 수 있도록 루틴을 짤 필요가 있을 것 같다.

[인프런 워밍업 클럽 CS 2기] 1주차 미션

운영체제 1. while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 } 위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요? ☞ CPU와 입출력 장치의 통신 방식 중 인터럽트 방식으로 변경해야 합니다. 폴링방식은 위에 나온 대로 입출력이 완료되는 시점을 몰라 주기적으로 확인해줘야 해 성능이 낮습니다. 이 문제점을 해결하기 위해 인터럽트 방식을 이용해야 합니다. 인터럽트 방식은 입출력 관리자에게 입출력 명령을 내린 뒤 CPU는 다른 작업을 진행하고, 입출력 완료 시 입출력 관리자가 CPU에게 신호를 주면 신호를 받은 CPU는 인터럽트 서비스 루틴(ISP)을 실행시켜 작업을 완료하여 CPU가 계속해서 다른 작업을 수행할 수 있습니다. 프로그램과 프로세스가 어떻게 다른가요? ☞ 프로그램(Program)은 애플리케이션 또는 앱이라고 하며, 사용자가 원하는 일을 처리할 수 있도록 프로그래밍 언어를 사용해 수행 절차를 표현해 놓은 명령어들의 집합입니다. 프로세스(Process)는 이 프로그램이 메모리에 올라가 실행 상태가 됐을 때의 '실행중인 프로그램'이다. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요? ☞ 멀티 프로그래밍은 CPU의 효율을 높이기 위해 고안된 것으로, 메모리에 여러 개의 프로세스가 동시에 올라가 있어 하나의 프로세스에서 입출력 작업 발생 시 이 작업이 완료될 동안 다른 프로세스를 실행할 수 있도록 합니다. 반면 멀티 프로세싱은 여러 개의 프로세서(CPU)가 서로 협력하여 작업을 병렬 처리함으로써 많은 양의 작업을 빠른 시간에 처리할 수 있도록 한 방식입니다. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요? ☞ 프로세스가 생성될 때, 운영체제는 해당 프로세스의 정보를 가지고 있는 PCB(Process Control Block)를 생성, 저장해 프로세스를 관리합니다. PCB는 다음과 같은 요소들로 구성됩니다.PCB의 구조1) 포인터: 프로세스의 한 상태에서 다른 상태로 전환될 때 저장2) 프로세스 상태: 현재 프로세스의 다섯 가지 상태(생성, 준비, 실행, 대기, 완료) 표시3) 프로세스 ID: 프로세스 식별 숫자 저장4) 프로그램 카운터: 다음에 실행될 명령어의 주소를 포함하는 프로그램 카운터 저장5) 레지스터 정보: 프로세스가 실행될 때 사용했던 레지스터 값 저장6) 메모리 관련 정보: 프로세스가 메모리에 있는 위치 정보, 메모리 침범을 막기 위한 경계 레지스터 값 등 저장7) CPU 스케줄링 정보: CPU 스케줄링에 필요한 우선순위, 최종 실행 시간, CPU 점유 시간 등 저장 컨텍스트 스위칭이란 뭔가요? ☞ 컨텍스트 스위칭(Context Switching)이란 프로세스 실행 중 다른 프로세스를 실행하기 위해 실행 중이던 프로세스를 저장하고 다른 프로세스의 상태 값으로 교체하는 작업입니다. 컨텍스트 스위칭이 발생하는 이유는 CPU 점유 시간 초과, I/O 요청 발생, 다른 종류의 인터럽트 발생 등이 있습니다. 프로세스 A와 프로세스 B의 컨텍스트 스위칭이 일어나는 과정은 다음과 같습니다.1) 실행 중이던 프로세스 A의 CPU 점유 시간 초과2) 운영체제가 인터럽트 발생3) 프로세스 A는 하던 일을 중단하고 현재 CPU의 레지스터 값 등을 PCB A에 저장4) PCB B를 참조해 이전 프로세스 B의 상태로 CPU의 레지스터 값 설정, 다음 명령어부터 다시 실행5) 실행 중이던 프로세스 B의 CPU 점유 시간 초과6) 운영체제가 인터럽트 발생7) 프로세스 B는 하던 일을 중단하고 현재 CPU의 레지스터 값 등을 PCB B에 저장8) PCB A를 참조해 이전 프로세스 A의 상태로 CPU의 레지스터 값 설정, 다음 명령어부터 다시 실행 자료구조와 알고리즘 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요. ☞ 교실의 학생 정보 데이터는 삽입 또는 삭제 발생이 거의 없고 열람이 주된 목적이기 때문에 참조 성능이 O(1)인 배열 자료구조를 선택합니다. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요. ☞ 먼저 들어온 데이터가 먼저 처리되는 선입선출(FIFO, First In First Out)의 특성을 가지는 큐(Queue) 자료구조를 선택합니다. 데크(Deque) 자료구조로도 이러한 처리가 가능하기 때문에 데크 자료구조를 이용해도 좋다고 생각합니다.

[인프런 워밍업 클럽 CS 2기] 1주차 발자국

자료구조와 알고리즘 자료구조(Data Structure)란 효율적인 데이터의 사용을 위해 데이터를 특정 방식으로 저장, 구성하는 방식이다.알고리즘(algorithm)이란 문제 해결 방법을 정의한 '일련의 단계적 절차'이자 어떠한 문제를 해결하기 위한 '동작들의 모임'이다.자료구조와 알고리즘을 함께 공부하는 이유는, 자료구조에 따라 알고리즘이 달라지기 때문이다. 즉, 어떤 방식으로 데이터를 저장하고 구성했냐에 따라 문제를 해결하는 방식이 달라진다. 또한 같은 자료구조일지라도 알고리즘은 여러가지가 될 수 있다.개발자라면 문제 해결을 위한 가장 좋은 알고리즘을 선택할 수 있어야 하며 가장 좋은 알고리즘을 위해 어떤 자료구조를 사용할지 결정할 수 있어야 한다. 그렇다면, 좋은 알고리즘이란 무엇일까?일반적으로 알고리즘의 속도를 성능의 척도로 사용하여 문제를 해결하는 속도가 빠를수록 좋은 알고리즘이라고 할 수 있다. 속도는 어떻게 측정할까? 시간복잡도시간복잡도(Time Complexity)란 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 뜻한다. 이 때의 시간은 초, 분을 뜻하는 것이 아니라 '문제해결을 위해 같은 방식을 몇 번이나 반복했는지'와 같은 반복 횟수를 뜻한다. 알고리즘에 대해 다음 세 가지 경우로 나누어 성능을 평가한다.최선의 경우: Big-Ω(빅-오메가).한 번에 데이터를 찾는 경우최악의 경우: Big-O(빅-오).마지막에 데이터를 찾는 경우평균의 경우: Big-Θ(빅-세타).배열 길이의 중간만큼 시간이 걸리는 경우가장 많이 사용하는 방법은 Big-O로, 앞으로 이야기하는 시간복잡도는 특정 알고리즘을 사용해 문제를 해결할 때 가장 오래걸리는 시간이다. 시간 복잡도에는 여러가지가 있는데, 입력량(데이터의 양)이 증가할수록 계산량도 비례하여 증가하는 일차함수의 모양을 띠는 O(n), 가장 성능이 좋은 O(1) 등이 있다. 자료구조 배열(Array)프로그래밍 언어에서 기본적으로 제공하는 자료구조로, 연속된 메모리 공간을 찾은 뒤 순서대로 데이터를 할당하고, 나머지 공간에 의미 없는 쓰레기 값을 저장한다.장점참조에 있어 O(1)의 좋은 성능을 보인다.단점데이터 삽입과 삭제에 대해 비효율적이다. 연결 리스트(LinkedList)저장하려는 데이터들을 메모리 공간에 분산해 할당한 뒤 이 데이터들을 노드로 연결하는 자료구조노드는 데이터를 담는 변수 하나와 다음 노드를 가리키는 변수 하나를 가지고 있어 다음 노드와 연결이 가능하다.연결 리스트는 첫 노드의 주소만 알고 있으면 다른 모든 노드에 접근이 가능하다.장점데이터의 삽입, 삭제에 유리단점참조에 있어 O(n)의 성능을 보여 비효율적이다. 데이터의 참조가 자주 발생한다면 배열을, 삭제 또는 삽입이 자주 발생한다면 연결 리스트를 쓰는 것이 효율적이다. 스택(Stack)First In Last Out(FILO) 즉, 가장 먼저 삽입된 데이터가 가장 나중에 나오는 특징을 가지는 자료구조이다.우리가 자주 사용하는 Ctrl+z(이전으로 되돌리기) 기능도 스택으로 구현된 것이다. 큐(Queue)First In First Out(FIFO) 즉, 먼저 들어간 데이터가 먼저 나오는 특징을 가지는 자료구조이다.FIFO 스케줄링에서 운영체제는 프로세스를 큐에 들어온 순서대로 넣고 CPU는 먼저 들어온 순서대로 프로세스를 처리한다. 덱(Deque)데이터의 삽입과 삭제를 head와 tail 두 군데에서 자유롭게 진행 가능한 자료구조이다. 해시 테이블(Hash Table)프로그래밍 언어에 따라 해시, 맵, 해시맵, 딕셔너리 등 다양한 이름으로 불린다. 해시와 테이블이 합쳐진 것으로, 특정 해시 함수에 따라 테이블의 Key와 Value에 매치된다.장점Key만 알면 Value에 O(1)의 성능으로 읽기가 가능하다.삽입, 수정, 삭제 또한 O(1)의 성능을 보인다.단점이미 어떤 Key에 대한 Value가 존재할 경우, 해당 Key에 대한 다른 데이터가 생성될 때 충돌이(Collision) 발생하는데, 이 충돌을 해결하기 위해 이전에 있던 Value와 새로 들어간 Value를 연결 리스트로 연결한다. 이후에 저장된 데이터에 접근하기 위해선 원래 있던 데이터에 먼저 접근 후 연결 리스트를 통해 다음 데이터로 접근한다. 이 때의 참조 성능은 O(n)이 된다. 그렇기 때문에 같은 Key에 여러 Value가 존재하지 않도록 데이터를 골고루 분산 시킬 수 있는 해시 함수의 선정이 중요하다.공간이 많이 필요해 메모리를 많이 차지한다. 셋(Set)데이터의 중복을 허용하지 않는 자료구조로, 해시 테이블을 이용해 구현할 수 있어 해시 셋(Hash set)이라고도 한다.해시 테이블의 Value값을 사용하지 않고 Key만 사용하여 구현한다. 즉, Key가 key이자 데이터가 되는 것이다. 운영체제(Operating System) 운영체제(Operating System)란 응용프로그램 또는 사용자가 컴퓨터 하드웨어를 편리하고 효율적으로 사용하게 하기 위하여 시스템 자원(메모리, 프로세서 등)을 관리하고 여러가지 프로그램이 필요로 하는 공통적인 서비스를 제공하는 소프트웨어이다. 운영체제의 역할프로세스 관리:여러가지 애플리케이션을 동시에 실행할 수 있도록 한다.메모리 관리: 여러가지 애플리케이션을 실행할 때 메모리를 관리한다.하드웨어 관리: 중요한 데이터를 보호하기 위해사용자의 하드웨어에 대한 직접적인 접근을 막는다. 파일 시스템 관리: 하드디스크에 파일들을 효율적으로 저장, 관리한다.운영체제의 구조커널: 프로세스와 메모리, 저장장치를 관리하는 운영체제의 핵심 부분. 사용자는 커널에 직접 접근하지 못하고, 인터페이스를 통해 접근 가능인터페이스: 사용자의 명령을 전달하고 실행 결과를 사용자에게 알려주는 역할시스템 콜: 사용자로부터 커널을 보호하기 위한 인터페이스. 하드웨어에 데이터 저장시 Write 함수를 통해 하드디스크의 빈 공간에 데이터를 저장해, 다른 데이터를 덮어쓰거나 침범하지 않도록 한다.드라이버: 하드웨어와 커널의 인터페이스. 운영체제는 많은 종류의 하드웨어를 지원하해야 하는데 마우스와 키보드같은 간단한 하드웨어 프로그램은 커널이 가지고 있기도 하지만, 보통 하드웨어는 그 하드웨어의 제조사가 드라이버를 만들어 제공한다. 사용자는 이런 디바이스 드라이버를 설치해서 사용을 할 수 있다. 컴퓨터와 하드웨어 구조오늘날 대부분의 컴퓨터는 프로그램 내장 방식의 폰 노이만 구조.메인보드: 다른 하드웨어를 연결하는 장치.CPU(Central Processing Unit, 중앙처리장치)CPU의 구성산술논리 연산장치(Arithmetic and Logic Unit, ALU): 데이터 연산제어 장치(Control Unit): 모든 장치들의 동작 지시, 제어레지스터: CPU 내에서 계산을 위해 임시로 보관하는 장치메모리RAM(Random Access Memory)랜덤으로 데이터를 읽어도 저장된 위치와 상관 없이 읽는 속도가 같다.전력이 끊기면 데이터를 읽어버린다. 메인 메모리로 사용ROM(Read Only Memory)전력이 끊겨도 데이터를 보관할 수 있지만 데이터를 한 번 쓰면 수정 불가컴퓨터 부팅과 관련된 BIOS 저장에 주로 쓰인다. CPU와 입출력 장치의 통신 방식폴링 방식: 입출력이 완료되는 시점을 몰라 주기적으로 확인해야 해 성능이 낮다.인터럽트: 폴링 방식의 단점을 해결하기 위한 방식. 입출력 관리자에게 입출력 명령을 내린 뒤 CPU는 다른 작업을 진행하고 입출력 완료 시 입출력 관리자가 CPU에게 신호를 주면 신호를 받은 CPU는 인터럽트 서비스 루틴(ISP)을 실행시켜 작업을 완료한다. 프로세스와 쓰레드프로그램(Program): 애플리케이션 또는 앱이라고도 불리며, 하드디스크 등과 같은 저장장치에 저장된 명령문의 집합체프로세스(Process): 실행 중인 프로그램, 즉 하드디스크에 저장된 프로그램이 메모리(RAM)에 올라갔을 때 프로세스의 구조Code: 자신을 실행하는 코드 저장Data: 전역 변수와 Static(정적) 변수가 저장Heap: 프로그래머가 동적으로 메모리를 할당할 수 있는 메모리 공간(malloc(), free())Stack: 지역 변수와 함수 호출을 했을 때 필요한 정보들 저장 PCB(Process Control Block)운영체제가 여러 개의 프로세스를 체계적으로 관리하기 위해 프로세스가 만들어지면 운영체제는 해당 프로세스의 정보를 가지고 있는 PCB를 생성, 저장한다. 이 PCB는 연결 리스트 자료구조로 저장된다.PCB의 구조포인터: 프로세스의 한 상태에서 다른 상태로 전환될 때 저장프로세스 상태: 현재 프로세스의 다섯 가지 상태(생성, 준비, 실행, 대기, 완료) 표시프로세스 ID: 프로세스 식별 숫자 저장프로그램 카운터: 다음에 실행될 명령어의 주소를 포함하는 프로그램 카운터 저장레지스터 정보: 프로세스가 실행될 때 사용했던 레지스터 값 저장메모리 관련 정보: 프로세스가 메모리에 있는 위치 정보, 메모리 침범을 막기 위한 경계 레지스터 값 등 저장CPU 스케줄링 정보: CPU 스케줄링에 필요한 우선순위, 최종 실행 시간, CPU 점유 시간 등 저장 프로세스 상태오늘날 운영체제는 시분할 프로세스로 여러 개의 프로세스를 돌아가며 실행하며, 이를 위해 다섯 가지 상태를 가진다. 생성(New): PCB 생성 및 메모리에 프로그램 적재 요청. 요청 승인 시 준비 상태로 전이준비(Ready): CPU를 사용하기 위해 기다림. CPU 할당대기(Waiting): 실행 중이던 프로세스가 입출력 요청을 하면 CPU는 입출력이 완료될 때까지 기다리지 않고 이 프로세스를 대기 상태로 놓은 채 다른 프로세스를 가져와 실행한다. 대기 상태의 프로세스의 입출력 작업이 완료되면 다시 CPU 할당 기회를 주기 위해 준비 상태로 보낸다.실행(Running): 준비상태에 있는 프로세스가 CPU 스케줄러에 의해 CPU를 할당받아 실행되는 상태. 실행상태의 프로세스 개수는 CPU의 개수와 같다. 실행상태에 있는 프로세스도 부여된 시간 초과시 할당된 CPU를 빼앗긴다. 이 때 프로세스는 다시 준비 상태로 돌아간다.완료(Terminated): 프로세스가 종료된 상태. 프로세스가 사용했던 데이터를 메모리에서 제거하고 PCB도 제거 컨텍스트 스위칭(Context Switching)프로세스 실행 중 다른 프로세스를 싱행하기 위해 실행중이던 프로세스를 저장하고 다른 프로세스의 상태값으로 교체하는 작업. CPU 점유시간 초과, I/O 요청, 다른 종류의 인터럽트 발생 시 컨텍스트 스위칭이 발생한다. 쓰레드(Thread)운영체제가 작업을 처리하는 단위는 프로세스로, 여러 작업을 요구할수록 프로세스 증가, PCB 증가 및 메모리에 각각의 코드, 데이터, 스택, 힙 영역 생성으로 컴퓨터가 느려지며 비용이 증가한다.한 개 이상의 쓰레드가 프로세스 내에 존재하며 쓰레드들은 그 프로세스의 PCB, 코드, 데이터, 힙 영역을 공유하며 스택은 각 쓰레드가 가지고 있다.작동 원리쓰레드 ID를 부여 및 Thread Control Block(TCB) 생성운영체제가 작업을 처리하는 단위가 프로세스에서 프로세스 내 쓰레드로 변경이제 여러 작업을 할 때 프로세스를 복사하는 것이 아닌 쓰레드를 생성프로세스와 쓰레드의 장단점안정성: 프로세스는 서로 독립적이기 때문에 하나의 프로세스에 이상이 생기더라도 다른 프로세스에는 영향이 없다. 반면 쓰레드는 자신이 속한 프로세스에 이상이 생기면 그 안에 있는 모든 쓰레드에도 문제가 생긴다.속도, 자원: 각각의 프로세스는 서로 고유한 자원을 소유(코드,데이터, 힙, 스택)하며 프로세스 간 통신을 할 때 IPC를 이용해야해 오버헤드가 크고 속도가 느리다. 반면 쓰레드는 스택을 제외한 자원을 공유하기 때문에 오버헤드가 적고 쓰레드 간 통신을 할 때 데이터를 공유할 수 있어 통신이 쉽지만 공유되는 공간에서 문제가 발생할 수 있다. CPU 스케줄링 CPU 스케줄링이란 운영체제(스케줄러)가 다음의 사항을 고려해 특정 방식으로 모든 프로세스에게 CPU를 할당/해제하는 작업이다.1. 어떤 프로세스에 CPU 리소스를 줄 것인가2. CPU를 할당받은 프로세스가 얼마의 시간동안 CPU를 사용해야 하는가 CPU 스케줄링 과정프로세스 실행 과정을 프로세스의 상태에 따라 조금 더 자세히 알아 보자.그 전에 먼저 이 과정에서 준비/대기 상태는 큐(Queue) 자료구조로 관리된다는 것을 인지하고 넘어가자. 큐(Queue) 자료구조는 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO, First In Fist Out) 방식의 자료구조이다.1. 프로그램을 실행해 프로세스와 프로세스의 정보를 담고 있는 PCB가 생성(New)되면 PBC는 준비(Ready) 상태의 다중큐에 들어가 실행되기를 기다린다.2. CPU 스케줄러는 준비 상태의 다중큐에 들어있는 프로세스 중 적당한 프로세스를 선택해 실행상태로 전환한다.3-1. 실행을 마치고 종료 시 프로세스는 완료(Terminated)된다.3-2. 하지만 프로세스가 CPU를 할당받아 실행되던 중 I/O 요청이 들어오면 대기(Waiting) 상태로 진입하는데, 이 때 I/O 작업 종류에 따라 분류된 큐(HDD, LAN, 키보드 등)로 들어가게 된다. 이 때 운영체제는 준비(Ready) 상태에 있던 다른 프로세스에 CPU를 할당해 실행시켜 CPU가 계속 일할 수 있도록 한다.4. I/O 작업 완료시 해당 큐에서 PCB를 꺼내 다시 준비(Ready) 상태의 다중큐에 위치시킨다. 이후 2번의 과정부터 다시 반복한다. 스케줄링 목표리소스 사용률: CPU 사용률 또는 I/O 디바이스 사용률 상승오버헤드 최소화공평성: 모든 프로세스에 공평하게 CPU 할당처리량: 같은 시간 내 더 많은 처리량 가지도록 함대기시간: 작업 요청 후 실제 작업 실행 전까지 대기 시간이 짧을 수 있도록응답시간: 대화형 시스템에서 사용자의 요청에 대해 빠른 응답목표 간 서로 상반되어 같이 달성할 수 없는 상황도 존재하기 때문에 사용하는 시스템에 따라 적절히 목표를 설정하여 스케줄링 한다. 회고생각보다 하루에 이해해야 할 양이 많았고, 구현 부분에서 시간이 많이 소요된다고 느꼈다. 하지만 이전까지 자료구조는 단순한 개념 중 하나라고만 생각했는데 구현을 해보니 조금 더 실체적으로 다가왔던 것 같다. 어렵다고도 생각했지만 그림과 함께 설명을 들으니 그래도 이해가 더 쉽고 빠르게 가능했다. 공부한 내용을 정리해 블로그에도 올리고, 깃헙 잔디도 심는 방식으로 발자취를 남긴 부분에서는 나 자신을 칭찬한다. 다만 지금까지는 구현할 때 알려주는 대로 따라 가고, 따라 치기만 했는데 다음에 그런 기회가 온다면 스스로 미리 구현해본다면 좋겠다고 생각했다.