인프런 워밍업 클럽 CS 3기 - 2주차 미션(운영체제)

운영체제FIFO 스케줄링의 장단점이 뭔가요?장점단순하고 직관적임CPU가 스케쥴링 큐에 먼저 들어온 작업부터 순차적으로 처리하는 방식단점FIFO 방식으로 처리되기 때문에 프로세스 실행 시간이 짧은 프로세스가 프로세스 실행 시간이 긴 프로세스보다 스케쥴링 큐에 늦게 들어오면 먼저 들어온 프로세스가 다 끝날 때까지 기다려야 하는 비효율성이 발생I/O 작업이 발생하면 I/O 작업이 끝날 때까지 CPU가 쉬게 되어 CPU 사용률이 떨어지게 됨SJF를 사용하기 어러운 이유가 뭔가요?CPU에 실행할 프로세스의 종료 시간을 예측할 수 없음사용자가 프로세스를 종료해야 끝나는 경우 CPU는 언제 프로세스가 종료될지 알 수 없기 때문에 실제로 프로세스의 종료 시간을 예측하기 어려움Burst Time이 긴 프로세스는 오랫동안 실행되지 않을 수 있음프로세스 실행 도중에 Burst Time이 짧은 프로세스가 계속 추가로 들어오는 경우 Burst Time이 긴 프로세스의 실행이 뒤로 밀려서 Burst Time이 짧은 프로세스가 전부 끝날 때까지 기다리게 됨RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?타임 슬라이스가 작으면 프로세스를 실행하는 시간이 짧아서 컨텍스트 스위칭이 빈번하게 일어나서 CPU를 컨텍스트 스위칭하는 것에 많이 사용하게 되어 성능 저하가 발생운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?CPU Bound Process : CPU 사용률이 높은 경우가 많기 때문에 정해진 타임 슬라이스 크기를 오버하여 스케쥴러가 CPU를 강제로 뺏을 확률이 높음I/O Bound Process : CPU 사용률이 낮은 경우가 많기 때문에 정해진 타임 슬라이스 크기를 오버하지 않고 스스로 CPU를 반납할 확률이 높음공유자원이란무엇인가요?프로세스 간의 통신을 할 때 사용하는 변수나 파일 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?다음 조건을 모두 충족하는 경우에만 교착상태가 발생함상호 배제 : 어떤 프로세스가 자원을 점유하고 있으면 해당 자원은 다른 프로세스에게 공유되면 안됨비선점 : 어떤 프로세스가 자원을 점유하고 있으면 해당 자원의 사용이 끝날 때까지 뺏을 수 없음점유와 대기 : 어떤 프로세스가 자원을 점유한 상태에서 다른 프로세스의 자원을 할당 받기 위해 기다림원형 대기 : 각 프로세스가 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있음

인프런 워밍업 클럽 3기 CS - 1주차 발자국

