워밍업 클럽(CS) 두번째 미션📓

운영체제Q1. FIFO 스케줄링의 장단점이 뭔가요?장점 : 단순하고 직관적단점 : 한 프로세스가 완전히 끝나야 다음 프로세스 시작, I/O 작업 시 CPU가 기다려야 하므로 사용률이 떨어짐. Q2. SJF를 사용하기 여러운 이유가 뭔가요?어떤 프로세스가 얼마나 실행될 지 예측하기가 어렵고, Burst Time이 긴 프로세스는 오랫동안 실행되지 않을 수 있는 문제가 있다. Q3. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?타임 슬라이스가 작으면 컨텍스트 스위칭이 너무 자주 일어나게 되어 오버헤드가 발생한다. Q4. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?스스로 CPU를 반납하면 CPU 사용이 적은 I/O Bound Process로 판단, 타임 슬라이스 크기를 오버해서 CPU 스케줄러에 의해 강제로 CPU를 뺏기는 상황이면 CPU Bound Process로 판단 Q5. 공유자원이란 무엇인가요?프로세스 간 통신을 할 때 공동으로 이용하는 변수나 파일들 Q6. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?상호배제/ 비선점/ 점유와 대기/ 원형 대기 자료구조와 알고리즘 Q1. 재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?콜스택(메모리 공간)이 가득 차서 자동으로 종료됨 Q2. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n){ if(n

워밍업 클럽 2주차 발자국🐾

그림으로 쉽게 배우는 자료구조와 알고리즘재귀(recursion) : 어떠한 것을 정의할 때 자기 자신을 참조하는 것콜스택함수가 호출되면서 올라가는 메모리 영역, 스택이라고도 부름First In Last Out(그림을 보면 기억이 더 잘 날 것 같아서 캡쳐! FILO를 시각적으로 이해할 수 있어서 좋다💕)재귀함수 예시 : 팩토리얼 함수function factorial(number){ if(number == 1 || number == 0){ return 1; } else{ return number * factorial(number - 1); } }(이게 어떻게 구현이 가능한 것인지 완벽히 이해되지는 않지만, 이렇게 간단히 표현 할 수 있다는 것이 놀랍다.)재귀적으로 생각하기하위 문제의 결과를 기반으로 현재 문제를 계산 -> 하향식 계산재귀함수의 위력은 하향식 계산에서 발휘 배열의 합 function sumArray(arr){ if(arr.length == 1) return arr[0]; return sumArray(arr.slice(0, -1)) + arr[arr.length -1]; }문자열의 길이를 계산function strLength(arr){ if(arr[0] == null) return 0; return strLength(arr.slice(0, -1)) + 1; }지수함수(밑 x, 지수 n)function power(x, n){ if(n == 0) return 1; retrun power(x, n-1) * x; }하노이 탑function hanoi(count, from, to, temp){ if(count == 0) return; hanoi(count - 1, from, temp, to); console.log({"원반 ${count}를 ${from}에서 ${to}로 이동"); hanoi(count -1, temp, to, from); } hanoi(3, "A", "C", "B"); 정렬 - 버블 정렬(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; } } } }버블정렬의 성능 : Ο(n²)장점 : 이해와 구현이 간단함단점 : 성능이 좋지 않음 정렬 - 선택 정렬(Selection Sort)배열의 정렬되지 않은 영역의 첫 번째 원소를 시작으로 마지막 원소까지 비교 후 가장 작은 값을 첫번째 원소로 가져옴function SelectionSort(arr){ for(let i = 0; i 선택 정렬의 성능 : Ο(n²)장점 : 이해와 구현이 간단함단점 : 성능이 좋지 않음 그림으로 쉽게 배우는 운영체제CPU 스케줄링운영체제는 모든 프로세스에게 CPU를 할당/해제하는데 이를 CPU 스케줄링이라고 한다.CPU 스케줄링에서 스케줄러(운영체제)가 고려해야 할 사항 첫번째, 어떤 프로세스에게 CPU 리소스를 줘야하는가?두번째, CPU를 할당받은 프로세스가 얼마의 시간동안 CPU를 사용해야하는가?스케줄링 목표 리소스 사용률오버헤드 최소화공평성 처리량대기시간응답시간스케줄링 알고리즘 FIFO(First In First Out) Burst Time이 짧은게 먼저 실행되면 평균 대기 시간이 짧아진다.SJF(Shortest Job First) 문제1 : 어떤 프로세스가 얼마나 실행될지 예측 어려움문제2 : Burst Time이 긴 프로세스는 오랫동안 실행되지 않을 수도 있다RR(Round Robin) 한 프로세스에 일정 시간만큼 CPU 할당(타임 슬라이스)타임 슬라이스가 작을 경우 컨텍스트 스위칭이 너무 자주 일어나게 되어 오버헤드 발생여러 프로세스가 동시에 실행되는 것처럼 느껴지면서 오버헤드가 너무 크지 않은 값을 찾아야 함Windows는 20ms, Unix는 100msMLFQ(Multi Level Feedback Queue) 오늘날 운영체제에서 가장 일반적으로 사용RR의 업그레이드 버전CPU Bound Process들에게는 타임 슬라이스를 크게 준다. 프로세스 동기화 프로세스 간 통신의 종류한 컴퓨터 내에서 프로세스 간 통신 파일과 파이프 이용쓰레드 이용(한 프로세스 내에서 쓰레드 간 통신)네트워크 이용(소켓통신, RPC(원격 프로시저 호출))공유자원과 임계구역공유자원 여러 프로세스가 공유하고 있기 때문에 각 프로세스의 접근 순서에 따라 결과가 달라질 수 있음"동기화 문제" 발생임계구역 여러 프로세스가 동시에 사용하면 안되는 영역상호 배제 메커니즘 필요 임계영역엔 동시에 하나의 프로세스만 접근한다.여러 요청에도 하나의 프로세스의 접근만 허용한다.임계구역에 들어간 프로세스는 빠르게 나와야한다.세마포어(상호베제 메커니즘의 한 가지)프린터실(공유자원) 열쇠관리자(운영체제) 예시 -> "열쇠 = 세마포어"단점 : wait()함수와 signal()함수의 순서를 이상하게 호출해서 세마포어를 잘못 사용할 가능성이 있음모니터세마포어의 단점을 해결한 상호배제 메커니즘프로그래밍 언어 차원에서 지원하는 방법자바 : synchronized교착상태(데드락)교착상태의 필요조건상호배제비선점점유와 대기원형 대기교착상태 해결 방법교착상태 회피 교착상태가 발생하지 않는 수준의 자원 할당전체 자원과 할당된 자원의 수를 기준으로 안정상태와 불안정상태 구분은행원 알고리즘 교착상태 검출 가벼운 교착 상태 검출 타이머 이용프로세스가 일정시간 동안 작업을 진행하지 않는다면 교착상태 발생 간주일정 시점마다 체크포인트를 만들어 작업 저장, 교착상태 발생했다면 마지막으로 저장했던 체크포인트로 롤백무거운 교착 상태 검출 자원 할당 그래프 이용프로세스가 어떤 자원을 사용하는지 지켜보고 교착상태가 발생했다면 해결교착상태를 일으킨 프로세스 강제 종료, 다시 실행할 때 체크포인트로 롤백자원 할당 그래프를 유지하고 검사해야 하기 때문에 오버헤드 발생 메모리메모리 종류레지스터 가장 빠른 기억장소, CPU 내에 존재휘발성 메모리32bit 64bit캐시 메인메모리에 있는 값을 레지스터로 옮기려면 한참 걸리기 때문에 필요할 것 같은 데이터 미리 가져와 저장메인메모리(RAM) 운영체제와 프로세스들이 올라가는 공간휘발성 메모리보조저장장치(HDD, SSD) 비휘발성 메모리 메모리와 주소 메모리 = 메인메모리(RAM)물리주소와 논리주소 - 사용자절대주소와 상대주소 - 메모리 관리자메모리 할당 방식 메모리 오버레이(memory overlay) 프로그램을 잘라서 실행시켜야 할 부분만 메모리에 올리고 나머지는 하드디스크(스왑영역)에 저장가변 분할 방식(세그멘테이션) 프로세스의 크기에 따라 메모리를 나누는 방식연속 메모리 할당장점 : 낭비되는 공간인 '내부 단편화'가 없음단점 : 외부 단편화 발생(조각모음으로 해결, but 실행되고 있는 프로세스 중지해야 함 오버헤드 발생)고정 분할 방식(페이징) 프로세스 크기와 상관없이 메모리를 할당비연속 메모리 할당장점 : 구현이 간단, 오버헤드가 적음단점 : 내부 단편화 발생버디 시스템(가변 + 고정 혼합) 2의 승수로 메모리 분할각 단점 최소화

워밍업 클럽(CS) 첫번째 미션📓

운영체제1번while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }Q : 위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?A : 인터럽트🔎개념폴링 : 주기적으로 CPU가 확인해줘야 하니 성능이 좋지 않다.인터럽트 : 폴링 방식의 단점을 해결 하드웨어 인터럽트 : 입출력 등과 같은 인터럽트소프트웨어 인터럽트 : 사용자 프로그램에서 발생한 인터럽트 예시) 유효하지 않은 메모리 접근, 0으로 나누는 명령 2번Q : 프로그램과 프로세스가 어떻게 다른가요?A : 프로그램이 메모리에 올라가 실행 중일 때를 프로세스라고 부른다.🔎개념프로그램 하드디스크 등과 같은 저장장치에 저장된 명령문의 집합체애플리케이션이나 앱이라고 불림Windows 운영체제에서는 .exe 파일의 모습컴퓨터 관점에서 하드디스크 즉 저장 장치만 사용하는 수동적 존재프로세스 실행중인 프로그램하드디스크에 저장된 프로그램이 메모리에 올라갔을 때메모리도 사용, 운영체제의 CPU 스케줄링 알고리즘에 따라 CPU도 사용, 입출력 사용하는 능동적 존재프로세스의 구조 Code 영역 : 자신을 실행하는 코드 저장Data 영역 : 전역 변수와 Static(정적) 변수 저장Stack 영역 : 지역 변수, 함수 호출시 매개변수와 돌아갈 주소가 저장Heap 영역 : 프로그래머가 런타임시 할당할 수 있는 메모리 공간 3번Q : 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?A : 멀티프로그래밍은 메모리의 관점, 멀티프로세싱은 CPU의 관점으로 정의🔎개념유니프로그래밍 : 메모리에 프로세스 1개멀티프로그래밍 : 메모리에 여러 개의 프로세스멀티프로세싱 : CPU가 여러 개의 프로세스를 처리하는 것 4번Q : 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?A : PCB(Process Control Block)🔎개념프로세스가 만들어지면 운영체제는 해당 프로세스의 정보를 가지고 있는 PCB를 만들고 저장PCB들은 연결리스트로 저장운영체제는 프로세스가 종료되면 연결리스트에서 해당 프로세스의 PCB 제거PCB의 구조 포인터 : 부모와 자식 프로세스에 대한 포인터, 할당된 자원에 대한 포인터, 프로세스의 한 상태에서 다른 상태로 전환될 때 저장하는 포인터프로세스 상태 : 현재 프로세스의 다섯가지 상태(생성, 준비, 실행, 대기, 완료)프로세스 ID : 프로세스를 식별하기 위한 숫자프로그램 카운터 : 다음에 실행될 명령어의 주소를 포함하는 프로그램 카운터 저장레지스터 정보 : 프로세스가 실행될 때 사용했던 레지스터 값 프로그램 카운터와 마찬가지로 CPU를 뺏기고 다시 시작할 때 이전에 사용하던 값을 복구하기 위한 용도메모리 관련 정보 : 프로세스가 메모리에 있는 위치 정보, 메모리 침범을 막기 위한 경계레지스터 값CPU 스케줄링 정보 : CPU 스케줄링에 필요한 우선순위, 최종 실행시간, CPU 점유시간 등 5번Q : 컨텍스트 스위칭이란 뭔가요?A : 프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행중인 프로세스의 상태를 저장하고 다른 프로세스의 상태값으로 교체하는 작업🔎개념컨텍스트 스위칭이 일어날 때 PCB의 내용이 변경됨실행중인 프로세스의 작업내용을 PCB에 저장하고 실행될 기존 프로세스의 PCB의 내용대로 CPU가 다시 세팅컨텍스트 스위칭이 일어날 때 PCB의 프로세스 상태, 프로그램 카운터, 각종 레지스터값 등이 변경 자료구조와 알고리즘1번Q : 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.A : 연결리스트, 데이터의 추가와 삭제가 간단한 작업으로 가능하기 때문에 학생이 전학을 오고 갈 때 관리가 쉬울 것으로 판단했습니다. 2번Q : 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.A : 큐, FIFO 먼저 들어간 데이터가 먼저 나오는 규칙이기 때문에 순서대로 들어온 주문을 처리하기 위해선 큐 자료구조가 적합하다고 판단했습니다.

