마지막 미션

운영체제1. 메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.레지스터휘발성 메모리CPU 내부에 있는 메모리로 ALU의 계산을 위한 값들을 저장하는 용도. 캐시 메모리휘발성 메모리레지스터와 RAM사이의 데이터 이동 작업으로 인한 병목 현상을 줄이기 위한 메모리RAM휘발성 메모리프로그램을 실행시키면 해당 메모리에 올라가서 프로세스가 된다. 보조저장장치비휘발성 메모리HDD, SSD파일 저장 공간으로 사용된다.메모리 크기가 작은 메모리일수록 비싸고 데이터 전송이 빠르다 2. 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?경계 레지스터 / CPU내에 존재하는 레지스터로 메모리 관리자가 사용자 프로세스가 경계 레지스터의 값을 벗어났는지 검사하고 만약 벗어났다면 해당 프로세스를 종료시킨다.3. 메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?가변 분할 방식장점메모리 영역을 모듈로 처리할 수 있기에 공유와 각 영역에 대한 메모리 접근 보호가 편리하다.영역별로 분할돼서 관리가 쉽다.단점외부 단편화가 발생한다.고정 분할 방식장점외부 단편화를 해결효율적인 메모리 관리단점내부 단편화특정 영역에 대한 공유, 권한 부여가 어렵다.페이지 테이블의 메모리 오버헤드페이지 폴트로 인한 오버헤드 4. CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?스레싱 / 제한된 물리 메모리에 의해 스왑 영역에 데이터가 많이 저장되고 Page Fault가 많이 발생하게 되면 스왑을 하는데 이 작업에 의한 오버헤드로 CPU 사용률이 떨어지며, 이를 통해 CPU 스케줄러에 의해 CPU 사용률을 올리기 위해 메모리에 더 많은 프로세스를 올리며 CPU 사용률이 0%에 가깝게 떨어지게 된다.5. HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요?이유를 함께 적어주세요.CPU를 동작하는데에는 운영체제가 필요한데, 메모리에서 비휘발성의 특성을 가진 메모리는 HDD나 SSD같은 보조저장장치 밖에 없기에 컴퓨터를 실행하기 위한 운영체제를 저장할 공간이 필요하다. 6. 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?파일 시스템은 효율적인 관리를 위해 빈 공간을 모아둔 free block list를 가지고 있고,특정 파일을 삭제할 경우 파일의 모든 정보를 지우는 게 아닌 파일 테이블의 헤더를 삭제하고 free block list에 추가한다.데이터는 지워진 게 아니라 복구가 가능한 상태이다.자료구조와 알고리즘1. 지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.버블 정렬 : O(n²)선택 정렬 : O(n²)삽입 정렬 : O(n²)병합 정렬 : O(nlogn)퀵 정렬 : 평균 O(nlogn) / 최악 O(n²)2. 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.타뷸레이션메모이제이션을 통한 방식은 재귀를 통해서 하기에 함수 호출에 대한 메모리 비용 또한 발생하기에타뷸레이션이 더 좋을 것 같습니다. 또한 반복문을 사용하기에 메모리의 크기가 어느 정도 예측 가능하다.

마지막 발자국