[강의 내용]운영체제폴링과 인터럽트폴링 : CPU가 입출력 명령이 완료되었는지 주기적으로 확인하는 방식CPU가 주기적으로 확인해줘야 하기 때문에 성능이 좋지 않음인터럽트 : 입출력 명령이 완료되면 CPU에게 신호를 주고 CPU는 신호를 받아 인터럽트 서비스 루틴을 실행시켜 작업을 완료하는 방식비동기적으로 동작하기 때문에 성능에 이점이 있음인터럽트는 하드웨어 인터럽트와 소프트웨어 인터럽트가 존재프로그램과 프로세스프로그램 : 하드디스크에 저장되어 있는 실행파일(.exe 파일)프로세스 : 프로그램을 실행하여 해당 프로그램이 하드디스크에서 메모리로 올려져서 실행 중인 프로그램멀티 프로그래밍과 멀티 프로세싱멀티 프로그래밍 : 하나의 CPU에서 여러 개의 프로세스를 메모리에 올려서 처리하는 기술멀티 프로세싱 : 여러 개의 CPU를 이용하여 프로세스를 처리하는 기술PCB(Process Control Block)프로세스를 관리할 필요가 있는 정보를 포함하는 운영체제 커널의 자료구PCB들은 연결 리스트 자료구조로 저장프로세스 상태생성(new) : PCB를 생성하고 메모리에 프로그램 적재를 요청한 상태준비(ready) : 프로세스가 CPU를 사용 위해 기다리는 상태실행(running) : 프로세스가 CPU를 할당 받아 실행 중인 상태대기(waiting) : 프로세스가 특정 이벤트를 기다리는 상태완료(terminated) : 프로세스가 종료된 상태컨텍스트 스위칭프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행 중인 프로세스 상태를 저장하고 다른 프로세스의 상태값으로 교체하는 작업 쓰레드프로세스 내부에 존재하는 운영체제가 실행하는 단쓰레드는 프로세스의 PCB, 코드, 데이터, 스택, 힙을 공유프로세스에 문제가 생기면 프로세스를 공유하는 모든 쓰레드에 문제가 발생스케쥴링프로세스에게 CPU를 할당/해제하는 알고리듬어떤 프로세스에게 얼마의 시간 동안 CPU를 할당할지에 따라 스케쥴링이 결정됨FIFO(First In First Out)먼저 들어온 프로세스가 먼저 처리하는 방식프로세스가 끝나지 않으면 다음 프로세스를 실행할 수 없음 SJF(Shortest Job First)버스트 타임이 가장 짧은 프로세스를 먼저 실행하는 방식어떤 프로세스가 얼마나 실행될지 예측할 수 없기 때문에 실제로는 구현되지 못한 스케쥴링버스트 타임이 짧은 프로세스가 계속 들어오면 버스트 타임이 긴 프로세스는 계속 실행할 수 없는 기아 상태가 발생하게 됨 RR(Round Robin)프로세스에게 CPU를 할당하고 일정 시간이 지나면 현재 프로세스의 CPU를 다른 프로세스에게 할당하는 방식타임 슬라이스가 크면 먼저 들어온 프로세스를 먼저 처리하는 FIFO 스케쥴링과 같아짐타임 슬라이스가 작으면 프로세스의 처리량보다 컨텍스트 스위칭의 처리량이 커짐MLFQ(Multi Level Feedback Queue)여러 개의 우선순위를 가진 큐를 사용높은 우선순위를 가진 큐는 타임 슬라이스가 작고 낮은 우선순위를 가진 큐는 타임 슬라이스가 큼프로세스가 스스로 CPU를 반납하면 CPU 사용이 적다는 의미로 I/O 바운드 프로세스일 가능성이 높음프로세스가 타임 슬라이스를 오버하여 CPU를 강제로 뺏기면 CPU 사용이 많다는 의미로 CPU 바운드 프로세스일 가능성이 높음 자료구조와 알고리듬자료구조데이터가 어떤 구조로 저장되고 어떻게 사용되는지를 나타내는 용어가장 간단한 자료구조는 변수변수를 어떤 규칙에 따라 생성하고 사용하는지에 따라서 배열, 스택, 큐 등의 다양한 자료구조가 됨시간 복잡도알고리듬의 성능을 측정하는 척도실제 성능을 측정하지 않고 연산의 횟수를 계산하여 대략적인 성능을 측정알고리듬에서 성능에 가장 큰 영향을 주는 연산은 반복문표기법빅 오(Big-O) 표기법은 함수의 상한을 표기빅 오메가(Big-Ω) 표기법은 함수의 하한을 표기빅 세타(Big-θ) 표기법은 함수의 평균을 표기 배열(Array)프로그래머가 요청한 크기만큼 메모리에 연속된 공간을 할당프로그래머가 처음 요청한 크기의 공간을 변경하기 어려움필요한 메모리 공간의 크기를 몰라서 처음부터 많은 메모리 공간을 할당하는 경우가 많아 메모리 낭비가 심함배열은 데이터를 탐색할 때 인덱스를 사용하여 데이터에 바로 접근할 수 있기 때문에 탐색 성능은 O(1)의 성능을 가짐배열은 데이터를 삽입, 삭제할 때 삽입, 삭제하는 데이터의 인덱스 위치 이후에 있는 모든 데이터를 이동 시켜야 하기 때문에 삽입, 삭제 성능은 O(n)의 성능을 가짐연결 리스트(Linked List)각 노드가 데이터를 담는 변수 하나와 다음 노드를 가리키는 변수로 이루어진 자료구조다음 노드를 가리키는 변수가 있어 필요할 때 새로운 노드를 생성하여 연결해줄 수 있음연결 리스트의 첫 번째 노드의 주소만 알고 있으면 다른 모든 노드로 접근이 가능연결 리스트는 데이터를 탐색할 때 첫 번째 노드부터 단계적으로 탐색해야 하기 때문에 탐색 성능은 O(n)의 성능을 가짐연결 리스트는 새로운 노드를 삽입, 삭제할 때 노드를 탐색 후 새로운 노드를 삽입, 삭제만 하면 되기 때문에 삽입, 삭제 성능은 O(1)의 성능을 가짐스택(Stack)가장 최근에 들어온 데이터가 가장 먼저 나가는 LIFO(Last In First Out) 방식의 자료구조스택은 데이터를 탐색할 때 모든 데이터를 삭제하면서 읽고 삭제한 데이터를 다시 스택에 넣어줘야 하기 때문에 탐색 성능은 O(n)의 성능을 가짐스택은 데이터를 삽입할 때 스택의 맨 위에 데이터를 삽입하기 때문에 삽입 성능은 O(1)의 성능을 가짐스택은 데이터를 삭제할 때 스택의 맨 위에 있는 데이터를 삭제하기 때문에 삭제 성능은 O(1)의 성능을 가짐큐(Queue)가장 먼저 들어온 데이터가 가장 먼저 나가는 FIFO(First In First Out) 방식의 자료구조큐도 스택처럼 데이터를 탐색할 때 모든 데이터를 삭제하면서 읽고 삭제한 데이터를 다시 큐에 넣어줘야 하기 때문에 탐색 성능은 O(n)의 성능을 가짐 큐는 데이터를 삽입할 때 큐의 맨 뒤에 데이터를 삽입하기 때문에 삽입 성능은 O(1)의 성능을 가짐큐는 데이터를 삭제할 때 큐의 맨 앞에 있는 데이터를 삭제하기 때문에 삭제 성능은 O(1)의 성능을 가짐덱(Deque)덱은 double-ended queue로 데이터를 head, tail 양쪽 방향에서 삽입, 삭제가 가능한 자료구조 스택과 큐의 특징을 모두 가짐 해시 테이블(Hash Table)Key-Value를 한 쌍으로 데이터를 저장하는 자료구조배열 안에 연결 리스트를 생성하여 같은 인덱스를 갖는 데이터를 연결하는 방식으로 데이터를 저장해시 함수를 이용하여 Key 값을 인덱스로 변경하여 해시 테이블에 골고루 퍼지게 저장하는 것이 성능의 핵심따라서 해시 함수의 성능이 매우 중요해시 테이블은 데이터를 탐색할 때 Key 값만 알면 데이터에 바로 접근할 수 있기 때문에 탐색 성능은 O(1)의 성능을 가짐해시 테이블은 데이터를 삽입, 삭제할 때 Key 값을 이용하여 데이터를 바로 삽입, 삭제하기 때문에 삽입, 삭제 성능은 O(1)의 성능을 가짐해시 셋(Hash Set)Key 값만 사용하여 해시 테이블에 저장하는 자료구조Key 값이 Key이면서 Value가 됨Key와 Value가 같기 때문에 중복된 데이터를 저장할 수 없음1주차 강의 회고발자국의 내용 요약을 작성할 때 진짜로 내용을 요약한 것이 아닌 알고 있는 내용을 나열한 것 같아서 다음 작성할 때는 좀 더 핵심 내용만 작성해 볼 것다음 주에는 강의 내용 이외의 내용들을 더 세세하게 찾아보면서 강의를 학습하며 1주차의 강의를 복습해 나갈 것[미션]미션을 해결하는 과정일단 미션의 내용을 보고 알고 있는 내용을 전부 작성한 후 미션의 내용과 맞는 강의 내용을 찾아보면서 미션을 해결1주차 미션 회고미션을 해결할 때 강의 내용을 찾아보기 전에 이미 알고 있는 내용을 좀 더 생각해서 나열해 보고 해결 방법을 찾는 것이 좋을 것 같음

