[인프런 워밍업클럽 CS 2기] 특별 미션

특별 미션) 실수로 워밍업 클럽 출석을 빼먹었는데 우연히 데이터를 수정할 수 있는 권한이 주어졌습니다. 러너분의 이름(name)과 출석수(count)가 저장된 배열에서 여러분(나)의 데이터를 퀵정렬을 이용해 오름차순 정렬하고 가장 첫 번째 데이터인 여러분의 출석수를 변경하도록 코드를 작성해주세요. (퀵정렬 구현 부분도 변경) // 퀵 정렬 구현 function quickSort(arr, left, right) { if (left left && arr[rightStartIndex].count > pivot) { rightStartIndex--; } if (leftStartIndex // 출력 결과

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

운영체제메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.: 레지스터 - 가장 빠른 기억장소로 CPU 내에 존재하고 있고, 휘발성 메모리입니다캐시 - 레지스터는 CPU가 사용하는 메모리로 빠른데, 그에 비해 메인메모리는 너무 느린편이라 메인메모리에 있는 데이터를 레지스터에 옮기려면 한참 걸리기 때문에 필요할 것 같은 데이터를 미리 가져와서 캐시에 저장합니다. 캐시는 휘발성 메모리입니다.메인 메모리 - 실제 운영체제와 다른 프로세스들이 올라가는 공간으로 휘발성 메모리입니다.보조저장장치 - 프로그램 파일들을 저장하고, 비휘발성 메모리입니다.사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?: 경계 레지스터 입니다.메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?: 가변 분할 방식 장점 - 메모리에 연속된 공간에 할당되기 때문에 더 크게 할당되서 낭비되는 공간인 ‘내부 단편화’가 없습니다. 단점 - ‘외부 단편화’ 발생합니다.고정 분할 방식 장점 - 구현이 간단하고, 오버헤드가 적습니다. 단점 - 작은 프로세스도 큰 영역에 할당되서 공간이 낭비되는 ‘내부 단편화’가 발생합니다.CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?: 스레싱입니다. 근본적인 원인은 물리메모리의 크기가 부족한 것으로, 하드웨어적으로 해결하려면 메모리 크기를 늘리면 됩니다. 운영체제면으로 해결하게 하려면 프로세스가 실행되는 동안 해당 프로세스에게 맞는 적절한 페이지 수를 결정함으로써 해결합니다.HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요? 이유를 함께 적어주세요.: 일반적으로 꼭 필요합니다. 왜냐하면 컴퓨터 부팅을 위해 운영체제 실행을 해야하고, 파일 접근이나 프로그램 실행을 위해 필요하기 때문입니다.파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?: 파일이 삭제될 때 실제 데이터가 완전히 제거되지 않고, 파일 시스템의 관리 정보만 업데이트되기 때문입니다.만약 특정 파일 삭제 시, 파일시스템은 파일의 모든 정보를 지우는 것이 아니라 파일 테이블의 헤더를 삭제하고 free block list에 추가하는 방법으로 처리하기 때문에 포렌식으로 파일 복구가 가능합니다. 자료구조와 알고리즘지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.: 버블정렬 장점 - 이해와 구현이 간단함 / 단점 - 성능이 O(n^2)으로 좋지 않음 / 성능 - O(n^2)선택정렬 장점 - 이해와 구현이 간단함 / 단점 - 성능이 O(n^2)으로 좋지 않음 / 성능 - O(n^2)삽입정렬 장점 - 이해와 구현이 간단함 / 단점 - 성능이 O(n^2)으로 좋지 않음 / 성능 - O(n^2)병합정렬 장점 - 성능이 O(nlogn)으로 좋음 / 단점 - 이해와 구현이 어려움 / 성능 - O(nlogn)퀵정렬 장점 - 성능이 O(nlogn)으로 좋음 / 단점 - 이해와 구현이 어려움 / 성능 - O(nlogn) (피벗이 한쪽에 쏠리면 최악의 경우 O(n^2)이긴 함)메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.: 메모리가 부족한 시스템에서 문제를 해결할 때는 타뷸레이션을 선택하는 것이 더 좋을 것 같습니다.그 이유는 타뷸레이션은 메모이제이션에 비해 적은 메모리를 사용함에도 불구하고 빠른 시간을 보이기 때문입니다. 회고아직 내용을 완벽하게 이해하지 못하여 이번주 강의를 다시한번 복습할 예정인데, 그래도 미션을 통해 한번 더 살펴보면서 들었던 내용들을 머릿속에 떠올려볼 수 있어서 좋았습니다.또한 메모리 부족 시스템에서의 메모이제이션, 타뷸레이션과 선택과 같이, 현재 가지고 있는 환경에 따라 로직을 어떻게 만들지에 대한 고민이 실제 무엇인가 개발할 때도 중요하다는 생각이 들었습니다.📝⭐️

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

