인프런 워밍업 클럽2 cs <day14> 끝!

드디어 마지막 복습 ㅜㅜ 하라고 할 때 안해서 이번주 수요일까지 숙제가 생겨버렸다..할 때 하자... 시간 더들이지말고알고리즘동적프로그래밍 - 메모이제이션앞서 재귀식을 배웠다. 재귀식은 콜스택에 함수를 계속해서 쌓고쌓고 하는 방식이였다.=> 자리차지하고 비효율적이다. 피보나치 수열을 이용해서 재귀식에서 상향식으로 효율적이고 빠르게 연산하는 방식을 알아보려고한다.피보나치 수열 : 첫번째 수와 두번째 수를 더해 세번째 수를 만들고 두번째 수와 세번째 수를 더해 네번째 수를 만든다. 이렇게 무한하게 배열을 이룰 수 있는 수열이다.피보나치 수열을 재귀식으로 만들어보자function fibo1(n){ if(n==0||n==1) return n; return fibo1(n-2) + fibo1(n-1); }그림으로 쉽게 배우는 알고리즘 - 감자하지만 수가 커지면 커질수로 중복되는 계산도 많아진다. 아래와 같이 초록색은 계산중인 부분, 노란색은 중복이 되는 부분이다.=> 효율성이 떨어진다. 이런 효율성을 보완하기 위해 메모이제이션을 사용하게 된다.메모이제이션 : 계산을 저장해서 같은 방식의 계산을 방지한다. 계산했을 때 저장되어있지않으면 그 결과를 저장한다. -> 해시테이블 이용해서 key는 계산하고자 하는 데이터, value는 결과를 저장한다. - 재귀식으로 인해서 중복 계산이 많은 것을 결과를 저장하는 방식으로 단점을 해소했다. 역시 메모이제이션도 재귀식이다.function fibo2(n, memo){ k if(n==0||n==1) return n; if(memo[n] == null) { memo[n] = fibo2(n - 2, memo) + fibo2(n - 1, memo);// value 결과를 저장 //이런 식으로 값을 만들어서 결과값을 나타내기 때문에 그냥 함수에 변수 넣은 게아니다. } return memo[n]; }재귀식 vs 메모이제이션재귀식 : 재귀만을 사용해서 중복되는 것들이 있다.메모이제이션 : 검색하고 없으면 저장하여 결과값 동적프로그래밍 - 타뷸레이션타뷸레이션 : 메모이제이션도 재귀식보다는 효율적이지만, 하나의 함수만 호출하는 것보다는 비효율적이였다. 타뷸레이션은 상향식을 이용해서 하나의 함수만 호출해서 값을 얻을 수있다. 이 때 객체를 만들어서 해시테이블처럼 이용해서 계산에 필요한 모든 값들을 저장해놓고 꺼내 쓸 수있도록한다.상향식방식의 피보나치 수열 구하긔function fibo3(n){ if(n재귀식(O(n^2)) 메모이제이션은 메모리를 사용해 성능을 향상시킬 수있다.동적 프로그래밍이 필요한 분할 정복 문제를 풀 때 상황에 따라 다르겠지만 다루기 어려운 메모리는 재귀식으로 쉽게 해결할 때가 있다.메모이제이션을 사용해야할 때는 - 재귀식으로 직관적으로 해결할 수 있는 메모리를 하향식으로 해결하고 더많은 메모리를 이용해서 성능을 향상시킨다.타뷸레이션을 사용하기 적할 할 때는 - 재귀가 직관적이지 않을 경우 상향식인 타뷸레이션으로 접근한다.아니 알고리즘 방금했는데 메모이제이션이랑 타뷸레이션 특성을 헷갈려함 빡대가리니 그렇게 달달 외울라고 하니까 이게 이거였나? 하고 헷갈리지 진짜 어이가 없네. 메모이제이션어캐쓰게됐는지 그래서 기존보다 어떤게 나아졌고 뭐는 나빠졌으며 하면서 이어져야되는데 특성! 외우고 아 이게 메모이제이션이엿나,, 이 특성이 타뷸레이션이였나? 이러니까 머리에 안들어오지운영체제파일과 파일 시스템파일을 사용자가 저장하려고 할 때 운영체제를 거쳐서 하드디스크에 저장된다. 파일 시스템 (=운영체제) : 운영체제가 파일을 관리하기위해 만듦 파일엔 파일테이블이 있는데 페이지테이블은 비슷하다.파일 시스템의 기능 파일과 디렉토리 생성/수정/삭제, 파일권한관리 - 다중 사용자 기능을 지원하는 요즘 다른 사용자로부터 파일 보호를 위해서이다. 무결성 보장 - 파일의 내용이 손상되지 않도록한다. 백업과 복구 암호화주변 장치( 캐릭터와 블록으로 전송단위를 나눌 수있다)파일 시스템은 하드디스크나 flash memory(보조기억장치)에 저장되기 때문에 전송단위는 블록이다.사용자는 바이트 단위로 접근, 파일관리자가 중간에서 변환해준다.뒤에 확장자를 붙여 (.exe, .txt)확장자에 알맞는 프로그램을 실행시켜 파일을 본다. (사진-포토샵, 텍스트 파일 - 메모장 ..)파일은 헤더와 데이터로 이뤄져있다. 파일의 헤더는 파일의 속성들이 저장되어있다.파일제어 블록(File Control Block) : 파일 관리를 위해 정보를 저장 해놓은 블록이다. 파일 디스크립터라고도 부르고 파일마다 존재한다. 저장장치에 저장되어있다가 파일이 오픈 시 메모리로 이동된다. 파일 시스템이 파일 디스크립터를 관리한다.사용자는 파일을 파일 시스템이 메모리에 건내준 파일 디스크립터를 이용해서 파일을 볼 수있다.4번째 줄 코드에서 open()했을 때 파일디스크립터,fd를 메모리에 이동시켰다. 5번째 줄 close()fd를 참조해 파일을 안전하게 닫았다. 파일은 데이터의 집합이다.데이터 집합이 어떻게 이뤄지는지에 따라 종류를 나눌 수있다.순차파일 구조 : 파일의 내용이 연속적으로 이어진 상태 (카세트 테이프) 파일디스크립터를 사용해서 처음부터 순차적으로 데이터를 확인할 수있다. lseek()함수를 이용해 보고자 하는 데이터의 위치로 파일 디스크립터 위치를 옮긴다. - 장점 : 순차적 기록, 단순 구조. 단편화 현상없음 - 단점 : 특정지점으로 이동 어려움. 데이터 삽입,삭제,탐색에 시간이 많이 걸린다. lseek(fd, 10,SEEK_CUR);// 현재 위치에서 10번 앞으로 파일디스크립터를 이동시킨다.직접파일 구조 : 저장하려는 데이터를 해시함수로 저장위치를 정한다. - hashTable 자료구조를 이용하고 요즘 사용이 많은 .JSON에서 사용한다. - 해시함수처럼 한번에 데이터를 찾을 수있지만 공간낭비가 있을 수있다.인덱스파일구조 : 순차접근 +직접파일접근 장점 데리고왔다~ - 순서대로 접근도 할 수 있고 직접 파일에 접근도 할 수있다.인덱스 테이블을 만들어서 노래를 클릭했을 때 순차적인 데이터를 참조해서 바로 노래를 들을 수있고순차데이터를 이용해서 노래재생을 해 순차적으로 노래를 들을 수 있다.디렉토리파일의 파일. 파일들을 모아둔 파일들관련있는 파일들을 모아둔다.루트디렉토리와 자식디렉토리가 존재한다.유닉스와 리눅스는 루트디렉토리를 /로, 경로도 / 로 표시한다. 원도우는 루트디렉토리를 c:으로 디렉토리와 디렉토리 경계구분은 \ 로 구분한다.디렉토리는 파일과 같은 구조이다. 파일은 데이터가, 디렉토리는 파일 정보가 저장되어있다.디렉토리도 헤드가 있다! 루트 디렉토리 헤더 : 디렉토리 정보가 시작하는 위치를 가리키고 000디렉토리 헤더 는 해당 프로그램의 정보가 시작하는 위치를 가리킨다.루트디렉토리는 상위 디렉토리가 없어서 ..은 본인을 나타낸다.디렉토리 구조 초기 파일 시스템의 디렉토리는 루트디렉토리에만 디렉토리가 존재해서 단순했다.-> 파일들이 많아지면서 다단계 디렉토리가 생겼다. 일반 디렉토리에서 하위 디렉토리를 만들수 있는 트리구조가 되었다.바로가기 기능때문에 운영체제는 트리구조에서 순환이 생긴다. 파일과 디스크파일시스템은 메모리와 비슷하게 일정한 크기로 나누고 나눈 공간을 블록이라 부른다. 메모리에선 페이지!한블록을 1~8KB 로 쪼갠다. 파일 제어 테이블 : 파일이 시작하는 블록의 위치 정보도 담고 있다.하나의 파일은 여러 개의 블록으로 이뤄져있고 어떻게 블록을 잇느냐에 따라연속할당과 불연속할당으로 나눌 수 있다.연속할당 : 블록들을 디스크에 연속적으로 저장한다. 파일 시작블록만 알면 모든 데이터를 접근할 수 있다.불연속할당 : 비어있는 디스크 공간에 데이터를 분산시켜서 저장하는 방식이다. 분산된 블록은 파일 시스템이 관리불연속할당의 연결할당 : 자료구조의 연결리스트방식 NULL을 만날 때까지 데이터를 참조해 모든 데이터를 얻을 수 있다.불연속할당의 인덱스 할당테이블의 블록포인터가 데이터 블록에 직접연결이 아닌 데이터들의 인덱스를 가지고 있는 인덱스 블록을 연결한다. 이 인덱스블록은 파일 테이블의 블록포인터가 가리키게된다.찾는 것이 블록이아니고 나는 데이터 0,3,4번이 필요해 했을 때 어떤 인덱스를 참조해야되지?하고 찾는것같다.파일 c를 찾을래 위치는1 이구나 그럼 1번 블록으로 ..가 아니고인덱스 블록에 있는 0,3,4번블록을 참조하면 데이터를 모두 찾을 수있다.인덱스 할당은 데이터가 많아 테이블이 꽉 찬 경우 인덱스 블록을 더 만들어 연결해 테이블 확장에 용이하다. 이해가 안가는데 왜 데이터블록이랑 인덱스블록이랑 똑같이 해놨음? 그럼 파일 B는 어캐 인덱스블록에 연결하나?디스크의 크기디스크의 블록 수를 잘게 자를 수록 공간을 낭비없이 사용가능하지만 각자 신경쓸 블록이 많아진다. 또 디스크를 크게 자를 경우 내부단편화가 생겨 낭비가 생긴다.->그럼 디스크의 빈공간을 찾아야되나? 그럼 처음부터 끝까지 메모리를 뒤져 빈 공간을 확인해야하므로 비효율적이다. free Block list로 이문제를 해결했다.Free Block List : 디스크의 빈공간을 모아둔 리스트. - 그럼 데이터 삭제하면 free block list로 가겠군녀=> 특정파일 삭제시 실제 모든 데이터를 지우는 게아니고 파일 테이블의 헤더를 삭제하고 블럭을 free block list에 추가한다.사용했던 블럭의 데이터는 여전히 남아 포렌식을 이용해 복구하면 데이터 사용이 가능하다.ex) a파일을 지웠는데 파일에 해당하는 4, 11, 14 블록은 리스트에 올라간다. = a파일에 해당하는 블록은 4,11,14블록으로 흩어져있다.복습할 때 시간이 정말 많이 걸린다. 하루 수업을 두시간동안 복습한거같다. 왤캐 오래걸리지...흑흑

인프런 워밍업 클럽2 cs <day13>

알고리즘퀵정렬퀵정렬은 병합정렬과 같이 분할 정복 알고리즘으로~재귀를 사용한다.피벗 : 첫 피벗은 첫번째 인덱스left, right : 각자 왼쪽 오른쪽 끝에 있는 것rightStartIndex : 왼쪽으로 이동, 피벗보다 작은 값을 만나면 멈춘다.leftStartIndex : 오른쪽으로 이동, 피벗보다 큰 값을 만나면 멈춘다.rightStartIndex와 leftStartIndex가 조건에 의해 멈췄을 때 두값을 스왑하여 바꾼다.rightStartIndex와 leftStartIndex가 지나칠 때 멈춘다. rightStartIdnex값과 피벗 위치를 바꿔 피벗은 5, rightSI는 4가된다.-> 피벗을 기준으로 왼쪽은 피벗보다 작은 값, 오른쪽은 피벗보다 큰 값으로 나뉘게되고나눠진 그 배열을 또 위에서 정렬한 것처럼 반복피벗을 기준으로 배열을 반으로 나눈다 -> O(log n) 이작업을 데이터 n개만큼 반복해야하므로 n을 곱한다. -> O(nlog n)최악의 경우 : 피벗이 가운데가 아니고 한쪽으로쏠림 -> O(n^2)근데 평균성능보는거라 Θ(nlogn) Θ는 세타병합이랑 퀵이랑 비교했을 때 병합이 더 좋아보이지만 퀵은 적은비교 적은 메모리사용으로 퀵이짱인것이다~ 운영체제주변장치내부구조를 보자면...레지스터들 : 입출력 작업 시에 데이터를 저장하는 역할 이 값들은 메모리에 이동되기도 한다.세가지 버스를 따로 받을 수있다. Address, Data, Control캐릭터 디바이스와 블록 디바이스 데이터 전송단위가 캐릭터(글자)이거나 블록 단위캐릭터 디바이스 특 : 데이터 전송단위가 캐릭터로 상대적으로 작다. 마우스,키보드블록 디바이스 특 : 데이터 전송단위가 블록단위로 캐릭터보다는 크다. 하드디스크 ,ssd 주변 장치들은 메인보드 내의 버스로 연결된다. 하나의 버스였지만 I/O작업을 수행하기위해서 입출력 제어기와 여러 개의 버스가 추가됐다.(CPU가 I/O 작업때문에 다른작업을 못했기때문)CPU는 I/O작업을 만나면 입출력 제어기에게 입출력 작업을 맡기고 다른 작업을 실행하러간다.입출력제어기 - 시스템버스와 입출력 버스로 구분 시스템버스는 CPU, 메모리가 사용하고 입출력 버스는 주변장치들이 사용입출력버스 - 고속입출력, 저속입출력->속도차이로인한 병목현상을 해결그래픽카드는 주변 장치이지만 대용량의 작업을 실행하기때문에 시스템 버스를 사용한다.입출력 제어기는 여러 주변장치를 처리하는데 입출력 버스에서 온 데이터를 메모리로 옮겨야한다. -> 입출력 제어기가 메모리 접근을 위해 CPU를 거쳐야되는데 CPU 도움없이 DMA제어기를 추가시켰다.Direact Memory Access : cpu없이 입출력 제어기가 메모리에 접근할 수있도록 한다.Memory Mapped I/O : cpu와 DMA 제어기가 사용하는 메모리 영역을 나눠 혼돈을 막는다.마우스광학마우스 , 키보드아래 카메라를 통해 초당 1500회를 찍어 디바이스 컨트롤러 안 DSP로 보낸다.x,y 축 좌표 움직임을 캐치한다.DSP가 움직임과 클릭을 감지했을 때 cpu에게 인터럽트를 발생시켜 마우스 드라이버가 동작해 데이터를 읽어간다.마우스 드라이버는 운영체제에게 이벤트 신호를 주고 운영체제는 이 이벤트를 foreground 애플리케이션으로 전달해준다.해당 애플리케이션은 받은마우스 이벤트를 처리한다. 하드디스크하드시스크 구조플레터 : 플레터는 여러개의 트랙으로 구성되었고 표면을 자성을 띈다. n극일경우 0, s일경우 1스핀들 : 플레터 자기화된 원판으로 이뤄졌다. 디스크암이 읽기/쓰기 헤드로 플레터의 표현을 read헤드 : 헤드는 여러 개 있고 항상 같이 움직인다. 이 헤드들은 여러 개의 플래터를 가리키게 된다.실린더 : 여러개의 같은 집합의 플래터에 있는 트랙의 집합을 실린더라고한다.트랙 : 여러 개의 섹터로 나뉜다.섹터 : 하드디스크의 가장 작은 단위유저프로세스가 하드 디스크의 특정 섹터에 접근하고 싶어서 이러한 요청을 보낸다.실린더 c로 가서 트랙 b에 있는 섹터 d를 읽어라seek : 디스크암은 헤드를 실린더 c로 이동seek time : 헤드를 실린더로 이동시키는데 시용하는 시간 트랙b의 섹터가 d 가 헤드에 닿을 때가지 스핀들ㅇ르 회전시키고 헤드에 섹터d가 읽히면 작업이 끝난다.다른 전자 기기 작업시간은 ns 단위지만 헤드 이동시간은 ms라 하드디스크가 느리다. 플레시 메모리(ssd)와 하드디스크자성을 띄는 하드디스크는 자석을 가져다대면 망가지지만 플레시 메모리는 그러지 않고 전기적으로 데이터를 읽어 조용하다.스핀들과 같은 회전축때문에 충격에 약한 하드디스크ssd 단점 : 특정 지점에 데이터를 썼다면 덮어쓰기가 불가능하다. 똑같은 지점에 데이터를 쓰고 싶으면 지워야하지만 메모리 지우기 기능 횟수가 정해져있다. ->똑같은 구간에 지우기 쓰기를 여러 번할 경우 망가질 수있다.

인프런 워밍업 클럽 스터디 2기 - CS 전공지식<10월 셋째주 발자국> +미션

⭐ 발자국운영체제가상메모리가상메모리와 가상메모리를 효율적으로 사용하는 방법!- 세그멘테이션 & 페이징 => 요즘엔 페이징과 페이지드 세그멘테이션 자주사용페이지 교체정책 : FIFO, LRU, 옵티멈, 클락 알고리즘, FIFO의 2차 기회 교체 알고리즘스레싱과 워킹셋 모두 pagefault를 줄여서 cpu 사용률이 떨어지는 것을 막음! 입출력 장치주변장치들 메인 보드 내의 버스로 연결(시스템버스, 입출력제어기,DMA ..)하드디스크(헤드, 플레터, 실린더,트렉,섹터..) 읽어오는 방법파일시스템 -> 위에서 공부한 메모리와 비슷하다 - 순차 파일 구조, 집적파일구조- 파일의 파일 디렉토리 알고리즘정렬 : 버블정렬, 선택정렬, 삽입정렬 모두 간단하지만 성능이 뛰어나진 않음병합정렬, 퀵정렬 모두 앞서 말한 정렬보다 성능이 뛰어나다.동적 프로그래밍 : 메모이제이션(재귀), 티뷸레이션(상향식 계산방식) ⭐ 미션운영체제1. 메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.cpu안에 있는 레지스터, 캐시메모리가 있다. 그리고 메인 메모리인 RAM 과 보조저장 장치가 존재한다.빠르고, 용량작고, 가격비쌈 ---> 느리지만,용량크고, 가격합리적!레지스터, 캐시메모리, RAM, 보조저장장치레지스터 : cpu와 가장 가까운 메모리이다. 휘발성 메모리를 가지고 있어 직접적으로 프로그램을 작업하기 어렵다.cpu가 연산처리를 할 때 RAM에 있는 정보를 가져와 레지스터에서 연산하고 결과를 RAM에 저장해둔다.캐시 메모리 : 너무 빠른 레지스터와 그에 비해 너무 느린 RAM을 이어주는 메모리.RAM이 직접 레지스터에 데이터를 올리기엔 너무 느리기 때문에레지스터가 필요할 것 같은 RAM에 있는 데이터를 캐시메모리에 올려놓는다.캐시 메모리는 여러개 있을 수 있다~!메인메모리 : 실제로 프로세스들이 올라가서 작업하는 메모리 공간이다.휘발성 메모리라 데이터를 저장하는 공간이기 보다는 운영체제, 프로세스들을 올리는 공간이다.보조저장장치 : 다른 메모리들과 다르게 휘발성이 아니면서 용량은 크고 가격은 합리적인 메모리. 2. 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?경계 레지스터이다. 메모리관리자가 프로세스가 경계 레지스터 값을 벗어났는지 검사한다. 벗어났을 경우 헤당 프로세스를 종료시킨다.3. 메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?가변분할 방식에서는 프로세스 크기에 맞게 메모리를 순서대로 할당 시킬 수있다. 연속적으로 메모리를 할당시켜서 내부단편화가 없다. 하지만 외부단편화가 생긴다.외부단편화란, 외부단편화는 메모리크기 100에 프로세스 a,b,c가 20,30,40씩 메모리를 할당하고 있었다. 프로세스b가 먼저 작업이 끝나 메모리를 떠났고 40크기의 새로운 프로세스d가 작업을 해야한다. 메모리에는 사용가능한 공간이 총 40이지만 연속적으로 비어 있지 않기 때문에 40짜리 프로세스는 들어갈 수 없게 된다.프로세스들을 끌어와서 빈공간이 연속적이게 만들 수있지만 오버헤드가 커지기 때문에 추천하지 않는다.고정 분할 방식에서는 정해진 크기로 메모리를 분할하고 프로세스는 크기에 맞게 할당된다. 외부단편화는 생기지 않지만 내부 단편화가 생긴다.내부단편화란, 정해진 크기로 프로세스가 할당되고 정해진 크기로 분할한 메모리에 빈공간이 남는 현상이다. 버디 시스템을 이용해서 메모리를 얼만큼 분할할지 어떤 크기에 어떤프로세스를 할당할지 선택할 수있어서 내부단편화를 줄일 수있다.4. CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?스레싱이라고 한다. 물리적인 메모리의 크기가 작은 것이 원인이다. 메모리의 크기를 늘ㄹ려 스레싱을 없애 성능을 향상시킬 수 있다. 하지만 메모리가 클수록 좋은 것은 아니다. 만약 4GB에서 스레싱이 일어나지 않았다면 4GB일 때 스레싱이 일어나기엔 충분한 메모리의 크기이다. 굳이 큰 메모리로 바꿀 필요가 없다는 것이다. 16GB로 바꾼다고 4GB보다 성능향상이 일어나는 게 아니고 똑같다!5. HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요?이유를 함께 적어주세요. 6. 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?파일 전체를 다 지우는 것이 아니다. 파일 테이블의 헤더를 삭제하고 프리블록 리스트에 추가하게된다. 그렇게 되기때문에 삭제하고자 하는 데이터는 그대로 남아있기 때문에 파일을 리스트에서 불러와서 복구가 가능하다.자료구조와 알고리즘1. 지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.버블 정렬, 선택정렬, 삽입정렬 모두 O(n제곱) -> 구현이 쉽지만 효율이 떨어진다.병합 정렬 O(n*logn) -> 재귀식을 사용해서 구현이 어렵지 효율up퀵정렬 (세타 n logn)-> 다른 정렬알고리즘에 비해 가장 불균형이 없을 경우 빠르다. 정렬된 리스트에서는 불균형때문에 오히려 수행시간이 더 걸릴 수가 있다. 다른 정렬에 비해 메모리사용도 적고 데이터간의 비교도 적기 때문에 효율성이 좋다.2. 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다.여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.메모이제이션을 사용해서 구현할 것 같다.이전에 계산한 값을 메모리에 저장하기 때문에 중복적인 계산을 한 데이터를 지우며 전체적으로 실행 속도를 빠르게 해주기 때문에 메모리가 부족한 시스템에서 해결할 때 필요할 것같다.회고윽.. 너무 늦게 내버렸다. 이번주 목표가 하루하루 계획한 날짜에 수업들으면서 복습하는 거였다.. 이번주는 나자신에게 졌다.. 이긴쪽도 나니까 내가 이긴 거일지도. ^^~여유롭게 복습하고 내고싶었는데 쫓기듯 수업을 듣게되어서 제대로 복습한 느낌도 별로 들지 않았다..... 이거 회고내고 내일 복습 다시하려고한다. 그래도 이해가안되면 다시 동영상듣고 복습하다보니까 자연스럽게 스토리(?)가 떠올라서 이 방식으로 공부하는 거. 나쁘지 않을지도

인프런 워밍업 클럽2 cs <day11>

운영체제가상메모리 | 세그먼트, 페이징RAM | 가변분할, 고정분할(세그먼트,페이징이랑 가변분할이랑 고정분할이랑 갑자기 뭔차이지? 라는 생각이 들어서 이전 수업 듣고 까먹지 않게 적어놨다)(가상메모리 ram 차이가아니고 그냥 가변분할은 어떤 종류다~ 말하는거같기도하고)가상메모리 개요컴퓨터마다 메모리의 크기가 달라, 작업할 프로세스크기 > 메모리 일 경우 -> 실행불가문제 해결 방법 : 가상메모리를 사용. 메모리 관리자가 프로세스크기와 할당할 번지를 신경쓰지 않도록 0x0 번지부터 할당한다고여기게 한다.메모리 관리자 덕분에 프로세스와 메모리는 직접적으로 부딪힐 일이 없다.? 가상메모리 안에 메모리 관리자가 들어있나여? 사진이 안에 들어가있네 가상메모리 관리자라고 해야되나가상메모리 크기는 이론적으로는 무한, cpu 비트 수 + 메모리 크기에 정해진다.프로세스 처리 양 > 메모리 크기 일때처리하지 못한 프로세스를 하드디스크에 있는 스왕엽역으로 이동처리가 필요할 때 물리 메모리로 가져와서 실행 시킨다.- 32bit = 4GB => 메모리 크기도 4GB- 메모리 크기가 4GB 일 때, 프로세스 4GB *5 개 작업해야한다. => 디스크의 스왑영역으로 이동동적 주소변환 (DAT) : 메모리 관리자는 물리메모리와 스왑여역까지 합쳐 프로세스가 사용하는 가상주소를 물리주소로 변환실제 0x0 번지 물리주소에는 운영체제 영역 -> 프로세스들은 사용 x가상메모리 시스템에서는 나머지영역을 가변분할 방식, 고정분할 방식으로 나뉜다.-가변분할 (세그먼테이션) / 고정분할방식 (페이징) / 페이지드 세그먼트 (혼용)메모리 관리자는 가상주소 - 물리주소 => 1대1 매핑 테이블로 관리세그멘테이션 (배치 정책)세그멘테이션 -> 프로세스를 함수, 모듈 등으로 세그먼트를 구성한다.사용자 입장 : 세그먼트들(함수 + 모듈 ..)은 서로 인접하지 않는다.프로세스 입장 : 영역들이 서로 인접해 있다.논리주소논리주소는 사용자, 프로세스 CPU 사용논리주소 -> 물리주소 변환은 메모리관리자가 담당메모리 관리자는 세그멘테이션 테이블을 가지고 물리 메모리 주소를 계산한다.논리주소 -> 물리주소 변환 과정cpu에서 논리주소 전달 -> 메모리 관리자가 몇번 세그먼트인지 알아낸다-> 메모리 관리자 내에 있는 Segment Table Base Register 를 이용해서 물리 메모리 내에 있는 세그멘테이션을 찾는다.(여기서 STBR 와 세그멘테이션 테이블은 다르다. STBR에서 세그멘테이션을 찾고 찾은 걸로 세그먼트번호 참조)-> 세그먼트 번호를 인덱스로 Base Address, BoundAddress를 찾는다.(운영체제는 컨텍스트 스위칭이 일어날 때마다 STBR의 내용을 해당 프로세스의 값으로 바꿔줘야한다.)-> Bound Address는 메모리의 크기를 나타낸다.메모리 관리자는 cpu에서 받은 논리주소와 Bound Address의 크기를 비교한다.-> 논리주소 , 논리주소 + Base Address = 물리주소 구하기.논리주소 > Bound Address 일 경우, 메모리를 침범했다고 생각하고 에러를 내보낸다.세그먼트 3번이 0x750번지로 접근cpu의 요청을 받은 메모리 관리자, STBR 을 이용해서 물리 메모리 내에 있는 세그멘테이션을 찾는다.-> 세그먼트 번호를 인덱스로 세그멘테이션 테이블을 참조한다. 3번 세그먼트, BA 500-> 논리주소 > Bound Address 이므로 에러를 발생시킨다. 세그멘테이션 장점 :메모리를 가변적으로 분할할 수 있다.코드영역,데이터영역,힙,스택 모두 모듈로 처리가능 => 각 영역의 공유와 접근보호가 쉽다.세그멘테이션 단점 :외부단편화 발생페이징(배치정책)고정분할 방식 사용메모리 할당 시 정해진 크기로 페이지를 나눈다. =>관리하기 쉬움, 외부단편화 발생하지 않음논리주소공간에서는 페이지, 물리주소 공간에서는 프레임이라고 부른다.페이징 주소변환페이지 넘버 (인덱스 ) = 논리주소 / 페이지크기오프셋 = 논리주소 % 페이지크기메모리관리자는 페이지테이블을 가진다.CPU 32bit , 논리주소공간 4GB 물리주소 공간 2GB (논리 > 물리 크기를 설정함으로써 스왑영역을 사용하는 걸로 가정)논리주소공간을 16MB 256페이지로 나눈다.물리주소 공간(2GB) -> 16MB * 128 로 나눈다CPU가 논리주소를 메모리 관리자에게 넘긴다.-> 메모리관리자 안에 있는 PageTableBaseRegister를 이용해서 페이지 물리 메모리에 있는 페이지 테이블을 찾는다.-> 페이지 번호는 인덱스로, 프레임 번호를 알아낸다.-> 오프셋을 이용해 물리주소로 변환한다.ex 1번 인덱스의 프레임 번호는 1번. 프레임번호 + 오프셋 = 물리주소 => 1477217(페이지 테이블에 프레임 = Invalid 일경우 스왑영역에 저장된 부분임)(PTBR은 운영체제가 컨텍스트 스위칭할 때 마다 해당 프로세스의 것으로 업데이트해준다)세그멘테이션 vs 페이징세그멘테이션 : 프소세스마다 크기가 달라서 bound Address가 필요하다.페이징 : 모든 페이지가 크기가 동일해서 Bound Address가 필요하지 않다.페이징의 내부단편화세그멘테이션 : 논리적인 영역별로 세그먼트를 나눈다.페이징 : 논리적인 영역별로 나누기보다 정해진 크기로 나눈다. 특정 영역만 공유하거나 권한 부여가 어렵다.페이지 테이블의 크기를 얼만큼씩 나눌지가 제일 중요하다,프로세스 많아질수록, 페이지테이블 늘어난다. => 프로세스가 실제로 사용할 수있는 메모리영역🔽페이지 테이블도 물리 메모리의 운영체제 영역에 저장되어 있다.-> 페이지 테이블이 크면 사용자 영역이 부족해진다STBR로 세그멘테이션을 찾는다고 했는데 그럼 세그멘테이션이 겁나 많아서 세그멘티에션 테이블도 많다는 건가? 위와 같은 맥락인 것 같다.페이지드 세그멘테이션(배치정책)세그멘테이션 + 페이징 장점 취합세그먼트로 나눠 관리해서 다른 프로세스와 공유, 권한 부여가 쉽다.오버헤드가 적고 페이지 크기를 정해 나눠서 할당 시킨다.메모리 접근 권한 : 메모리 특정번지에 부여된 권한읽기(READ), 쓰기(Write), 실행(EXECUTE)프로세스는 영역마다 접근권한이 있다.CODE영역 : 프로그램 그자체. 수정되면 안됨. 읽기 실행권한DATA 영역 : 일반변수, 전역변수, 상수로 선언한 변수가 저장. 읽기권한 쓰기권한은 없거나 있다.HEAP,STACK영역 : 읽기 쓰기 권한메모리 접근 권한 검사 : 논리주소에서 물리주소로 변환할 때마다 실시된다.권한비트를 추가해서 검사를 한다.권한이 없는 메모리가 접근 시 에러를 발생시킨다.페이지드 세그멘테이션 : 세그멘테이션 테이블 + 페이지 테이블 사용권한비트 , Bass Addres(페이지넘버), Bound Address(페이지개수) 로 변환 시킨다.cpu에서 논리주소를 메모리 관리자에게 넘긴다.-> 세그먼트를 찾는 방식으로 세그먼트를 찾는다.-> 권한비트로 세그먼트 권한을 위반하는지 검사한다.(권한 위반 시 프로세스 종료)-> 페이지 넘버 = 인덱스. 페이지 넘버에서 인덱스를 참조해서 프레임을 알아낸다.페이지드 세그먼트 단점 : 세그멘테이션테이블과 페이지 테이블을 참조할 때 총 메모리 접근이 두 번이다.=> 현재 운영체제는 페이지드 세그먼트와 페이징 기능을 적절히 섞어 작업한다. 알고리즘삽입 정렬정렬된 영역 맨 끝 원소와 정렬되지 않은 영역 첫 원소와 크기를 비교하여 정렬하고정렬되지 않은 영역에서 비교하는 원소A > 정렬된 영역 원소B 경우 => 정렬된 영역 원소 다음 원소와 비교해당원소 자리에 정렬된 영역 원소B 복사정렬되지 않은 영역에서 비교하는 원소A 정렬된 영역 원소 이전 원소에 A 삽입function InsertionSort (arr) { for(let i =1; i=0;--j){ //정렬된 배열 if(arr[j] > insertingData ){ arr[j+1] =arr[j]; }else{ break;// for문탈출 } } arr[j+1] = insertingData; } }오늘의 질문메모리 관리자는 어디에 위치해있나? cpu안? 혹은 메모리마다 가지고 있나?cpu 와 메모리 관리자는 따로 존재한다.CPU가 메모리에 접근하는 것을 관리하는 컴퓨터 하드웨어 부품 이라고 한다.테이블은 메모리에 할당되어있다고 하지만 그럼 STBR이랑 PTBR은 메모리 관리자 안에 있는데 어캐그럼? 험~

인프런 워밍업 클럽 스터디 2기 - CS 전공지식<10월 둘째주 발자국>

⭐10월 첫 째주 회고배운 내용CS => cpu 스케줄링,공유자원, 메모리FIFO -> SJF -> RR ->MLFQ타임슬라이스 등장으로 스케줄링 발전이 이뤄졌다.오버헤드없이, 공평하게 모든 프로세스들이 작업하는 것이 목표타임슬라이스 크기에 따라 성능이 달라진다.공유자원 : 통신하면서 같이 이용하는 변수,파일들을 말한다.공유자원은 한 프로세스가 사용하고 있을 때 다른 프로세스도 같이 사용되어서는 안된다. 1프로세스,1공유자원 -> 그렇지 않을 때 동기화 문제가 생긴다.임계구역, 경쟁조건, 상호배제 알고리즘상호배제 :세마포어, 모니터교착상태 : 상호배제, 비선점,점유과 대기, 원형대기 데드락, 은행원 알고리즘메모리 : --레지스터 --> 캐쉬 --> RAM ----> 보조저장장치 순으로 느림Algorithm => 재귀재귀 : 자기자신을 참조한다.하위문제의 결과를 현재문제와 계산재귀함수 : 콜스택, 팩토리얼 계산, 하노이탑정렬 : 배열을 기반으로 한 알고리즘 -> 버블,선택 정렬 회고알고리즘의 어느정도 메커니즘은 알겠다! 하지만 이런 알고리즘을 문제화되서 풀기엔 개념강의만 보면 부족할 것이다. 알고리즘 관련 문제도 풀어보려고 노력하는데 첫 걸음 떼기가 어렵다.알고리즘 문제, 백준이나 프로그래머스-- 같은 알고리즘 프로그램을 같이 하는 스터디같은 걸 만들어서 하면 어떨까 싶다. 혼자하면 어려운 거 나올 때 진짜 포기하고싶어지니까... 혼자하면 오래못하니까 ..운영체제같은 경우에는 스토리따라서 이해하고 외워가고 있다. 이렇게 회고할 때나 리프레쉬하고 월요일날 공부시작할 때 저번주에 어떤거공부했지 하면서 핵심키워드 따라서 복습하고 있다.공부할 때 시간에 쫓겨서 하지 말자 ㅜㅜㅜ 머리에 더 안들어온다.잘한점! 이번주 그래도 전날 들은 수업 블로그에 또 다시 올려서 복습했다! 수업들을 때도 노션에 필기하고 블로그에도 필기하고 회고에도 한 번 씩 더 쓰면서 상기시키기 더 좋은 것 같다.이번주 목표! 아침운동꼭! 알바 가기 전에 인프런 수업 두개 듣기@@

인프런 워밍업 클럽2 cs <day8>

알고리즘정렬 : 배열을 가지고 하는 알고리즘 버블 정렬, 선택정렬 -> O(n*n)버블정렬첫번째 배열의 수(a)와 다음 수(b)와 비교하여 a>b일 시 b와 교체되고 작은 수는 정렬된 배열이기 때문에 나중에 비교대상이 아니게 된다. 선택정렬정렬되지 않은 첫번째 배열안의 원소 값과 그다음 배열안 원소~끝까지 다 비교하고 첫번째보다 작을 경우 자리를 바꿔 정렬 운영체제메모리레지스터 : 메모리중 속도가 가장 빠르고 값도 비싸다.캐시메모리 : 느린 RAM과 빠른 레지스터 중간에서 레지스터가 필요할 데이터를 미리 보기 좋게 저장한다.RAM : 실제로 프로세스들이 올라가서 작업하는 공간보조저장장치 : 메모리 중에서 효율이 제일 좋은 유일한 비휘발성 메모리메모리와 주소물리 주소 : 메모리의 실제 주소논리 주소 : 사용자 입장에서의 주소 사용자는 실제 물리주소를 알 수 없기 때문에 실행될 주소를 0번지라고 가정하고 프로세스를 작업한다. 물리주소를 일일히 신경쓰지 않고 프로그램 개발물리주소로는 0x2000번지이지만 논리 주소로는 0x0번지라고 인지된다.RAM은 항상 운영체제 영역과 사용자공간을 따로 빼놓는다.이때 사용자 공간에서 운영체제 영역을 침범하면 안되기 때문에 ->? 왜여?경계레지스터를 사용해서 선을 긋는다.경계레지스터 : 메모리 관리자가 사용자 프로세스가 경계 레지스터 값을 넘어갔는지 확인 넘어갔다면 해당 프로세스를 정지 시켜버린다. CPU에 있다.메모리를 가져오는 방식사용자 : ㅌㅌㅌ번지 데이터가져와.-->CPU : 응 알겠어~ ㅌㅌㅌ번지 데이터~. 메모리관리자야~ ㅌㅌㅌ번지 데이터좀~ --> 메모리관리자 : ㅌㅌㅌ번지 데이터? 음~ 재배치 레지스터엔 물리주소를 xxxx를 가리키는 번지네 알겠어~ xxxx번지데이터 보내줄게~메모리 할당 방식가변 분할 방식 : 메모리에 프로세스가 들어올 때 프로세스 크기에 맞게 메모리에 할당 시킨다.연속된 메모리에 프로세스 할당외부단편화 발생 고정 분할 방식 : 메모리에 프로세스에 들어올 때 정해진 크기에 맞게 프로세스를 잘라 메모리에 할당 시킨다.단순하고 오버헤드가 없다.내부단편화 발생외부단편화 : 순서대로 프로세스가 할당되고 프로세스a와 프로세스b가 작업을 마친상태. 60mb짜리 프로세스가 들어올 때빈공간이 총 60mb이지만 고정분할 방식이 아니기때문에 많은 양의 손실이 생긴다.해결 방법 : 조각모음 조각모음으로 메모리에 들어있는 프로세스를 멈추고 하나하나씩 땡겨서 이동시킨다. ->오버헤드 발생내부단편화: 낭비공간이 쪼그만한하게 생기는 현상 해결방법 : 버디시스템 메모리를 2승수단위로 쪼갠 후 할당하는 방식 (2048바이트를 1024바이트 두개로, 1024바이트를 512바이트두개로, 512바이트를 256바이트 두개로 ....)들어가야할 프로세스 크기에 알맞는(프로세스크기보다 크지만 낭비가 제일 적은) 메모리에 할당시켜서 최소한의 낭비를 줄인다. -> 내부단편화가 생겨도 전보다는 덜하다!어제 복습 블로그 글올렸어야했는데 ㅜㅜ 오늘 하니까 드문 기억만 나네

인프런 워밍업 클럽2 cs <day8>

운영체제데드락 = 교착상태프로세스들 중 작업이 끝나기를 기다리다가 아무것도 못하는 프로세스가 이렇지도 저러지도 못하는 상황 => 공유자원이 원인식사하는 철학자식탁에 세 명의 철학자가 있고 세 개의 포크가 존재한다.밥을 먹을 땐 두 개의 포크를 사용해서 먹어야된다.포크 = 공유자원 , 철학자 = 프로세스교착상태 => 철학자 두 명이상이 밥을 같이 먹게 될 때 포크가 부족한 상황교착상태의 필요조건상호배제 : 프로세스가 리소스를 점유했을 때 점유한 리소스가 다른 프로세스와 같이 사용될 때비선점 : 프로세스a가 작업 중인데 프로세스 b가 와서 강제로 선점점유과 대기 : 프로세스가 리소스를 하나 점유하고 있고 또다른 리소스를 원하고(대기하고) 있는 상태원형대기 : 점유와 대기 형태가 원을 만들어 무한히 대기 중인 모습데드락 해결교착상태를 회피 : 교착상태가 일어날 정도로 프로세스에게 자원을 많이 할당해주지 않는다.안정상태 ------------- 불안정상태 --교착상태에 빠질확률 🔼--->은행원 알고리즘은행이 돈을 빌려줄 때 사업자의 자금상태를 확인하고(안정상태)여러 사업자에게 돈을 빌려주고 다른 사업자가 돈을 갚았을 때 그 돈으로 다른 사람에게 돈을 빌려주는 방식은행이 교착상태일 때 - 가진 돈은 100이지만 50, 50씩 빌려주었고 A는 20을 더 빌려주면 50까지 갚겠노라 한다 그래서 B에게 가서 50을 갚으라고 하고 그돈으로 A에게 돈을 빌려주려 했지만 갚지 못했다.-> 은행은 가진돈이 없다. 교착상태은행의 안정상태 : 기업가들이 여윳돈과 대출을 했을 때 빌릴 수 있는 능력이 있는지 확인한다. https://www.inflearn.com/users/17036/@%EA%B0%90%EC%9E%90 감자님 강의 중위에 상태 중 p1이 자원을 4만큼 요구한다. -> 사용가능한 자원은 2이므로 거절된다. p2에서는 자원을 2만큼 요구한다 -> 자원을 할당 시켜주고 4+2해서 6을 돌려받아 >>> 프로세스 p1과 p2의 나머지 자원을 할당시켜준다.불안정상태: 사용가능한 자원은 1개지만 프로세스들이 요구하고자 하는 자원이 훨씬 많을 경우 교착상태를 예방하기엔 어렵고 교착상태가 일어났을 때의 해결방법이 뭐가 있을까교착상태를 구분하기 -> 가벼운 교착상태 무거운 교착상태가벼운 교착 상태 : 프로세스가 일정시간 안에 작업을 진행하지 않음 -> 교착상태로 간주 해결 : 일정 시점마다 체크포인트에 저장을 하도록 하고 이전 체크포인트로 롤백하여 복구무거운 교착 상태 : 자원할당 그래프 이용 자원할당 그래프가 아래와 같이 순환구조 -> 교착상태 해결 : 교착상태가 일어난 프로세스 P2를 강제 종료시켜서 원형대기를 풀어버린다. 다시 실행 시킬 때 체크포인트로 롤백시킨다.이렇게 자원할당 그래프를 유지하고 검사 => 오버헤드가벼운 교첵상태에 비해 문제의 프로세스만 강제종료하면 되기때문에 효율적일지도?알고리즘재귀 -하노이탑이게 왜 재귀문과 연관이 있나...하향식 방식 계산을 한다. 원반 3을 움직이기 위해서는 원반1,2 전처리를 해야하게 때문function ha(count, from, to,temp){ if(count==0) return ; //기저함수 ha(count-1,from,temp,to); console.log(`원반 ${count}를 ${from} 에서 ${to}로 이동`); ha(count-1, temp,to,from); } ha(3,"A","B","C"); //원반갯수count,원반들이 처음에 꽃혀있는 기둥 from, //원반들이 최종적으로 꽂힐 기둥to, // 원반들이 이동을 위해 일시적으로 사용할 기둥temp //원반3이 기둥c로 이동하기위해서는 (하위문제) 원반 1,2,가 기둥 B로 위치해야함

인프런 워밍업 클럽 스터디 2기 - CS 전공지식<10월 둘째주 미션>

운영체제1. FIFO 스케줄링의 장단점이 뭔가요?FIFO : 먼저들어간 작업이 먼저 나온다.- 프로세스가 작업이 다 끝나야 비로소 다른 프로세스가 작업할 수 있기 때문에 직관적이고 쉽지만 비효율적이다. 입출력 작업이 들어올 땐 cpu가 그 작업이 끝났다는 메시지만 기다리고 있기 때문에 cpu가 낭비된다.- 먼저 들어간 프로세스의 작업시간이 길수록 오래걸리고 다음에 오는 프로세스들의 대기 시간이 길어진다.그렇게 되면 평균적인 대기시간이 길어지는데 효율이 낮다고 볼 수 있다.짧은 작업시간을 가진 프로세스 먼저 실행하게 되면 뒤에 있는 프로세스들의 대기 시간이 짧아지면서 평균 대기시간도 줄고, 전체적인 효율도 높아진다.단점을 보안하기위해 sjf 이라는 짧은 작업시간 먼저 실행하도록 하는 알고리즘이 생겼다. 2. SJF를 사용하기 여러운 이유가 뭔가요?짧은 평균 대기 시간을 갖을 수 있다. 하지만 대기 중인 프로세스 중에서 계속 짧은 작업시간을 가진 프로세스가 들어온다면 아주 예전부터 대기하던 긴 작업시간을 프로세스들이 무한히 기다리게 될 수있는 상황이 생기게 된다.그렇게 되면 작업수행을 하지 못하는 프로세스들이 생길 수 있게 된다. 또한 프로세스 중에 어떤 것이 짧은 작업시간을 갖는지 구분하기 불가능하기 때문에 SJF 을 사용하기 어렵다. 3. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?RR : Round Robin 타임슬라이스를 부여해서 순서대로 온 프로세스들을 스케줄링한다.타임슬라이스 길이를 초과하는 작업이라면 그때까지 한 작업을 강제로 멈추고 프로세스들 중 맨 뒤로 보낸다. 그 후 그 다음 프로세스가 타임슬라이스 동안 작업한다.> 타임 슬라이스가 너무 작을 경우에는 컨텍스트 스위칭이 실행시간보다 더 많이 생겨서 오버헤드가 생긴다.적절한 타임슬라이스로 작업하여 사용자가 사용했을 때 동시에 이용하고 있다는 느낌을 주어야한다.(타임 슬라이스 크기가 크면 FIFO 이랑 똑같이 된다. 오히려 RR 알고리즘이 컨텍스트 스위칭이 일어나 더 비효율적이게 된다.) 4. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?MLFQ : 멀티 레벨 피드백 큐. 여러 큐를 준비하고 큐마다 타임슬라이스와 우선순위를 준다.우선순위가 낮을수록 타임슬라이스 값이 커진다.작은 타임 슬라이스를 이용해서 프로세스들을 처리하게 된다. -> 긴 대기 시간을 가진 프로세스 오버헤드🔼 불리함.긴 대기시간을 가진 프로세스도 불이익 없게 하기 위해서는 어떻게 해야할까?-> MLFQ 알고리즘 사용 > CPU Bound Process는 cpu에 할당되어 작업할 것이 많을 텐데 그렇게되면 타임 슬라이스에 비해 오래 걸리기 때문에 자주 cpu를 뺏길 것이다. I/O Bound Process는 cpu 보다 입출력 작업을 더 많이 한다. 그렇게 된다면 분명 cpu를 자주 혹은 빨리 cpu 돌려줄 것이다. 이것을 보고 I/O bound Process 인 것을 예상할 수 있다. 5. 공유자원이란무엇인가요?> 프로세스들간에 작업을 할 때 같이 공통으로 쓰이게 되는 자원.공유자원을 한 프로세스가 사용할 때 다른 프로세스가 차지하지 않도록해야한다.-> 세마포어, 모니터 상호배제 알고리즘이 있다. 6. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?> 총 4가지 조건을 충족해야 한다.상호배제 : 작업 중인 프로세스가 공유자원을 사용하는데, 다른 프로세스가 공유자원을 사용비선점 : 프로세스가 하는 작업을 다른 프로세스가 와서 뺏지 않는다.점유와 대기 : 프로세스가 a작업을 하는 중에 다른 b작업을 하려고 대기하는 상태환형대기 : 점유와 대기 모습이 원형 모습으로 서로서로 대기하는 상태 자료구조와 알고리즘1. 재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?기저 조건에 따라 다르지만 프로그램이 멈추지 못하고 영원히 재귀함수를 호출하거나 원하지 않는 결과가 나올 수있다. 2. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n){ // 재귀 로직 if(n

인프런 워밍업 클럽2 cs <day7>

운영체제프로세스간 통신프로세스간의 통신 종류 : 한 컴퓨터 안에 프로세스들 간의 통신다른 컴퓨터 안에 있는 프로세스들 간의 통신한 컴퓨터 안에 프로세스들 간의 통신 방법파일 사용: 하나의 파일을 이용하여 통신하려는 프로세스끼리 읽고 쓰기파이프 사용 : 운영체제가 만든 파이프를 통해 데이터를 읽고 쓰기쓰레드 사용 : 한 프로세스 안에서 여러 쓰레드 간 통신 방법데이터 영역에 있는 전역변수나 힙 영역을 이용하면 통신이 가능하다.네트워크 사용 : 운영체제가 제공하는 소켓, RPC(원격프로 시저 호출)를 이용RPC(Remote Procedure call) - 다른 컴퓨터를 호출 공유자원과 임계구역공유자원 : 통신하면서 공동으로 이용하는 변수나 파일들공유자원은 프로세스 접근 순서에 따라 결과가 달라진다.컨텍스트 스위칭으로 인해서 시분할된다 -> 어떤 프로세스가 먼저 실행될지 예측하기 어렵다.-> 동기화 문제 : 연산 결과가 예측이 어려워 이 과정에서 생기는 문제들.임계구역 (Critical Section) : 여러 프로세스가 동시에 사용하면 안되는 영역.경쟁조건 (Race Condition) : 공유 자원을 서로 사용하기 위해 경쟁하는 것.임계구역에 대한 해결을 위해서 상호배제 매커니즘 필요상호배제 : 둘 이상의 프로세스가 동시에 임계 영역(CS : Critical Section)에 진입하는 것을 방지하기 위해 사용되는 알고리즘상호배제의 요구사항 임계영역엔 동시에 하나의 프로세스만 접근 가능여러 요청에도 하나의 프로세스만 접근 허용한다.임계구역에 들어간 프로세스는 빠르게 나와야한다.(다른 프로세스가 오래 기다리기 때문) 세마포어 https://baebalja.tistory.com/340세마 포어란? 공유자원이 하나 이상일 때 처리하는 동기화 방법현재 공유 자원에 접근할 수 있는 프로세스/스레드(resource)의 수예시 프린터를 사용하려는 다른 컴퓨터 두 대프린터기 : 공유자원컴퓨터 : 프로세스들, 경쟁조건해소 방법 : 프린터실을 만들어 오직 한 컴퓨터만 프린터를 사용할 수 있게 만든다.열쇠관리자 : 운영체제열쇠 : 세마포어프로세스에서 동기화 대상이 여러 개가 될 수있기 때문에 세마포어는 여러 개가 존재할 수있다.wait()함수와 signal()함수를 이용 위 함수에 들어갈 인자 값은 동기화하고있는 프로세스의 개수wait() : 열쇠를 요청해서 열쇠를 받고 문을 잠그는 함수. 다른 함수는 실행되지 않고 멈춘다.signal() : 열쇠 관리자(OS)에게 열쇠 반납 함수. 다음 함수가 실행된다.단점 : 두 개의 함수는 순서를 지키지 않고 호출해서 세마포어를 사용하지 못할 수가 있다. 모니터세마포어를 보완한 상호배제 알고리즘프로그래밍 언어 차원에서 지원하는 방법으로 자바에서 주로 모니터한다.synchronized 가 붙은 함수 : 동시에 여러 프로세스가 실행 시킬 수 없다.ex) synchronized 가 붙은 increase()함수 사용 시 synchronized 가 붙은 decrease()함수도 사용할 수없다.->synchronized 가 붙은 함수가 사용된다면 다른 synchronized 함수도 사용불가.wait(), signal()함수를 임계영역에 감싸지 않아도 된다. 알고리즘재귀적으로 생각하기(재귀적 사고 skrr)for문 vs 재귀함수 => for문이 더 효율적, 재귀함수는 어떨때 효율적일까?하향식 계산에 유리한 재귀함수하향식 계산 : 하위 문제의 결과를 기반으로 현재 문제를 계산한다 (재귀함수)return number * factorial(number -1);상향식 계산 : 일반적으로 실행되는 계산(for문) 재귀함수를 상향식으로 계산한다고 성능이 좋아지진 않아서 굳이 재귀문을 상향식 계산하지 않는다.function factorial(number){ if( number ==1 || number ==0) return 1;//기저 조건 return number * factorial(number-1);// 현재문제 * 하위 문제 } 부족하다고 생각되는 부분은 블로그에 찾아가서 읽어봤다. 이 열정이 얼마나 갈지 모르겠네

인프런 워밍업 클럽2 cs <day6>

DAY 6 과제운영체제 -섹션 3유닛 5,6,7 SJF,RR, MLFQ알고리즘 - 섹션 3 유닛 1 재귀 알고리즘재귀함수란 자기 자신을 호출하는 함수콜스택에 자리를 많이 차지하여 메모리효율에 떨어진다.콜스택 : 프로세스에서 코드,데이터, 힙,스택 으로 메모리 영역이 있다. 그 중 하나콜스택은 함수가 First In Last Out으로 처음 들어가는 함수가 나중에 나온다.재귀함수가 호출될 때마다 콜스택에 계속 쌓이는데 거기서 메모리 효율이 떨어진다.그럼에도 불구하고 사용하는 이유팩토리얼을 표현하기 편리하다.팩토리얼 : 1부터 n까지 모두 곱하여 표현하는 것 (표기 5!)5! =5*4*3*2*1 function facto(num){ if(num == 1 || num == 0){ return 1; }else{ return num * fac(num-1); //5 * fac(4)= 5 * 4 * fac(3).... } }운영체제SJFShort Job FirstFIFO 의 단점을 보안해보려고 만든 알고리즘이지만brustTime(대기시간)이 너무 긴 프로세스에게는 계속 밀려나서 불리한 알고리즘프로세스의 실행시간을 예측하기도 어렵기 때문에->실패해버린 알고리즘 ㅜㅜ RRRound Robin실행시간이 다끝날 때까지 기다리는 FIFO 과 SJF 단점을 보안해서타임 슬라이스를 부여해서 일정 시간이 지나면 프로세스가 cpu 할당하는 것을 끊고맨 뒤로 보내버리는 알고리즘RR 대기시간 = FIFO 대기시간 -> RR은 비효율적인 방식!RR은 컨텍스트 스위칭에 시간을 더 많이 사용하기 때문RR은 타임슬라이스의 크기에 따라 효율이 달라진다.타임 슬라이스⬇, 컨텍스트 스위칭⬆ -> 배보다 배꼽이 더 커진다.타임 슬라이스 ⬆, 사용자가 여러 프로세스를 같이 사용할 때 버벅임을 느낄 수있다.하지만 실제 타임슬라이스는 1ms으로 설정되어 있다~ MLFQMulti Level Feedback QueueRR 업그레이드 버전타임 슬라이스의 크기에 따라 달라지는 알고리즘 이다.CPU Bound Process :cpu 사용률과 처리량을 제일 중요 시 여긴다.I/O Bound Process : 입출력 장치 사용률과 처리량을 제일 중요 시 여긴다. 타임 슬라이스 크기 차이에 따라 i/o 사용률이 확연히 다른 걸 볼 수있지만,오른쪽 p1은 컨텍스트 스와칭⬆, 오버헤드도 ⬆p1과 같이 실행시간이 긴 애들은 오버헤드와 같은 불공평을 견뎌야한다...->MLFQ를 사용해서 불공평을 없애보자!cpu 바운드프로세스와 입출력 바운드 프로세스 각각 다른 타임 슬라이스를 부여한다.->구분해야된다.구분하는 방법!cpu 바운드 프로세스 일 경우 cpu 사용하는 프로세스가 타임슬라이스 크기를 오버해 cpu 스케줄러에 의해 강제로 cpu를 빼앗기는 상황이 생긴다.반대로 입출력 바운드 프로세스는 스스로 cpu를 반납하려는 상황이 생긴다.(cpu 사용률 적음)이 방법을 토대로 우선순위와 타임슬라이스에 따른 큐를 준비한다.👇1. 프로세스가 우선순위 1큐에 들어간다.2. 타임슬라이스 크기를 오버해 강제로 CPU를 뺏긴다-> 우선순위 2 큐로 우선순위가 낮은 큐로 이동=> 우선순위에 밀릴수록 타임 슬라이스크기가 커지고 CPU를 효율적으로 사용할 수 있는 환경이 된다.다른 알고리즘은 되게 친근했는데 MLFQ는 들을 때 예? 하면서 한 번씩 다시들었다.사실 공부했던 건데 큐와 큐사이를 이동할 수 있는 알고리즘임~ 하고 외워버리기만하고 이렇게 자세하게 보지 않았던 것 같다.