인프런 워밍업 클럽 CS 3기 - 1주차 미션(자료구조와 알고리듬)

자료구조와 알고리즘여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.해시 테이블을 선택합니다.학생 정보는 학번과 이름 같은 다양한 정보를 Key-Value 형태로 저장Key 값만 알고 있으면 O(1)의 속도로 학생 정보를 수정할 수 있음Key 값만 알고 있으면 O(1)의 속도로 학생 정보를 삭제할 수 있음해시 함수를 잘 고른다면 O(1)의 속도로 빠르게 학생 정보를 조회할 수 있음 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.큐를 선택합니다.큐는 FIFO 방식으로 먼저 들어온 데이터가 먼저 나가는 자료구조기 때문에 들어온 순서대로 처리하는 대기열 같은 프로그램을 만들 때 적합함우리가 구현한 스택은 0번 인덱스, 즉 입구쪽으로 데이터가 삽입되고 나오는 구조입니다. 반대로 마지막 인덱스, 즉 출구쪽으로 데이터가 삽입되고 나오는 구조로 코드를 변경해주세요. push(data){ this.list.insertAt(this.list.count, data); } pop(){ try{ return this.list.deleteAt(this.list.count - 1); } catch(e){ return null; } } peek(){ return this.list.getNodeAt(this.list.count - 1); }해시테이블의 성능은 해시 함수에 따라 달라집니다. 수업 시간에 등번호를 이용해 간단한 해시 함수를 만들어봤습니다. 이번엔 등번호가 아닌 이름을 이용해 데이터를 골고루 분산시키는 코드로 수정해주세요. 힌트: charCodeAt() 함수를 이용 예시: name1 = "이운재"; name1.charCodeAt(0); // 51060 이운재의 0번 인덱스 ‘이’의 유니코드 출력hashFunction(name){ return name.charCodeAt(0) % 10; }