워밍업 클럽(CS) 첫 스타트🐣 1주차 발자국🐾

전공자 만큼의 지식을 갖기 위한 나의 첫걸음, 인프런 워밍업 클럽과 함께❤비전공자에 공무원인 내가 개발자가 되기를 꿈꾸며 시작한 인프런 워밍업클럽!진짜 먼 여정이 남았지만 첫 시작을 이번 워밍업클럽과 하게되어 너무 즐겁고,그 첫 발자국을 이렇게 남깁니다. 강의 한줄평✏'감자'님의 강의는 깔끔한 화면과 깔끔한 설명으로 공부하면서 눈도 즐거운 완벽한 강의다.1주차 발자국📓 그림으로 쉽게 배우는 자료구조와 알고리즘프로그램 = 자료구조 + 알고리즘자료구조 데이터가 어떤 구조로 저장되고 어떻게 사용되는 지를 나타냄예시 : 변수, 배열알고리즘 어떤 문제를 해결하기 위한 확실한 방법 알고리즘의 속도 => 성능의 척도 "시간복잡도"특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간코드에서 성능에 많은 영향을 주는 부분 -> "반복문"성능 평가 Big-Ω 최선의 경우 한 번에 찾음Big-Ο 최악의 경우 배열의 길이만큼 걸림 ✔Big-Θ 평균의 경우 배열의 길이 중간만큼 걸림 배열일반적인 배열 배열을 선언할 때 배열의 크기를 알려준다.예시 int arr[10] = {1, 2, 3, 4, 5};운영체제는 숫자 10개가 들어갈 수 있는 연속된 빈 공간을 찾아 1,2,3,4,5 할당운영체제는 배열의 시작 주소, 즉 1이 들어간 주소만 기억배열의 인덱스 참조는 길이에 상관없이 한 번에 가져오기 때문에 Ο(1)의 성능을 가진다.읽기 쓰기 참조 성능 Good, 데이터의 삽입 삭제 성능 Bad 자바스크립트의 배열 상황에 따라 연속적, 불연속적으로 메모리 할당불연속적으로 할당된 메모리는 내부적으로 연결 연결리스트(Linked List)크기를 모르면 메모리가 낭비될 수 있다는 배열의 단점을 해결하기 위해 등장저장하려는 데이터를 메모리 공간에 분산해 할당하고 데이터들을 서로 연결노드(Node)를 만들어서 수행 , 노드 = 데이터를 담는 변수 + 다음 노드를 가리키는 변수연결리스트는 데이터들이 전부 떨어져 있기 때문에 바로 접근 X데이터 참조 성능 : O(n)추상자료형 : 어떠한 데이터와 그 데이터에 대한 연산연결리스트의 추상자료형 모든 데이터 출력 printAll()모든 데이터 제거 clear()인덱스 삽입 insertAt(index, data);마지막 삽입 insertLast(data); 인덱스 삭제 deleteAt(index);마지막 삭제 deleteLast();인덱스 읽기 getNodeAt(index);"Node" 클래스 선언, "LinkedList" 클래스 선언class Node{ constructor(data, next = null){ this.data = data; # 자바스크립트에서 클래스 내의 변수는 프로퍼티 this.next = next; } } class LinkedList{ constructor(){ this.head = null; this.count = 0; } insertAt(index, data){ if(index > this.count || index 스택(stack)First In Last Out(FILO)먼저 들어간 데이터가 나중에 나오는 규칙head에만 삽입, 제거큐(Queue)First In First Out(FIFO)먼저 들어간 데이터가 먼저 나오는 규칙head에 삽입하고 tail에서 제거덱(Deque)데이터의 삽입과 제거를 head와 tail 두 군데서 자유롭게 할 수 있는 자료구조해시 테이블(Hash Table)해시(Hash), 맵(Map), 해시맵(HashMap), 딕셔너리(Dictionary)Key만 알면 Value에 Ο(1)의 성능으로 읽기 가능삽입, 수정, 삭제까지 Ο(1)의 성능셋(set)데이터의 중복을 허용하지 않는 자료구조그림으로 쉽게 배우는 운영체제운영체제가 하는 일프로세스 관리메모리 관리하드웨어 관리파일시스템 관리운영체제의 역사1940년도 애니악1943년부터 미군지휘하에 펜실베니아 대학교에서 개발최초 목적 : 미사일 탄도계산스위치와 배선 연결을 통한 프로그래밍 1950년도 초반 진공관과 전선으로 만들어진 논리 회로를 아주 작은 크기로 만든 직접 회로(IC) 개발현대적인 컴퓨터 모습 갖춤CPU, 메모리 있었지만 키보드와 모니터는 없었음펀치카드 이용, 프로그래머가 카드에 구멍을 뚫어 프로그래밍 1950년도 중후반 "싱글스트림 배치시스템"프로그래머가 여러개의 펀치카드를 오퍼레이터에 전달, 컴퓨터는 순서대로 실행입출력 I/O 디바이스 컨트롤러를 만들어 입출력 중에도 CPU가 계산할 수 있도록 만듦한계 : 입출력에도 CPU를 기다려야 하는 작업이 있음 1960년도 "시분할 시스템"프로그램을 동시에 여러개 사용여러 사용자들이 여러 터미널로 하나의 컴퓨터에 접근하여 사용 -> 파일시스템 등장UNIX AT&T벨 연구소에서 C언어로 유닉스 운영체제 개발멀티 프로그래밍, 다중 사용자, 파일시스템 구현메모리 침범 이슈 발생베이스 레지스터 : 프로그램의 시작 주소 저장, 모든 프로그램은 0번지에서 실행한다고 가정 1970년도 이후 개인용 컴퓨터의 시대 시작애플의 매킨토시, 마이크로소프트의 MS-DOS가 많이 사용 운영체제의 구조운영체제의 핵심은 커널 폰 노이만 구조CPU 스케줄링운영체제는 모든 프로세스에게 CPU를 할당/해제하는데 이를 CPU 스케줄링이라고 한다.CPU 스케줄링에서 스케줄러(운영체제)가 고려해야 할 사항 첫번째, 어떤 프로세스에게 CPU 리소스를 줘야하는가?두번째, CPU를 할당받은 프로세스가 얼마의 시간동안 CPU를 사용해야하는가?스케줄링 목표 리소스 사용률오버헤드 최소화공평성 처리량대기시간응답시간스케줄링 알고리즘 FIFO(First In First Out)SJFRRMLFQ