인프런 워밍업 클럽 스터디 2기 CS | 2주차 발자국

운영체제운영체제 스케줄링 관련 내용으로 FIFO, SJF, RR, MLFQ를 들었고 프로세스 간 통신, 공유자원, 데드락, 메모리에 대한 내용을 수강하였다. 단어들이 생소해서 들어도 기억에 잘 남지 않지만 이것도 반복을 열심히 해야겠다.알고리즘재귀 문제는 자주 접했던것 같은데도 여전히 잘 모르는 것 같아서 당황스러웠다. 하지만 강의 덕에 다시한번 되돌아보게 되었다.버블정렬은 강의를 듣고 우연히 관련 알고리즘 문제를 풀게 되어 기억에 잘 남게 되었다. 이렇게 관련 문제를 하나씩 풀어줘야겠다 :) 회고다른사람들의 발자국을 살펴보니 나처럼(1회차 때는 엄청 길게 썼다... 🙃) 길게 쓰지 않고 딱 적당한 강의 내용과 후기여서 다 지우고 다시 작성하게 되었다.이번주 해야할게 많아서 몰아서 강의를 듣느라 머리에 남아있는게 별로 없는 듯하다. 미션 문제를 풀때 새로워서 강의를 다시 찾아보기 일수였다. 심지어 저번주에 들었던 것도 기억이 별로 남아있지 않아서 충격적이였다... 스터디가 끝나면 다시 차근차근 봐야겠다.다음주가 마지막이니 복습도 하면서 최대한 열심히 들어야겠다!!

인프런 워밍업 클럽 스터디 2기 CS | 2주차 미션