인프런 워밍업 클럽 CS 3기 - 1주차 미션(운영체제)

운영체제 while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?인터럽트 방식을 사용하면 문제를 해결할 수 있음인터럽트 방식은 입출력이 완료되면 CPU에 인터럽트 신호를 보내 현재 실행 중인 프로세스를 중단하고 인터럽트 서비스 루틴을 실행하여 인터럽트를 처리 후 프로세스를 재실행프로그램과 프로세스가 어떻게 다른가요?프로그램 : 하드디스크에 저장되어 있는 실행파일(.exe 파일)실행파일은 해당 프로그램의 동작에 대한 코드로 이루어져 있음프로세스 : 프로그램을 실행하여 해당 프로그램이 하드디스크에서 메모리로 올려져서 실행 중인 프로그램멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티 프로그래밍 : 하나의 CPU에서 여러 개의 프로세스를 메모리에 올려서 처리하는 기술멀티 프로세싱 : 여러 개의 CPU를 이용하여 프로세스를 처리하는 기술운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요? 스케쥴링을 이용하여 각 프로세스에 CPU를 할당 및 해제하여 프로세스의 실행을 관리스케쥴링에 필요한 프로세스의 정보를 각 프로세스의 PCB에 저장컨텍스트 스위칭이란 뭔가요?CPU에 실행 중인 프로세스를 다른 프로세스로 교체하는 기술운영체제에서 CPU에 실행 중인 프로세스의 점유 시간이 끝나면 인터럽트를 발생시켜 프로세스의 상태를 PCB에 저장한 후 메모리에 저장하고 교체할 프로세스의 PCB를 메모리에서 CPU에 가져와 실행시켜줌