알고리즘삽입정렬졍렬된 영역과 정렬되지 않은 영역으로 구분한다.정렬되지 않은 영역에서 데이터를 하나씩 꺼내 정렬된 영역 내 적절한 위치에 삽입하는 알고리즘성능O(n²)장점이해와 구현이 간단단점성능이 좋지 않다void SelectionSort(int* arr, int size) { for(int i = 1; i = 0; j--) { if(arr[j] > insertingData) { arr[j + 1] = arr[j]; } else { break; } } arr[j + 1] = insertingData; } } 병합 정렬 ( Merge Sort)분할정복하는 방법의 정렬 방식 : 해결하기 힘든 문제가 발생하면 한번에 해결하지 않고 해결하기 쉬울 정도로 쪼갠 다음 하나씩 해결병합 정렬은 재귀로 정렬하는 알고리즘병합 정렬 성능 : O(nlogn);장점성능이 좋음단점이해와 구현이 어려움void MergeSort(int* arr, int leftIndex, int rightIndex) { if(leftIndex midIndex) { for(int i = rightAreaIndex; i 퀵 정렬(Quick Sort)분할 정복 알고리즘퀵 정렬의 성능 : O(nlogn) / 최악의 경우 O(n²) : 피벗이 배열을 반으로 가르지 않고 한쪽에 쏠리는 경우성능만 보면 병합 정렬이 더 좋다고 볼 수 있지만 퀵 정렬이 더 적은 비교와 더 적은 메모리 공간을 차지하기 때문에 더 좋은 알고리즘으로 평가받음void QuickSort(int* arr, int left, int right) { if(left = arr[leftStartIndex]) { leftStartIndex++; } while(rightStartIndex >= (left + 1) && pivot 동적 프로그래밍메모이제이션(memoization)계산 결과를 저장해서 여러 번 계산하지 않도록 하는 기법피노나치 수열을 재귀함수로만 구현하면 중복된 계산이 많기에 성능이 좋지 않다.int Fibonacci(int n) { if(n == 0 || n == 1) return n; return Fibonacci(n - 2) + Fibonacci(n - 1); } 계산하려는 데이터가 있는지 검색하고 없다면 함수를 호출해 계산을 하고 그 결과를 저장한다.빠른 데이터 탐색, 삽입, 삭제가 빠른 해시 테이블을 이용.Key에 계산하려는 값을 Value에 계산 결과를 저장하여 계산하려는 값의 검색.#include using namespace std; unordered_map um_memo; int Fibonacci(int n) { if(n == 0 || n == 1) return n; if(um_memo.count(n) > 0) { return um_memo[n]; } else { um_memo[n] = Fibonacci(n - 2) + Fibonacci(n - 1); return um_memo[n]; } } 재귀를 통한 피보나치 수열 시간 복잡도 : O(2^n)메모이제이션을 통한 피보나치 수열 시간 복잡도 : O(n)메모이제이션은 속도가 향상되지만, 메모리를 그만큼 사용한다.타뷸레이션(Tabulation)계산에 필요한 모든 값을 전부 계산 후 테이블에 저장하는 기법 / 상향식 계산 방식에 사용된다.메모이제이션은 재귀를 통해 함수를 호출하기에 콜스택에 함수 호출이 쌓이는 메모리적인 비용이 더 든다.#include using namespace std; unordered_map um_tb; int Fibonacci(int n) { if(n 가상메모리가상메모리 개요프로세스는 가상 메모리를 통해 실행된다. (0X0번지)물리 메모리의 주소를 몰라도 메모리 관리자를 통해 가상 메모리를 통해 물리 메모리로 연결된다.동적 주소 변환 (Dynamic Address Translation) : 메모리 관리자는 메모리와 하드디스크 내 스왑 영역을 합쳐서 프로세스사 사용하는 가상 주소를 물리주소로 변환한다.메모리 관리자의 역할물리 메모리를 어떻게 나눌지프로세스를 어디다 배치할지부족한 물리 메모리는 어떻게 처리할지등의 문제를 처리해야 하기에 복잡한 과정을 거친다.메모리 관리자는 가상 주소와 물리 주소를 일대일 매핑 테이블로 관리한다.세그멘테이션(배치정책)가변분할 방식세그멘테이션에서 프로그램은 함수나 모듈등으로 세그먼트를 구성한다.코드 영역 : 메인 코드가 있는 세그먼트데이터 영역 : 전역 변수들이 있는 세그먼트힙 영역 : 힙 영역이 있는 세그먼트스택 영역 : 스택 영역이 있는 세그먼트각 세그먼트들은 서로 인접할 필요가 없다.사용자와 프로세스, CPU가 바라보는 주소는 논리주소라고 한다.실제 물리 주소로의 변환은 중간에서 메모리 관리자(MMU)가 해준다.메모리 관리자가 논리주소를 물리주소로 변환해주는 방법메모리 관리자는 세그멘테이션 테이블이라는 것을 가지고 있다.세그멘테이션 테이블에는 Base Address와 Bound Address정보가 저장되고 이걸 이용해 물리 메모리 주소를 계산한다.CPU에서 메모리를 전달해주면 메모리 관리자는 이 논리 주소가 몇번 세그먼트인지 알아낸다.메모리 관리자 내에 Segment Table Base Register를 이용해서 물리 메모리 내에 있는 세그멘테이션 테이블을 찾고세그먼트 번호를 인덱스로 Base Address와 Bound Address를 찾는다.운영체제는 컨텍스트 스위칭을 할 때마다 메모리 관리자 내에 Segment Table Base Register를 해당 프로세스의 것으로 값을 바꿔줘야 한다.컨텍스트 스위칭은 이런 작업까지 하기에 굉장히 무거운 동작이다.Bound Address는 세그먼트의 크기를 나타낸다.메모리 관리자는 CPU에서 받은 논리주소와 이 Bound Address의 크기를 비교한다.만약 논리 주소가 Bound Address보다 작다면 논리 주소와 Base Address를 더해 물리 주소를 구하고논리 주소가 Bound Address보다 크다면 메모리를 침범했다고 생각하고 에러를 발생시킨다.장점메모리를 가변적으로 분할할 수 있다코드 영역, 데이터 영역, 스택 영역, 힙 영역등을 모듈로 처리할 수 있기에 공유와 각 영역에 대한 메모리 접근 보호가 편리하다. / 영역별로 분할돼서 관리가 쉬움단점가변 분할 방식의 단점인 외부 단편화가 발생한다.페이징(배치정책)세그멘테이션의 외부단편화를 해결하기 위해 고안되었다.페이징은 메모리를 할당할 때 정해진 크기의 페이지로 나눈다. / 내부단편화가 발생페이지 : 논리 주소 공간에서 일정한 크기로 균일하게 나뉜 것.프레임 : 물리 주소 공간에서 일정한 크기로 균일하게 나뉜 것.메모리 관리자는 페이지 테이블을 가진다.메모리 관리자는 CPU에서 전해주는 논리 주소가 몇 번 페이지인지, 오프셋은 얼마인지 알아낸다.메모리 관리자 내에 있는 PTBR(Page Table Base Register)를 이용해서 물리 메모리에 있는 페이지 테이블을 찾고 페이지 번호를 인덱스로 프레임 번호를 알아내고 오프셋을 이용해 물리주소로 변환을 한다.오프셋은 계산을 통해 쉽게 구할 수 있다.페이지 테이블에 Invalid로 표기되어 있으면 스왑 영역에 저장되어 있다는 의미이다.컨텍스으 스위칭이 발생할 때마다 PTBR을 헤딩 프로세스의 것으로 업데이트 해준다.페이지 넘버 = 논리 주소 / 페이지 크기페이지 넘버는 논리주소를 페이지 크기로 나눈 몫으로 구할 수 있다.오프셋 = 논리주소 % 페이지 크기오프셋은 논리 주소를 페이지 크기로 나눈 나머지이다.페이지 넘버를 페이지 테이블의 인덱스로 사용하여 프레임을 구한 후 해당 프레임 위치에서 오프셋을 더해주면 물리주소로 변환이 완료된다.세그멘테이션과 페이징의 차이프로세스마다 크기가 달라 Bound Address를 가지고 있지만, 페이징은 모든 페이지의 크기가 동일해서 크기를 표현하는 Bound Address는 필요하지 않다.세그멘테이션은 외부단편화가 발생하고 페이징은 내부단편화가 발생한다.외부단편화가 더 많은 공간이 낭비되기에 내부단편화는 심각하게 생각하지는 않는다.세그멘테이션은 논리적인 영역별로 세그먼트를 나눈다. / 코드, 데이터, 힙, 스택페이징은 페이지의 크기가 고정되어 있기에 논리적인 영역을 나눌 수 없다. 그래서 특정 영역만 떼어내서 공유하거나 권한을 부여하는게 더 어렵다. 페이징에서 가장 신경써야 하는 것은 페이지 테이블 크기이다.각 프로세스마다 페이지 테이블을 가지고 있는데 프로세스가 많아질수록 페이지 테이블도 많아지기에 프로세스가 실제로 사용할 수 있는 메모리 영역이 줄어든다.메모리 관리자가 참조하는 페이지 테이블도 물리 메모리의 운영체제 영역에 저장되어 있기에 페이지 테이블 크기가 너무 크면 사용자 영역이 부족해진다. 그렇기에 페이지 테이블의 크기를 적절하게 유지하는 것이 중요하다.페이지드 세그멘테이션(배치정책)세그멘테이션과 페이징을 혼합해 장점을 취한 방식이다. 새로운 단점도 생기긴 했다.메모리 접근 권한메모리의 특정 번지에 부여된 권한으로 읽기, 쓰기, 실행 세 가지가 있다.프로세스는 데이터 영역별로 접근 권한이 있다.코드 : 프로그램 그 자체이므로 수정하면 안됨 | 읽기 / 실행 권한데이터 : 일반변수, 전역변수, 상수로 선언한 변수가 저장된다 | 읽기 / (쓰기) 권한스택, 힙 : 읽기 / 쓰기 권한메모리 접근 권한에 대한 검사는 가상주소에서 물리주소로의 변환이 있을 때마다 일어나는데만약 권한을 위반하면 에러를 발생시킨다.페이지드 세그멘테이션의 세그멘티테이션 테이블은 권한비트, 페이지 넘버, 페이재 개수루 구성된다.가상주소가 들어오면 몇 번 세그먼트인지 알아낸다.그 이후 가상주소의 요청 권한을 확인한 후 위반된 경우 프로세스를 종료시킨다.위반되지 않으면 페이지 넘부와 페이지 개수를 가져온 후 페이지 넘버로 페이지 테이블에 접근해서프레임 번호를 가져오고 물리 메모리 내에 해당 프레임에 접근해 그 위치에서 페이지 개수를 더해 물리주소를 구한다.만약 물리 메모리에 해당 프레임이 없다면 스왑 영역에서 물리 메모리로 가져온다.페이지드 세그멘테이션의 단점은 물리메모리에 접근하기 위해서 메모리에 접근을 두 번해야 된다는 것이다.첫번째는 세그멘테이션 테이블을 참조할 때 두번째는 페이지 테이블에 참조할 때이다.현대 운영체제는 페이징과 페이지드 세그멘테이션 기법을 적절히 혼용한다.디맨드 페이징(가져오기 정책)코드, 데이터, 힙, 스택 영역의 모든 데이터들이 메모리에 올라오는 것이 아니다.필요한 메모리 일부만 올라와서 실행된다.컴퓨터 과학자 도널드 커누스가 발견한 90:10 법칙⇒ 90%의 시간이 10%의 코드에서 보내는 것을 의미이것을 지역성 이론이다.공간의 지역성현재 위치와 가까운 데이터에 접근할 확률이 높음시간의 지역성최근 접근했던 데이터가 오래 전에 접근했던 데이터보다 접근할 확률이 높음goto문 지향의 이유는 코드의 구조파악이 어려운 것도 있지만지역성 이론에 따라 성능에 좋지 않기 때문. / 지역성 이론을 위배지역성 이론은 조만간 사용될 것 같은 데이터만 메모리에 올리고 당분간 필요하지 않을 것 같은 데이터는 스왑영역으로 보내 성능을 향상시킨다.디맨드 페이징 : 조만간 필요할 것 같은 데이터를 메모리로 가져오고 쓰이지 않을 것 같은 데이터는 스왑영역으로 이동시키는 정책이다. / 지역성 이론을 구현한 정책디맨드 페이징은 스왑영역을 보조저장장치에 저장하는데 성능 향상을 위해서는 스왑 영역으로 데이터를 이동시키는 것을 최소화 시켜야한다.가상 메모리 = 메인 메모리 + 하드디스크 내 스왑영역스왑영역에서 물리 메모리로 데이터를 가져오는 것을 스왑인이라 부른다.반대는 스왑아웃이라 부른다.페이지 테이블의 한 행을 페이지 테이블 엔트리(PTE)라고 부른다.페이지 테이블 엔트리에는 프레임 뿐 아니라 여러 정보를 담은 비트로 이루어져 있다.접근 비트 | 변경 비트 | 유효 비트 | 읽기 / 쓰기 / 실행 비트 | 프레임접근 비트 : 페이지가 메모리에 올라온 후 데이터에 접근이 있었는지 알려주는 비트. 메모리에 읽기나 실행 작업을 했다면 1로 바뀐다.변경 비트 : 페이지가 메모리에 올라온 후 데이터의 변경 있었는지 알려주는 비트. 메모리에 쓰기 작업을 했다면 1로 바뀐다.유효 비트 : 페이지가 물리 메모리에 있는지 알려주는 비트. 만약 유효비트가 1이라면 페이지가 스왑영역에 있고 0이라면 물리 메모리에 있다는 의미.읽기 / 쓰기 / 실행 비트 : 권한비트로 해당 메모리에 접근 권한이 있는지 검사하는 비트.프로세스가 가상 메모리에 접근 요청을 했을 때 메모리 관리자는 페이지 테이블을 보고 물리 메모리의 프레임을 찾는데 만약 물리 메모리에 없다면 Page Fault라는 인터럽트를 발생시킨다. Page Fault가 발생하면 보조저장장치의 스왑 영역에 접근하게 되고 해당 프로세스는 대기상태가 된다. 스왑영역에 있는 데이터가 메모리로 올라가는 작업을 시작하고 메모리로 올라갔다면 대기상태에 있던 프로세스는 다시 실행된다.페이지 교체정책페이지 교체정책프로세스가 데이터 참조를 요청했는데 Page Fault가 발생하는 경우 스왑 영역으로 옮길 페이지를 결정하는 정책무작위로 선택하는 방법 : 지역성을 고려하지 않기에 자주 사용되는 페이지가 선택될 수 있어 성능이 좋지 않다. / 거의 사용되지 않음FIFO : 가장 오래된 페이지 선택 / 자주 쓰이는 페이지가 교체되면 공평하지 않을 수 있음 구현이 간단하고 성능도 꽤 괜찮아서 변형해서 많이 사용된다.Optimum : 앞으로 가장 오랫동안 쓰이지 않을 페이지를 선택하는 방법. 사실상 구현이 불가능한 이론적인 선택 방법이다. / 뭐가 가장 사용되지 않을지 알 방법이 없음. / 다른 알고리즘과 성능 비교를 할 때 참조용으로 쓰인다.LRU (Least Recently Used) : 최근에 가장 사용이 적은 페이지를 선택하는 방법. 접근 비트를 통해 LRU에 근접하게 접근한다. / Optimum에 가장 근접한 성능을 보임 최근에 들어온 페이지의 참조 수를 계산해서 판별Clock Algorithm : 접근 비트를 원형으로 연결하고 클락 핸드를 통해 페이지들의 접근 비트를 순회하면서 접근 비트가 0인 경우(데이터 접근 X) 해당 페이지를 스왑 영역으로 보낸다.Enhanced Clock Algorithm : 접근 비트, 변경 비트를 이용 두 비트를 통해 스왑 영역으로 보내질 우선순위 결정하드웨어적으로 접근비트를 지원하지 않는 시스템에선 FIFO를 이용할 수 밖에 없기에 FIFO의 성능을 높이기 위한 방법을 고안함FIFO의 자주 사용하는 페이지가 교체될 수 있다는 단점을 해결하기 위헤 2차 기회 페이지 교체 알고리즘을 고안 / 자주 사용하는 페이지에게 또 한번의 기회를 제공 Page Fault없이 페이지 접근에 성공했다면 해당 페이지를 큐의 맨 뒤로 이동시켜 수명을 연장시키는 방법LRU > 2차 기회 페이지 교체 알고리즘 > FIFO스레싱과 워킹셋스레싱제한된 물리 메모리에 의해 스왑 영역에 데이터가 많이 저장되고 Page Fault가 많이 발생하게 되면 CPU 사용률이 떨어진다. CPU 스케줄러에 의해 CPU 사용률을 올리기 위해 더 많은 프로세스를 메모리에 올리게 되고 이를 반복하게 되면 CPU 사용률이 0에 가깝게 떨어지는데 이를 스레싱이라고 한다.근본적인 원인은 물리 메모리의 크기가 작은것이다.하드웨어적인 해결 방법메모리 크기를 늘린다. 스레싱 발생 지점이 늦춰진다.스레싱이 발생하지 않는다면 메모리 크기를 늘려도 성능에 별 차이 없다.워킹셋소프트웨어적인 해결 방법프로세스가 실행되면 일정량의 페이지를 할당하고 만약 Page Fault가 발생하면 더 많은 페이지를 할당한다. Page Fault가 너무 적게 발생하면 메모리가 낭비되는 것이라 판단하고 페이지를 회수한다. 이렇게 프로세스가 실행되는 동안 해당 프로세스에게 맞는 적절한 페이지 수가 결정된다. 지역성 이론에 따라서 어떤 페이지들을 유지할 것인가가 결정된다. 현재 메모리에 올라온 페이지는 다시 사용할 확률이 높기에 하나의 세트로 묶어서 메모리에 올리는데 이를 워킹셋이라 부르고 워킹셋은 프로세스가 준비상태에서 실행상태가 되는 컨텍스트 스위칭을 할 때 사용된다.입출력 장치주변장치(I/O 디바이스, 저장장치)주변 장치들은 메인보드에 있는 버스로 연결된다.하나의 버스는 Address 버스, Data 버스, Control 버스를 따로 받을 수 있다.각 하드웨어에 맞게 외부 인터페이스가 존재한다.장치의 상태와 데이터를 보관할 수 있는 각종 레지스터들이 존재.이 레지스터들은 입출력 작업을 할 때 데이터를 저장하는 역할.이 값들은 CPU가 사용하기 위해 메모리로 이동되기도 한다.데이터의 전송단위가 캐릭터(글자)냐 블록이냐로 나뉜다.캐릭터 디바이스마우스, 키보드, 사운드 카드, 직렬/병렬 포트등데이터 전송 단위가 캐릭터(글자)로 상대적으로 크기가 작음블록 디바이스하드디스크, SSD, 그래픽 카드 등데이터 전송 단위가 블록(범위)로 상대적으로 크기가 큼예전에는 주변장치들을 하나의 버스로 연결해서 사용했다. CPU 가 작업을 하다 I/O명령을 만나면 직접 입출력 장치에서 데이터를 가져왔는데 입출력중에는 다른 작업을 하지 못하기에 CPU 사용률이 떨어졌다.이를 해결하기 위해 입출력 제어기(I/O Controller)와 여러 개의 버스가 추가됐다.CPU 는 I/O 명령을 만나면 입출력 제어기에게 입출력 작업을 맡기고 다른 작업을 실행한다.입출력 제어기는 두 개의 채널, 시스템 버스와 입출력 버스로 구분한다.시스템 버스는 고속으로 작동하는 CPU와 메모리가 사용하고입출력 버스는 주변장치가 사용.입출력 버스는 세부적으로 느린 장치와 빠른장치를 구분하기 위해 고속 입출력 버스와 저속 입출력 버스로 나눈다. 느린 장치와 빠른 장치를 구분해 속도 차이로 인한 병목 현상을 해결했습니다.그래픽 카드가 다루는 데이터는 매우 대용량이라 고속 입출력 버스로도 감당이 안된다. 그래픽 카드는 입출력 버스에 있지 않고 시스템 버스에 바로 연결해 사용한다.기존에는 입출력 제어기가 여러 주변 장치를 처리하는데 입출력 버스에서 온 데이터를 메모리로 옮긴다. 근데 메모리는 CPU의 명령으로 움직이기 때문에 입출력 제어기가 메모리에 접근하기 위해서는 CPU가 필요하다. 입출력 제어기가 CPU의 도움이 필요 없도록 DMA 제어기가 추가되었습니다.DMA (Direct Memory Access)의 약자로 직접 메모리 접근이라는 뜻.입출력 제어기는 DMA로 데이터를 직접 메모리에 저장하거나 가져올 수 있습니다.CPU와 DMA가 사용하는 메모리가 겹치지 않도록 CPU가 사용하는 메모리 영역과 DMA가 사용하는 메모리 영역을 나누는데 이를 Memory Mapped I/O 라고 부른다. 마우스/키보드광학 마우스는 아래쪽에 작은 카메라가 달려있고, 표면으로 초당 1500회가 넘는 사진을 찍어 마우스의 디바이스 컨트롤내 DSP (Digital Signal Processor)로 보낸다. DSP는 이 사진을 분석해 마우스의 X축 좌표와 Y축 좌표 움직임을 캐치한다. DSP가 마우스의 움직임과 클릭같은 데이터를 감지하면 디바이스 컨트롤러는 CPU에게 인터럽트를 보내고 마우스 드라이버가 동작해서 데이터를 읽어간다. 마우스 드라이버는 운영체제에게 이벤트 신호를 주는데 운영체제는 이 이벤트를 Foreground 애플리케이션으로 전달해주고 해당 애플리케이션은 받은 마우스 이벤트를 처리한다.키보드의 디바이스 컨트롤러가 어떤 키를 입력 받았는지 알아낸다. CPU에게 인터럽트를 보내고 키보드 드라이버는 운영체제에게 이벤트를 보낸다. 그럼 운영체제는 Foreground 애플리케이션으로 이 이벤트를 전달해주고 애플리케이션에서 해당 키에 맞는 동작을 수행한다. 하드디스크/Flash Memory(SSD)주변장치 중 블록 디바이스의 한 종류하드디스크 구조스핀들(spindle)이라는 막대가 있다.스핀들에는 플래터(platter)라는 원판들이 붙어있다.플래터는 자기화된 원판으로 이루어져 있는데 디스크암이 읽기/쓰기 헤드로 플래터의 표면을 읽는다.플래터는 여러 개의 트랙으로 구성되어 있고 표면에 자성이 있기에 표면이 N극을 띄면 0, S극을 띄면 1로 인식한다. 보통 하드디스크의 플래터 수는 2개 이상이다. 헤드는 디스크암에 고정되어 있기에 모든 헤드는 항상 같이 움직인다. 헤드가 움직이면 이 헤드들은 여러 개의 플래터들을 가리키게 되는데 이때 여러 개의 플래터에 있는 같은 트랙의 집합을 실린더라고 부른다. 트랙은 다시 여러 개의 섹터로 나뉘는데 이 섹터가 하드디스크의 가장 작은 단위이다.하드디스크에서 데이터를 읽어오는 예시유저 프로세스가 하드디스크의 특정 섹터에 접근하고 싶어서 이러한 요청을 보낸다.하드디스크의 섹터를 읽어라는 명령을 내리면 디스크암은 헤드를 실린더로 이동시키는데 이를 ‘Seek’라고 부르며 헤드를 실린더로 이동시키는데 걸리는 시간을 Seek Time이라고 부르는데 이것 때문에 하드디스크가 굉장히 느린것이다. 헤드를 목표 지점까지 움직이는 시간은 수 ms인데 다른 전자장비들은 ns단위로 움직이니 상대적으로 굉장히 느리게 느껴짐. 디스크암을 움직여 헤드를 실린더까지 보냈으면 트랙의 섹터가 헤드에 닿을때까지 스핀들을 회전시킨다. 그러다가 헤드에 섹터가 읽히면 작업이 끝난다.Flash Memory(SSD)하드 디스크는 기계적으로 헤드를 움직여 속도가 많이 느리고 소음도 났지만 Flash Memeory는 전기적으로 읽기 때문에 굉장히 빠르고 조용하다. 또한 자기적으로 처리하는 하드디스크는 자석을 갖다 대면 데이터가 손상되지만 Flash Memory는 안전하다.하드디스크는 스핀들처럼 회전축 같은 것들이 있어서 충격에 매우 약하지만 Flash Memory는 그렇지 않다. Flash Memory의 가장 큰 단점은 특정한 지점에 데이터를 썼다면 덮어쓰기가 불가능 하다는 것. 똑같은 지점에 데이터를 쓰려면 기존에 있던 데이터를 지우고 새로 써야 하는데 Flash Memory는 지우기 가능한 횟수가 정해져있다. 그래서 똑같은 지점에 지우기/쓰기를 계속하면 망가진다.파일과 파일 시스템파일은 사용자 요청에 따라 운영체제에 의해 안전하게 저장된다. / 악의적인 사용자에 의한 훼손 가능성 때문에파일 시스템운영체제가 파일을 관리하기 위한 파일 관리자.파일 시스템은 파일 테이블을 이용해서 파일을 관리한다.파일 시스템의 기능파일과 디렉토리 생성파일과 디렉토리 수정/삭제파일 권환 관리 : 다른 사용자로부터 파일을 보호하기 위함 / 요즘 운영체제는 다중 사용자 기능을 지원하기 때문에 파일 보호를 위해 필요한 기능무결성 보장 : 파일의 내용이 손상되지 않도록.백업과 복구 : 예기치 못한 사고로부터 백업과 복구를 한다.암호화파일 접근 방법파일을 관리하는 하드디스크나 Flash Memory(SSD)는 블록 디바이스입니다. 파일 시스템은 전송 단위는 블록이지만, 사용자는 바이트 단위로 파일에 접근이 가능해야 한다. 파일 관리자가 이를 중간에서 관리해준다.파일 구조파일은 헤더와 데이터로 이루어져 있다. 헤더 : 파일의 속성들이 담겨져 있다.파일 이름파일 식별자파일 유형파일 크기시간저장 위치접근 권한소유자파일제어블록(File Control Block, FCB) | (File Descriptor)운영체제는 파일을 관리하기 위해 정보를 보관한다.파일 디스크립터(File Descriptor)라고도 부른다.파일마다 독립적으로 존재하고 저장장치에 존재하다가 파일이 오픈되면 메모리로 이동한다. 파일 디스크립터는 파일 시스템(운영체제)이 관리하고 사용자가 직접 참조할 수는 없다. 사용자는 파일 시스템이 건내준 파일 디스크립터로 파일에 접근할 수 있다.파일의 종류파일의 데이터 집합을 어떻게 구성하느냐에 따라 종류가 구분된다.순차파일구조파일의 내용이 연속적으로 이어진 형태장점 : 모든 데이터가 순서대로 기록되기에 공간의 낭비가 없고 구조가 단순하다.단점 : 특정 지점에 바로 이동이 어려워 데이터를 삽입하거나 삭제하려면 탐색하는데 시간이 많이 걸린다는 것.직접파일구조저장하려는 데이터를 해시함수를 통해 저장 위치를 결정하는 파일구조.해시테이블 방식이며 요즘 많이 쓰이는 데이터 포맷인 json도 이 방식이다.장점 : 해시함수를 이용하기에 데이터 접근이 굉장히 빠르다.단점 : 해시함수의 선정이 굉장히 중요하기에 해시함수를 잘 골라야 한다. / 저장 공간이 낭비될 수 있다.인덱스파일구조순차접근과 직접접근 방식의 장점을 취한 것.두 가지 방식 모두 가능하다.인덱스 테이블을 통해 원하는 순차 데이터의 블록 번호로 접근할 수 있다. 디렉토리파일을 한 공간에 보관하면 파일이 많아지며 관리가 복잡해진다. 그래서 관련있는 파일을 모아둘 수 있도록 디렉토리가 생겼다.디렉토리는 1개 이상의 파일을 가질 수 있고 자식 디렉토리도 가질 수 있다. 최상위에 있는 디렉토리를 루트 디렉토리라 부르며, 그 하위 디렉토리는 자식 디렉토리라고 부른다.윈도우에서는 루트 디렉토리는 파티션 이름으로 사용한다. 보통 C:으로 표시한다. 디렉토리와 디렉토리 구분은 \로 한다.디렉토리도 파일이다. 일반 파일에는 데이터가 저장, 디렉토리에는 파일 정보가 저장되어 있다.디렉토리에서 헤더는 디렉토리 정보가 시작하는 위치를 가리킨다..는 현재 디렉토리를 의미하며..는 상위 디렉토리를 가리킨다.디렉토리는 순환이 있는(바로 이동하기) 트리 구조이다.파일과 디스크파일 시스템은 메모리와 비슷하다.전체 디스크 공간을 일정한 크기를 나누고 그 공간에 주소를 할당해 관리한다.일정한 크기로 나눈 것을 블록이라고 부른다. 한 블록의 크기는 1~8KB정도이다.파일 시스템은 파일 정보를 파일 테이블로 관리하는데 파일이 시작하는 위치 정보도 담겨있다.하나의 파일은 여러 개의 블록으로 이루어져 있는데 이 블록들을 연결한 방식에 따라 연속할당과 불연속할당으로 나눠진다.연속할당파일을 구성하는 블록들을 디스크에 연속적으로 저장하는 방식이다. 파일의 시작 블록만 알면 파일의 전체를 찾을 수 있다.세그멘테이션처럼 외부단편화가 발생하기에 사용되지 않는다.불연속할당디스크에 비어있는 공간에 데이터를 분산해 저장하는 방식이다. 이 분산된 블록은 파일시스템이 관리한다.연결 할당파일에 속한 데이터를 연결리스트로 관리한다.파일 테이블에는 시작 블록에 대한 정보만 저장하고 나머지는 연결리스트를 이용해 다른 블록에 접근하는 방식인덱스 할당테이블의 블록 포인터가 데이터 블록에 직접 연결하는 것이 아닌 데이터들의 인덱스를 가지고 있는 인덱스 블록을 연결한다.인덱스 할당은 데이터가 많아서 테이블이 꽉 찬 경우 인덱스 블록을 더 만들어 연결하기에 테이블을 확장할 수 있다.파일 시스템 저장/삭제 방식디스크에 파일을 저장할 때 빈 공간을 찾으려고 모든 공간을 뒤지는 방식은 비효율적이다.파일 시스템은 효율적인 관리를 위해 빈 공간을 모아둔 free block list를 가지고 있다. 특정 파일을 삭제할 경우 파일의 모든 정보를 지우는 것이 아니라 파일 테이블의 헤더를 삭제하고 free block list에 추가한다. 데이터는 지워진 게 아니라 복구가 가능한 형태이다.

두번째 미션

운영체제 FIFO 스케줄링의 장단점이 뭔가요?장점 : 모든 프로세스가 순차적으로 실행될 수 있고, 일괄처리 시스템에 사용된다.단점 : 처리량, 평균대기시간등의 효율성이 떨어진다, / I/O 작업이 있다면 해당 I/O 작업이 끝날때까지 CPU가 쉬게된다.SJF를 사용하기 여러운 이유가 뭔가요?Burst Time이 짧은 프로세스가 먼저 실행되는데, Burst Time이 긴 프로세스는 실행이 안될 수도 있다.프로세스 종료 시간이 예측이 불가능하다.RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?실행되는 프로세스의 처리량보다 컨텍스트 스위칭이 일어나는 비용이 더 커지게 된다.운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?프로세스가 CPU 점유 시간이 지나 운영체제에 의해 강제로 권한을 뺏기는지, 스스로 CPU 사용을 반납하는지로 구분한다. 공유자원이란무엇인가요?프로세스간 통신을 할 때 공동으로 이용하는 변수나 파일들을 의미교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?상호배제비선점점유와 대기원형 대기 자료구조와 알고리즘 재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?무한루프에 빠져서 콜스택의 메모리를 초과하여 프로세스가 강제종료된다.0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.int sumOdd(int n){ // 재귀 로직 if(n

두번째 발자국

알고리즘재귀재귀란 어떠한 것을 정의할 때 자기 자신을 참조하는 것 콜스텍이란 함수가 호출되면서 올라가는 메모리 영역으로 스택이라고도 부른다.콜스택은 FIFO 특성을 가지고 있다.콜스택은 스택 자료구조를 잘 활용한 대표적인 사례이다. 재귀함수는 자기자신을 호출하는 함수이며, 기저 조건(탈출 조건)이 필요함기저 조건을 만날 때까지 콜스택에 함수가 쌓인다. 재귀함수는 for문을 대신하려고 쓰는게 아닌 더 복잡한 문제를 쉽게 해결하기 위함대표적인 예시로 팩토리얼이 있다.int Factorial(int value) { if(value == 1) return 1; return value * Factorial(value - 1); } 하노이탑재귀함수의 대표적인 예시void Hanoi(int cnt, string from, string to, string temp) { if(cnt == 0) return; Hanoi(cnt - 1, from, temp, to); cout 버블 정렬 (Bubble Sort)가장 쉽게 생각할 수 있는 정렬 중 하나이기에 구현은 쉽지만, 성능은 나쁘다.앞에 있는 숫자와 뒤에 있는 숫자를 비교해서 자리를 바꾸는 알고리즘버블 정렬은 데이터를 옆 데이터와 비교하면서 자리를 바꾸는 게 버블이 일어나는 것 같다 해서 버블 정렬이라는 이름이 붙음.버블 정렬의 성능시간 복잡도 : O(n²)장점이해와 구현이 쉽다.단점성능이 좋지 않다 O(n²)void BubbleSort(int* arr, int size) { for(int i = 0; i arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } 선택 정렬 (Sellection Sort)선택 정렬도 이해와 구현이 쉽지만, 성능이 나쁘다.배열의 정렬 되지 않은 영역을 순회하며 가장 작은 값을 탐색 후 교체다음 원소부터 다시 해당 작업 반복선택 정렬의 성능시간 복잡도 : O(n²)장점이해와 구현이 쉽다.단점성능이 좋지 않음void SelectionSort(int* arr, int size) { for(int i = 0; i arr[j]) { minIndex = j; } } if(minIndex != i) { int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } } CPU 스케줄링SJFShortest Job FirstFIFO 에서 Burst Time이 짧은게 먼저 실행되면 평균 대기 시간이 짧아진다는 것을 발견하고짧은 작업을 먼저 실행하면 된다는 발상에 의해 만들어짐.문제점프로세스 종료 시간 예측 불가능Burst Time이 긴 프로세스는 실행이 안될 수도 있다.RRRound Robin운영체제가 CPU 할당 시간을 지정해 현재 프로세스의 할당 시간이 지나면 다음 프로세스에게 CPU를 할당해주는 방법이 CPU 할당 시간을 타임 슬라이스 or 타임 퀀텀이라고 부른다.RR 알고리즘은 컨텍스트 스위칭이 있기에 비용이 더 발생할 수도 있다.RR 알고리즘의 성능은 타임 슬라이스의 값에 따라 크게 달라진다.타임 슬라이스를 너무 크게 설정하면 FIFO알고리즘과 같은 평균 대기 시간이 발생되고,너무 작게 설정하면 실행되는 프로세스의 처리량보다 컨텍스트 스위칭의 비용이 더 커지게 된다.그렇기에 사용자가 느끼기에 최적의 타임 슬라이스를 찾아야 한다.Windows는 타임 슬라이스가 20ms, Unix는 100ms 정도이다.MLFQMulti Level Feedback Queue현대 운영체제에서 가장 일반적으로 사용되는 CPU 스케줄링 기법이다.MLFQ 는 RR의 업그레이드된 알고리즘이다.CPU Bound Process는 I/O 작업 없이 CPU 연산만 하는 프로세스이다.CPU 사용률과 처리량이 중요I/O Bound Process는 CPU작업은 조금만 하고 대부분의 시간은 I/O 작업에 사용된다.응답 속도가 중요RR 알고리즘으로는 CPU Bound Process 와 I/O Bound Process 둘 다 이득을 보는 구조로 만드려면타임 슬라이스를 작게 설정해야 한다. 이렇게 할 시 I/O Bound Process 는 무조건 이득인 구조이지만,CPU Bound Process에서 같은 프로세스를 계속 실행하지만 컨텍스트 스위칭을 계속해서 해당 비용이 발생하는 문제가 생김.이러한 손해를 해결하기 위해 만들어진 알고리즘이 MLFQ 알고리즘이다.MLFQ의 핵심 로직은 프로세스의 CPU 점유 시간이 지나 강제로 뺏기는지, 스스로 CPU 사용을 반납하는지이다.우선순위를 가진 큐를 여러 개 준비하고, 해당 큐는 우선순위가 낮을 수록 타임 슬라이스 시간을 길게 설정한다.CPU 에게 강제로 뺏긴다면 현재 큐보다 우선순위가 낮은 큐로 이동시킨다. 프로세스 동기화프로세스 간 통신프로세스는 독립적으로도 실행하지만 다른 프로세스와 데이터를 주고 받으며 통신을 하는 경우도 있다.통신은 한 PC 내에 다른 프로세스와 할 수도 있고네트워크로 연결된 다른 프로세스와 할 수도 있다.통신 방법한 PC 내에 프로세스 간 통신 하는 방법파일 : 통신을 하려는 프로세스들이 하나의 파일을 이용해 읽고 쓰는 방법파이프 : 운영체제가 생성한 파이프를 이용해 데이터를 읽고 쓰는 방법네트워크를 이용한 방법운영체제가 제공하는 소켓통신이나 다른 컴퓨터에 있는 함수를 호출하는 RPC(Remote Procedure Call, 원격 프로시저 호출)를 이용해 통신하는 방법한 프로세스 내에 쓰레드 간 통신 하는 방법데이터에 있는 전역변수나 힙을 이용하여 통신이 가능하다.공유자원과 임계구역공유 자원 : 프로세스 간 통신을 할 때 공동으로 이용하는 변수나 파일들공유자원은 여러 프로세스가 공유하고 있기에 각 프로세스의 접근 순서에 따라 결과가 달라질 수 있다.또한 컨텍스트 스위칭으로 시분할 처리를 하기에 프로세스 실행 순서 예측이 힘들며 연산 결과를 예측하기 힘들고 여기서 발생한 문제를 ‘동기화 문제’ 라고 부른다.임계 구역(Critical Section) : 여러 프로세스가 동시에 사용하면 안되는 영역경쟁 조건(Race Condition) : 공유 자원을 서로 사용하기 위해서 경쟁하는 것.임계 구역 문제를 해결하기 위해서는 상호 배제(Mutual Exclusion) 메커니즘이 필요상호 배제의 요구 사항임계 영역엔 동시에 하나의 프로세스만 접근한다.여러 요청에도 하나의 프로세스의 접근만 허용한다.임계 영역에 들어간 프로세스는 최대한 빠르게 나와야한다.세마포어상호 배제 메커니즘의 한 가지세마포어는 운영체제가 관리하는 int형 정수이다.프로세스가 공유 자원을 사용할 때 접근 권한을 얻고 해당 접근 권한을 다시 반납하기 전 까지다른 프로세스가 해당 공유 자원에 접근하지 못하게 하는 것.단점순서를 기다리는 wait()함수와 순서를 반납하는 signal()함수의 순서를 잘못 사용할 가능성이 있음.모니터세마포어의 단점을 해결한 상호 배제 매커니즘이다.모니터는 운영체제가 처리하는 것이 아닌 프로그래밍 언어 차원에서 지원하는 방법이다.키워드가 붙은 함수를 사용중인 프로세스가 있다면 같은 키워드가 붙은 함수를 다른 프로세스에서 실행하지 못함. 자바에서는 synchronized키워드를 사용. 완벽한 상호 배제가 일어남.C++ 에서는 mutex를 사용C#(유니티) 에서는 lock 키워드를 사용데드락데드락이란?데드락(교착상태) : 여러 프로세스가 서로 다른 프로세스의 작업이 끝나기를 기다리다가 아무도 작업을 진행하지 못하는 상태교착상태가 발생하는 이유는 공유자원 때문이다.공유자원을 서로 차지하려다가 교착상태가 발생한 것.교착상태의 필요조건 : 한가지라도 충족되지 않으면 교착상태가 발생하지 않는다.상호배제 : 공유자원에 대한 접근 권한을 부여하여 하나의 프로세스만 이용 가능비선점 : 프로세스가 점유하고 있는 리소스를 다른 프로세스가 빼앗지 못해야 한다.점유와 대기 : 어떤 프로세스가 리소스A를 가지고 있는 상태에서 리소스 B를 원하는 상태여야 한다.원형 대기 : 점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있다.데드락 해결교착상태 예방은 힘들고 해결하는 방안으로 발전교착상태 회피(Deadlock avoidance) : 운영체제가 가지는 총자원의 수와 프로세스들이 요구하는 최대 요구 자원, 현재 할당된 자원, 요청이 예상되는 자원을 통해 안정상태, 불안정상태를 나눈다.가벼운 교착 상태 검출 : 타이머를 이용한 방식. 프로세스가 일정시간 동안 작업을 진행하지 않으면 교착상태가 일어났다고 간주하고 해결하는 방식. / 일정 시점마다 체크포인트를 만들어 작업을 저장하고 타임아웃으로 교착상태가 발생했다면 마지막으로 저장했던 체크포인트로 롤백.무거운 교착 상태 검출 : 자원 할당 그래프를 이용. 운영체제에서 프로세스가 어떤 자원을 사용하는지 지켜보고 교착상태가 발생했다면 해결. / 프로세스들의 자원 요청이 순환인지 아닌지 확인 후 교착상태를 파악한다. 교착상태를 일으킨 프로세스는 강제 종료시킨다. 다시 실행시킬 때 체크포인트로 롤백 시킨다.이 방식은 운영체제가 지속적으로 자원 할당 그래프를 유지고 검사하기에 오버헤드가 발생한다. 하지만 가벼운 교착 상태 검출에서 발생하는 억울하게 종료되는 프로세스가 만들어지지 않는다.메모리레지스터가장 빠른 기억장소로 CPU 내에 존재휘발성 메모리CPU 구분할 때 32bit, 64bit 가 레지스터의 크기를 의미CPU는 계산을 할 때 메인메모리에 있는 값을 레지스터로 가져와 계산을 한다.계산 결과는 다시 메인메모리에 저장시킨다.캐시레지스터는 작업 속도가 매우 빠르고, 메인 메모리는 작업 속도가 느리다.메인 메모리에 있는 값을 레지스터로 옮기려면 한참 걸리기에 미리 필요할 것 같은 데이터를미리 가져오기로 하는데 이 데이터를 저장하는 곳이 캐시이다.휘발성 메모리캐시는 성능의 이유로 여러 개를 둔다.만약 CPU가 값을 요청해 레지스터로 값을 옮겨야 한다면단계에 따라 가장 속도가 빠른 L1 캐시를 보고 여기에 데이터가 없다면 L2 ~ L3 캐시를 확인해보고여기에도 없다면 메인 메모리에서 값을 가져온다.메인 메모리(RAM)메인 메모리는 실제 운영체제와 다른 프로세스들이 올라가는 공간이다.휘발성 메모리실행중인 프로그램만 올리는 용도이다.보조저장장치 (SSD, HDD)비휘발성 메모리사무용 프로그램이나 게임, 작업한 파일등의 데이터를 저장하는데 사용메모리와 주소메모리운영체제는 메모리를 관리하기 위해 1바이트 크기로 구역을 나누고 숫자를 메긴다. 이 숫자가 주소를 의미한다.CPU의 레지스터 크기에 따라 ALU(산술 논리 연산 장치)의 크기와, 데이터가 이동하는 버스의 크기, CPU가 다룰 수 있는 메모리의 크기도 같다.32bit, 64bit레지스터 크기가 클수록 한번에 처리할 수 있는 양이 많기에 속도도 빠르다.물리 주소(절대 주소)와 논리 주소(상대 주소)물리 주소 공간 : 메모리를 컴퓨터에 연결하면 0x0번지부터 시작하는 주소 공간논리 주소 공간 : 사용자 관점에서 바라본 주소 공간사용자는 물리 주소를 몰라도 논리 주소로 물리 주소에 접근 가능하다.운영체제는 특별하기에 운영체제를 위한 공간은 따로 마련한다.사용자가 악의적인 프로그램을 만들어 운영체제를 침범하면 굉장히 위험할 수도 있기 때문그래서 하드웨어적으로 운영체제 공간과 사용자 공간을 나누는 경계 레지스터를 만든다.경계 레지스터 : CPU 내에 존재하는 레지스터로 메모리 관리자가 사용자 프로세스가 경계 레지스터의 값을 벗어났는지 검사하고 만약 벗어났다면 해당 프로세스를 종료시킨다.컴파일러 / 모든 사용자 프로세스가 컴파일을 할 때 메모리 0번지에서 실행한다고 가정.사용자 관점으로 바라보는 주소는 상대 주소는 논리 주소 공간을 의미.메모리 관리자 관점으로 보는 주소는 절대 주소이다.사용자가 100번지의 주소를 요청했을때 CPU가 메모리 관리자에게 100번지의 데이터를 메모리 관리자에게 요청하고 메모리 관리자는 CPU가 요청한 주소와 재배치 레지스터에 있는 4000번지(프로그램의 실제 물리 주소) 값을 더한 4100번지에 접근해 데이터를 가져온다.재배치 레지스터 : 프로그램의 시작 주소가 저장되어 있다.메모리 할당 방식예전에는 유니 프로그래밍 환경에서 메모리보다 더 큰 프로그램을 실행시키는 방법으로메모리 오버 레이 (Memory Overlay) : 큰 프로그램을 메모리에 올릴 수 있도록 잘라서 당장 실행시켜야 할 부분만 메모리에 올리고 나머지는 용량이 큰 하드디스크의 스왑영역에 저장하는 기법스왑 : 스왑영역에 있는 데이터 일부를 메모리로 가져오고 메모리에 있는 데이터를 스왑영역으로 옮기는 것메모리 할방 방식가변 분할 방식(세그멘테이션)프로세스의 크기에 따라 메모리를 나누는 방식한 프로세스가 메모리에 연속된 공간에 할당되기에 연속 메모리 할당이라고 한다.장점크기에 맞게 할당되기에 더 크게 할당되어서 낭비되는 공간인 내부 단편화가 없다. 단점외부 단편화가 발생 세그멘테이션에서 발생하는 외부 단편화는 연속된 공간에 할당되어야 하기에만약에 50MB와 10MB의 빈 공간이 있지만, 데이터 상으로는 60MB도 실행시킬 수 있지만,떨어져있기에 실행이 안되는 현상을 외부 단편화라고 부른다.이 현상을 해결하기 위해서는 운영체제가 조각 모음을 실행해줘야 하는데, 이 작업을 실행하면 모든 프로세스의 작업이 일시 중지되고, 메모리 공간을 이동시키는 작업을 해야 하기에 오버헤드가 발생.고정 분할 방식(페이징)프로세스의 크기와는 상관없이 메모리를 정해진 크기로 나누는 방식한 프로세스가 메모리에 분산되어 할당되기에 비연속 메모리 할당이라고 한다. 장점구현이 간단하고 오버헤드가 적다. 단점공간이 낭비되는 내부 단편화가 발생 내부 단편화 : 분할된 크기보다 작기에 내부에 빈 공간이 생겨 낭비된다.이를 해결하는 방법은 없고 분할되는 크기를 조절해서 내부 단편화를 최소화한다.오늘날의 운영체제는 가변 분할 방식과 고정 분할 방식을 혼합하여 단점을 줄였다.버디 시스템2의 승수로 메모리를 분할해 메모리를 할당하는 방식이다.프로세스가 요청하는 메모리 공간보다 작은 값이 나올 때까지 메모리 공간을 나눈다.그리고 그보다 큰 공간을 프로세스에게 할당해준다.해당 프로세스가 사용을 마치고 메모리에서 나가도 근접한 메모리 공간을 합치기 쉽다.2의 숭수로 동일하게 나눠서 반대로 조립만 하면 큰 공간이 만들어지기에 조각 모음보다 훨씬 간단하다.이 방식의 장점은 가변 분할 방식처럼 프로세스 크기에 따라 할당되는 메모리 크기가 달라지고 외부 단편화를 방지하기 위헤 메모리 공간을 확보하는 것이 간단.내부 단편화가 발생하기는 하지만 많은 공간의 낭비가 발생하지 않는다.

첫번째 미션

운영체제 C while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다.이 방식은 폴링방식입니다.1초마다 체크하기 때문에 성능에 좋지 않습니다.이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?매 순간 체크 해야하는 폴링 방식이 아니라 인터럽트 방식을 적용한다.코드로 구현하자면 콜백 방식을 적용한다는 것이 조금 더 올바른 표현 방식으로 생각됩니다.게임 루프 (물리 => 사용자 입력 => 게임 로직 => 렌더링)사용자 입력 부분에서 스킬 사용이 되었다면 해당 순간에 콜백함수를 호출하여 게임로직에 적용되면매 순간 체크하는 것이 아닌 해당 사용자 입력 순간에만 적용하기에 오버헤드가 감소할 것 입니다. 2. 프로그램과 프로세스가 어떻게 다른가요?프로그램은 저장장치에 코드, 데이터영역이 저장되는 것을 의미하며,프로세스는 해당 프로그램이 메모리에 올라가 코드, 데이터, 힙, 스택영역과 PCB를 할당받아 CPU를 통해 실행되는 것을 의미합니다. 3. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티프로그래밍은 메모리내에 여러 프로그램을 올리는 것이고,멀티프로세싱은 운영체제의 시분할을 이용하여 여러 프로세스를 빠르게 전환하여 사용자 입장에서 동시에 처리되는 것처럼 느껴지는 작업을 의미한다. 4. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?PCB를 통해 프로세스의 정보를 갱신하고, CPU 스케줄링을 통해 프로세스들의 CPU 점유를 결정한다. 5. 컨텍스트 스위칭이란 뭔가요?프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 현재 실행중인 PCB상태를 수정하고 다른 프로세스의 PCB정보를 가져와서 CPU를 다시 세팅하는 과정을 의미한다.자료구조와 알고리즘1. 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요?이유를 함께 적어주세요.강의에는 없지만, 동적배열과 해시 테이블을 같이 사용할 것 같습니다.키 값으로 학년, 반을 구분하고 벨류 값에는 동적배열을 넣어 학생의 출석번호를 인덱스로 삼아 참조하는 방식을 사용할 것 같습니다.해시 테이블을 사용한 이유는 학년, 반을 통해 학생이 소속되어 있는 교실을 찾을 수 있으며,교실의 학생 수는 반 마다 다를 수 있기에, 확장성과 참조속도를 고려하여 동적배열이 어울려 보입니다. 2. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.기본적으로는 큐를 사용하지만, 큐를 응용하여 다중 큐를 구현할 것 같습니다.고객의 메뉴 선택에 따라 오래 걸리는 음식이 있고, 메뉴가 다양할 수도 있습니다.이러한 조건으로 여러 개의 다중 큐를 만들어 손님들의 평균 대기 시간을 줄이려는 시스템을 구축할 것 같습니다.걸리는 시간에 의한 조건만 추가하면 안되고, 후순위 메뉴가 주문이 들어온 지 얼마나 경과했냐 또한 고려해야 합니다.

첫번째 발자국

'그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)'수강생 여러분께 하고 싶은 말외우려 하지 말고 이해해라 어렵다면 그림으로 풀어서 이해해라당장 이해하기 어렵다면 특징만 외우고 나중에 다시 공부하기이해를 했다면 기억도 오래 남고 특징들을 유추할 수 있다자료구조와 알고리즘이란?자료구조는 데이터가 어떤 구조로 저장되고 사용되는지를 나타낸다. (ex. int, float, 정적배열, 동적배열, 연결리스트 등)알고리즘은 어떤 문제를 해결하기 위한 확실한 방법이다.자료구조에 따라 알고리즘이 달라진다.어떤 구현을 할 때 하나의 자료구조가 하나의 알고리즘만을 사용할 수 있는건 아니다. 상황에 맞는 적절한 자료구조와 알고리즘을 적용할 수 있어야 한다.시간복잡도더 좋은 알고리즘이란 무엇일까? 이는 사용자의 요구에 따라 변한다. 보통 메모리, 속도로 구분되며 일반적으로 알고리즘의 속도를 성능의 척도로 사용시간복잡도란 특정 알고리즘이 어떤 문제를 해결할 때 걸리는 시간이며 사용자의 PC성능에 따라 시간 측정은 달라질 수 있으므로 코드에서 성능에 많은 영향을 주는 것을 찾아 실행 시간을 예측하는 것이다.시간복잡도는 최악의 경우를 표현하는 빅 오 표기법을 사용한다.빅 오 표기법은 가장 큰 영향을 미치는 항으로만 표현한다.보통 자료구조의 시간복잡도는 평균, 최악의 경우를 생각한다.자료구조배열연속된 메모리 공간을 할당 받는다.운영체제는 배열의 시작 주소만 기억한다.순차적으로 메모리가 적재되고 운영체제가 배열의 시작 주소를 알기에 인덱스를 통해 접근 가능하다.삽입, 삭제 시 공간이 부족하거나 중간에 있는 요소를 삭제 시 데이터에 대한 이동이 필요해서 오버헤드가 많이 발생한다.인덱스 참조 O(1) / 삭제, 삽입 성능 O(n)연길리스트배열의 단점을 해결하기 위해 만들어진 자료구조저장하려는 데이터들을 메모리 공간에 분산하여 할당하고 이 데이터들을 서로 연결이는 노드라는 것을 만들어 수행노드의 구조는 데이터를 담는 변수 하나와 다음 노드를 가리키는 변수 하나이러한 노드끼리 연결시킨것을 연결리스트라 한다.연결리스트는 첫 노드의 주소만 알고 있으면 다른 모든 노드에 접근 가능.삽입, 삭제시 다음 가리키는 노드만 바꿔주면 된다. / 삽입, 삭제 O(1)메모리 공간이 분산되어 있기에 인덱스 참조가 불가능 즉, 모든 노드 순회해야함 / 참조 O(n)스택First In Last Out (FILO)먼저 들어간 데이터가 나중에 나오는 자료구조삽입, 삭제, 참조 O(1) / 맨 위에 요소만 가능연결리스트, 배열 등으로 구현 가능사용 예제명령 / Undo, Redo문법 괄호 검사큐와 병행하여 회문 검사큐First In First Out (FIFO)먼저 들어간 데이터가 먼저 나오는 자료구조삽입, 삭제, 참조 O(1) / 맨 앞에 요소만 가능이중 연결리스트, 배열등으로 구현 가능사용예제대기열 / 마트 계산대, 게임 큐, 식당 줄 등운영체제 프로세스 작업 요청 / FIFO 스케줄링덱데이터의 삽입과 제거를 Head와 Tail 양쪽에서 자유롭게 할 수 있는 자료구조양방향 끝 삽입 삭제, 참조 O(1) / 가운데 O(n)해시테이블Key와 Value로 이루어진 자료구조Key를 이용한 해시함수를 통해 데이터를 저장만약 해시 충돌이 발생할 경우, 해당 인덱스의 연결리스트에 삽입해시함수의 구현에 따라 공간의 낭비가 극대화될 수도 최적화될 수도 있다.최고의 효율 : 참조, 삽입, 삭제 O(1)최악의 효율 : 참조, 삽입, 삭제 O(n)셋데이터의 중복을 허용하지 않는 자료구조해시 테이블을 활용하기에 해시 셋이라고도 불린다.셋은 헤시 테이블의 Value값은 사용하지 않고 Key만 사용해 구현한다.Key가 Key인 동시에 데이터로 사용하는 것'그림으로 쉽게 배우는 운영체제'운영체제 개요프로세스 관리 메모리 관리 하드웨어 관리 파일 시스템 관리운영체제의 구조운영체제의 핵심 커널은 프로세스와 메모리, 저장장치를 관리한다.사용자는 커널에 직접 접근할 수 없고 인터페이스를 통해 접근 가능하다. (GUI, CLI)어플리케이션은 시스템 콜을 통해 커널에 접근 가능하며, 이를 통해 메모리를 사용할 수 있다.하드웨어는 드라이버를 통해 커널에 접근 가능하다. 컴퓨터 하드웨어와 구조하드웨어로 프로그램을 만들었기에 프로그램이 달라질 때마다 매번 스위치와 배선을 다시 조정해야 했다.폰 노이만은 이를 해결하기 위해 CPU와 메모리를 두고 이들 사이는 버스로 연결한다.버스는 데이터를 전달하는 통로이다.메모리에 올라간 프로그램은 명령에 따라 처리된다.컴퓨터 하드웨어메인보드다른 하드웨어를 연결하는 장치장치 간에 데이터를 전송하는 건 메인보드의 버스가 담당.CPU메모리하드디스크그래픽카드마우스, 키보드, 사운드, 모니터 입출력 장치 CPU(Central Processing Unit)산술논리연산장치(Arithmetic and Logic Unit, ALU) : CPU 에서 실제로 데이터 연산을 담당제어장치 : 모든 장치들의 동작을 지시하고 제어레지스터 : CPU 내에서 계산을 위해 데이터를 임시로 보관하는 장치 메모리 종류RAM(Random Access Memory)랜덤으로 데이터를 읽어도 저장된 위치와 상관 없이 읽는 속도가 같다.전력이 끊기면 데이터를 잃는다(휘발성) / 메인 메모리로 사용ROM(Read Only Memory)전력이 끊겨도 데이터를 계속 보관 가능데이터를 한 번 쓰면 수정 불가능컴퓨터의 부팅과 관련된 바이오스를 저장하는데 사용컴퓨터의 부팅과정ROM에 저장된 BIOS 실행BIOS는 전원, CPU, 메모리, 키보드, 마우스, 하드디스크 등 주요 하드웨어에 이상이 없는지 확인하드디스크에 있는 마스터 부트 레코드에 저장된 부트로더를 메모리에 가져와 실행설치된 운영체제 실행, 메모리에 불러온다.바탕화면이 나오고 실행되는 모든 응용 프로그램은 메모리에 올라가 운영체제가 관리인터럽트입출력 처리 방식폴링CPU가 주기적으로 입출력 장치의 상태를 확인하는 방식효율성이 떨어지고 자원 낭비 심함인터럽트폴링 방식을 개선한 현재 사용되는 방식입력이나 출력이 발생하면 CPU에 인터럽트를 발생CPU는 현재 작업을 중단하고, 이 인터럽트를 처리하기 위해 인터럽트 처리 루틴(Interrupt Service Routine, ISR)로 이동 및 처리완료 후 다른 작업 수행프로세스와 쓰레드프로그램과 프로세스프로그램은 저장장치에 저장된 명령문의 집합체프로세스는 프로그램이 메모리에 올라가 실행중인 프로그램을 의미멀티프로그래밍과 멀티프로세싱멀티프로그래밍은 메모리에 여러 개의 프로세스가 올라간 것.멀티프로세싱은 CPU를 시분할로 여러 개의 프로세스를 처리하면서 동시에 실행되는 것처럼 보이게 하는 것.과거에는 메모리가 작기에 멀티프로그래밍이 불가하여 다른 저장장치에 있는 프로그램을 메모리에 올리는 스와핑을 통해 멀티프로세싱을 처리했다.PCB프로세스가 생성될 때 운영체제는 해당 프로세스의 정보를 가지고 있는 PCB(Process Control Block)를 만들어 저장한다.운영체제는 PCB들을 연결리스트로 관리한다.PCB의 구조포인터 : 부모와 지식 프로세스에 대한 포인터 / 할당된 자원에 대한 포인터 / 프로세스 상태 전환시 저장하는 포인터프로세스 상태 : 생성, 준비, 실행, 대기, 완료프로세스 ID : 식별자프로그램 카운터 : 다음에 실행될 명령어의 주소 저장 / 프로세스가 실행되던 지점 저장레지스터 정보 : 프로세스가 실행될 때 사용했던 레지스터 값들메모리 관련 : 프로세스가 메모리에 있는 위치 정보, 메모리 침범을 막기 위한 경계레지스터 값등 저장CPU 스케줄링 정보 : CPU 스케줄링에 필요한 우선순위, 최종 실행시간, CPU 점유시간 등이 저장등등프로세스 상태운영체제는 시분할 시스템을 활용하여 여러 개의 프로세스를 빠르게 전환하며 실행시킨다.시분할 처리를 위한 다섯가지 상태생성(New) : PCB를 생성하고 메모리에 프로그램 적재를 요청한 상태준비(Ready) : CPU를 사용하기 위해 기다리는 상태대기(Waiting) : 프로세스가 입출력 요청을 하면 입출력이 완료될 때 까지 기다리는 상태 / CPU는 굉장히 빠르고 입출력 작업은 상당히 느리다. 입출력 요청을 하는 프로세스가 완료될 때 까지 CPU를 기다리게 하는 것은 비효율적이기에 대기 상태가 만들어졌다.실행(Running) : CPU 스케줄러에 의해 CPU를 할당받아 실행되는 상태 / 실행상태에 있는 프로세스의 수는 CPU의 개수만큼 존재할 수 있다.완료(Terminated) : 프로세스가 종료된 상태 / 프로세스가 사용했던 데이터를 메모리에서 제거하고 PCB도 제거 컨텍스트 스위칭컨텍스트 스위칭은 프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행중인 프로세스 상태를 저장하고 다른 프로세스의 상태값으로 교체하는 작업을 의미.컨텍스트 스위칭이 일어날 때 PCB의 내용이 변경된다.실행중인 프로세스의 작업내용을 PCB에 저장하고 실행될 프로세스의 PCB의 내용대로 CPU가 다시 세팅된다.컨텍스트 스위칭이 일어날 때 PCB에 변경되는 값들은 아래와 같다.프로세스 상태프로그램 카운터레지스터 정보메모리 관련 정보 프로세스의 CPU 점유시간을 초과하거나 입출력 작업요청 등이 들어오면 인터럽트가 발생하며 컨텍스트 스위칭이 일어난다.프로세스 생성과 종료실행파일이 실행되면 운영체제는 해당 프로그램의 코드영역과 데이터영역을 메모리에 로드하고빈 스택과 빈 힙을 만들어 공간을 확보하며 이 프로세스를 관리하기 위한 PCB를 만들어서 값을 초기화해준다.해당 프로세스 생성 과정은 운영체제가 부팅되고 0번 프로세스가 실행될 때 딱 한번 실행된다.그 이후에 프로세스는 새로 생성하지 않고 0번 프로세스를 복사(fork함수)해서 사용한다.새로 생성하는 것 보다 복사를 하는 게 더 빠르다.exec함수를 통해 부모를 복사한 자식 프로세스의 코드와 데이터 영역을 원하는 값으로 덮어쓴다.exit함수는 자식 프로세스가 부모 프로세스에게 정상 종료를 알리는 함수이다. / 부모 프로세스의 경우 종료부모 프로세스는 자식 프로세스의 Exit Status를 읽고 자식 프로세스를 정리한다.만약 부모 프로세스가 자식 프로세스보다 먼저 종료 되거나 자식 프로세스가 비정상적으로 종료되어 exit()신호를 주지 못해서 Exit Status를 읽지 못해 메모리에 계속 살아 있는 상태를 좀비 프로세스라고 한다.컴퓨터를 오래 켜두면 느려지는 현상이 발생하곤 하는데 메모리에 많은 프로세스가 올라오는 경우거나 좀비 프로세스가 메모리를 차지하기 때문이다.컴퓨터를 껏다키면 메모리가 초기화 되기에 다시 빨라진다.쓰레드사용자가 운영체제에게 작업을 요구하면 그만큼 프로세스 수가 증가프로세스는 메모리에 코드, 데이터, 스택, 힙영역, PCB를 할당해준다.프로세스끼리의 통신은 IPC(Inter Process Comunication)를 이용 / 해당 작업은 비용이 많이 든다.이러한 단점들을 해결하기 위해 고안된 것이 쓰레드이다.쓰레드는 프로세스 내에 존재하는 것으로 1개 이상이 있을 수 있다.쓰레드는 프로세스의 PCB, 코드, 데이터, 힙영역을 공유한다.스택은 공유하지 않고 쓰레드 마다 고유하다.한 프로세스 내에 쓰레드가 여러개 존재하기에 쓰레드 ID, TCB(Thread Control Block)가 생겼다.이제 운영체제가 작업을 처리하는 단위는 프로세스 내에 쓰레드이다.특징안전성 : 프로세스는 서로 독립적이기에 하나의 프로세스가 문제가 있더라도 다른 프로세스는 영향을 받지 않는다.반면 쓰레드는 하나의 프로세스 내에 존재하기에 해당 프로세스에 문제가 생기면 그 안에 모든 쓰레드에 문제가 생긴다.속도, 자원 : 각각의 프로세스는 서로 고유한 자원을 가진다 / 코드, 데이터, 힙, 스택영역을 전부 따로 둔다. 프로세스간의 통신을 하려면 IPC를 이용해야해서 오버헤드가 크고 속도가 느리다.반면 쓰레드는 한 프로세스내에서 스택영역을 제외한 영역은 모두 공유하기에 오버헤드가 굉장히 작다. 쓰레드간의 통신은 데이터를 공유할 수 있으니 쉽게 가능하지만 공유되는 공간에서 문제(공유자원 문제)가 발생할 수 있다. CPU 스케줄링CPU 스케줄링 개요CPU 스케줄링은 운영체제가 모든 프로세스에게 CPU를 할당/해제하는 방식을 의미한다.CPU 스케줄링에서 스케줄러(운영체제)가 고려해야할 사항은어떤 프로세스에게 CPU 리소스를 줘야하는가?CPU를 할당받은 프로세스가 얼마의 시간동안 CPU를 사용해야하는가?두 가지이다.이 두 가지 고려사항이 컴퓨터의 성능에 굉장히 큰 영향을 미친다.이 고려사항을 통해 여러 CPU 스케줄링 방식이 만들어진다.CPU를 할당받아 실행하는 작업을 CPU Burst라 부른다.입출력 작업을 I/O Burst라고 부른다.다중큐해당 프로세스의 우선순위를 보고 준비큐에 넣는다.CPU 스케줄러는 준비상태의 다중큐에 들어있는 프로세스들 중에 적당한 프로세스의 정보(PCB)를 선택해서 실행상태로 전환시킨다프로세스 정보를 담고 있는 PCB가 준비상태의 다중큐에 들어가서 실행되기를 기다리고 있고CPU 스케줄러에의해 실행상태로 전환된다.이때 CPU 스케줄러는 준비상태의 다중큐를 참조해서 어떤 프로세스를 실행시킬지 결정.스케줄링 목표리소스 사용률 : CPU 사용률을 높이는 것, I/O 디바이스 사용률 높이는 것오버헤드 최소화 : 스케줄링을 위한 계산, 컨텍스트 스위칭 오버헤드 비용 최소화공평성 : 모든 프로세스에게 스케줄링 기법에 맞춰 공평하게 CPU가 할당되어야 한다.처리량 : 같은 시간 내에 더 많은 처리를 할 수 있는 방법을 목표로 한다.대기시간 : 작업을 요청하고 실제 작업이 이루어지기 전까지 대기하는 시간이 짧은 것을 목표로 한다.응답시간 : 응답시간이 짧은 것을 목표로 한다.모든 목표를 만족할 수 없기에 사용자가 사용하는 시스템에 따라서 목표를 다르게 설정해야 한다.특별한 목적이 없을 경우, 밸런스를 유지하는게 중요.FIFO먼저 들어온 작업이 먼저 처리되는 스케줄링 방식스케줄링 큐에 들어온 순서대로 CPU를 할당받는 방식 / 해당 방식은 프로세스가 완전히 끝나야만 다음 프로세스가 실행될 수 있다.단점실행중인 프로세스가 완전히 끝나야 다음 프로세스가 실행되는데, 만약 현재 실행중인 프로세스 작업이 길고, 다음 프로세스가 엄청 짧아도, 다음 프로세스는 대기해야 한다. / 효율성(처리량, 대기시간)이 떨어진다.I/O 작업이 있다면 해당 작업이 끝날때까지 CPU가 쉬게되어 CPU 사용률이 떨어진다.스케줄링의 성능은 평균 대기 시간으로 평가된다.평균 대기 시간은 프로세스들 모두가 실행되가끼지 대기시간의 평균을 의미한다. Burst Time이 짧은게 먼저 실행되면 평균 대기 시간 짧아짐.Burst Time이 긴게 먼저 실행되면 평균 대기 시간 길어짐. FIFO알고리즘은 프로세스의 Burst Time에 따라 성능의 차이가 심하게 나기에 현대 운영체제에서 잘 쓰이지 않고 일괄처리 시스템에 쓰인다.