블로그
전체 9#태그
- 발자국
- 인프런워밍업클럽
2025. 03. 23.
0
[인프런 워밍업 클럽 3기] CS - 3주차 발자국
스터디 회고 무사히 3주차 스터디를 마쳤다.마치고 나서 든 생각은 혼자서 공부했다면 절대 이 시점에 마무리하지 못했을 것이라는 점이다.아마 혼자 했다면 계속 차일 피일 미뤘을 것이다...억지로라도 따로 시간을 내게 해준 것 만으로도 나에겐 충분히 의미가 깊은 스터디였다. 이번 스터디를 하는 내내 만족스러운 강의였다.어느덧 벌써 3주일이 지났는데, 1주차 회고에서 말했듯이 시작할 때 비전공자를 위한 수업이 아닌가 하는 걱정이 있었다.열심히 공부한 것은 아니지만 그래도 한번씩 다 본 내용들이라는 생각과, 심지어 옆에서 따로 전공책으로 CS를 공부하는 친구들도 있었기에 계속 고민이 됐다. 완주를 한 지금 나는, 이해하기 어려웠던것을 그림으로 차근차근 핵심만 짚어주는 강의와 함께 전반적으로 CS 지식을 한번 훑어봤지만따로 CS를 공부했던 친구는, 스터디를 시작하지 않았을 나의 모습처럼 아직 반도 끝내지 못했다.물론 이 강의로 자료구조와 운영체제를 완전히 섭렵했다고 생각하진 않는다. 하지만 전반적인 내용을 쉽게, 이해해서, 한번 훑어봤다는 점에서 아주 만족한다.친구에게도 추천해봤지만 CS 공부에 정답은 없는 만큼 그 친구만의 길이 있으리라 생각한다. 만약 어느 전공자가 이 강의, 또는 스터디를 듣길 고민한다면 정말 추천해주고싶다. 물론 비전공자 또한 말할것도 없다. 크게 빠지는 내용 없이 정말 교수님보다 잘가르친다고 생각한다.
2025. 03. 23.
0
[인프런 워밍업 클럽_3기 CS] 3주차 운영체제 미션
메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요. 레지스터 - 휘발성 메모리로, cpu 계산할 때 메인메모리에 있는 값을 레지스터로 가져온 후 계산한다. 가장 속도가 빠르고 용량이 작다. 캐시 - 휘발성 메모리로, 메인메모리에 있는 값을 레지스터로 옮기려면 시간이 오래걸리기에 필요할것같은 데이터를 저장한다.단계에 따라 가장 속도가 빠른 L1캐시를 보고, 없다면 L2 캐시 확인, 또 없으면 메인 메모리에서 값을 가져온다. RAM - 휘발성으로, 실제 운영체제와 프로세스들이 올라가는 공간이다. 저장공간 대비 비싸기 때문에 데이터를 저장하기보단 실행중인프로그램만 올린다. HDD,SSD - 비휘발성 메모리로, 앞서 말한 메모리보다 상대적으로 느리다. 하지만 저장할 수 있는 용량이 크고 저장공간 대비 상대적으로 값이 싸다. 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요? base register 메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요? 가변 분할 방식은 원하는 논리영역만큼 할당하여 필요한 만큼만 메모리 영역을 사용할 수 있다. 이를 통해 다른 프로세스와 세그먼트를 공유하기 편하고, 각 영역에 댛나 메모리 접근 보호도 편하다.하지만 사용 후 회수할 때 외부단편화가 일어나서 메모리 낭비가 심하다. 고정 분할 방식은 메모리 영역을 미리 고정된 크기로 나누기 때문에 오버헤드가 적다.하지만 작은 프로세스도 큰 영역에 할당되기 때문에 내부단편화가 발생한다. CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요? 스레싱 HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요? 단지 데이터를 저장하는 장치일 뿐이기 때문에 실행에 꼭 필요하다고 생각하지 않는다.그 외의 메모리 안에 운영체제, 실행시킬 파일의 데이터가 모두 올라간다면 문제되지 않는다. 하지만 HDD나 SSD를 제외한 저장장치는 휘발성 메모리이기 때문에, 운영체제를 저장해둘 비휘발성 메모리가 필요하다. 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요? 특정 파일을 삭제해도 파일 시스템은 파일의 모든 정보를 지우는 것이 아니라, 파일 테이블의 헤더만 삭제하고 free block list에 추가하기때문에 사용자 입장에선 사라진것처럼 보이지만사용했던 블록의 데이터는 그대로 남아있기 때문에 복구할 수 있다.
2025. 03. 23.
0
[인프런 워밍업 클럽_3기 CS] 3주차 자료구조 미션
지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요. 버블 정렬은 바로 옆에 숫자와 비교해서 자리를 바꾸는 알고리즘으로, 한번 끝까지 진행하면 가장 큰 숫자는 자기 위치를 찾아서 가장 끝에 정렬된다. 이해와 구현이 간단하지만 O(n^2)의 시간복잡도를 가져서 성능이 별로 안좋다. 선택 정렬은 배열의 정렬되지 않은 영역의 첫 번째 원소를 시작으로 마지막 원소까지 비교하여 가장 작은 값을 첫 번째 원소로 가져온다.역시 이해와 구현이 간단하지만 O(n^2)의 시간복잡도를 가져서 성능이 별로 안좋다. 삽입 정렬은 배열을 정렬,비정렬 영역으로 나눠서 정렬한다. 정렬되지 않은 영역에서 데이터를 꺼내고, 정렬된 영역 내의 적절한 위치에 삽입하여 정렬한다.마찬가지로 구현이 쉽지만, O(n^2)의 시간복잡도를 가져서 성능이 별로 안좋다. 병합 정렬은 분할정복의 방식을 따라서, 큰 문제를 작은 문제로 쪼개서 하나씩 해결한다.쉽게 병렬화되어 처리할 수 있고, O(n log n)의 시간복잡도를 얻기 때문에 다른 정렬에 비해 이득을 볼 수 있다.하지만 높은 메모리 사용량이 필요하고 분석하기가 어렵다. 퀵 정렬도 분할정복 방식을 따른다. 정렬 전에 하나의 원소를 피벗으로 설정하여 피벗보다 크고 작은 값을 기준으로 left, right index 영역으로 구분한다. 즉, 한 번 진행이 될 때 마다 피벗이 정렬되고, 왼쪽 오른쪽 영역을 재귀호출하여 모든 영역을 정렬한다.O(n log n)의 시간복잡도로 병합 정렬과 같아보이지만, 퀵정렬이 더 적은 비교랑 메모리 공간을 차지하기 때문에 퀵 정렬이 더 좋은 알고리즘으로 평가된다. 하지만 피벗을 어떤 것으로 지정하냐에 따라 왼쪽 오른쪽 영역이 한쪽으로 치우칠 수 있기 때문에 최악의 상황으로 O(n^2)이 될 수도 있다. 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요. 우리가 해결해야 하는 것은 메모리가 부족한 상황을 해결해야 하는 것이므로 타뷸레이션을 사용할 것이다.재귀로 쉽게 구현이 가능하다는 판단이 있어도 메모이제이션을 사용한다면 여러 재귀호출로 인해 오히려 메모리를 더 많이 사용하게 될 것이기 때문이다.
2025. 03. 16.
0
[인프런 워밍업 클럽 3기] CS - 2주차 발자국
재귀에 대해 설명해주셨는데, 콜스택을 기반으로 설명해주셔서 머리속에 특히 더 쉽게 받아들인것 같다.학교에서 하노이의 탑 슈도 코드를 처음 봤을 때 저기에서 왜 저쪽 인자를 대입하는 것인지 머리속에 도저히 상상이 안갔었다.대충 재귀 개념만 인지하고 그냥 넘어갔었는데 그림과 화살표, 이 코드가 어느 부분으로 더 작게 쪼개서 구현할 수 있는지 알 수 있어서 이 부분이 제일 이번주에 의미가 있었다고 생각한다. 정렬 알고리즘의 기초인 버블, 선택 정렬 설명도 오랜만에 다시 보니까 쉽게 환기되어 좋았다. 세마포어와 모니터 설명을 위한 그림이 귀여웠다. 책에는 공유자원을 이용하면 안되니까 대기큐에 프로세스를 둔다, 구현해봐라 등등 뜬구름 잡는 글들 한가득이었는데 설명 진짜 대단하다고 느꼈다. 학교에서는 솔직히 운영체제 과목 거의 던져놓고 방치했었는데, 이 강의 덕분에 웬만한 개념들을 확실히 이해할 수 있다는 생각이 든다. cs 기반이 정말 부족하다고 생각했었는데 스스로도 채워지고 있음을 느낀다.
2025. 03. 16.
0
[인프런 워밍업 클럽_3기 CS] 2주차 자료구조와 알고리즘 미션
재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?계속 콜스택에 함수가 쌓이다가 스택 오버플로우가 발생한다. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.int sumOdd(n){ // 재귀 로직 if(n == 1) return 1; return n + sumOdd(n-1); } std::cout 다음 코드는 매개변수로 주어진 파일 경로(.는 현재 디렉토리)에 있는 하위 모든 파일과 디렉토리를 출력하는 코드입니다. 다음 코드를 재귀 함수를 이용하는 코드로 변경해보세요.const fs = require("fs"); // 파일을 이용하는 모듈 const path = require("path"); // 폴더와 파일의 경로를 지정해주는 모듈 function traverseDirectory1(directory){ const stack = [directory]; // 순회해야 할 디렉토리를 저장할 스택 while (stack.length > 0) { // 스택이 빌 때까지 반복 const currentDir = stack.pop(); // 현재 디렉토리 const files = fs.readdirSync(currentDir); // 인자로 주어진 경로의 디렉토리에 있는 파일or디렉토리들 for (const file of files) { // 현재 디렉토리의 모든 파일or디렉토리 순회 const filePath = path.join(currentDir, file); //directory와 file을 하나의 경로로 합쳐줌 const fileStatus= fs.statSync(filePath); // 파일정보 얻기 if (fileStatus.isDirectory()) { // 해당 파일이 디렉토리라면 console.log('디렉토리:', filePath); stack.push(filePath); } else { // 해당 파일이 파일이라면 console.log('파일:', filePath); } } } } traverseDirectory1("."); // 현재 경로의 모든 하위 경로의 파일, 디렉토리 출력 기저조건 : 더 남아있는 directory가 없을때반복 : 인자로 주어진 경로의 디렉토리에 있는 파일or디렉토리들 순회 모르겠습니다
2025. 03. 16.
0
[인프런 워밍업 클럽_3기 CS] 2주차 운영체제 미션
FIFO 스케줄링의 장단점이 뭔가요?구현이 쉽고 직관적이지만, 타임 슬라이스가 큰 프로세스 차례가 되면 그 다음 프로세스가 언제 실행될지 장담할 수 없고 평균 대기시간이 커진다. SJF를 사용하기 어러운 이유가 뭔가요?짧은 프로세스를 먼저 실행하고자 하는 스케줄링인데, 어떤 프로세스가 짧을지 예측이 안되서 사용이 어렵다.또한 FIFO의 단점을 그대로 갖고 있다. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?컨텍스트 스위칭으로 인한 오버헤드가 너무 커져서 프로세스 처리량보다 많아진다. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?프로세스가 실행 중 스스로 cpu를 반납하면 cpu 사용이 적다는 뜻이니 i/o로 구분하고 타임 슬라이스를 오버하는 프로세스는 cpu bound로 구분한다. 공유자원이란무엇인가요?여러 개의 프로세스가 공유해서 사용하는 자원 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?상호배제, 비선점, 점유와 대기, 원형 대기
2025. 03. 09.
0
[인프런 워밍업 클럽_3기 CS] 1주차 자료구조와 알고리즘 미션
여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요. 학생의 정보는 전학, 퇴학이 아니라면 자주 수정되는 것이 아니고, 자료의 참조가 빈번하게 사용될 것으로 예상되므로삽입/삭제, 쓰기 성능에 큰 무게를 두지 않고 읽기 성능이 빠른 자료구조를 선택할 것이다. 우선, 인덱스를 참조하는 자료구조를 선택할텐데 연결리스트는 이에 해당하지 않고배열 또는 해시 테이블을 선택할 것인데, 빈번하진 않더라도 일단 학생의 정보를 저장(삽입/삭제)하긴 해야 하기때문에정보의 삽입 삭제 연산이 더 좋은 해시 테이블을 선택한다. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.선입선출 구조를 이야기하고 있다. 이는 Queue 구조를 말하고 있으므로 Queue 자료구조를 선택한다. 우리가 구현한 스택은 0번 인덱스, 즉 입구쪽으로 데이터가 삽입되고 나오는 구조입니다. 반대로 마지막 인덱스, 즉 출구쪽으로 데이터가 삽입되고 나오는 구조로 코드를 변경해주세요.void push(data){ this.list.insertAt(this.list.count, data); } int pop(){ if(this.list.count == 0) return null; return this.list.deleteAt(this.list.count-1); } 해시테이블의 성능은 해시 함수에 따라 달라집니다. 수업 시간에 등번호를 이용해 간단한 해시 함수를 만들어봤습니다. 이번엔 등번호가 아닌 이름을 이용해 데이터를 골고루 분산시키는 코드로 수정해주세요. 힌트: charCodeAt() 함수를 이용 예시: name1 = "이운재"; name1.charCodeAt(0); // 51060 이운재의 0번 인덱스 ‘이’의 유니코드 출력int hashFunction(name){ int AsciiName = name.charCodeAt(0) int result = AsciiName - 44032 return result % 588; }
2025. 03. 09.
0
[인프런 워밍업 클럽_3기 CS] 1주차 운영체제 미션
운영체제 while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 } 위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요? cpu가 입출력 관리자에게 interrupt를 주어서 해당 프로세스 작업을 멈춘 후 다른 작업을 실행한다.입출력 작업이 끝난다면 입출력 관리자는 cpu에게 신호를 보내고, cpu는 진행중인 프로세스 작업이 끝난 후 해당 프로세스를 실행한다. 프로그램과 프로세스가 어떻게 다른가요? 프로그램은 저장장치에 있는 하나의 application을 의미하고 (명령문 집합체)이 프로그램이 저장장치로부터 메모리에 올라와서 작업을 실행중이면 프로세스라고 말한다. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티 프로그래밍은 메모리에 여러개의 프로세스를 올려서 작업하는 것을 의미하고멀티 프로세싱은 메모리에 올라온 프로세스들을 여러개의 cpu로 작업을 처리하는 것을 의미한다. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요? Process Control Block 을 사용한다. 컨텍스트 스위칭이란 뭔가요?운영체제가 스케줄링을 통해 CPU를 할당 할 프로세스를 바꾸는 작업을 말한다.
2025. 03. 09.
0
[인프런 워밍업 클럽 3기] CS - 1주차 발자국
1주차 회고 나는 컴퓨터 전공생이지만 항상 CS 지식이 부족하다고 느낀다.분명 공부했던 내용이고, 대략적인 흐름은 알고 있지만 질문이 들어온다면 명확하게 대답할 자신이 없다. 비록 학교에서 열심히 공부했던 사람은 아니지만, 그래서 자료구조가 무엇인가에 대해 묻는다면지난주의 나는 기억도 가물가물하고 머리속에 애매하게 남은 기억으로 명확한 개념을 제시하지 못할 것이다.대충 배열, 연결리스트, 스택 등등... 이어지는 흐름은 기억이 나지만그것을 다시 구현하라고 하면 코드 몇줄 끄적이다 포기하는 내가 상상된다. 배운 것은 있지만 뭔가 어렵게 느껴지고 명확하게 대답하지 못하는 나를 보게 됐을 때 CS 스터디를 신청하게 됐다. 처음 강의 목차를 봤을 때학교에서 1학기라는 시간을 투자해서 공부하는 과목을 이렇게 짧은 시간동안만 가르치는게 가능한가? 싶었다.하지만 강의를 보고 난 후, 그동안 CS를 괜히 복잡하고 어렵게만 생각했던 것 같았다. 그림을 통해서, 그것도 집중할 수 있게 짧은 시간 나눠서 핵심만 강의하는 방식에 정말 만족한다. 지금 다시 각각 자료구조들을 구현할 수 있는지, 자료구조가 무엇인지 묻는다면 명확하게 대답할 수 있다.그럴 필요가 없었는데, 처음 자료구조를 배울 때 너무 어렵게 접근했던 것 같다.물론 이미 한번 배웠었던 개념이기에 이해가 쉽다고 느껴질 수도 있다.그래도 이번 1주차 강의 덕분에 CS에 대한 딱딱하고 복잡하게 접근하는 관점을 더 부드럽게 풀어는 계기가 됐다. 요약자료구조 배열의 읽기/쓰기와 삽입/삭제 성능을 Big-O로 알아봤다.이를 응용하여 연결리스트를 만들었고, 배열과 연결리스트의 장단점을 비교했다. 배열은 크기가 고정되어있지만 연결 리스트는 고정되어있지 않고데이터 참조가 자주 필요한 상황이라면 배열의 인덱스를, 데이터의 삽입/삭제가 자주 일어난다면 연결 리스트를 이용하는 것이 좋다. 연결리스트로 스택 자료구조를 구현할 수 있다. 이는 후입선출 구조이다. 선입 선출 구조를 갖는 큐 역시 구현할 수 있다. 삽입은 헤드로, 삭제는 가장 뒤에서부터 노드를 제거한다. 하지만 이런 자료 구조는 앞에 노드가 뒤를 가리키는 일방적인 방향의 자료구조이기 때문에 삭제 연산이 아주 비효율적이다.그래서 단방향 연결리스트를 응용한 이중연결 리스트를 배웠다. 이제 tail 노드를 삭제할 때에 굳이 head 노드부터 차례대로 타고가지 않아도 바로 삭제 가능하다. 다음으로 해시 테이블 자료구조를 배웠다.표에 어떤 내용을 형식 순서에 따라 나타낸 자료구조인데, 이를 인덱스로 접근하다보니 빈 공간이 많이 생겨서 메모리 낭비가 발생한다.그래서 해시함수를 통해 입력받은 데이터를 고루 분포할 수 있도록 인덱스를 부여해준다. 해시 테이블의 장점은 배열과 마찬가지로 빠른 데이터 참조와 삽입/삭제가 있다.하지만 메모리를 많이 차지하기 때문에 미리 공간을 많이 마련해둬야 한다.데이터가 중복된다면 동일 인덱스에 연결리스트로 구현하여 저장했다. 중복을 허용하고 싶지 않다면 Set 자료 구조를 이용한다.이 자료구조는 테이블의 value 값은 사용하지 않고 key 만 사용한다. 즉, 데이터 자체가 key로 사용된다. 운영체제 운영체제는 프로세스, 메모리, 하드웨어, 파일 등을 관리한다.간단하게 컴퓨터의 구조에 대해 알아봤는데, 메인보드 판에서 장치간의 전송을 진행한다.메인보드에 cpu와 메모리를 꽂아주고, 저장장치 연산장치인 하드디스크, gpu 등을 연결함으로서 서로 데이터를 전송할 수 있다. cpu는 중앙 처리 장치의 약자로,산술 논리 연산장치 ALU, 제어장치, 레지스터로 이루어져 있다. 입출력이 들어오면 cpu가 (제어장치) 입출력 장치에게언제 입출력이 완료되는지를 주기적으로 계속 확인한다. 이런 방식을 polling이라고 한다. 이런 방식은 cpu 가동률이 안좋기 때문에 인터럽트를 발생시킨다.인터럽트를 발생시키면 cpu는 해당 입출력 명령을 놔두고, 다른 작업을 한다.입출력 작업이 완료되면 그 때 입출력 관리자는 cpu에게 신호를 주고,cpu는 신호를 받아서 interrupt service routine을 실행시켜서 작업을 완료한다.비동기적이라 성능적으로 이득이다. application이 실행 되면 메모리에 해당 프로그램이 올라간다. 이를 프로세스라고 말하는데운영체제는 이런 프로세스들을 관리하기 위한 Process Control Block을 만들고 저장한다.PCB들은 연결리스트로 저장된다.덕분에 만약 프로세스가 종료된다면 해당 PCB를 쉽게 제거할 수 있다. PCB에는 프로세스에 관련한 여러가지 정보가 있는데CPU가 다른 프로세스에게 할당될 때 PCB는프로세스 상태, 다음 실행할 명령어의 주소를 담고있는 프로그램 카운터, 각종 레지스터값이 변경된다. 프로그램이 실행되면 운영체제는 해당 코드영역과 데이터영역을 메모리에 로드하고 pcb를 만들어서 값을 초기화한다. 그런데 프로세스 단위로 데이터를 처리하기에는 그 수만큼 PCB를 만들어줘야 하기 때문에 메모리가 너무 무거워진다.그래서 프로세스 내에 여러개 존재하는 쓰레드를 고안해냈다. 하나의 프로세스 내의 쓰레드들은 그 프로세스의 pcb, 코드 , 데이터, 힙 영역을 공유한다.스택 영역은 공유하지 않고 쓰레드마다 하나씩 갖고 있다. 이렇게 운영체제는 프로세스가 아닌 쓰레드별로 작업을 처리한다.추가적인 작업이 필요하다면 프로세스가 아닌 쓰레드를 복사하여 처리한다. 프로세스는 각각 독립적이라 하나가 문제생겨도 다른것에 영향을 주지 않는다.하지만 쓰레드는 하나의 프로세스 안에서 존재하기 때문에 모두 영향받기 때문에 안정성 면에서는 프로세스가 우수하다고 할 수 있지만 각각의 프로세스는 자원을 따로 두고 있기 때문에 서로 통신하려면 비용이 크다.반면, 쓰레드는 자원을 공유하기 때문에 오버헤드가 굉장히 적다.속도와 자원면에서는 쓰레드가 더 우수하다. 이제 프로세스들에게 cpu를 할당해줘야 하는데어떤 프로세스에게 할당해줄 것인지, 그럼 얼마나 사용하게 해줄것인지 등 고려사항이 있다.이를 스케줄링이라고 하는데, 각 프로세스들의 평균 대기 시간을 통해 성능을 결정한다. FIFO 방식으로 프로세스에 cpu를 할당한다면, 타임 슬라이스가 큰 프로세스가 먼저 큐에 들어가는 경우그 뒤에 있는 프로세스는 엄청난 시간동안 대기해야 한다.그래서 평균 대기시간이 엄청나게 늘어나기 때문에 보통 사용되진 않는다. 여기에서 burst time이 짧은 것을 먼저 실행시킬 때 평균 대기 시간이 짧아지는 것을 알 수 있었다.그렇다면 짧은 작업 먼저 배치하여 FIFO로 실행하는 Shortest Job First 방법은 어떨까?이런 방법을 사용하기에는 문제가 있는데 어떤 프로세스가 얼마나 실행될지 예측이 힘들다. 즉, 종료시간 예측힘듦burst time이 짧은 프로세스가 중간에 계속 들어오면 burst time 긴 프로세스는 앞에 프로세스 종료될때까지 계속 기다려야해서 영원히 실행안될수도 있다. 그래서 SJF도 사용하지 않는다. 다시 처음으로 돌아가서 FIFO 방식을 극복한 방법으로 Round Robin 방식이 있다. FIFO는 먼저 들어온 것이 다 끝나야 다음 프로세스가 실행된다.이를 해결하기 위해 한 프로세스에게 일정 시간만큼만 cpu를 할당한다.할당시간이 지나면 다른 프로세스에게 강제로 일정시간 cpu를 할당한다.강제로 cpu를 뺏긴 프로세스는 큐의 가장 뒷부분으로 이동시켜서 문제를 해결한다. 하지만 RR 방식은 FIFO와 평균 대기시간이 비슷하다면 더 비효율적이다.큐를 뒷부분으로 이동시키는 컨텍스트 스위칭 시간이 추가되기 때문이다. RR알고리즘의 성능은 타임 슬라이스의 값에 따라 크게 달라진다.타임슬라이스가 무한대면 그냥 fifo이고,적당히 5초로 설정하자니 작업들이 뚝뚝 끊기는 느낌이고,0.0001초를 할당하자니 실행되는 프로세스 처리량보다 컨텍스트스위칭 처리량이 훨씬 커지게 된다.이런 상황을 오버헤드가 너무 크다고 말한다. RR 방식을 극복한 오늘날 보편적인 스케줄링 방식인 Multi Level Feedback Queue가 있다.기본적으론 사용률이 높은 작은 크기 타임슬라이스를 선택한다.대신, cpu 사용률이 높은 cpu bound process들에게는 타임슬라이스를 크게 할당한다. 그렇다면, 운영체제는 cpu bound process랑 i/o bound process 를 어떻게 구분할까? cpu를 사용하는 프로세스가 실행 도중 스스로 cpu를 반납하면 cpu 사용이 적은거니, i/o일 가능성이 높다.반대로 cpu를 사용하는 프로세스가 타임슬라이스 크기를 오버해서 cpu 스케줄러에의해 강제로 cpu를 뺏기는 상황이라면 cpu bound일 확률이 높다. 이런 아이디어를 바탕으로 우선순위를 가진 큐를 여러개 준비해둔다.우선순위가 높으면 타임슬라이스가 작고, 낮으면 타임슬라이스 크기가 커진다.만약 프로세스를 실행하다가 강제로 cpu를 뺏기면 원래 있던 큐보다 낮은 우선순위 큐로 이동한다.최종적으론 무한초 타임슬라이스이기 때문에 fifo처럼 연속적으로 작업을 마칠 수 있게된다.
발자국
・
인프런워밍업클럽