3주차 학습 내용 '그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)' Section 3(Unit 6~10)'그림으로 쉽게 배우는 운영체제' Section 8, 9, 10 '그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)' Section 3(Unit 6~10) Section 3. 알고리즘정렬 - 병합정렬(Merge Sort)divide and conquer - 분할 정복해결하기 힘든 문제가 발생한다면 이걸 한 번에 해결하려고 하지 말고, 해결하기 쉬울 정도로 문제를 쪼갠 다음 하나씩 해결하라원소를 하나일 때까지 쪼개고, 역순으로 순서에 맞게 하나의 배열로 병합해줌 (재귀함수를 호출한 모양과 비슷함)코드 구현function MergeSort(arr, leftIndex, rightIndex) { if(leftIndex idIndex) { for(let i = rightAreaIndex; i 병합정렬 성능성능측정 부분은 Merge() 함수 내 흩어진 배열을 합치는 부분하나의 데이터와 하나의 데이터가 두 개로 합쳐질 때 비교 연산을 두 번 함두 개의 데이터와 두 개의 데이터가 네개로 합쳐질 때 비교가 네 번 이뤄짐각 단계를 거칠 때마다 영역의 수가 반으로 줄어 logn이 됨분할된 배열을 병합할 때는 n개의 데이터를 n번 비교하므로 O(nlogn) 성능이 나옴병합정렬 장단점장점 - 성능이 좋음(O(nlogn))단점 - 이해와 구현이 어려움정렬 - 퀵정렬(Quick Sort)분할 정복 알고리즘으로 재귀를 사용함퀵정렬 설명정렬하기 전에 배열에 있는 숫자 중 하나를 피벗으로 설정해줌leftStartIndex는 피벗보다 큰 값을 만나면 멈춤rightStartIndex는 피벗보다 작은 값을 만나면 멈춤leftStartIndex, rightStartIndex의 값을 스왑해줌서로 지나쳤다면 더이상 진행하지 않음이상태에서 피벗과 rightStartIndex 값 스왑해줌피벗값을 기준으로 오른쪽, 왼쪽을 정렬해줌코드 구현function quickSort(arr, left, right) { if(left = arr[leftStartIndex]) { leftStartIndex++; } while(rightStartIndex = arr[rightStartIndex]) { rightStartIndex++; } if(leftStartIndex 퀵 정렬의 성능피벗이 매번 배열의 반을 가르는 경우O(nlogn)피벗이 배열을 반으로 가르지 않고 한쪽에 쏠리는 경우 - 최악의 경우O(n^2)성능만 보면 병합 정렬이 더 좋다고 볼 수 있는데, 실제로 비교하면 퀵정렬이 더 적은 비교와 더 적은 메모리 공간을 차지하기 때문에 더 좋은 알고리즘으로 평가됨퀵정렬의 장단점 - 병합정렬과 동일동적 프로그래밍 - 메모이제이션재귀의 단점피보나치 수열피보나치 수열 코드function fibonacci(n) { if(n == 0 || n == 1) return n; return fibonacci(n - 2) + fibonacci(n - 1); } console.log(fibonacci(5)); 성능이 좋지 못함 - 반복 계산단점 - 이미 계산했던 것을 다시 또 계산하게 됨메모이제이션재귀의 문제점 해결방법계산 결과를 저장해두고 사용해시테이블 사용피보나치 수열 코드를 메모이제이션을 사용해 수정function fibonacci1(n) { if(n == 0 || n == 1) return n; return fibonacci(n - 2) + fibonacci(n - 1); } function fibonacci2(n) { if(n == 0 || n == 1) return n; if(memo[n] == null) { memo[n] = fibonacci2(n - 2, memo) + fibonacci2(n - 1, memo); } return memo[n]; } let start = new Date(); console.log(fibonacci1(40)); let end = new Date(); console.log("fibonacci1 함수 실행시간 : ${end - start}ms"); let start = new Date(); console.log(fibonacci2(40, {})); let end = new Date(); console.log("fibonacci2 함수 실행시간 : ${end - start}ms"); 메모이제이션 장단점장점성능 O(n)을 보임재귀덕분에 하향식 계산 방식으로 어려운 문제를 간단하게 해결할 수 있음중복 계산을 하지 않아서 속도가 빠름단점메모리 영역을 사용함(ex, 캐시)동적 프로그래밍 - 타뷸레이션상향식 계산 방식으로, 계산에 필요하지 않을 수 있는 값도 미리 계산해 테이블에 저장해둠코드 구현function fibonacci1(n) { if(n == 0 || n == 1) return n; return fibonacci(n - 2) + fibonacci(n - 1); } function fibonacci2(n) { if(n == 0 || n == 1) return n; if(memo[n] == null) { memo[n] = fibonacci2(n - 2, memo) + fibonacci2(n - 1, memo); } return memo[n]; } function fibonacci3(n) { if(n 성능메모이제이션은 여러번의 함수 호출로 메모리 공간에 스택을 차지하고, 메모이제이션을 위한 해시 테이블 공간까지 차지하기 때문에 메모리를 더 많이 사용함타뷸레이션은 적은 메모리 사용임에도 불구하고 빠른 시간을 보임메모이제이션 vs 타뷸레이션메모이제이션재귀를 이용해 문제를 하향식으로 해결함재귀만 이용한다면 중복 계산을 하기 때문에 성능의 문제가 발생했는데 계산 결과를 저장하는 방식으로 단점을 해결함해결하기 힘든 문제를 하향식으로 접근하고, 더 많은 메모리를 이용해 성능을 향상시킴이러한 이유로 분할 정복을 해결할 때 재귀가 더 직관적이라면 메모이제이션을 이용하는 것이 유리함타뷸레이션재귀가 직관적이지 않을 때는 상향식 접근인 타뷸레이션을 이용해 메모리도 절약하고 속도도 빠르게 할 수 있음 '그림으로 쉽게 배우는 운영체제' Section 8, 9, 10Section 8. 가상메모리가상메모리 개요컴퓨터마다 실제 메모리 크기가 다른데, 만약 운영체제나 프로세스가 특정 크기에서 동작하도록 만들어졌다면 그 크기보다 작은 메모리를 가진 컴퓨터에서는 실행되지 않음 → 가상 메모리는 이 문제를 해결함가상 메모리프로세스는 운영체제의 영역이 어디있는지, 물리 메모리의 크기가 얼마나 큰지 몰라도 됨프로세스는 메모리 관리자에게 요청만 하면됨메모리 관리자는 프로세스의 요청이 있으면 그에 맞는 물리 메모리로 연결시켜줌가상메모리의 크기는 이론적으로는 무한대이지만 실제로는 물리 메모리 크기와 CPU의 비트 수로 결정됨 (ex, 32bit CPU(대략 4GB) → 가상 메모리 크기도 4GB가 됨)가상메모리로 프로세스들 실행시키는 방법물리메모리 내용의 일부를 하드 디스크에 있는 스왑영역으로 옮기고, 처리가 필요할 때 물리 메모리로 가져와 실행시키기 때문에 운영체제와 프로세스 5개를 전부 실행시킬 수 있음 동적주소변환(Dynamic Address Translation)메모리 관리자는 물리메모리와 스왑영역을 합쳐서 프로세스가 사용하는 가상주소를 물리주소로 변환함 동적 주소 변환을 거치면 프로세스는 마음대로 사용자 데이터를 물리 메모리에 배치할 수 있음메모리 관리자의 역할물리 메모리를 어떻게 나눌지프로세스를 어디다 배치할지부족한 물리 메모리는 어떻게 처리할지 등등을 위해 복잡한 과정을 거침가상 메모리 시스템의 메모리 할당 방법가상 메모리 시스템에서는 운영체제 영역을 제외한 나머지 영역을 일정한 크기로 나누어서 프로세스에게 할당함할당하는 방식은 메모리 분할방식과 마찬가지로 ‘가변 분할 방식’, ‘고정 분할 방식’으로 나뉨 가변 분할 방식(세그멘테이션)단점 - 외부 단편화고정 분할 방식(페이징)단점 - 내부 단편화각각의 단점을 보완한 ‘세그멘테이션-페이징 혼용기법 ’ 사용세그멘테이션-페이징 혼용기법가상메모리 시스템에서 가상주소는 메모리나 스왑영역 한 곳 중에 위치메모리 관리자는 가상주소와 물리주소를 일대일 매핑 테이블로 관리함 세그멘테이션(배치정책)가변 분할 방식을 이용하는 세그멘테이션 기법프로그램은 함수나 모듈등으로 세그먼트 구성프로그램(사용자) 관점 메모리 - 코드, 데이터, 힙, 라이브러리, 스택 각각 구성(인접할 필요 없음)프로세스 관점 메모리 - 코드, 데이터, 힙, 스택 영역을 서로 인접한 것처럼 바라봄논리주소사용자, 프로세스, CPU가 바라보는 주소실제 물리주소로 변환은 중간에서 메모리 관리자(MMU)가 해줌메모리 관리자가 논리주소 → 물리주소 변환 방법메모리 관리자가 가지고 있는 세그멘테이션 테이블에 Base Address, Bound Address(Segment 크기) 정보가 저장되고 이걸 이용해 물리 메모리 주소를 계산함운영체제는 컨텍스트 스위칭을 할 떄마다 메모리 관리자 내에 Segment Table Base Register를 해당 프로세스의 것으로 값을 바꿔줘야함 → 굉장히 무거운 동작논리주소가 Bound Address보다 작다면, 논리주소 + Base Address 로 물리주소를 구함논리주소가 Bound Address보다 크다면, 메모리를 침범했다고 생각하고 에러를 발생세그멘테이션 장점메모리를 가변적으로 분할할 수 있고, 코드 영역, 데이터 영역, 스택 영역, 힙 영역을 모듈로 처리할 수 있음 → 공유와 각 영역에 대한 메모리 접근보호가 편리함세그멘테이션 단점가변 분할 방식의 단점인 “외부 단편화”가 발생함페이징(배치정책)고정분할방식을 이용한 페이징세그멘테이션 기법은 외부 단편화 문제가 있기 때문에 이를 해결하기 위해 고안됨페이징메모리를 할당할 때 정해진 크기의 페이지로 나눔모든 페이지는 크기가 같기때문에 관리가 편하고, 일정한 크기로 나눴기 때문에 외부 단편화 현상이 일어나지 않음논리주소공간에서의 페이징 → 페이지물리주소공간에서의 페이징 → 프레임 페이징의 주소변환 방법메모리 관리자가 “페이지 테이블”을 통해 CPU에서 전달받은 논리주소가 몇번 페이지, 오프셋은 얼마인지 알아냄메모리 관리자 내에 Page Table Base Register(PTBR)를 이용해서 물리 메모리에 있는 페이지 테이블을 찾고, 페이지 번호를 인덱스로 프레임 번호를 알아내고, 오프셋을 이용해 물리주소로 변환을 함페이지 테이블에 Invalid로 표시되어 있으면 스왑영역, 즉 하드디스크레 저장되어 있다는 의미임PTBR은 운영체제가 컨텍스트 스위칭을 할 때마다 해당 프로세스의 것으로 업데이트 해줌 세그멘테이션 vs 페이징 차이점페이지의 크기가 다름세그멘테이션은 프로세스마다 크기가 달라 Bound Address를 가지고 있지만, 페이징은 모든 페이지의 크기가 동일해서 크기를 표현하는 Bound Addresss는 필요하지 않음페이징은 이런 특성때문에 외부단편화는 발생하지 않지만 내부단편화가 발생함 (정해진 크기의 페이징보다 프로세스의 정보가 작으면 그만큼 공간이 낭비됨)세그멘테이션의 단점과 비교하면 많은 고간이 낭비되는게 아니라서 심각하게 생각하지 않음세그멘테이션은 논리적인 영역별로 세그먼트를 나눔(코드, 데이터, 스택, 힙 영역), 그러나 페이징은 페이지의 크기가 고정되어 있어 논리적인 영역별로 나누는 것이 아니라 페이지로 나누기 때문에 논리적인 영역을 나눌 수 없음 그래서 특정 영역만 공유하거나 권한을 부여하는게 더 어려움페이징에서 가장 신경써야하는 것은 페이지 테이블 크기임각 프로세스마다 페이지 테이블을 가지고 있는데 프로세스가 많아질수록 페이지 테이블도 많아지기 때문에 프로세스가 실제로 사용할 수 있는 메모리 영역이 줄어듦실제로 메모리 관리자가 참조하는 페이지 테이블도 물리 메모리의 운영체제 영역에 저장되어 있기 때문에 페이지 테이블 크기가 너무 크면 사용자 영역이 부족하게 됨 → 페이지 테이블의 크기를 적절하게 유지하는 것이 굉장히 중요함페이지드 세그멘테이션(배치정책)페이징과 세그멘테이션의 각각의 장점을 취한 방식 → 새로운 단점이 생기기도 함세그멘테이션 장점가변 분할 방식이라서 코드 영역, 데이터 영역, 스택 영역, 힙 영역을 세그먼트로 나눠서 관리할 수 있음그에 따라 다른 프로세스와 공유하기도 편하고, 각 영역에 대한 메모리 접근보호를 하기가 쉬움페이징 장점고정분할 방식으로 메모리를 효율적으로 관리할 수 있음메모리 접근 권한메모리의 특정 번지에 부여된 권한으로 읽기(Read), 쓰기(Write), 실행(Execute) 세 가지가 있음 프로세스는 코드 여역, 데이터 여역, 스택 영역, 힙 영역이 있는데 각 영역마다 접근 권한이 있음 코드 영역프로그램 그 자체이기 때문에 수정되면 안되므로, 읽기와 실행 권한만 있음데이터 영역일반변수, 전역변수, 상수로 선언한 변수가 저장되기 때문에 읽기 권한이 있고, 쓰기 권한은 있거나 없거나 함 실행권한은 없음스택, 힙 영역읽기, 쓰기 권한이 있고, 실행권한은 없음메모리 접근권한에 대한 검사는 가상주소에서 물리주소로 변환될 때마다 일어나는데, 만약 권한을 위반하면 에러를 발생시킴 페이지드 세그멘테이션세그멘테이션 기법 - 세그멘테이션 테이블은 Base Address와 Bound Address로 구성됨페이징 기법 - 페이지 테이블은 프레임 번호로 구성됨 위의 둘을 혼합해 페이지드 세그멘테이션으로 만듦 (각각의 역할은 이름만 바꼈을 뿐 달라진 것은 없음)세그멘테이션 테이블에 권한 비트를 추가함Base Address는 페이지 넘버로 바뀜Bound Address는 이 세그먼트 페이지 개수로 바뀜 페이지드 세그멘테이션의 단점은 물리메모리에 접근하기 위해서 메모리에 접근을 두 번해야 된다는 것첫번째, 세그멘테이션 테이블을 참조할 때두번째, 페이지 테이블을 참조할 때 일어남위의 단점 때문에 운영체제는 페이징과 페이지드 세그멘테이션 기법을 적절히 섞어서 사용함디맨드 페이징(가져오기 정책)프로세스가 실행될 때, 프로세스를 이루고 있는 코드영역, 데이터영역, 힙영역, 스택영역과 같은 모듈이 모두 메모리에 올라와 실행된다고 알고 있음하지만 실제로는 모든 모듈이 메모리에 올라오는 것이 아니라 필요한 모듈만 올라와서 실행됨도널드 커누스의 발견 - 90:10 법칙90%의 시간이 10% 코드에서 보내는 것 → 지역성 이론이라고 함지역성(두가지)공간의 지역성현재 위치에서 가까운 데이터에 접근할 확률이 높다는 것시간의 지역성최근 접근했던 데이터가 오래전에 접근했던 데이터보다 접근할 확률이 높음goto문 - 지역성 이론에 따라 성능이 좋지 않기 때문에 쓰지 않는 것을 추천지역성 이론은 조만간 쓰일 데이터만 메모리에 올리고 당분간 필요하지 않을 것 같은 데이터는 스왑영역으로 보내 성능을 향상시킴 디맨드 페이징은 조만간 필요할 것 같은 데이터를 메모리로 가져오고 쓰이지 않을 것 같은 데이터는 스왑영역으로 이동시키는 정책ex, 포토샵포토샵은 본 프로그램 외에도 이미지에 효과를 주는 외부 필터들이 있는데, 이 필터들을 포토샵과 같이 메모리에 모두 올리면 메모리를 많이 차지해서 프로그램이 더 무거워짐그래서 본 프로그램만 메모리에 올리고 외부 필터들은 사용자의 요청이 있을 때만 메모리로 가져오는 것이 메모리도 절약되고, 메모리를 효율적으로 관리할 수 있고, 프로세스의 응답속도도 빨라짐 메모리 계층구조메모리는 레지스터, 캐시, 메인 메모리, 보조저장장치로 나눌 수 있음메인 메모리에 접근하는 시간 레지스터CPU 내에 존재하고, CPU의 한사이클에 접근할 수 있어서 굉장히 빠름캐시CPU의 수 사이클에서 수십 사이클에 접근 가능메인 메모리CPU의 수백 사이클에 접근 가능보조저장장치(HDD, SSD)CPU의 수백만 사이클에 접근 가능디맨드 페이징은 스왑영역을 보조저장장치에 저장하는데, 성능향상을 위해서는 스왑영역으로 데이터를 이동시키는 것을 최소화 시켜야 함가상 메모리의 크기 = 물리 메모리 크기 + 스왑영역임스왑인, 스왑아웃 스왑인 - 스왑영역에서 물리메모리로 데이터를 가져오는 것스왑아웃 - 물리메모리에서 스왑영역으로 데이터를 내보내는 것메모리 관리자는 페이지 테이블을 참조해서 물리 메모리가 있는 프레임을 알아내거나 스왑영역의 위치를 알아내야 하는데, 이를 위해 페이지 테이블에는 여러가지 비트가 있음페이지 테이블을 이루고 있는 한 행을 페이지 테이블 엔트리(PTE)라고 부름 페이지 테이블 엔트리(PTE) 접근 비트페이지가 메모리에 올라온 후 데이터에 접근이 있었는지 알려주는 비트메모리에 읽거나 실행 작업을 했다면 1로 바뀌게 됨변경비트페이지가 메모리에 올라온 후 데이터의 변경이 있었는지 알려주는 비트메모리에 쓰기 작업을 했으면 1로 바뀌게 됨유효비트페이지가 물리 메모리에 있는지 알려주는 비트만약 유효비트가 1이라면 페이지가 스왑영역에 있고, 0이라면 물리 메모리에 있다는 의미임읽기, 쓰기, 실행 비트권한 비트로 해당 메모리에 접근권한이 있는지 검사하는 비트프로세스가 가상 메모리에 접근요청을 했을 때 메모리 관리자는 페이지 테이블을 보고 물리 메모리의 프레임을 찾아냄만약 물리 메모리에 없다면 Page Fault라는 인터럽트를 발생시킴Page Fault가 발생하면 보조저장장치의 스왑영역에 접근하게 되고 해당 프로세스는 대기상태가 됨스왑영역에 있는 데이터가 메모리에 올라가는 작업을 시작하고, 메모리에 올라갔다면 대기상태에 있던 프로세스는 다시 실행하게 됨물리 메모리와 스왑영역에서 어떻게 참조되는가(세가지)스왑이 필요없는 경우 ex, 프로세스가 페이지 0을 요청페이지 테이블의 0번 인덱스를 살펴보면 유효비트 0, 프레임 넘버 1 → 해당 주소가 물리메모리의 1번 프레임물리 메모리에 있는 1번 프레임에 접근해 데이터를 참조함스왑영역에 있는 데이터를 참조하는 경우ex, 프로세스가 페이지 2번을 요청 페이지 테이블의 2번 인덱스를 살펴보면, 유효비트가 1이고 프레임 넘버가 2임 → 페이지가 스왑영역 2번에 있다는 뜻물리메모리에 적절히 빈 공간을 찾음스왑영역 2번에 저장된 C를 물리메모리 3번 프레임으로 가져오고페이지 테이블에서 해당 엔트리의 유효비트를 0으로, 프레임 넘버를 3으로 수정함프로세스에게 데이터를 참조하게 해줌물리메모리가 꽉찼을 때 스왑영역에 있는 데이터를 참조하는 경우ex, 프로세스가 페이지 1번을 요청했다고 가정 페이지 테이블 1번 인덱스를 살펴보면, 유효비트 1, 프레임 넘버 0 → 페이지가 스왑영역 0번에 있음물리메모리로 가져오기 위해 적절한 빈공간을 찾지만 꽉 차서 여유가 없음현재 물리 메모리에서 필요하지 않다고 판단하는 영역을 스왑영역으로 옮김A가 필요하지 않다고 가정하고 스왑영역 3번으로 옮김페이지 테이블에서 0번 인덱스의 유효비트를 1, 프레임 넘버를 3으로 변경물리메모리 빈공간이 된 1번으로 B를 가져옴페이지 테이블에서 1번 인덱스의 유효비트를 0으로, 프레임 넘버를 1로 수정함프로세스에게 데이터를 참조하게 해줌스왑인(스왑영역 → 물리메모리), 스왑아웃(물리메모리 → 스왑영역) 시, 어떤게 적절한지는 운영체제가 판단함 → 페이지 교체 알고리즘페이지 교체정책메모리가 꽉찼을 때, 어떤 페이지를 스왑영역으로 보낼지 결정하는 정책임프로세스는 데이터 접근을 위해 메모리를 참조하는데, 해당 데이터가 메모리에 없으면 Page Fault가 발생함Page Fault가 발생하면, 해당 페이지를 스왑영역에서 메모리로 불러들여야하는데 메모리가 꽉차서 공간이 없다면 메모리에 있는 페이지 중 하나를 선택해서 스왑영역으로 옮겨야함메모리에 있는 페이지를 스왑영역으로 옮길 때 어떤 페이지를 선택할지 결정하는 정책을 페이지 교체 정책이라고 부르고, 페이지 교체 정책에는 여러가지가 있음페이지 교체 정책의 방법들무작위로 선택하는 방법(Random)지역성을 고려하지 않기 때문에 자주 사용되는 페이지가 선택될 때도 있어 성능이 별로 좋지 않음그래서 거의 사용되지 않음메모리에 들어온지 가장 오래된 페이지를 선택하는 방법(FIFO)자주 쓰이는 페이지가 먼저 들어왔다는 이유로 해당 페이지가 교체되면 공평하지 않음위의 단점이 있지만 구현이 간단하고 성능도 꽤 괜찮아서 조금 변형해서 많이 쓰임앞으로 가장 오랫동안 쓰이지 않을 페이지를 선택하는 방법(Optimum)사실상 구현이 불가능한 이론적인 선택방법구현이 불가능해서 필요가 없을 것 같지만, 다른 알고리즘과 성능 비교를 할 때 참조용으로 쓰임최근에 가장 사용이 적은 페이지를 선택하는 방법(LRU - Least Recently Used)지역성 이론의 시간의 지역성에 따르면 최근 사용한 데이터가 앞으로도 사용될 확률이 높기 때문에 최근에 가장 사용을 적게한 페이지가 앞으로도 사용될 확률이 적다는 결론이 나옴실제로도 Optimum 알고리즘에 근접한 성능을 보임그러나 프로그램이 지역성을 띄지 않을땐 성능이 떨어지게됨페이지 테이블 엔트리는 여러개의 비트와 페이지 넘버가 저장되는데, 이곳에 시간을 기록하려면 비트가 많이 필요하게됨많은 비트를 준비하기 어려우므로 실제 LRU를 구현할 때는 접근비트를 이용해서 LRU에 근접하게 구현함Optimum vs FIFO vs LRU 비교 ex, 페이지가 A B C A C D A D C A B 순서대로 요청되는 상황 세 방법 모두 메모리가 비어있기 때문에 처음 요청에서는 전부 Page Fault가 발생함A 요청 들어옴세 알고리즘 모두 Page Fault가 일어나지 않음C 요청 들어옴세 알고리즘 모두 Page Fault가 일어나지 않음D 요청 들어옴Page Fault 발생Optimum뒤에 들어오는 요청을 훑어봄페이지 B가 가장 사용되지 않을 것을 알기 때문에 페이지 B를 스왑영역으로 옮기고, B가 있던 자리에 D를 가져옴FIFO먼저 들어온 페이지가 먼저 나가기 때문에 가장 먼저 들어온 페이지 A를 스왑영역으로 보내고, A가 있던 자리에 D를 가져옴LRU최근에 가장 사용이 적은 페이지가 나가기 때문에 최근에 들어온 페이지의 참조 수를 계산함A 2번, B 1번, C 2번으로 B가 가장 덜 사용됐으니 B를 스왑영역으로 옮기고 B가 있던 자리에 D가 들어옴빌레이디의 역설(Belady’s Anomaly)Page Fault를 줄이려고 메모리를 더 늘려서 프레임 수를 늘렸는데, 오히려 Page Fault가 더 많이 발생하는 현상→ FIFO의 가장 큰 문제임FIFO에서만 발생하며 LRU에서는 발생하지 않음LRU 문제점시간을 기록해야하는 LRU는 구현이 힘듦시간을 기록할 bit가 많이 필요많은 bit가 있어도 시간이 아주 오래 지난다고 가정하면 어쩔수없이 오버플로우가 발생 → 오버플로우로 값이 초기화되면서 시간을 올바르게 표현할 수 없게됨클락 알고리즘 LRU 알고리즘과 유사하게 구현하는 방법접근비트 하나만 이용일정 시간 간격마다 모든 페이지의 접근 비트를 0으로 초기화함접근비트의 초기값은 0으로 설정되어 있고, 만약 페이지가 참조되었다면 1로 설정됨페이지를 원형으로 연결함스왑영역으로 옮길 페이지를 포인터로 가르키는데, 이 포인터를 클락 핸드라고 부름클락 핸드는 시계방향으로 돌게됨만약 Page Fault가 발생해서 스왑영역으로 보내야하는 상황이 나오면, 클락 핸드는 현재 참조하고 있는 페이지의 접근비트를 봄만약 접근비트가 1이라면 해당 접근비트를 0으로 바꾸고, 클락핸드가 다음 페이지를 가르킴이렇게 반복하다가 접근비트가 0인 페이지를 발견하면, 해당 페이지를 스왑영역으로 보냄향상된 클락 알고리즘(Enhanced Clock Algorithm)이 알고리즘은 접근비트만 이용하는 것이 아니라 변경비트까지 봄스왑 영역으로 보내지는 순위가 가장 높은 것은 접근비트가 0이고, 변경비트도 0인 페이지임그 다음으로 접근비트가 0, 변경비트가 1인 페이지임그 다음으로 접근비트가 1, 변경비트가 0인 페이지임마지막으로 접근비트가 1, 변경비트가 1인 페이지가 교체됨FIFO를 사용하는 경우LRU에서는 접근비트를 이용하는데, 하드웨어적으로 접근비트를 지원하지 않는 시스템에서는 FIFO를 이용할 수 밖에 없음어쩔 수 없이 FIFO를 이용하기 위해 성능을 높이는 방법을 고안함2차 기회 페이지 교체 알고리즘FIFO방식에서 자주 사용하는 페이지에게는 또 한번의 기회를 줌FIFO방식과 동일하게 동작하지만, 만약 Page Fault없이 페이지 접근에 성공했다면 해당 페이지를 큐의 맨 뒤로 이동시켜 수명을 연장시켜주는 방식이 알고리즘은 LRU보다는 안좋고, FIFO보다는 좋음스레싱과 워킹셋CPU 스케줄링CPU 사용률을 높이는 것이 목표CPU 사용률을 높이기 위해서는 동시에 실행하는 프로세스의 수, 멀티프로그래밍의 정도를 올리는 것동시에 실행하는 프로세스의 수가 늘어나면, 어떤 프로세스가 I/O작업으로 CPU를 사용할 수 없을 때 다른 프로세스로 컨텍스트 스위칭을 해서 CPU 사용률을 높일 수 있음CPU 사용률을 위해 멀티프로그래밍의 정도를 높였으면, 프로세스들이 필요로하는 공간이 있기때문에 물리메모리에 프레임을 할당해야함물리메모리의 크기는 한계가 있기 때문에 모든 프로세스의 모든 프레임을 물리메모리에 올릴 수 없고, 일부는 스왑영역에 저장됨멀티프로그래밍 정도가 늘어나는 경우에 문제가 나타남멀티프로그래밍 정도가 늘어나면 제한된 물리메모리에 모든 프로세스를 올려야하고, 당장 실행되는 프레임을 제외한 나머지 프레임들은 스왑영역에 저장되고 Page Fault가 많이 발생하게 됨CPU가 작업하는 시간보다 스왑작업의 시간이 더 길어지고, CPU 사용률은 떨어지게됨CPU 스케줄러는 CPU 사용률이 낮아지면, 더 많은 프로세스를 메모리에 올리게되고, 이렇게 반복하다보면 어느새 CPU 사용률이 0에 가깝게 떨어지게됨스레싱CPU 사용률을 높이려했지만 오히려 더 떨어지는 상황근본적인 원인은 물리메모리의 크기가 부족한 것하드웨어적으로 해결하려면 메모리 크기를 늘리면 됨그러나 4GB 램에서 16GB 램으로 올려도 성능향상을 느끼기 힘듦현재 메모리가 프로세스들이 작업을 하는데 충분한 크기라서 스레싱이 발생하지 않는다면 크기를 늘려도 별 다른점이 없기 때문임운영체제가 스레싱을 소프트웨어적으로 해결하기 위한 방법한 프로세스가 실행될 때 너무 많은 페이지를 할당하면 다른 프로세스가 사용할 페이지가 줄어들기 때문에 효율이 떨어지게됨반대로 너무 적은 페이지를 할당하면 빈번한 Page Fault가 발생하고, 스왑요청이 많아 스레싱이 발생하게됨이를 해결하기 위한, 프로세스가 실행되는 동안 해당 프로세스에게 맞는 적절한 페이지 수 결정 방법프로세스가 실행되면 일정량의 페이지를 할당 후, 만약 Page Fault가 발생하면 더 많은 페이지를 할당하고, 반대로 Page Fault가 너무 적게 발생하면 페이지를 과하게 할당해 메모리가 낭비되는 것이라고 판단하고 페이지를 회수함어떤 페이지를 유지할 것인지 결정 방법지역성 이론을 따름현재 메모리에 올라온 페이지는 다시 사용할 확률이 높기 때문에 하나의 세트로 묶어서 메모리에 올림 → 워킹셋워킹셋은 프로세스가 준비상태에서 실행상태가 되는 컨텍스트 스위칭을 할 때 사용됨Section 9. 입출력주변장치(I/O 디바이스, 저장장치)주변장치 종류그래픽카드, 하드디스크, SSD, 키보드, 마우스 등이 있음 주변장치들은 메인보드에 있는 버스로 연결됨버스 Address 버스, Data 버스, Control 버스로 이루어져 있음I/O 디바이스는 이 세가지 버스를 따로 받을 수 있음외부 인터페이스각 하드웨어에 맞게 존재함각종 레지스터장치의 상태와 데이터를 보관할 수 있음입출력 작업을 할 때 데이터를 저장하는 역할을 함값들은 CPU가 사용하기위해 메모리로 이동되기도 함데이터의 전송단위에 따른 주변장치 분류데이터의 전송단위가 캐릭터(글자)인지, 블록인지에 따라 나뉨캐릭터 디바이스마우스, 키보드, 사운드카드, 직별렬포트 등데이터 전송 단위가 캐릭터(글자)로 상대적으로 크기가 작음블록 디바이스하드디스크, SSD, 그래픽카드 등데이터 전송 단위가 블록(범위)로 상대적으로 크기가 큼각 장치 세부 설명버스 예전에는 주변장치들을 하나의 버스로 연결해서 사용함CPU가 작업을 하다가 I/O 명령을 만나면 직접 입출력장치에서 데이터를 가져왔는데 입출력중에는 다른 작업을 하지 못했기 때문에 CPU사용률이 떨어짐이를 해결하기 위해 입출력 제어기(I/O Controller)와 여러개의 버스가 추가됨 CPU는 I/O 명령을 만나면 입출력 제어기에게 입출력작업을 맡기고 다른 작업을 실행함입출력 제어기시스템 버스, 입출력 버스로 구분하여 두 개의 채널을 가지고 있음시스템 버스고속으로 작동하는 CPU와 메모리가 사용입출력 버스주변장치가 사용입출력 버스는 세부적으로 느린장치와 빠른장치를 구분하기 위해 다시 고속 입출력 버스, 저속 입출력 버스 두 개의 채널로 나뉨 → 느린장치와 빠른장치로 구분 해 속도차이로 인한 병목현상을 해결함그래픽 카드그래픽 카드가 다루는 데이터는 매우 대용량이라 고속 입출력 버스로도 감당이 안됨그에 따라 그래픽 카드는 입출력 버스에 있지 않고, 시스템 버스에 바로 연결해 사용함입출력 제어기입출력 제어기는 여러 주변장치를 처리하는데 입출력 버스에서 온 데이터를 메모리로 옮김메모리는 CPU의 명령으로 움직이기 때문에 입출력 제어기가 메모리에 접근하기 위해서는 CPU가 필요함 입출력 제어기가 CPU의 도움이 필요없도록 DMA(Direct Memory Access - 직접 메모리 접근) 제어기가 추가됨입출력 제어기는 DMA로 데이터를 직접 메모리에 저장하거나 가져올 수 있음Memory Mapped I/OCPU와 DMA가 사용하는 메모리가 겹치지 않도록 CPU가 사용하는 메모리 영역과 DMA가 사용하는 메모리 영역을 나눔마우스/키보드마우스볼 마우스회전을 감지해서 움직임을 처리하는 방식광학 마우스아래쪽에 작은 카메라가 표면으로 초당 1500회가 넘는 사진을 찍어 마우스의 디바이스 컨트롤러 내 DSP(Digital Signal Processor)로 보냄DSP는 이 사진을 분석해 마우스의 X축 좌표와 Y축 좌표 움직임을 캐치함DSP가 마우스의 움직임과 클릭같은 데이터를 감지하면, 디바이스 컨트롤러는 CPU에게 인터럽트를 보내고, 마우스 드라이버가 동작해서 데이터를 읽어감마우스 드라이버는 운영체제에게 이벤트 신호를 주는데, 운영체제는 이 이벤트 Foreground 애플리케이션으로 전달해주고 해당 애플리케이션은 받은 마우스 이벤트 처리를 함키보드사용자가 키보드 버튼을 누르면 키보드의 디바이스 컨트롤러가 어떤 키를 입력 받았는지 알아냄CPU에게 인터럽트를 보내고 키보드 드라이버는 운영체제에게 이벤트를 보냄운영체제는 Foreground 애플리케이션으로 이 이벤트를 전달해주고, 애플리케이션에서 해당 키에 맞는 동작을 수행함하드디스크/Flash Memory(SSD)하드디스크 구조 spindleplatter여러개의 트랙으로 구성됨표면에 자성이 있어 N극을 띄면 0, S극을 띄면 1로 인식함보통 하드디스크의 플래터 수는 2개 이상임실린더(cylinder)트랙은 다시 여러개의 섹터로 나뉘는데, 섹터가 하드디스크의 가장 작은 단위임 disk Arm읽기/쓰기 헤드로 플래터의 표면을 읽음read/write head헤드는 disk Arm에 고정되어 있기 때문에 모든 헤드는 항상 같이 움직임헤드가 움직이면 이 헤드들은 여러 개의 플래터를 가리키게 되는데, 이때 여러개의 플래터에 있는 같은 트랙의 집합을 실린더(cylinder)라고 부름하드디스크에서 데이터 읽어오는 예시유저프로세스가 하드디스크의 특정 섹터에 접근을 위해 요청을 보냄 (ex, 실린더 C로 가서 트랙 B에 있는 섹터 D를 읽어라)디스크암은 헤드를 실린더 C로 이동시키는데, 이를 Seek라고 부름헤드를 실린더로 이동시키는데 걸리는 시간을 Seek Time이라고 부름 → 이것때문에 하드디스크가 굉장히 느림트랙 B의 섹터 D가 헤드에 닿을 때까지 스핀들을 회전시키고, 헤드에 섹터 D가 읽히면 작업이 끝남Flash Memory요즘은 하드디스크보다 Flash Memory를 더 많이 사용함데스크탑에는 Flash Memory 이점으로 많은 사람이 SSD를 사용함핸드폰, 테블릿은 하드디스크를 넣을 큰 공간이 없어서 Flash Memory를 사용함하드디스크 vs Flash Memory하드디스크기계적으로 헤드를 움직여 속도가 많이 느리고 소음도 남자기적으로 처리하는 하드디스크는 자석을 갖다대면 데이터가 손상됨스핀들처럼 회전축같은 것들이 있어서 충격에 매우 약함Flash Memory전기적으로 읽기 때문에 굉장히 빠르고 조용함자석을 갖다대도 데이터가 안전함충격에 약하지 않음그러나 특정한 지점에 데이터를 썼다면 덮어쓰기가 불가능 하다는 단점이 있음 똑같은 지점에 데이터를 쓰려면 기존에 있던 데이터를 지우고 새로 써야하는데, Flash Memory는 지우기 가능한 횟수가 정해져있음(읽기/쓰기를 반복하면 망가져 사용할 수 없음) Section 10. 파일시스템파일과 파일시스템파일들을 하드디스크나 SSD와 같은 저장장치에 저장됨사용자가 운영체제에게 요청 시, 운영체제가 하드디스크에 안전하게 저장함운영체제는 파일 관리를 위해 파일 관리자를 둠 → 파일 시스템파일 시스템파일 관리자는 가상메모리에서 메모리 관리자가 페이지 테이블을 이용해서 가상주소를 물리주소로 변환하는 것처럼 파일 테이블을 이용해서 파일을 관리함파일 시스템의 기능파일과 디렉토리를 만듦파일과 디렉토리의 수정, 삭제를 함다른 사용자로부터 파일을 보호하기 위해 접근권한을 관리함 (요즘 운영체제는 다중 사용자 기능을 지원하기 때문에 파일을 보호하기 위해서 꼭 필요한 기능임)파일의 내용이 손상되지 않도록 무결성을 보장함예기치 못한 사고로부터 백업과 복구를 함파일을 암호화해 파일을 보호함파일시스팀 전송단위하드디스크와 Flash Memory는 블록 디바이스임 따라서 전송단위가 블록임저장 단위는 블록이지만, 사용자는 바이트 단위로 파일에 접근이 가능해야하기 때문에 파일관리자가 중간에서 관리해줌파일확장자유닉스 운영체제에는 파일확장자가 없음윈도우즈는 파일확장자가 있음파일 내부 구성헤더, 데이터로 이루어져있음헤더파일의 속성들이 담겨 있음파일 디스크립터(File Descriptor)운영체제는 파일을 관리하기 위해 정보를 보관하는 파일제어블록(File Control Block, FCB)을 가지고 있는데, 이를 파일 디스크립터(File Descriptor)라고 부름파일 디스크립터는 파일마다 독립적으로 존재하고, 저장장치에 존재하다가 파일이 오픈되면 메모리로 이동함파일 디스크립터는 파일시스템(운영체제)이 관리하고, 사용자가 직접 참조할 수는 없음사용자는 파일시스템이 건내준 파일 디스크립터로 파일에 접근할 수 있음파일 종류 분류파일은 데이터의 집합으로, 데이터의 집합을 어떻게 구성하느냐에 따라 종류를 나눌 수 있음순차파일구조파일의 내용이 연속적으로 이어진 상태 (ex, 카세트테이프)파일시스템이 사용자에게 전달해준 파일디스크립터는 파일의 맨 앞에 위치해서 사용자가 쓰거나 읽기를 시작하면 처음부터 진행함파일의 다른영역으로 가고 싶을 때 - lseek함수를 이용해 파일디스크립터 위치를 옮김 장점모든 데이터가 순서대로 기록되기 때문에 공간의 낭비가 없고 구조가 단순함단점특정지점에 바로 이동이 어려워 데이터를 삽입하거나 삭제하려면 탐색하는데 시간이 많이 걸림직접파일구조저장하려는 데이터를 해시함수를 통해 저장위치를 결정하는 파일구조자료구조에서 해시 테이블이라는 이름으로 불리는 방식json도 이 방식임 장점해시함수를 이용하기 때문에 데이터 접근이 굉장히 빠르다는 것단점해시함수의 선정이 굉장히 중요하기 때문에 해시함수를 잘 골라야한다는 점과 저장공간이 낭비될 수 있다는 점인덱스파일구조순차접근과 직접접근 방식의 장점을 취한 것으로 두가지 방식 모두 가능함ex, 음악재생 프로그램의 재생목록 디렉토리디렉토리란?파일을 하나의 공간이 아닌, 관련있는 파일을 모아둘 수 있게 하기 위함한 개 이상의 파일을 가질 수 있고, 자식 디렉토리도 가질 수 있음디렉토리는 여러층으로 구성됨최상위에 있는 디렉토리 - 루트 디렉토리유닉스, 리눅스에서는 루트 디렉토리를 “/”로 표시함, 디렉토리 별 구분을 위해서도 “/”를 사용함윈도우즈는 루트 디렉토리를 파티션 이름으로 사용하는데, 보통 “C:”으로 표시함윈도우즈는 디렉토리와 디렉토리 구분을 “\”로 함디렉토리도 파일임. 단지 일반 파일에는 데이터가 저장되어 있고, 디렉토리에는 파일 정보가 저장되어 있음 디렉토리 구조과거 - 루트 디렉토리에만 하위 디렉토리 존재했었음파일이 많아지면서 다단계 디렉토리구조가 등장함다단계 디렉토리구조어떤 디렉토리에서도 하위 디렉토리를 만들 수 있는 트리구조운영체제는 트리구조에서 순환이 생기는데, 바로가기 기능이 있기 때문임 파일과 디스크파일은 메모리와 비슷한데, 페이징과 같이 전체 디스크 공간을 일정한 크기로 나누고, 그 공간에 주소를 할당해 관리함일정한 크기로 나눈 공간을 파일시스템에서는 블록이라고 함 (메모리에서는 페이지라고 부름)한 블록의 크기는 1~8KB파일시스템은 파일정보를 파일테이블로 관리하는데, 파일이 시작하는 블록의 위치정보도 담겨있음파일 내 블록 분류여러 개의 블록들로 이루어져 있는 하나의 파일에서, 그 블록들이 어떻게 연결되었는지에 따라 분류됨연속할당파일을 구성하는 블록들을 디스크에 연속적으로 저장하는 방식임파일의 시작 블록만 알면 파일의 전체를 찾을 수 있음메모리에서 세그멘테이션 기법처럼 외부 단편화가 발생하기 때문에 실제로 사용되지 않는 방식임불연속할당디스크에 비어있는 공간에 데이터를 분산해 저장하는 방식분산된 블록은 파일시스템이 관리함연결할당, 인덱스 할당이 있음연결할당파일에 속한 데이터를 연결리스트로 관리함파일테이블에는 시작 블록에 대한 정보만 저장하고, 나머지는 연결리스트를 이용해 다른 블록에 접근하는 방식 인덱스할당테이블의 블록포인터가 데이터 블록에 직접 연결하는 것이 아니라 데이터들의 인덱스를 가지고 있는 인덱스 블록을 연결함 인덱스 할당은 데이터가 많아서 테이블이 꽉 찬 경우 인덱스 블록을 더 만들어서 연결하기 때문에 테이블을 확장할 수 있음파일의 크기가 작다면, 데이터를 바로 참조하는 블록 포인터를 이용하고, 파일의 크기가 크다면 간접 포인터를 이용해 많은 데이터에 접근할 수 있음만약 더 큰 데이터가 필요하다면, 이중 간접 포인터, 삼중 간접 포인터를 이용할 수 있음 (i-node라는 이름으로 유닉스와 리눅스에서 많이 사용되고 있음)free block list빈 공간을 찾기위해 매번 모든 메모리를 찾지 않기 위해 빈 공간을 모아둠만약 특정 파일 삭제 시, 파일시스템은 파일의 모든 정보를 지우는 것이 아니라 파일 테이블의 헤더를 삭제하고 free block list에 추가함 회고일주일 동안 스스로 칭찬하고 싶은 점, 아쉬웠던 점, 보완하고 싶은 점칭찬하고 싶은 점 : 이번주 강의가 조금 어렵게 느껴졌지만 포기하지 않고 끝까지 잘 학습한 점아쉬웠던 점 : 이번주에 회사일이 많아서 내용 중 이틀 치를 몰아서 듣게 되었는데 충분한 학습을 하지 못했다는 아쉬움이 남음보완하고 싶은 점 : 중간중간 이해가 안되는 부분들이 있었는데, 그 부분을 반복학습 해야겠습니다🙌다음주에는 어떤 식으로 학습하겠다는 스스로의 목표수료식 전까지 따로 스터디 스케쥴이 없는 것 같으니 이번주 강의를 다시한번 봐야겠습니다💪

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

운영체제FIFO 스케줄링의 장단점이 뭔가요?: 장점은 단순하고 직관적이라는 것이 있지만, 단점은 온 순서대로 실행되기 때문에 짧고 늦게 도착한 프로세스가 길고 일찍 도착한 프로세스를 기다려야한다는점이 있습니다.또한 I/O 작업이 있다면 끝날 때까지 쉬고있기 때문에 CPU 사용률이 떨어지게 됩니다.SJF를 사용하기 여러운 이유가 뭔가요?: 이론적으로는 좋은 알고리즘이지만, 어떤 프로세스가 얼마나 사용될지 예측이 어렵고 Burst Time이 긴 프로세스는 아주 오랫동안 실행되지 않을 수도 있다는 점이 있기 때문입니다.RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?: 컨텍스트 스위칭이 자주 일어나게되고, 타임 슬라이스에서 처리되는 프로세스 처리량보다 컨텍스트 스위칭 처리양이 많아져서 오버헤드가 커지게 됩니다.운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?: 프로세스가 CPU를 사용하다가 스스로 반납한다면 CPU 사용률이 적은 것이기 때문에 - I/O Bound Process,프로세스가 CPU를 사용하다가 타임 슬라이스 크기를 오버해서 강제로 CPU를 뺏기게 되면 CPU 사용률이 많은 것이기 때문에 - CPU Bound Process 입니다.공유자원이란무엇인가요?: 여러 프로세스가 공유하고 있는, 공동으로 사용하는 변수나 파일들입니다.교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?: 아래 네가지 조건들을 모두 충족해야합니다.(1) 상호배제 - 어떤 프로세스가 한 리소스를 점유했다면, 그 리소스는 다른 프로세스에게 공유되면 안됨(2) 비선점 - 어떤 프로세스가 한 리소스를 점유했다면, 다른 프로세스가 그 리소스를 빼앗을 수 없음(3) 점유와 대기 - 어떤 프로세스가 한 A 리소스를 가지고 있고, 그 상태에서 B 리소스를 원하는 상태여야함(4) 원형대기 - 점유와 대기를 하는 프로세스들의 관계가 원형을 이룸 자료구조와 알고리즘재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?: 무한 실행되서 메모리 이슈가 나게 되는 문제가 발생할 수 있습니다.0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n){ // 재귀 로직 if (n 회고미션을 풀어나가는데 복습이 큰 도움이 되어 계속해서 해나가야겠다는 생각이 들었습니다. 다만, 재귀 함수를 만들어보는 자료구조와 알고리즘의 2번 문제인 코드 작성 미션이 생각보다 잘 풀리지 않았는데, 재귀 부분 코드 작성을 좀 더 복습하며 익혀야될 것 같습니다.

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

2주차 학습 내용 '그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)' Section 3(Unit 1~5)'그림으로 쉽게 배우는 운영체제' Section 3(Unit 5~7), Section 4, 5, 7 '그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)' Section 3(Unit 1~5) Section 3. 알고리즘재귀재귀란?어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻함재귀적으로 정의된 함수를 재귀함수라고 함콜스택?함수가 호출되면서 올라가는 메모리 영역으로 스택이라고도 불림스택이기 때문에 First In Last Out 특성을 가짐 function factorial(number) { if(number == 1 || number == 0) { return 1; } else { return number * factorial(number - 1); } } console.log(factorial(5)); 재귀적으로 생각하기패턴 1. 반복실행 : 반복문에 비해 크게 이점이 되는 부분은 없음. 오히려 콜스택에 공간을 많이 차지해 성능은 for문 보다 좋지 않음.for(let i = 1; i 10) return; console.log(number); myFunction(number + 1); } myFunction(1); 패턴 2. 하위 문제의 결과를 기반으로 현재 문제를 계산하는 것 : 팩토리얼 계산하향식 계산return number * factorial(number - 1); 상향식 계산function factorial(number) { let sum = 1; for(let i = 1; i function factorial2(number, i = 1, sum = 1) { if(i > number) return sum; return factorial2(number, i + 1, sum * i); } 재귀함수를 위의 코드처럼 상향식으로 쓸 수도 있긴하지만의 진정한 위력은 하향식 계산에서 발휘됨하향식 계산 예제로 알아보기예제 1) 배열의 숫자 모두 더하기function sumArray(arr) { if(arr.length == 1) return arr[0]; return sumArray(arr.slice(0, -1) + arr[arr.length - 1]); } let arr = [1,2,3,4,5]; let sum = sumArray(arr); console.log(sum); 예제 2) 문자열 길이 구하기function strLength(arr) { if(arr[0] == null) return 0; return strLength(arr.slice(0, -1)) + 1; } let str = "abcde"; let len = strLength(str) console.log(len); 예제 3) 지수함수 만들기function power(x, n) { if(n == 0) return 1; return power(x, n - 1) * x; } console.log(power(2, 5)); 재귀 - 하노이 탑1883년 프랑스 수학자 에두아르드 뤼카가 발표한 게임기둥 A → 기둥 C 옮기기원반 1 → 기둥 C 이동, 원반 2→ 기둥 B, 원반 1 → 기둥 B 이동, 원반 3 → 기둥 C 이동, 원반 1 → 기둥 A 이동, 원반 2 → 기둥 C 이동, 원반 1 → 기둥 C 이동 → 성공하향식 재귀함수로 하노이 탑 게임 풀어보기기둥 A에 있는 원반 1, 2, 3을 기둥 C로 옮기려 함첫번째 목표로 원반 3을 기둥 C로 옮기는 것원반 1, 2를 목표 기둥이 아닌 기둥 B로 옮겨야 함원반 1이 기둥 C로 이동하위 문제가 없다면 스택에서 하나씩 꺼내서 문제를 해결할 수 있음두번째 목표로 원반 2를 기둥 C로 옮기는 것원반 1을 기둥 A로 옮김코드로 살펴보기honoi(3, "A", "B", "C") : honoi(원반갯수, 시작기둥, 목표기둥, 임시기둥)function hanoi(count, from, to, temp) { // 3, A, C, B if(count == 0) return; hanoi(count - 1, from, temp, to); // 2, A, B, C console.log(`원반 $(count)를 $(from)에서 $(to)로 이동`); hanoi(count - 1, temp, to, from); // 2, B, C, A } 정렬 - 버블정렬(Bubble Sort)배열에 숫자가 무작위로 들어가 있을 때, 데이터를 옆 데이터와 비교하면서 자리를 바꿈(반복에 따라 맨 마지막 원소는 큰 값이므로 범위에서 제외)코드 구현function BubbleSort(arr) { for(let i = 0; i arr[j + 1]) { let temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } let arr = [4, 2, 3, 1]; console.log("==== 정렬 전 ===="); console.log(arr); BubbleSort(arr); console.log("==== 정렬 후 ===="); console.log(arr); 버블 정렬의 성능버블 정렬의 장단점장점 - 이해와 구현이 간단함단점 - 성능이 O(n^2)으로 좋지 않음 정렬 - 선택정렬(Selection Sort)배열의 정렬되지 않은 영역의 첫번째 원소를 시작으로 마지막 원소까지 비교 후, 가장 작은 값을 첫번째 원소로 가져옴(배열 끝까지 반복)코드 구현function SelectionSort(arr) { for(let i = 0; i 선택 정렬의 성능선택 정렬의 장단점장점 - 이해와 구현이 간단함단점 - 성능이 좋지 못함 (O(n^2)) '그림으로 쉽게 배우는 운영체제' Section 3(Unit 5~7), Section 4, 5, 7 Section 3. CPU 스케줄링(Unit 5~7)CPU스케줄링 개요컴퓨터 자원필수 장치 - CPU, 메모리주변 장치 - HDD, 키보드, 마우스CPU스케줄링운영체제가 모든 프로세스에게 CPU를 할당/해제 하는 것CPU가 스케줄링에서 고려할 사항어떤 프로세스에게 CPU 리소스를 줄 것인가?CPU를 할당받은 프로세스가 얼마의 시간동안 CPU를 사용해야하는가?CPU BurstCPU를 할당받아 실행하는 작업I/O Burst입출력 작업다중큐프로세스 상태에서 준비상태, 대기상태는 큐(Queue)라는 자료구조로 관리됨실행 → 준비 상태가 될 때, 운영체제는 그에 맞는 준비 큐에 넣음실행 → 대기 상태가 될 때, I/O 작업 종류에 따라서 분류된 큐에 들어가게 됨 (ex, 하드디스크 작업 → HDD 큐)정확히는 프로세스 정보를 가지고 있는 PCB가 들어가게 됨스케줄링 목표리소스 사용률CPU 사용률 높이기, I/O 디바이스의 사용률 높이기 등등오버헤드 최소화스케줄링을 하기 위한 계산이 너무 복잡해지거나, 컨텍스트 스위칭을 너무 자주하지 않도록공평성모든 프로세스에게 공평하게 CPU가 할당되어야 함공평의 의미는 시스템에 따라 달라질 수 있음처리량같은 시간 내에 더 많은 처리를 할 수 있는 방법대기 시간작업을 요청하고 실제 작업이 이루어지기 전까지 대기 시간이 짧은 것을 목표로 함응답 시간대화형 시스템에서 사용자의 요청이 얼마나 빨리 반응하는지가 중요하기 때문에 응답시간이 짧은 것을 목표로 함목표간에 서로 상반되는 상황이 있는데, 이 때는 사용자가 사용하는 시스템에 따라 목표를 다르게 설정하게 됨 (ex, 터치스크린 → 응답시간 짧도록, 과학 계산 → 처리량이 높도록 초점 맞춤)FIFO(First In First Out)스케줄링 큐에 들어온 순서대로 CPU를 할당받는 방식먼저 들어온 프로세스가 완전히 끝나야만 다음 프로세스가 실행될 수 있음장점단순하고 직관적단점한 프로세스가 완전히 끝나야 다음 프로세스가 시작되기 때문에 실행시간이 짧고 늦게 도착한 프로세스가 실행시간이 길고 빨리 도착한 프로세스의 작업을 기다려야 함I/O 작업이 있다면 끝날 때까지 쉬고있기 때문에 CPU 사용률이 떨어지게 됨스케줄링의 성능 → 평균 대기 시간으로 평가함프로세스의 실행 순서만 바꿔도 평균 대기 시간의 차이가 많이 남FIFO 알고리즘은 프로세스의 Burst Time에 따라 성능의 차이가 심하게 나기 때문에 현대 운영체제에서 잘 쓰이지 않고, 일괄처리시스템에 쓰임SJF(Shortest Job First)작업의 순서에 따라 평균 대기 시간이 달라지는 FIFO에서 Burst Time이 짧은 프로세스를 먼저 실행했을 때 평균대기시간이 짧아지는 알고리즘을 만들기로 함 → SJFFIFO보다 이론적으로 성능이 좋음실제 구현 시 두 가지 문제 발생첫번째 문제어떤 프로세스가 얼마나 실행될지 예측하기 어려움 (유저의 사용시간에 따라 달라짐)두번째 문제Burst Time이 긴 프로세스는 아주 오랫동안 실행되지 않을 수도 있다는 것RR(Round Robin)FIFO 알고리즘은 일괄처리 시스템에 적절하기 때문에 시분할 처리 시스템에서는 사용하기 힘들고, SJF 알고리즘은 프로세스의 종료시간을 예측하기 힘듦FIFO 알고리즘의 단점을 해결해보기로 함문제점 - 한 프로세스가 그 다음 프로세스가 실행됨한 프로세스에게 일정 시간만큼 CPU를 할당하고 강제로 다른 프로세스에게 일정시간만큼 CPU를 할당함 → 강제로 CPU를 뺏긴 프로세스는 큐의 가장 뒷부분으로 밀려남프로세스에게 할당하는 일정 시간은 ‘타임 슬라이스’ 또는 ‘타임 퀀텀’이라고 부름작업에 따라 RR 알고리즘과 FIFO 알고리즘의 평균 대기 시간이 비슷할 수도 있는데, 이 때는 RR 알고리즘이 더 비효율적인 방식임컨텍스트 스위칭이 있기 때문에 컨텍스트 스위칭 시간이 더 추가되기 때문RR 알고리즘 성능은 타임 슬라이스의 값에 따라 크게 달라짐타임 슬라이스가 큰 경우 : 먼저 들어온 프로세스의 작업이 종료될 때까지 실행하니 FIFO 알고리즘과 동일해짐타임 슬라이스가 작은 경우 : 컨텍스트 스위칭이 너무 자주 일어나게 되고, 타임 슬라이스에서 실행되는 프로세스의 처리량보다 컨텍스트 스위칭을 처리하는 양이 훨씬 커져서 오버헤드가 너무 커지게 됨최적의 타임 슬라이스를 결정하는 방법 → 유저가 느끼기에 여러 프로세스를 사용하기에 동시에 실행되는 것처럼 버벅이지 않고 오버헤드가 너무 크지 않은 값을 찾아야 하는 것MLFQ(Multi Level Feedback Queue)오늘날 운영체제에서 가장 일반적으로 쓰이는 CPU 스케줄링 기법RR의 업그레이드 된 알고리즘MLFQ 설명 예시P1 (CPU Bound Process)I/O 작업 없이 CPU 연산만 하는 프로세스CPU 사용률과 처리량을 가장 중요하게 생각P2 (I/O Bound Process)1초 CPU 작업을 하고 10초 I/O 작업을 함응답속도를 가장 중요하게 생각두 프로세스로 두 가지 상황에 따라 성능을 비교해 봄타임 슬라이스가 100초인 경우타임 슬라이스가 1초인 경우I/O 사용률을 봤을 때 더 좋음P1 입장에서는 CPU 사용율은 100초일 때와 비교했을 때 손해가 없지만, 컨텍스트 스위칭이 있기 때문에 오버헤드가 생겨서 손해를 봄P2 입장에서는 I/O 사용률이 많이 높아졌기 때문에 이득을 봄손해를 보는 프로세스의 문제를 해결하기 위해 MLFQ가 나오게 됨MLFQ는 기본적으로 CPU 사용률과 I/O 사용률이 좋게 나오는 작은 크기의 타임 슬라이스를 선택함. 그리고 P1과 같은 CPU Bound Process들에게는 타임 슬라이스를 크게 줌운영체제가 프로세스가 I/O Bound Process인지, CPU Bound Process인지 구분하는 방법I/O Bound ProcessCPU를 사용하는 프로세스가 실행하다가 스스로 CPU를 반납하면 CPU 사용이 적은 것이니 I/O Bound Process일 확률이 높음CPU Bound ProcessCPU를 사용하는 프로세스가 타임 슬라이스 크기를 오버해서 CPU 스케줄러에 의해 강제로 CPU를 뺏기는 상황이면 CPU 사용이 많은 것이니 CPU Bound Process일 확률이 높음위의 아이디어를 가지고 우선순위를 가진 큐를 여러개 준비함 → 우선순위가 높으면 타임 슬라이스가 작고, 우선순위가 낮을수록 타임 슬라이스 크기가 커짐MLFQ 외에도 HRN, SRT, MLQ, Priority 등 다양한 알고리즘이 있지만, MLFQ가 주류임 Section 4. 프로세스 동기화프로세스 간 통신프로세스는 독립적으로 실행되기도 하지만 다른 프로세스와 데이터를 주고받으며 통신을 하는 경우도 있음네트워크로 연결된 다른 프로세스와 통신할 수도 있음통신 방법한 컴퓨터 내에서 통신하는 방법파일과 파이프 이용파일통신하려는 프로세스들이 하나의 파일을 이용해 읽고 쓰는 방법파이프운영체제가 생성한 파이프를 이용해 데이터를 읽고 쓰는 방법쓰레드를 이용한 방법한 프로세스 내에서 쓰레드 간 통신을 하는 방법코드, 데이터, 힙 영역을 공유, 스택만 따로 가짐여기서 데이터 영역에 있는 전역변수나 힙을 이용네트워크를 이용한 방법운영체제가 제공하는 소켓통신이나 다른 컴퓨터에 있는 함수를 호출하는 RPC(원격 프로시저 호출)를 이용해 통신하는 방법이 있음공유자원과 임계구역공유자원공동으로 이용하는 변수나 파일들문제점공유자원은 여러 프로세스가 공유하고 있기 때문에 각 프로세스의 접근 순서에 따라 결과가 달라질 수 있음컨텍스트 스위칭으로 시분할 처리를 하기 때문에 프로세스의 실행 순서를 예측하기 어려움그에 따라 실행 결과를 예측하기 힘들고, 여기서 발생한 문제를 ‘동기화 문제’라고 부름이 문제를 해결하기 위해 여러 프로세스가 동시에 사용하면 안되는 영역을 ‘임계구역(Critical Section)’이라고 함공유자원을 서로 사용하기 위해 경쟁하는 것을 ‘경쟁조건(Race Condition)’이라고 함임계구역의 문제를 해결하기 위한 방법상호 배제(Mutual Exclusion) 매커니즘상호 배제 매커니즘의 요구사항주어진 시간에 항상 하나의 프로세스만 접근할 수 있음동시에 여러개의 요청이 있더라도 하나의 프로세스의 접근만 허용함임계구역에 들어간 프로세스는 빠르게 나와야 함세마포어상호배제 매커니즘의 한가지예시직원 A, 직원 B가 공유자원인 프린터를 사용하는 상황동시에 프린터 요청 시, 경쟁 조건이 됨직원 A, 직원 B의 결과물이 섞여서 나오게 되는 오류 발생프린터실과 프린터실 열쇠 관리자를 두어 프린터 사용 시, 프린터실 열쇠를 받아 프린터 이용하게 됨. 프린터실 열쇠 관리자에게 열쇠가 없다면 누군가 프린터실 사용중이므로 기다려야 함위의 예시는 세마포어 매커니즘동기화에서 중요한 개념예시를 현실 프로세스 매커니즘으로 생각직원들 → 프로세스프린터 → 공유자원프로세스가 기다리는 공간 → 대기큐열쇠 관리자 → 운영체제열쇠 → 세마포어(semaphore)세마포어 - 정수형 변수코드 예시예시) 게임에서 물약 먹어서 체력 회복 / 공격받아서 체력 줄어드는 상황이 동시에 진행됨// 세마포어 선언 int s = 1; // 물약 먹는 코드 wait(s); // 열쇠를 요청해서 열쇠를 받고 문을 잠금 int currentHealth = GetHealth(); health = currentHealth + 50; signal(s); // 방에서 나와 문지키는 직원에게 열쇠 반납 // 공격받는 코드 wait(s); // 열쇠를 요청해서 열쇠를 받고 문을 잠금 int currentHealth = GetHealth(); health = currentHealth - 10; signal(s); // 방에서 나와 문지키는 직원에게 열쇠 반납 세마포어를 이용하면 공유자원에 여러 프로세스가 동시에 접근하지 못하기 때문에 동기화 문제가 발생하지 않음세마포어의 문제점wait() 함수와 signal() 함수를 이상하게 호출하여 세마포어를 잘못사용할 가능성이 있음이 문제를 해결한 방법 → 모니터모니터세마포어의 단점을 해결한 상호배제 매커니즘모니터는 따로 운영체제가 처리하는 것이 아니라 프로그래밍 언어 차원에서 지원하는 방법자바 예시synchronized가 붙으면 동시에 여러 프로세스에서 실행시킬 수 없음 → 상호배제가 완벽하게 됨increase() 뿐만 아니라 synchronized가 붙은 decrease()도 실행할 수 없음모니터의 구현만 완벽하다면, 프로그래머는 세마포어처럼 wait(), signal() 함수를 임계영역에 감싸지 않아도 되서 편리하고 안전하게 코드 작성 가능함 Section 5. 데드락데드락이란?(feat.식사하는 철학자)여러 프로세스가 서로 다른 프로세스의 작업이 끝나기를 기다리다가 아무도 작업을 진행하지 못하는 상태 → 교착상태일상생활 예시교통상황교착상태가 발생하는 이유공유자원 때문. 만약 어떤 자원을 여러 개의 프로세스가 공유하지 않는다면 교착상태는 발생하지않음식사하는 철학자 예시포크가 2개 있어야 식사가 가능한데, 우연히 모든 철학자가 자신의 오른쪽의 포크를 동시에 사용할 때 → 교착상태교착상태의 필요조건필요조건에는 네 가지가 있는데, 모두 충족되어야 교착상태 발생함상호배제어떤 프로세스가 한 리소스를 점유했다면, 그 리소스는 다른 프로세스에게 공유가 되면 안됨식사하는 철학자 예시에서 ‘포크’가 리소스에 해당비선점프로세스 A가 리소스를 점유하고 있는데, 프로세스 B가 리소스를 빼앗을 수 없어야 함식사하는 철학자 예시에서 철학자 A의 포크를 철학자 B가 뺏을 수 없음점유와 대기어떤 프로세스가 리소스 A를 가지고 있는 상태에서 리소스 B를 원하는 상태여야 함식사하는 철학자에서 오른쪽 포크를 든 상태에서 왼쪽 포크를 기다리고 있는 상태원형 대기점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있음식사하는 철학자에서 서로가 서로의 포크를 원하는 상황이 원형을 이룸교착상태를 예방하는 방법을 고려했으나, 제약이 많고 비효율적이라 다른 방식 연구 → 교착상태에 빠졌을 때 해결하는 방법 연구데드락 해결(feat. 은행원 알고리즘)교착상태 해결방법으로 ‘교착상태 회피(Deadlock avoidance)’라는 방법이 있음교착상태 회피(Deadlock avoidance)프로세스에게 자원을 할당할 때 어느정도 자원을 할당해야 교착상태가 발생하는지 파악해서 교착상태가 발생하지 않는 수준의 자원 할당을 함교착상태 회피는 전체 자원의 수와 할당된 자원의 수를 기준으로 안전상태(Safe state)와 불안정 상태(Unsafe state)로 나눔운영체제가 최대한 안정상태를 유지하려고 자원할당을 함불안정 상태에 있더라도 무조건 교착상태에 빠지는 것이 아니라 교착상태에 빠질 확률이 높아짐교착상태 회피를 표한한 알고리즘 → 은행원 알고리즘은행이 1000만원을 가지고 있다고 가정하고, 사업가 A에게 500만원, 사업가 B에게 400만원을 빌려줌(은행 잔고 100만원) → 이후 사업가 A가 은행에게 200만원을 더 빌려주면 빌린돈을 상환할 수 있다고 함 → 은행이 B에게 상환을 요청할 때, B도 200만원을 더 빌려주면 상환가능하다고 함 → 은행은 대출해줄 수도, 상환받을 수도 없는 교착상태에 빠지게 됨은행이 사업가들에게 돈을 빌려줄 때, 은행의 여윳돈과 사업가들에게 빌려준 돈들을 보고 대출 가능한 상황(안전상태)인지 확인하고 빌려줌운영체제에서 은행원 알고리즘을 구현하는 방법운영체제는 프로세스에게 자원을 할당하기 전에 자기가 가지고 있는 전체 자원의 수를 알고 있어야 함 → 시스템의 총 자원프로세스들은 각자 자기가 필요한 자원의 최대 숫자를 운영체제에게 알려줘야 함 → 최대 요구자원안정상태모든 프로세스에게 자원할당 후, 요청이 예상되는 자원이 맞는 프로세스에게 먼저 할당 함 그 후에 자원을 반납 받고 다른 프로세스에게 또 다시 할당할 수 있게 됨불안정상태현재 사용 가능한 자원이 1개이기 때문에 P1, P2, P3 모두 자원 추가할당이 안됨불안정상태에 있더라도 모든 프로세스가 최대자원을 요청하지 않는다면, 교착상태에 빠지지 않을수도 있지만 불안정상태에 빠지지 않도록 유지하는게 좋음은행원 알고리즘은 교착상태를 피하는 좋은 방법이지만, 비용이 비싸고 비효율적임 → 그래서 알고리즘 연구자들은 교착상태가 발생하지만, 교착상태가 발생했을 때 이를 해결하는 방식을 연구함교착상태를 검출하는 방법을 연구(두가지)가벼운 교착상태 검출 → 타이머 이용프로세스가 일정시간동안 작업을 진행하지 않는다면, 교착상태가 발생했다고 간주하고 이를 해결함해결방법 - 일정 시점마다 체크포인트를 만들어 작업을 저장하고 타임아웃으로 교착상태 발생 시, 마지막으로 저장했던 체크포인트로 롤백하는 것무거운 교착상태 검출 → 자원 할당 그래프 이용현재 운영체제에서 프로세스가 어떤 자원을 사용하는지 지켜보고, 교착상태 발생 시 이를 해결함해결방법 - 운영체제가 자원 할당 그래프를 계속 지켜보고 교착상태 검출 시, 교착상태를 일으킨 프로세스를 강제 종료 시킴 그 후 다시 실행시킬 때 체크포인트로 롤백을 시킴이 방법은 운영체제가 지속적으로 ‘자원 할당 그래프’를 유지하고 검사해야 하기때문에 오버헤드가 발생함그러나 가벼운 교착상태 검출에서 발생할 수 있는 억울하게 종료되는 프로세스는 발생하지 않음Section 7. 메모리메모리 종류왜 여러종류의 메모리가 필요한가레지스터가장 빠른 기억장소로 CPU 내에 존재하고 있음컴퓨터 전원이 꺼지면, 데이터 사라짐 - 휘발성 메모리32bit, 64bit - 레지스터 크기CPU는 계산을 할 때 메인메모리에 있는 값을 레지스터로 가져와 계산을 함 → 계산 결과는 다시 메인메모리에 저장캐시휘발성 메모리레지스터는 CPU가 사용하는 메모리로 빠름, 그에 비해 메인메모리는 너무 느린편 → 메인메모리에 있는 데이터를 레지스터에 옮기려면 한참 걸리기 때문에 필요할 것 같은 데이터를 미리 가져와서 저장함 → 캐시캐시는 성능의 이유로 여러개를 둠만약, CPU가 값을 요청해 레지스터로 값을 옮겨야한다면, 단계에 따라 가장 속도가 빠른 L1캐시를 보고 → 여기 없다면 L2캐시를 확인 → 여기도 없으면 메인 메모리에서 값을 가져옴메인 메모리실제 운영체제와 다른 프로세스들이 올라가는 공간전원이 공급되지 않으면 데이터가 지워짐 → 휘발성 메모리하드디스크나 SSD보다 속도는 빠르지만 가격이 비쌈 → 데이터 저장보다는 실행중인 프로그램만 올림보조저장장치(HDD, SSD)사무용 프로그램 게임과 같은 파일들을 저장가격이 저렴하고 전원이 공급되지 않아도 데이터가 지워지지 않음 → 비휘발성 메모리메모리와 주소메인메모리폰 노이만 구조는 모든 프로그램을 메모리에 올려 실행시킴멀티프로그램 - 여러개의 프로그램이 올라오게 되어 관리가 복잡해짐운영체제는 관리를 위해 1바이트(8bit) 크기로 구역을 나누고 숫자를 매김 → 주소32bit CPU vs 64bit CPU32bit CPU레지스터 크기가 32bit이고, CPU가 처리하는 ALU도, 데이터가 이동하는 버스도 32bit임.CPU가 다룰 수 있는 메모리도 2^32로 4GB임32bit CPU레지스터 크기가 64bit이고, CPU가 처리하는 ALU도, 데이터가 이동하는 버스도 64bit임.CPU가 다룰 수 있는 메모리도 2^64로 거의 무한대에 가까움64bit CPU가 32bit CPU보다 한번에 처리할 수 있는 양이 많기 때문에 속도가 더 빠름물리주소, 논리주소물리주소 공간 - 메모리를 컴퓨터에 연결하면 0x0번지부터 시작하는 주소공간논리주소 공간 - 사용자 관점에서 바라본 주소공간사용자 프로세스가 운영체제를 침범하지 않도록 하드웨어적으로 운영체제 공간과 사용자 공간을 나누는 ‘경계 레지스터’를 만듦경계 레지스터CPU 내에 존재하는 레지스터메모리 관리자가 사용자 프로세스가 경계 레지스터의 값을 벗어났는지 검사하고, 만약 벗어났다면 그 프로세스를 종료시킴절대주소, 상대주소상대주소(논리 주소 공간) - 컴파일러가 컴파일을 할 때, 메모리 0번지에서 실행한다고 가정함절대주소(물리 주소 공간) - 실제 프로그램이 올라간 주소는 4000번지(메모리 관리자가 바라본 주소)예를 들어 0x100번지 데이터를 가져올 때, 메모리 관리자는 CPU가 요청한 0x100번지와 재배치 레지스터에 있는 0x4000번지의 값을 더한 0x4100(절대 주소, 물리 주소)에 접근해서 데이터를 가져옴재배치 레지스터에는 프로그램의 시작 주소가 저장되어 있음메모리 관리자는 사용자가 메모리에 접근할 때마다 위의 예시처럼 계산함메모리 할당방식유니프로그래밍에서 메모리의 크기보다 큰 프로그램을 실행시키는 방법큰 프로그램을 메모리에 올릴 수 있도록 잘라서 당장 실행시켜야할 부분만 메모리에 올리고, 나머지는 용량이 큰 하드디스크(하드디스크 내 스왑영역)에 저장시키는 기법 → 메모리 오버레이(memory overlay)멀티프로그래밍에서 메모리의 크기보다 큰 프로그램을 실행시키는 방법(두가지)가변 분할 방식(가상 메모리 관점 - 세그멘테이션)프로세스의 크기에 따라 메모리를 나누는 방식한 프로세스가 메모리에 연속된 공간에 할당되기 때문에 ‘연속 메모리 할당’이라고 함장단점장점 - 메모리에 연속된 공간에 할당되기 때문에 더 크게 할당되서 낭비되는 공간인 ‘내부 단편화’가 없음단점 - ‘외부 단편화’ 발생메모리 공간이 쪼개져있어서 용량을 합쳐 계산하면 프로세스에게 할당을 할 수 있을 것 같지만, 사실 할당할 수 없음 → 외부 단편화해결방법외부 단편화가 발생한 공간을 합쳐주는 조각모음을 함그러나 조각모음을 하려면 현재 메모리에서 실행되고 있는 프로세스들의 작업을 일시 중지해야하고, 메모리공간을 이동시키는 작업을 해야하기 때문에 오버헤드가 발생함고정 분할 방식(가상 메모리 관점 - 페이징)프로세스 크기와 상관없이 메모리를 정해진 크기로 할당한 프로세스가 메모리에 분산되어 할당되기 때문에 ‘비연속 메모리 할당’이라고 함장단점장점 - 구현이 간단하고, 오버헤드가 적음단점 - 작은 프로세스도 큰 영역에 할당되서 공간이 낭비되는 ‘내부 단편화’가 발생내부 단편화따로 해결방법은 없고, 분할되는 크기를 조절해서 내부단편화를 최소화 함버디 시스템오늘날의 운영체제는 가변분할 방식과 고정분할방식을 혼합하여 단점을 줄임2의 승수로 메모리를 분할해 메모리를 할당하는 방식여기서도 내부 단편화가 발생하지만, 적은 용량으로 발생또한 프로세스가 사용을 마치고 메모리에서 나가도 근접한 메모리 공간을 합치기 쉬움 → 2의 승수로 동일하게 나눠서 반대로 조립만 하면 큰 공간이 만들어지기 때문 (조각모음보다 간단)장단점 가변 분할 방식처럼 프로세스 크기에 따라 할당되는 메모리 크기가 달라지고 외부 단편화를 방지하기 위해 메모리 공간을 확보하는 것이 간단함고정분할 방식처럼 내부 단편화가 발생하기는 하지만, 많은 공간의 낭비가 발생하지는 않음 회고일주일 동안 스스로 칭찬하고 싶은 점, 아쉬웠던 점, 보완하고 싶은 점칭찬하고 싶은 점 : 이번주 강의를 매일 집중해서 잘 학습한 점아쉬웠던 점 : 어제 들었던 강의 내용이 오늘 다시보면 잘 기억이 안난다는 점보완하고 싶은 점 : 기억력 이슈라 반복할 수밖에 없을 것 같습니다🥲다음주에는 어떤 식으로 학습하겠다는 스스로의 목표다음주에도 이번주처럼 오늘 범위의 강의를 듣기 전에 어제 범위의 강의를 머릿속으로 다시 생각하고 정리하는 시간을 갖겠습니다.

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

운영체제while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?: 플레이어가 스킬을 사용했을 때 콜백을 받는 방식(비동기 프로그래밍 이벤트 처리)으로 문제를 해결할 수 있습니다.프로그램과 프로세스가 어떻게 다른가요?: 프로그램은 앱, .exe파일과 같은 저장장치에 저장된 명령문의 집합체이고, 프로세스는 프로그램이 메모리에 올라갔을 때 실행중인 프로그램입니다. 그래서 컴퓨터 관점에서 보면 프로그램은 저장장치만 사용하는 수동적인 존재이고, 프로세스는 운영체제의 CPU 스케줄링 알고리즘에 따라 CPU도 사용하고, 필요에 따라 입출력도 하기에 능동적인 존재라고 볼 수 있습니다.멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?: 멀티프로그래밍은 메모리 관점에서 메모리에 여러개의 프로세스가 올라온 것이고, 멀티프로세싱은 CPU의 관점에서 CPU가 여러개의 프로세스를 처리하는 것입니다.운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?: 프로세스 생성 시, 프로세스의 정보를 가지고 있는 PCB를 만들고 저장합니다.PCB들은 연결리스트로 저장되고,운영체제는 프로세스가 종료되면 연결리스트에서 해당 프로세스의 PCB를 제거합니다.컨텍스트 스위칭이란 뭔가요?: 프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행중인 프로세스의 상태를 저장하고, 다른 프로세스의 상태값으로 교체하는 작업입니다.좀 더 정확하게는 PCB의 내용이 변경되는 것으로 프로세스 상태, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보 등이 변경됩니다.컨텍스트 스위칭은CPU 점유시간이 다 되거나,I/O 요청이 있을 때, 또는다른 종류의 인터럽트가 있을 때 발생하게 됩니다. 자료구조와 알고리즘여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.: 학번을 key값으로 가지는 해시테이블을 선택할 것입니다. 학생이 전학가거나 오는 상황에 있어 고정된 크기를 가지는 배열보다는 동적으로 크기 조정이 가능한 해시테이블이 유연합니다.또한 해시테이블은 학번을 key값으로 사용하여 검색 시, 시간 복잡도 O(1)을 가지기 때문에 학생정보를 빠르게 검색할 수 있습니다.만약 동일한 해시값을 갖는다면, 연결리스트 사용 등으로 충돌을 해결할 수 있습니다.여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.: 큐(Queue)를 선택할 것입니다. First In First Out의 특성을 가지는 자료구조로 들어온 순서대로 처리되는 주문에 적합하다고 생각합니다. 회고강의를 들을 때는 끄덕끄덕하며 다 이해되었다고 생각했는데, 막상 미션을 해결하려니 정리해서 작성하기에 조금 어려웠고, 또 가물가물한 부분도 있어 당황하기도 하였습니다. 그래서 다시 정리해뒀던 것을 찾아보며 미션을 하게 되었는데, 앞으로 일주일마다 제가 작성했던 발자국과 미션을 반복적으로 보면서 복습해야겠다고 생각하게 되었습니다.

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

1주차 학습 내용 '그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)' Section 1, 2'그림으로 쉽게 배우는 운영체제' Section 1, 2, Section 3(Unit 1~4) '그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)' Section 1, 2 Section 1. 개요자료구조와 알고리즘이란?자료구조데이터가 어떤 구조로 저장되고 어떻게 사용되는지를 나타냄(ex, 변수, 배열)자료구조에 따라 처리 방법이 달라짐, 코드가 달라질 수 있음알고리즘어떤 문제를 해결하기 위한 확실한 방법한가지 자료구조에 대해서도 여러가지 알고리즘이 있을 수 있음 (ex, 표현방법에 따라) → 더 좋은 알고리즘을 사용시간 복잡도더 좋은 알고리즘이란?메모리 사용이 적은 것, 속도가 더 빠른 것 등 사용자에 따라 달라짐일반적으로 알고리즘의 속도를 성능의 척도로 사용 → 시간복잡도시간 복잡도란, 특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간을 말함그러나 사용자마다 컴퓨터 사양이 다르기 때문에 시간을 측정하는 방식이 아닌, 코드에서 성능에 많은 영향을 주는 부분을 찾아 실행시간을 예측함 → 반복문을 보고 성능 평가함표현 방법Big-Ω : 최선의 경우 한 번에 찾음Big-O : 최악의 경우 배열의 길이만큼 걸림Big-Θ : 평균의 경우 배열의 길이 중간 만큼 걸림 Section 2. 자료구조배열일반적으로 배열은 생성하게 되면 운영체제에서 배열의 크기만큼 메모리를 잡게 됨운영체제는 배열의 시작 주소만 기억하고, 배열의 index에 따라 한번에 접근하게됨배열의 참조 성능은 좋지만, 데이터의 삽입, 삭제 성능은 좋지 않음데이터 삽입 시 → 초기에 잡은 메모리 크기보다 큰 크기가 필요할 때, 그만큼의 연속된 메모리 공간을 또다시 찾아야 함. 또 기존 데이터를 복사도 해줘야 함.데이터 삭제 시 → 공간 낭비됨자바스크립트는 다른 프로그래밍 언어와 달리 배열이 연결리스트 형태로 되어 있어서 배열 생성 시 메모리가 연속적으로 있어야하는 단점을 해결함연결리스트저장하려는 데이터들을 메모리 공간에 분산해 할당하고, 이 데이터들을 서로 연결해줌 → Node를 만들어서 사용Node의 구조데이터를 담는 변수다음 노드를 가리키는 변수장점빈 메모리공간 아무 곳에 데이터를 생성하고 연결만 해주면 되기 때문에 배열에서 초기 크기를 알아야 하는 단점이 없음중간에 데이터 삽입 시, 연속된 공간 확보 필요 없이 앞, 뒤 노드의 다음을 가리키는 노드만 바꿔주면 됨단점기존 배열은 시작 주소만 알면 index에 따른 데이터의 접근이 쉽지만(O(1)), 연결리스트는 연결된 노드를 따라 접근해야함(O(n))스택(Stack)FILO(First In Last Out)데이터 삽입을 무조건 첫 번째 인덱스에 하고, 삭제 또한 첫번째 인덱스에서 함일상생활 예시엘리베이터 - 일찍타는 사람이 늦게 내리게 됨포토샵 - 작업 되돌리기 작업문법 에러 체크 시큐(Queue)First In First Out데이터 삽입을 첫 번째 인덱스에 하고, 삭제는 뒤에서부터 제거 함문제점기존 연결리스트에서 구현한 구조로는 맨 뒤의 인덱스에 접근을 하기 위해 O(n) 성능이 나옴.따라서 맨 뒤 인덱스를 가리키는 tail을 만들고, 노드에 이전 노드를 가리키는 변수를 추가해서 이중연결리스트를 만듦.O(1)의 성능으로 삭제를 할 수 있게 함일상생활 예시마트에서 줄 순서대로 계산운영체제 프로세스 처리 (FIFO 스케줄링)맛집, 놀이공원 줄덱(Deque)데이터의 삽입과 제거를 head와 tail 두군데서 자유롭게 할 수 있는 자료구조특성에 따라 스택과 큐 모두 구현할 수 있음해시테이블(Hash)프로그래밍 언어에 따라 해시, 맵, 해시맵, 딕셔너리라고도 불림배열의 공간 낭비를 줄이기 위해 어떤 계산을 거쳐 특정 공간 인덱스에 데이터를 저장하는 방법을 사용 → 어떤 계산 - 해시 함수 (ex, 선수 등번호 % 10)해시 함수에서의 충돌을 해결하기 위해 인덱스를 연결리스트로 구성해 데이터들을 연결함좋은 해시 함수는 데이터를 골고루 분배시켜주는 함수장점빠른 데이터 읽기, 삽입, 삭제 가능단점메모리를 많이 차지함해시 함수에 따라 메모리를 많이 차지할 수도 아닐 수도 있음셋(Set)데이터의 중복을 허용하지 않는 자료구조해시테이블을 사용해 Hash Set이라고 불리기도 함테이블의 value값은 사용하지 않고, key만 사용해서 구현함 '그림으로 쉽게 배우는 운영체제' Section 1, 2, Section 3(Unit 1~4) Section 1. 운영체제 들어가기운영체제 개요운영체제들개인용 컴퓨터 - Windows, MacOS대형 컴퓨터, 서버용 - 유닉스, 리눅스스마트폰, 테블릿 - iOS, Android스마트워치, 세탁기, 냉장고 - 임베디드 운영체제컴퓨터는 운영체제가 있어야 하는가?No, 그러나 원래 설계된대로만 쓸 수 있기에 기능을 추가할 수 있음 (ex, 예전 유선 전화기 vs 스마트폰)운영체제가 하는 일프로세스 관리 : 하나의 프로그램이 CPU를 독차지 하지 않고, 여러프로그램이 동시에 실행될 수 있도록 함메모리 관리 : 여러 프로그램을 메모리에서 관리함하드웨어를 관리 : 사용자의 하드웨어에 대한 직접적인 접근을 막음파일 시스템 관리 : 하드디스크에 많은 파일들의 효율적인 저장과 관리를 함운영체제 역사비싼 CPU를 더 많이 사용하려고 고민했었고, 오퍼레이터와 프로그래머 사이의 낭비되는 시간을 줄이려함 → CPU 사용률과 비용절감을 위한 노력으로 오늘날의 운영체제가 탄생함연도별 운영체제 발전애니악 출현 (1940년대)펜실베니아 대학교에서 미사일 탄도계산을 위해 개발된 컴퓨터 (세계에서 가장 큰 스케일의 전자디지털 계산기)스위치와 배선을 사람이 직접 연결함하드웨어의 비용이 비싸기 때문에 CPU를 최대한 많이 사용할 수 있는 방법에 대해 연구하게 됨직접회로(IC) 개발 (1950년도)진공관과 전선으로 만들어진 논리회로를 아주 작은 크기로 만듦 → 현대적인 컴퓨터의 모습CPU, 메모리는 있지만, 키보드와 마우스는 없음 → 프로그래머가 펀치 카드에 구멍을 뚫어서 프로그래밍을 함오퍼레이터가 직접 컴퓨터에 카드를 넣고 결과가 나오면 프로그래머에게 전달함싱글스트림 배치시스템 (1950년대 중후반)오퍼레이터 오버헤드가 커서 이를 해결하기 위해 프로그래머가 여러개의 펀치카드를 전달하고, 이를 CPU가 순서대로 처리해서 결과도 한번에 확인할 수 있도록 개발함 → CPU 사용률이 올라감I/O 디바이스 컨트롤러 개발(인터럽트) - 입출력 중에도 CPU가 계산할 수 있도록 만들어서 CPU 사용률을 더욱 높임그러나 입력의 경우 어쩔 수 없이 입력이 끝날 때까지 기다려야하기 때문에 CPU 사용률이 떨어지게 됨 → 싱글스트림 배치시스템 한계점시분할 시스템 (1960년대)메모리에 여러 프로그램을 올려놓고 시간을 나누어서 빠르게 돌아가며 실행시킴 → CPU 사용률 증가컴퓨터가 비싸기에 사용자가 여러개의 터미널을 두고 하나의 컴퓨터에 접근해서 사용 → 여러 사용자가 각자의 프로그램을 각각 사용 가능하게 됨 → 개인 컴퓨터같아져서 개인 파일을 저장하게 되면서 파일 시스템 개념이 생겨남 (AT&T 벨 연구소 - UNIX)문제점 생김메모리에 여러 프로그램이 올라와서 작업을 실행함에 따라 메모리 침범 이슈 생김여러 프로그램이 실행됨에 따라 프로그램의 메모리 위치가 변동됨 → 하드웨어적으로 베이스 레지스터를 추가하게 됨개인용 컴퓨터의 시대 (1970년대)애플 매킨토시(GUI 사용), 마이크로소프트 MS-DOS운영체제 구조커널프로세스, 메모리, 저장장치를 관리함사용자는 커널에 직접 접근할 수 없고, 인터페이스를 통해 접근 가능함인터페이스는 GUI, CLI가 있음어플리케이션은 시스템 콜을 이용해서 커널에 접근 가능 → 시스템 콜을 통해 안전하게 하드디스크 빈공간에 데이터를 저장하게 됨하드웨어는 드라이버를 이용해서 커널에 접근 가능 → 그래픽카드나 타블렛 같은 복잡한 장치들은 디바이스 드라이버를 설채해서 사용해야함컴퓨터 하드웨어와 구조폰 노이만 구조 - 프로그램 내장 방식 (프로그램을 메모리에 내장함)애니악 시절 사람이 직접 스위치와 배선을 매번 조정하던 불편함을 해결하기 위해 CPU와 메모리 사이를 버스로 연결하는 방법으로 데이터를 전달하도록 함메모리에 올라간 프로그램은 명령에 따라 처리되고, 소프트웨어만 바꿔주면 됨오늘날의 컴퓨터 하드웨어메인보드 - 다른 하드웨어 연결하는 장치CPU, 메모리, 하드디스크, 그래픽카드, 모니터, 마우스, 키보드, 스피커 등 연결CPU(Central Processing Unit)산술논리 연산장치, 제어 장치, 레지스터로 구성메모리RAM(Random Access Memory), ROM(Read Only Memory)로 구성RAM랜덤으로 데이터를 읽어도 저장된 위치와 상관없이 읽는 속도가 같음전력이 끊기면 데이터를 잃어버림메인메모리로 사용됨ROM전력이 끊겨도 데이터를 계속 보관할 수 있음데이터를 한 번 쓰면 수정 불가능 → 따라서 컴퓨터 부팅과 관련된 바이오스를 저장하는 데에 주로 쓰임컴퓨터의 부팅과정전원 켬 → 바이오스 실행 (주요 하드웨어에 이상 여부 체크) → 이상 없을 시, 하드디스크의 마스터 부트 레코드에 저장된 부트로더를 메모리로 가져와서 실행 → 운영체제 선택 → 컴퓨터 바탕화면 보임 → 실행되는 모든 프로그램은 메모리에 올라와서 운영체제가 관리함인터럽트CPU 관점에서 입출력 완료 여부를 알 수 없기에 주기적으로 계속 체크함(Polling 방식) → 주기적으로 CPU가 체크해야하기 때문에 성능이 좋지 않음인터럽트Polling 방식의 단점을 해결한 방식입출력 관리자가 입출력이 완료되었을 때 CPU에게 신호를 주고, CPU는 그 신호를 받아 인터럽트 서비스 루틴(ISR)을 실행시켜 작업을 완료 함인터럽트 서비스 루틴(ISR) - 특정 인터럽트가 들어오면 그 인터럽트를 처리하는 함수인터럽트는 비동기적으로 동작하기 때문에 성능에 이점이 있음인터럽트 방식하드웨어 방식 - ex, 입출력소프트웨어 방식 - ex, 사용자 프로그램에서 발생한 인터럽트 (유효하지 않은 메모리 접근, 0으로 나누는 명령어) Section 2. 프로세스와 쓰레드프로그램과 프로세스프로그램하드디스크등과 같은 저장장치에 저장된 명령문의 집합체 (ex, 앱, .exe파일 등)컴퓨터 관점에서 저장장치만 사용하는 수동적인 존재프로세스실행중인 프로그램하드디스크에 저장된 프로그램이 메모리에 올라갔을 때, 실행중인 프로그램 → 프로세스라고 불림컴퓨터 관점에서 메모리, 운영체제의 CPU스케줄링 알고리즘에 따라 CPU 사용, 필요에 따라 입출력도 하기에 능동적인 존재프로세스의 구조Code, Data, Heap, Stack으로 나눠짐Code - 자신을 실행하는 코드 저장Data - 전역 변수, Static 변수 저장Stack - 지역 변수, 함수 호출 시 필요한 정보들이 저장Heap - 프로그래머가 동적으로 메모리를 할당하는 데 쓰임코드가 프로세스가 되는 과정코드(ex, C언어) → test.c → 전처리기 → test.i → 컴파일러 → test.s → 어셈블러 → test.o → 링커 → test.exe → 메모리에 올라감 → 프로세스(운영체제에 의해 관리됨)멀티프로그래밍과 멀티프로세싱유니프로그래밍 - 메모리에 오직 하나의 프로세스가 올라온 것(메모리 관점)멀티프로그래밍 - 메모리에 여러개의 프로세스가 올라온 것(메모리 관점)멀티프로세싱 - CPU가 여러개의 프로세스를 처리하는 것(CPU의 관점)오늘날의 OS는 멀티프로그래밍과 멀티프로세싱이 공존함예전에는 메모리의의 크기가 작았기 때문에 유니프로그래밍으로 멀티프로세싱 기법(메모리, 저장장치 데이터 스와핑)을 사용함PCB(Process Control Block)프로세스 생성 시, 프로세스의 정보를 가지고 있는 PCB를 만들고 저장함PCB들은 연결리스트로 저장됨운영체제는 프로세스가 종료되면 연결리스트에서 해당 프로세스의 PCB를 제거함PCB 구조포인터 - 부모와 자식 프로세스에 대한 포인터, 할당된 자원에 대한 포인터, 프로세스의 한 상태에서 다른 상태로 전환될 때 저장하는 포인터 가짐프로세스 상태 - 생성, 준비, 실행, 대기, 완료 나타냄프로세스 ID - 프로세스를 식별하기 위한 숫자 저장프로그램 카운터 - 다음에 실행될 명령어의 주소를 포함하는 프로그램 카운터 저장(시분할처리로 여러 프로세스를 번갈아 실행시키기에 필요하게 됨)레지스터 정보 - 프로세스가 실행될 때 사용했던 레지스터 값들이 저장됨(프로그램 카운터와 마찬가지로 시분할처리에 필요)메모리 관련 정보 - 프로세스가 메모리에 있는 위치 정보, 메모리 침범을 막기위한 경계레지스터 값 등 저장CPU 스케줄링 정보 - CPU 스케줄링에 필요한 우선순위, 최종 실행시간, CPU 점유시간 등이 저장프로세스 상태프로세스는 시분할 처리를 위한 다섯가지 상태를 가짐 : 생성, 준비, 실행, 대기, 완료생성 상태(New)PCB를 생성하고, 메모리에 프로그램 적재를 요청한 상태준비 상태(Ready)메모리에 프로그램 적재를 승인받으면 넘어오게 됨CPU를 사용하기위해 기다리고 있는 상태CPU스케줄러에 의해 CPU가 할당됨실행 상태(Running)준비상태에 있는 프로세스가 CPU스케줄러에 의해 CPU를 할당받아 실행되는 상태실행상태에 있는 프로세스의 수는 CPU의 개수만큼임부여된 시간만큼 CPU 사용 가능 → 시간이 초과되면 다시 준비상태로 돌아감대기 상태(Waiting)프로세스가 입출력 요청을 하면 입출력이 완료될 때까지 기다리는 상태완료 상태(Terminated)프로세스가 종료된 상태프로세스가 사용했던 데이터를 메모리에서 제거하고, 생성된 PCB도 제거함컨텍스트 스위칭(Context Switching)프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행중인 프로세스의 상태를 저장하고 다른 프로세스의 상태값으로 교체하는 작업PCB의 내용이 변경됨 - 실행중인 프로세스의 작업내용을 PCB에 저장하고, 실행될 기존 프로세스의 PCB의 내용대로 CPU가 다시 세팅됨컨텍스트 스위칭이 일어날 때, 프로세스 상태, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보 등이 변경됨컨텍스트 스위칭이 발생하는 이유CPU 점유시간이 다 됨I/O 요청이 있음다른 종류의 인터럽트가 있을 때프로세스 생성과 종료프로세스 생성 방법.exe 파일 실행 → 운영체제가 코드영역, 데이터영역을 메모리에 로드 → 빈 스택, 빈 힙을 만들어 공간 확보 → PCB 생성 및 값 초기화 (운영체제 부팅 후 0번 프로세스가 생성될 때 한 번 실행됨) → 부모 프로세스나머지 프로세스는 0번 프로세스를 복사하게 됨 (fork() 함수 이용) → 새로 생성하는 것보다 복사가 빠르기 때문 → 자식 프로세스자식 프로세스는 부모 프로세스의 코드, 데이터, 스택, PCB 내용 모두 복사함fork() → exex() 실행 시, 자식 프로세스의 코드, 데이터 영역을 원하는 값으로 덮어쓰게 됨 → 부모 프로세스와 다르게 동작함exit() → 자식 프로세스가 부모 프로세스에게 정상 종료를 알림 → 부모 프로세스가 자식 프로세스를 정리함좀비 프로세스 - 부모 프로세스가 먼저 종료되거나, 자식 프로세스가 exit()를 주지못해서 메모리에 계속 살아있는 상태쓰레드프로세스가 많아지면 PCB, 코드, 데이터, 스택, 힙영역도 만들어줘야하기 때문에 무거워짐 → 메모리 많이 차지함 → 쓰레드 고안쓰레드는 프로세스 내에 존재하는 것으로, 1개 이상 있을 수 있음PCB, 코드, 데이터, 힙영역을 공유함스택은 공유하지 않고 쓰레드마다 하나씩 가지고 있음쓰레드를 구분하기 위한 쓰레드ID, TCB(Thread Control Block) 생성프로세스, 쓰레드 장단점안정성 - 프로세스는 독립되어 있기에 다른 프로세스 문제에 영향을 받지 않음, 프로세스는 영향을 받음속도, 자원 - 프로세스는 각자 코드, 데이터, 힙, 스택을 가지고 있고 프로세스간 통신을 하려면 IPC를 이용해야해서 오버헤드가 크고 속도가 느림, 프로세스는 스택영역을 제외한 영역은 모두 공유하기 때문에 오버헤드가 작음. 그러나 공유되는 공간에서 문제가 생길 수도 있음 Section 3. CPU 스케줄링 - (Unit 1~4)CPU스케줄링 개요컴퓨터 자원필수 장치 - CPU, 메모리주변 장치 - HDD, 키보드, 마우스CPU스케줄링운영체제가 모든 프로세스에게 CPU를 할당/해제 하는 것CPU가 스케줄링에서 고려할 사항어떤 프로세스에게 CPU 리소스를 줄 것인가?CPU를 할당받은 프로세스가 얼마의 시간동안 CPU를 사용해야하는가?CPU BurstCPU를 할당받아 실행하는 작업I/O Burst입출력 작업다중큐프로세스 상태에서 준비상태, 대기상태는 큐(Queue)라는 자료구조로 관리됨실행 → 준비 상태가 될 때, 운영체제는 그에 맞는 준비 큐에 넣음실행 → 대기 상태가 될 때, I/O 작업 종류에 따라서 분류된 큐에 들어가게 됨 (ex, 하드디스크 작업 → HDD 큐)정확히는 프로세스 정보를 가지고 있는 PCB가 들어가게 됨스케줄링 목표리소스 사용률CPU 사용률 높이기, I/O 디바이스의 사용률 높이기 등등오버헤드 최소화스케줄링을 하기 위한 계산이 너무 복잡해지거나, 컨텍스트 스위칭을 너무 자주하지 않도록공평성모든 프로세스에게 공평하게 CPU가 할당되어야 함공평의 의미는 시스템에 따라 달라질 수 있음처리량같은 시간 내에 더 많은 처리를 할 수 있는 방법대기 시간작업을 요청하고 실제 작업이 이루어지기 전까지 대기 시간이 짧은 것을 목표로 함응답 시간대화형 시스템에서 사용자의 요청이 얼마나 빨리 반응하는지가 중요하기 때문에 응답시간이 짧은 것을 목표로 함목표간에 서로 상반되는 상황이 있는데, 이 때는 사용자가 사용하는 시스템에 따라 목표를 다르게 설정하게 됨 (ex, 터치스크린 → 응답시간 짧도록, 과학 계산 → 처리량이 높도록 초점 맞춤)FIFO(First In First Out)스케줄링 큐에 들어온 순서대로 CPU를 할당받는 방식먼저 들어온 프로세스가 완전히 끝나야만 다음 프로세스가 실행될 수 있음장점단순하고 직관적단점한 프로세스가 완전히 끝나야 다음 프로세스가 시작되기 때문에 실행시간이 짧고 늦게 도착한 프로세스가 실행시간이 길고 빨리 도착한 프로세스의 작업을 기다려야 함I/O 작업이 있다면 끝날 때까지 쉬고있기 때문에 CPU 사용률이 떨어지게 됨스케줄링의 성능 → 평균 대기 시간으로 평가함프로세스의 실행 순서만 바꿔도 평균 대기 시간의 차이가 많이 남FIFO 알고리즘은 프로세스의 Burst Time에 따라 성능의 차이가 심하게 나기 때문에 현대 운영체제에서 잘 쓰이지 않고, 일괄처리시스템에 쓰임 회고일주일 동안 스스로 칭찬하고 싶은 점, 아쉬웠던 점, 보완하고 싶은 점칭찬하고 싶은 점 : 바쁜 일정 중에도 이번주 범위를 전체적으로 두 번 반복해서 강의를 들으면서 놓친 부분은 없는지 확인했던 점입니다.아쉬웠던 점 : 강의를 듣고 잘 이해했다고 생각했는데, 내 스타일로 아직 명확하게 정리가 되지 않아서 미션 수행 시 조금 당황했던 점입니다.보완하고 싶은 점 : 강의를 듣고 강의 내용에 대해 머릿속으로 정리해보는 시간을 좀 더 가지면 좋을 것 같습니다.다음주에는 어떤 식으로 학습하겠다는 스스로의 목표다음주에는 오늘 범위의 강의를 듣기 전에 어제 범위의 강의를 머릿속으로 다시 생각하고 정리하는 시간을 갖겠습니다.