운영체제 FIFO 스케줄링의 장단점이 뭔가요?장점: 구현이 간단하고 이해하기 쉽다.단점: Burst Time에 따라 성능차이가 발생해 평균 대기 시간이 길어질 수 있다. SJF를 사용하기 여러운 이유가 뭔가요?어떤 프로세스가 얼마나 실행될 지 예측하기가 힘들다. Burst Time이 긴 프로세스는 아주 오랫동안 실행되지 않을 수 있다. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요? 타임 슬라이스가 아주 작으면 컨텍스트 스위칭이 자주 발생하게 되어 오버헤드가 커진다. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?타임 슬라이스 내에서 CPU를 반납하는가, CPU를 강제로 뺏기는가로 구분CPU를 반납하면 I/O Bound ProcessCPU를 강제로 뺏기면 CPU Bound Process 공유자원이란무엇인가요?프로세스가 공동으로 이용하는 변수, 메모리, 파일 등을 말한다. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?상호 배제어떤 프로세스가 리소스를 차지했다면 그 리소스는 다른 프로세스에 공유되어서는 안된다.비선점 다른 프로세스에 할당된 리소스는 끝날 때까지 강제로 빼앗을 수 없다.점유와 대기프로세스가 이미 리소스를 보유한 상태에서 다른 리소스를 요청하며 대기한다.원형 대기점유와 대기를 하는 프로세스의 관계가 원형을 이룬다. 자료구조와 알고리즘 재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?무한루프에 빠지게 되어 스택 오버플로우가 일어나거나 잘못된 결과가 나올 수 있다. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n) { if (n

인프런 워밍업 클럽 스터디 2기 CS | 1주차 미션

운영체제위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }인터럽트 방식인터렙트 방식은 작업이 완료되었는지 계속해서 확인하지 않고 비동기적으로 동작하기 때문에 폴링 방식보다 성능이 좋음프로그램과 프로세스가 어떻게 다른가요?프로그램(애플리케이션, 앱)하드디스크 등과 같은 저장장치(HDD, SSD)에 저장된 명령문의 집합체Windows 운영체제에서는 .exe 파일의 모습컴퓨터 관점에서 프로그램은 저장 장치만 사용하는 수동적인 존재프로세스하드디스크에 저장된 프로그램이 메모리에 올라갔을 때 실행 중인 프로그램컴퓨터 관점에서 프로세스는 메모리도 사용하고 운영체제의 CPU스케줄링 알고리즘에 따라서 CPU도 사용,필요에 따라 입력과 출력을 하기 때문에 능동적인 존재멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티프로그래밍메모리에 여러 개의 프로세스가 올라온 것을 말함멀티프로세싱CPU가 여러 개의 프로세스를 처리하는 것을 말함운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?PCB(Process Control Block) 프로세스가 만들어지면 운영체제는 해당 프로세스의 정보를 가지고 있는 PCB를 만들고 저장PCB들은 연결리스트 자료구조로 저장 컨텍스트 스위칭이란 뭔가요? 프로세스 실행 중에 다른 프로세스로 변경하기 위해 실행 중인 프로세스의 상태를 저장하고 다른 프로세스의 상태값으로 교체하는 작업 컨텍스트 스위칭이 발생할 때 PCB에서 프로세스 상태, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보 등이 변경컨텍스트 스위칭이 발생하는 이유는 CPU점유 시간을 초과했거나, I/O요청이 있거나 다른 종류의 인터럽트가 있을 때 발생 자료구조와 알고리즘여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요. 배열을 선택할 것입니다. 학생 정보 조회가 가장 빈번한 작업일 것으로 예상되며, 배열은 인덱스를 통합 빠른 접근으로 시간복잡도가 O(1)이기 때문입니다. 전학을 오거나 가는 경우처럼 데이터가 추가되거나 삭제가 될 수 있겠지만 이는 상대적으로 드문 이벤트입니다. 데이터의 크기가 크게 변경되지 않을 것이라 예상되어 연결리스트보다 배열이 적합할 것같습니다.여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요. FIFO 선입선출 방식의 Queue를 선택할 것입니다. 주문을 먼저한 손님 순으로 서비스가 제공되어야하기 때문입니다.

인프런 워밍업 클럽 스터디 2기 CS | 1주차 발자국

"인프런 워밍업 클럽 스터디 2기 CS" 과정을 듣게 되었다.프로그래밍 언어 공부하기만 바빴지 CS에 대해서는 아는 것이 없었기에, 강의 수집가라 수집만 하고 완강을 한 적이 별로 없었기에, 항상 장바구니에 넣어두고 언젠가 사야지 고민하던 "감자"님 강의기에2일 정도 고민 후 바로 강의 구매 및 스터디 신청을 하게 되었다.그림으로 쉽게 배우는 운영체제섹션1) 운영체제 들어가기운영체제 개요컴퓨터는 운영체제가 없어도 동작할 수 있다. 하지만 다른 기능을 추가할 수 없다.운영체제 없는 컴퓨터 === 통화만 가능했던 옛날 유선 전화기요즘 컴퓨터 === 요즘 스마트폰 운영체제가 하는 일1. 프로세스 관리노래, 게임, 인터넷 서핑 전부 동시 실행 가능현재 실행 중인 것 외에는 백그라운드에서 실행됨만약 운영체제가 관리하지 않으면 CPU가 독차지 되어 동시에 실행 불가2. 메모리 관리모든 프로그램은 메모리에 올라와서 동작 3. 하드웨어 관리운영체제는 사용자의 하드웨어에 대한 직접적인 접근을 막음사용자가 데이터를 저장하려고 할 때 하드디스크의 특정 영역에 바로 저장 못 함운영체제가 판단해서 적절한 위치에 저장 하드디스크 특정 영역에 중요한 데이터가 존재할 수 있기 때문사용자의 악의적인 공격 방어 4. 파일 시스템 관리 운영체제의 역사비싼 CPU의 사용률을 늘릴려고 고민오퍼레이터와 프로그래머 사이에서 낭비되는 시간을 줄이려고 함 => 오늘날의 운영체제 탄생 운영체제의 구조이미지 참조 ) https://ko.wikipedia.org/wiki/%EC%BB%A4%EB%84%90_%28%EC%BB%B4%ED%93%A8%ED%8C%85%29운영체제의 핵심은 커널(kernel)컴퓨터 운영체제의 핵심이 되는 컴퓨터 프로그램, 시스템의 모든 것을 완전히 제어. 프로세스와 메모리, 저장장치를 관리하는 핵심적인 기능을 담당사용자는 운영체제의 커널에 직접 접근X, 인터페이스를 통해서 접근할 수 있음.인터페이스GUI(Graphic User Interface)e.g. windows, Mac OSCLI(Command-Line Interface)e.g. 유닉스, 리눅스시스템 콜(system call)시스템 호출 또는 시스템 콜, 간단히 시스콜은 운영체제의 커널이 제공하는 서비스에 대해 응용 프로그램의 요청에 따라 커널에 접근하기 위한 인터페이스어플리케이션은 시스템 콜을 통해서 커널에 접근 가능드라이버하드웨어와 커널의 인터페이스e.g. 키보드, 마우스 등컴퓨터 하드웨어와 구조오늘날 대부분의 컴퓨터는 프로그램 내장 방식의 폰 노이만 구조CPU와 메모리(RAM)를 두고 이들 사이는 버스로 연결버스: 데이터를 전달하는 통로프로그램은 메모리에 올려서 실행시키는데 프로그램을 메모리에 내장했다고 해서 프로그램 내장방식이라고 함메모리에 올라간 프로그램은 명령에 따라 처리컴퓨터 하드웨어가장 기본이 되는 것은 메인보드메인보드: 다른 하드웨어를 연결하는 장치장치 간에 데이터를 전송하는 건 메인보드의 버스가 담당CPU(Central Processing Unit) 구조중앙처리장치, 컴퓨터 시스템을 통제하고 프로그램의 연산을 실행, 처리하는 가장 핵심적인 컴퓨터의 제어 장치, 혹은 그 기능을 내장한 칩. 컴퓨터에서 기억, 해석, 연산, 제어라는 4대 주요 기능을 관할하는 장치산술논리 연산장치CPU에서 실제로 데이터 연산을 담당하는 것제어장치모든 장치들의 동작을 지시하고 제어하는 장치레지스터CPU 내에서 계산을 위해 임시로 보관하는 장치. 변수라고 생각해라메모리 종류RAM(Random Access Memory)램덤으로 데이터를 읽어도 저장된 위치와 상관없이 읽는 속도가 같음전력이 끊기면 데이터를 잃어버림메인 메모리로 사용ROM(Read Only Memory)전력이 끊겨도 데이터를 계속 보관할 수 있음데이터를 한 번 쓰면 수정 불가능컴퓨터 부팅과 관련된 바이오스를 저장하는 데에 주로 쓰임컴퓨터의 부팅과정컴퓨터 부팅 -> ROM에 저장된 바이오스 실행 -> 바이오스는 전원, CPU, 메모리, 키보드, 마우스, 하드디스크 등 주요 하드웨어에 이상유무 확인 -> 이상 없으면 부트로더 실행, 있으면 부팅 불가 -> 부팅 후 실행되는 모든 응용 프로그램은 메모리에 올라와서 운영체제가 관리인터럽트(Interrupt)프로세스 실행 중 예기치 않은 상황이 발행할 때 발생한 상황을 처리한 후 실행 중인 작업으로 복귀하는 것. CPU가 특정 기능을 수행하는 도중에 급하게 다른 일을 처리하고자 할 때 사용할 수 있는 기능 CPU가 입출력 장치에 데이터를 읽거나 쓰려고 하는 상황CPU는 입출력 작업이 들어오면 입출력 관리자에게 입출력 명령을 내림CPU 관점에선 입출력 명령이 언제 완료될 지 알 수 없음CPU는 주기적으로 계속 확인함 => 폴링(Polling)방식폴링 방식은 주기적으로 CPU가 확인해야 해서 성능이 안좋음폴링 방식의 단점을 해결한게 인터럽트 방식CPU가 입출력 관리자에게 입출력 명령을 내리고CPU는 다른 작업을 함입출력 관리자는 입출력이 완료되었을 때 CPU에게 신호를 주고 CPU는 그 신호를 받아 인터럽트 서비스 루틴(ISR)을 실행시켜 작업을 완료인터럽트 서비스 루틴(ISR): 특정 인터럽트가 들어오면 그 인터럽트를 처리하는 함수인터럽트는 비동기적으로 동작 => 성능에 이점인터럽트 2가지 방식하드웨어 인터럽트위의 입출력 등과 같은 인터럽트소프트웨어 인터럽트사용자 프로그램에서 발생한 인터럽트e.g. 유효하지 않은 메모리에 접근, 0으로 나누는 명령어 등 섹션2) 프로세스와 쓰레드프로그램과 프로세스프로그램(애플리케이션, 앱)하드디스크 등과 같은 저장장치(HDD, SSD)에 저장된 명령문의 집합체Windows 운영체제에서는 .exe 파일의 모습컴퓨터 관점에서 프로그램은 저장 장치만 사용하는 수동적인 존재프로세스하드디스크에 저장된 프로그램이 메모리에 올라갔을 때 실행 중인 프로그램컴퓨터 관점에서 프로세스는 메모리도 사용하고 운영체제의 CPU스케줄링 알고리즘에 따라서 CPU도 사용,필요에 따라 입력과 출력을 하기 때문에 능동적인 존재멀티프로그래밍과 멀티프로세싱유니프로그래밍메모리에 오직 하나의 프로세스가 올라온 것을 말함멀티프로그래밍메모리에 여러 개의 프로세스가 올라온 것을 말함멀티프로세싱CPU가 여러 개의 프로세스를 처리하는 것을 말함PCB(Process Control Block) 프로세스가 만들어지면 운영체제는 해당 프로세스의 정보를 가지고 있는 PCB를 만들고 저장PCB들은 연결리스트 자료구조로 저장 컨텍스트 스위칭프로세스 실행 중에 다른 프로세스로 변경하기 위해 실행 중인 프로세스의 상태를 저장하고 다른 프로세스의 상태값으로 교체하는 작업 컨텍스트 스위칭이 발생할 때 PCB에서 프로세스 상태, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보 등이 변경컨텍스트 스위칭이 발생하는 이유는 CPU점유 시간을 초과했거나, I/O요청이 있거나 다른 종류의 인터럽트가 있을 때 발생프로세스 생성과 종료일반적인 프로세스 생성.exe파일 실행 -> 운영체제 해당 프로그램의 코드 영역과 데이터 영역을 메모리에 로드 -> 빈 스택과 빈 힙을 만들어 공간 확보 -> 이 프로세스를 관리하기 위한 PCB를 만들어 값을 초기화운영체제가 부팅되고 0번 프로세스가 생성될 때 딱 한번만 실행 됨다음의 모든 프로세스는 새로 생성되지않고 0번 프로세스를 fork() 함수로 복사해 생성됨새로 생성하는 것보다 복사가 더 빠르기 때문복사된 프로세스는 자식 프로세스자식 프로세스 입장에서 0번 프로세스는 부모 프로세스fork()함수로 프로세스 복사 후 exec()함수를 실행하면 부모를 복사한 자식 프로세스의 코드와 데이터 영역을 원하는 값으로 덮어쓰게 됨exit()함수는 자식 프로세스가 부모 프로세스에게 정상 종료됨을 알리는 함수부모 프로세스는 자식 프로세스의 exit status를 읽고 자식 프로세스를 정리부모 프로세스가 자식 프로세스보다 먼저 종료되거나, 자식 프로세스가 비정상적으로 종료돼 exit()신호를 주지 못해 exit status를 읽지 못해 메모리에 계속 살아 있는 상태는 "좀비 프로세스"라고 부름쓰레드운영체제가 작업을 처리하는 단위는 프로세스기존 프로세스를 복사해서 사용하니 메모리를 많이 먹어 쓰레드가 등장쓰레드는 프로세스 내에 존재하는 것으로 1개의 프로세스에 여러개의 쓰레드가 존재 가능한 프로세스 내 쓰레드들은 그 프로세스의 PCB, 코드, 데이터, 힙 영역을 공유 => 메모리 절약스택은 공유하지 않고 쓰레드마다 하나씩 가지고 있음쓰레드와 프로세스의 장단점안정성프로세스 > 쓰레드프로세스는 서로 독립적이기 때문에 하나의 프로세스가 문제가 있어도 다른 프로세스 영향을 받지 않음. 안정성쓰레는 하나의 프로세스 내에 있기 때문에 프로세스가 문제가 생기면 안의 모든 쓰레드에 문제가 생김속도, 자원프로세스 프로세스는 서로 고유한 자원을 가지고 있음. 프로세스간의 통신을 하려면 IPC를 이용해야해서 오버헤드가 크고 속도가 느림쓰레드는 스택을 제외한 영역을 모두 공유하고 있기 때문에 오버헤드가 작음CPU스케줄링운영체제는 모든 프로세스에게 CPU를 할당/해제하는데 이를 CPU스케줄링이라고 함CPU스케줄링에서 스케줄러(운영체제)가 고려해야할 사항어떤 프로세스에게 CPU리소스를 줘야하는가?CPU를 할당받은 프로세스가 얼마의 시간동안 CPU를 사용해야하는가?CPU BurstCPU를 할당받아 실행하는 작업I/O Burst 다중큐프로세스 정보를 가지고 있는 PCB는 준비 상태의 다중큐에 들어가서 실행되기를 기다리고 있고 CPU스케줄러에 의해 실행상태로 전환이때 CPU스케줄러는 준비 상태의 다중큐를 참조해서 어떤 프로세스를 실행시킬지 결정I/O 작업 또한 실행 중인 프로세스에서 I/O 작업이 발생하면 해당 I/O 작업의 종류별로 나뉜 큐에 들어가고 CPU스케줄러는 이를 참조해서 스케줄링스케줄링 목표리소스 사용률CPU 사용률을 높이는 것을 목표로 함I/O 디바이스의 사용률을 높이는 것을 목표호 함오버헤드 최소화스케줄링을 하기 위한 계산이 너무 복잡하거나 컨텍스트 스위칭을 너무 자주 X공평성모든 프로세스에게 공평하게 CPU할당처리량같은 시간 내에 더 많은 처리를 할 수 있는 방법을 목표로 함대기 시간대기 시간이 짧은 것을 목표로 함응답 시간응답 시간이 짧은 것을 목표로 함사용자가 사용하는 시스템에 따라 목표를 다르게 설정해야 함터치스크린: 응답 시간이 짧게과학 계산: 처리량이 높게일반 사용자: 밸런스 유지FIFO(First In First Out)단순하고 직관적이나 한 프로세스가 완전히 끝나야 다음 프로세스가 시작된다는 단점이 있음I/O작업이 있다면 CPU는 끝날 때까지 쉬고 있기 때문에 CPU 사용률이 떨어짐스케줄링의 성능은 "평균 대기시간"으로 평가FIFO알고리즘은 프로세스의 Burst Time에 따라 성능 차이가 심하게 나기 때문에 현대 운영체제에서는 잘 쓰이지 않고 일괄처리 시스템에 쓰임그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편) 섹션1) 개요자료구조와 알고리즘이란?자료구조데이터가 어떤 구조로 저장되고 어떻게 사용되는지를 나타냄변수, 배열알고리즘어떤 문제를 해결하기 위한 확실한 방법데이터가 어떤 자료구조를 하고 있는 지에 따라서 값을 구하는 방식이 달라짐 => 자료구조에 따라 알고리즘이 달라짐시간복잡도특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간코드에서 성능에 많은 영향을 주는 부분을 찾아 실행시간을 예측 => 반복문최악의 경우를 평가하는 Big-O를 많이 사용성능을 정확하게 표현하진 못함 => 단순히 해당 알고리즘의 입력이 늘어날 때 계산량이 얼마나 늘어나는지 표현하는 방법일 뿐 O(n): 선형시간 알고리즘, 데이터가 많아지면 그와 비례해서 계산량이 많아짐O(1): 상수시간 알고리즘, 입력의 크기에 상관없이 상수의 시간이 소요O(logn), O(nlogn), O(n^2), O(2^n), O(n!) 등배열자바스크립트에서 배열은 불연속적으로 할당, 내부적으로 연결해서 사용자에게 배열인 것처럼 보이게 함연결리스트(Linked List)빈 메모리 공간 아무곳에 데이터를 생성하고 연결만 해주면 되기 때문에 배열 초기 크기를 몰라도 됨삽입, 삭제가 쉽다는 장점데이터들이 전부 떨어져있기 때문에 바로 접근할 수 없다는 단점데이터참조 O(n)의 성능스택(Stack)Fist In Last Out(FILO)먼저 들어간 데이터가 나중에 나오는 규칙head에만 삽입, 제거하는 자료구조큐(Queue)First In First Out(FIFO)먼저 들어간 데이터가 먼저 나오는 규칙운영체제에서 쓰는 FIFO 스케줄링: 먼저 들어온 프로세스 순으로 CPU가 처리head에서 삽입하고 tail에서 제거하는 자료구조덱(Deque)데이터의 삽입과 제거를 head와 tail 두 곳에서 자유롭게 할 수 있는 자료구조스택, 큐 전부 구현 가능해시테이블(Hash Table)해시와 테이블이 합쳐진 자료구조프로그래밍 언어에 따라서 조금씩 다른 이름을 가지고 있음해시, 맵, 해시맵, 딕셔너리장점Key만 알면 Value에 O(1)의 성능으로 읽기 가능삽입, 수정, 삭제 다 O(1)단점메모리를 많이 차지함좋은 해시 함수 구현이 필수해시충돌충돌을 해결하기 위해서 해당 인덱스를 연결리스트로 구성해 데이터들을 연결 => O(n)셋(Set)데이터의 중복을 허용하지 않는 자료구조해시 테이블을 사용한다고 해서 해시 셋(Hash Set)이라고도 불림회고운영체제를 처음 공부해서 그런지 낯선 단어들이 굉장히 많았다. 그래서인지 생각했던 시간보다 많이 소요되었다.알고리즘 개념은 어느정도 알고 있었지만 구현을 하려니 어려웠고 이것 또한 생각했던 것보다 시간이 많이 소요되었다...반복하다보면 익숙해지겠지 🙂 그리고 강의 들으면서 길게 작성하는 방법보단 강의의 핵심만 작성하도록 해야겠다.