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

운영체제섹션 8. 가상메모리8-1. 가상메모리 개요가상메모리를 사용해 프로세스는 운영체제 영역이 어디있는지, 물리메모리 크기가 얼마나 큰지 몰라도 됨. 즉, 프로그래머는 물리 메모리의 크기와 프로세스가 메모리에 어느 위치에 올라가는지 신경쓰지 않고 0x0번지에서 시작된다고 생각하고 프로그래밍을 하면 됨프로세스 입장에서는 물리 메모리에 직접 접근할 일이 없고, 메모리 관리자에게 요청만 하면 됨메모리 관리자는 프로세스의 요청이 있으면 그에 맞는 물리 메모리로 연결시킴가상 메모리의 크기는 이론적으로는 무한대이지만, 실제로는 물리 메모리 크기와 CPU의 비트 수로 결정됨동적주소변환(DAT)이란? 메모리 관리자는 물리 메모리 + 스왑영역을 합쳐서 프로세스가 사용하는 가상주소를 물리주소로 변환하는 것동적주소변환을 거치면 프로세스는 마음대로 사용자 데이터를 물리 메모리에 배치할 수 있음가변 분할 방식(세그멘테이션)단점: 외부 단편화고정 분할 방식(페이징)단점: 내부 단편화가변 분할 방식, 고정 분할 방식 둘 다 단점이 있기에 이를 보완한 세그멘테이션-페이징 혼용기법을 사용함8-2. 세그멘테이션(배치정책)세그멘테이션에서 프로그램은 함수나 모듈등으로 세그먼트를 구성함사용자와 프로세스, CPU가 바라보는 주소는 논리주소. 실제 물리주소로의 변환은 중간에서 메모리 관리자(MMU)가 수행. 세그멘테이션 테이블에는 Base Address와 Bound Address 정보가 저장되고 이걸 이용해 물리 메모리 주소를 계산함CPU에서 논리 주소 전달 → 메모리 관리자는 이 논리주소가 몇번 세그먼트인지 확인 → 메모리 관리자 내에 Segment Table Based Register를 이용해 물리 메모리내에 있는 세그멘테이션 테이블 찾음운영체제는 컨텍스트 스위칭을 할 때마다 메모리 관리자내에 Segment Table Base Register를 해당 프로세스의 것으로 값을 바꿔줘야 함메모리 관리자는 CPU에서 받은 논리주소와 이 Bound Address의 크기를 비교함만약 논리주소가 Bound Address보다 작다면 논리주소와 Base Address를 더해 물리주소를 구하고, 논리주소가 Bound Address보다 크다면 메모리를 침범했다고 생각하고 에러를 발생시킴세그멘테이션장점메모리를 가변적으로 반할할 수 있음코드 영역, 데이터 영역, 스택 영역, 힙 영역을 모듈로 처리할 수 있기에 공유와 각 영역에 대한 메모리 접근보호가 편리함단점가변 분할 방식의 단점인 “외부 단편화”가 발생함8-3. 페이징(배치정책)페이징은 메모리를 할당할 때 정해진 크기의 페이지로 나눔. 모든 페이지는 크기가 같기에 관리가 굉장히 쉬워짐. 또한 일정한 크기로 나눴기에 외부단편화 현상이 일어나지 않음. 하지만 단점으로 “내부 단편화”가 발생함페이징에서 논리주소공간은 일정한 크기로 균일하게 나눔. 이를 “페이지”라 부름물리주소공간도 페이지의 크기와 동일하게 나뉘는데 이를 “프레임”이라고 부름CPU에서 논리주소 전달 → 메모리 관리자는 이 논리주소가 몇번 페이지인지, 오프셋은 얼마인지 알아냄 → 메모리 관리자 내 Page Table Base Register(PTBR)를 이용해 물리 메모리에 있는 페이지 테이블을 찾음 → 페이지 번호를 인덱스로 프레임 번호를 알아냄 → 오프셋을 이용해 물리주소로 변환페이지 테이블에 Invalid로 표시되어 있으면 스왑영역, 즉 하드디스크에 저장되어있다는 의미. 세그멘테이션과 마찬가지로 Page Table Base Register는 운영체제가 컨텍스트 스위칭을 할 때마다 해당 프로세스의 것으로 업데이트 해줌물리주소의 크기가 가상주소의 크기보다 작아도 문제 없음을 보여주기위해 물리주소공간을 적게 설정함부족한 물리메모리는 스왑처리를 하기에 괜찮음세그멘테이션은 프로세스마다 크기가 달라 Bound Address를 가지고 있지만, 페이징은 모든 페이지의 크기가 동일해서 크기를 표현하는 Bound Address는 필요하지 않음페이징은 이러한 특징 때문에 외부단편화는 발생하지 않지만 내부단편화가 발생함정해진 크기의 페이징보다 프로세스의 정보가 작으면 그만큼 공간이 낭비되는데 이를 내부 단편화라고 부름세그멘테이션은 논리적인 영역별로 세그먼트를 나눔. 세그먼트별로 크기를 다르게 나눌 수 있으니 코드 영역, 데이터 영역, 스택 영역, 힙 영역을 나눌 수 있음. 하지만 페이징은 크기가 고정되어 있어 논리적인 영역별로 나누는 것이 아니라 페이지로 나누기에 논리적인 영역을 나눌 수 없음 그래서 특정 영역만 딱 떼어내서 공유하거나 권한을 부여하는게 더 어려움페이징에서 가장 신경써야하는 것은 페이지 테이블의 크기각 프로세스별로 페이지를 가지고 있는데, 프로세스가 많아질수록 페이지 테이블도 많아지기에 프로세스가 실제로 사용할 수 있는 메모리 영역이 줄어듬. 실제로 메모리 관리자가 참조하는 페이지 테이블도 물리 메모리의 운영체제 영역에 저장되어 있기에 페이지 테이블의 크기가 너무 크면 사용자 영역이 부족하게 됨. 이 때문에 페이지 테이블의 크기를 적절하게 유지하는 것이 굉장히 중요함8-4. 페이지드 세그멘테이션(배치정책)페이지드 세그멘테이션은 세그멘테이션과 페이징을 혼합해 장점을 취한 방식세그멘테이션은 가변 분할 방식이어서 코드 영역, 데이터 영역, 스택 영역, 힙 영역을 세그먼트로 나눠서 관리할 수 있음. 때문에 다른 프로세스와 공유하기도 편하고, 각 영역에 대한 메모리 접근보호를 하기 쉬움페이징은 고정 분할 방식으로 메모리를 효율적으로 관리 할 수 있음메모리 접근 권한은 메모리의 특정 번지에 부여된 권한으로 읽기(Read), 쓰기(Write), 실행(Execute) 세 가지가 있음. 프로세스는 코드 영역, 데이터 영역, 스택 영역, 힙 영역이 있는데 각 영역마다 접근 권한이 있음코드 영역: 프로그램 그 자체이므로 수정되면 안되기 때문에 읽기/실행 권한만 있음데이터 영역: 일반변수, 전역변수, 상수로 선언한 변수가 저장되기에 읽기 권한이 있고, 쓰기 권한은 있거나 없거나임. 당연히 실행권한은 없음스택&힙 영역: 읽기/쓰기 권한. 실행권한은 없음메모리 접근 권한에 대한 검사는 가상주소에서 물리주소로 변활될 때마다 일어남. 만약 권한을 위반하면 에러를 발생시킴페이지드 세그멘테이션장점메모리 관리의 효율화세그먼트를 페이지로 나누어 효율 증ㅇ가외부 단편화 감소효율적인 메모리 할당유연함페이지 단위의 물리적 관리동적으로 크기 조절보안세그먼트 단위 보호단점물리메모리에 접근하기 위해 메모리에 접근을 두 번 해야되기에 복잡함세그멘테이션 테이블을 참조할 때페이지 테이블을 참조할 때테이블 관리세그먼트 테이블, 페이지 테이블 모두 관리가 필요하여 관리 비용 증가주소 변환 시간 증가8-5. 디멘드 페이징(가져오기 정책)프로세스를 이루고 있는 모든 모듈이 올라와 실행되는게 아니라, 필요한 모듈만 올라와서 실행됨지역성 이론공간의 지역성: 현재 위치와 가까운 데이터 접근할 확률이 높음시간의 지역성: 최근 접근했던 데이터가 오래 전에 접근했던 데이터보다 접근할 확률이 높음디멘드 페이징은 조만간 필요할 것 같은 데이터를 메모리로 가져오고 쓰이지 않을 것 같은 데이터는 스왑영역으로 이동시키는 정책. 필요한 페이지만 메모리에 적재하여 사용하는 가상 메모리 시스템의 핵심메모리에 접근하는 시간이 보조저장장치 쪽으로 갈수록 느려짐. 디멘드 페이징은 스왑영역을 보조저장장치에 저장하는데 성능향상을 위해선 스왑영역으로 데이터를 이동시키는 것을 최소화 시켜야함접근 비트: 페이지가 메모리에 올라온 후 데이터에 접근이 있었는지 알려주는 비트. 메모리에 읽기나 실행 작업을 했다면 1로 바뀜변경 비트: 페이지가 메모리에 올라온 후 데이터의 변경이 있었는지 알려주는 비트. 메모리에 쓰기 작업을 했으면 1로 바뀜유효 비트: 페이지가 물리 메모리에 있는지 알려주는 비트. 만약 유효비트가 1이라면 페이지가 스왑영역에 있고 0이라면 물리 메모리에 있다는 의미읽기/쓰기/실행 비트: 권한비트로 해당 메모리에 접근권한이 있는지 검사하는 비트프로세스가 가상 메모리에 접근요청을 했을 때 메모리 관리자는 페이지 테이블을 보고 물리 메모리의 프레임을 찾아내는데 만약 물리 메모리에 없다면 Page Fault라는 인터럽트를 발생시킴Page Fault가 발생하면 보조저장장치의 스왑영역에 접근하게 되고 해당 프로세스는 대기상태가 됨그럼 스왑영역에 있는 데이터가 메모리로 올라가는 작업을 시작하고 메모리로 올라갔다면 대기상태에 있던 프로세스는 다시 실행하게됨8-6. 페이지 교체정책프로세스는 데이터 접근을 위해 메모리를 참조하는데 해당 데이터가 메모리에 없으면 Page Fault가 발생함. Page Fault가 발생하면 해당 페이지를 스왑영역에서 메모리로 불러들여야하는데 메모리가 꽉 차서 공간이 없다면 메모리에 있는 페이지 중에 하나를 선택해서 스왑영역으로 옮겨야함메모리에 있는 페이지를 스왑영역으로 옮길 때 어떤 페이지를 선택할지 결정하는 정책을 페이지 교체 정책이라고 함무작위로 선택하는 방법(Random): 지역성을 고려하지 않기에 자주 사용되는 페이지가 선택될 때도 있어 성능이 별로 좋지 않음. 그래서 거의 사용되지 않음메모리에 들어온지 가장 오래된 페이지를 선택하는 방법(FIFO): 페이지 교체 정책에서는 자주 쓰이는 페이지가 먼저 들어왔다는 이유로 해당 페이지 교체되면 공평하지 않음. 하지만 구현이 간단하고 성능도 꽤 괜찮아서 조금 변형해서 많이 쓰임앞으로 가장 오랫동안 쓰이지 않을 페이지를 선택하는 방법(Optimum): 이 방법은 사실상 구현이 불가능한 이론적인 선택방법. 다른 알고리즘과 성능 비교를 할때 참조용으로 쓰임최근에 가장 사용이 적은 페이지를 선택하는 방법(LRU - Least Recently Used): 지역성 이론의 시간의 지역성에 따르면 최근 사용한 데이터가 앞으로도 사용될 확률이 높기 때문에 최근에 가장 사용을 적게한 페이지가 앞으로도 사용될 확률이 적다는 결론. 실제로도 Optimum 알고리즘에 근접한 성능을 보임. 하지만 프로그램이 지역성을 띄지 않을땐 성능이 떨어짐FIFO의 가장 큰 문제는 빌레이디라는 사람이 제시한 빌레이디의 역설빌레이디의 역설이란 Page Fault를 줄이려고 메모리를 더 늘려서 프레임의 수를 늘렸는데 오히려 Page Fault가 더 많이 발생하는 현상을 말함. 빌레이디의 역설은 FIFO에서만 발생하며 LRU에서는 발생하지 않음클락 알고리즘LRU와 유사하게 만든 알고리즘. 클락 알고리즘은 접근비트 하나만 이용함. 일정 시간 간격마다 모든 페이지의 접근 비트를 0으로 초기화함. 접근비트의 초기값은 0으로 설정되어있고 만약 페이지가 참조되었다면 1로 설정됨. 그럼 일정 시간간격마다 페이지가 참조되었는지 참조되지 않았는지 확인할 수 있음클락 알고리즘은 페이지를 원형으로 연결함. 스왑 영역으로 옮길 페이지를 포인터로 가르키는데 이 포인터를 클락 핸드라고 부름. 클락 핸드는 시계 방향으로 돎만약 Page Fault가 발생해서 스왑영역으로 보내야하는 상황이 나오면 클락 핸드는 현재 참조하고있는 페이지의 접근비트를 봄. 만약 접근비트가 1이라면 해당 접근비트를 0으로 바꾸고 클락 핸드가 다음 페이지를 가르킴. 반복하다가 접근비트가 0인 페이지를 발결하면 해당 페이지를 스왑 영역으로 보냄향상된 클락 알고리즘의 경우 접근비트만 이용하는 것이 아니라 변경비트까지 봄부득이하게 FIFO를 사용해야하는 경우가 있음LRU에선 접근비트를 이용하는데 하드웨어적으로 접근비트를 지원하지 않는 시스템에선 FIFO를 이용할 수 밖에 없음. 어쩔 수 없이 FIFO를 사용하는 경우도 생기기에 FIFO의 성능을 높이기 위한 방법이 고안됨. 위 사진의 단점 때문에 2차 기회 페이지 교체 알고리즘이 고안됨2차 기회 페이지 교체 알고리즘은 FIFO 방식에서 자주 사용하는 페이지에게는 또 한 번의 기회를 줌. FIFO 방식과 동일하게 동작하지만 만약 Page Fault 없이 페이지 접근만 성공했다면 해당 페이지를 큐의 맨 뒤로 이동시켜 수명을 연장시켜주는 방식8-7. 스레싱과 워킹셋CPU 스케줄링의 목표는 CPU 사용률을 높이는 것CPU 사용률을 높이기 위해서는 동시에 실행하는 프로세스의 수. 즉, 멀티프로그래밍 정도를 올려야함동시에 실행하는 프로세스의 수가 늘어나면 어떤 프로세스가 I/O 작업으로 CPU를 사용할 수 없을 때 다른 프로세스로 컨텍스트 스위칭을 해서 CPU사용률을 높일 수 있음멀티프로그래밍 정도가 올라가면 제한된 물리메모리에 모든 프로세스를 올려야하고 당장 실행되는 프레임을 제외한 나머지 프레임들은 스왑영역에 저장되고 Page Fault가 많이 발생하게 됨그러면 CPU가 작업하는 시간보다 스왑작업의 시간이 더 길어지고 CPU의 사용률은 떨어지게됨CPU 스케줄러는 CPU 사용률이 떨어지면 더 많은 프로세스를 메모리에 올리게되고, 이렇게 반복하다 보면 어느새 CPU 사용률이 0에 가깝게 떨어지게 됨CPU 사용률을 높이려 했지만 오히려 더 떨어지는 상황을 스레싱 이라고 함하드웨어적으로 해결하려면 메모리 크기를 늘리면 됨. 하지만 무작정 메모리의 크기를 늘린다고 성능이 좋아지지는 않음. 그 이유는 현재 메모리가 프로세스들이 작업을 하는데 충분한 크기라서 스레싱이 발생하지 않는다면 크기를 늘려도 별 다른점이 없기 때문한 프로세스가 실행될 때 너무 많은 페이지를 할당하면 다른 프로세스가 사용할 페이지가 줄어들기 때문에 효율이 떨어지게됨. 반대로 너무 적은 페이지를 할당하면 빈번한 Page Fault가 발생하고 스왑 요청이 많아 스레싱이 발생하게 됨이를 해결하기 위해 프로세스가 실행되면 일정량의 페이지를 할당하고 만약 Page Fault가 발생하면 더 많은 페이지를 할당함. 반대로, Page Fault가 너무 적게 발생하면 페이지를 과하게 할당해 메모리가 낭비되는 것이라고 판단하고 페이지를 회수함이렇게 하면 프로세스가 실행되는 동안 해당 프로세스에게 맞는 적절한 페이지 수가 결정됨현재 메모리에 올라온 페이지는 다시 사용할 확률이 높기 때문에 하나의 세트로 묶어서 메모리에 올림이를 워킹셋이라고 부름. 워킹셋은 프로세스가 준비상태에서 실행 상태가 되는 컨텍스트 스위칭을 할 때 사용됨섹션 9. 입출력 장치9-1. 주변장치(I/O 디바이스, 저장장치)주변장치는 그래픽 카드, HDD, SSD, 키보드, 마우스 등등 여러가지가 있음주변장치들은 메인보드에 있는 버스로 연결됨실제로 하나의 버스는 Address 버스, Data 버스, Control 버스로 이루어짐. 그래서 I/O 디바이스는 이 세 가지 버스를 따로 받을 수 있음. 그리고 각 하드웨어에 맞게 외부 인터페이스가 존재함. 또 장치의 상태와 데이터를 보관할 수 있는 각종 레지스터들이 존재함. 레지스터들은 입출력 작업을 할 때 데이터를 저장하는 역할을 함. 이 값들은 CPU가 사용하기 위해 메모리로 이동되기도 함캐릭터 디바이스마우스, 키보드, 사운드 카드, 직병렬 포트 등데이터 전송 단위가 캐릭터(글자)로 상대적으로 크기가 작음블록 디바이스HDD, SSD, 그래픽 카드 등데이터 전송 단위가 블록(범위)로 상대적으로 크기가 큼여러 주변장치는 메인보드 내의 버스로 연결예전에는 주변장치들을 하나의 버스로 연결해서 사용함. CPU가 작업을 하다가 I/O 명령을 만나면 직접 입출력 장치에서 데이터를 가져왔는데 입출력중에는 다른 작업을 하지 못했기 때문에 CPU 사용률이 떨어짐. 이를 해결하기 위해 입출력 제어기(I/O Controller)와 여러 개의 버스가 추가됨CPU는 I/O명령을 만나면 입출력 제어기에게 입출력작업을 맡기고 다른 작업을 실행함입출력 제어기는 두 개의 채널, 시스템 버스와 입출력 버스로 구분함시스템 버스는 고속으로 작동하는 CPU와 메모리가 사용하고 입출력 버스는 주변장치가 사용함입출력 버스는 세부적으로 느린장치와 빠른장치를 구분하기 위해 다시 고속 입출력 버스와 저속 입출력 버스로 나뉨느린 장치와 빠른 장치를 구분해 속도차이로 인한 병목현상을 해결함그래픽 카드는 다루는 데이터가 매우 대용량이라 고속 입출력 버스로도 감당이 안됨. 그래서 그래픽 카드는 입출력 버스에 있지않고 시스템 버스에 바로 연결해 사용함입출력 제어기는 여러 주변장치를 처리하는데 입출력 버스에서 온 데이터를 메모리로 옮김. 메모리는 CPU의 명령으로 움직이기에 입출력 제어기가 메모리에 접근하기 위해선 CPU가 필요함.입출력 제어기가 CPU의 도움이 필요없도록 DMA 제어기가 추가됨DMA는 직접 메모리 접근이라는 뜻. 입출력 제어기는 DMA로 데이터를 직접 메모리에 저장하거나 가져올 수 있음. CPU와 DMA가 사용하는 메모리가 겹쳐지지 않도록 CPU가 사용하는 메모리 영역과 DMA가 사용하는 메모리 영역을 나누는데 이를 Memory Mapped I/O라고 부름9-2. 마우스/키보드광학 카메라는 초당 1500회가 넘는 사진을 찍어 마우스의 디바이스 컨트롤러내 DSP로 보냄DSP는 이 사진을 분석해 마우스의 X축, Y축 좌표 움직임을 캐치함DSP가 마우스의 움직임과 클릭같은 데이터를 감지하면 디바이스 컨트롤러는 CPU에게 인터럽트를 보내고 마우스 드라이버가 동작해서 데이터를 읽어감 → 마우스 드라이버는 운영체제에게 이벤트 신호 전송 → 운영체제는 이 이벤트를 Foreground 애플리케이션으로 전달 → 해당 애플리케이션은 마우스 이벤트 처리키보드 또한 사용자가 키보드를 누르면 → CPU에게 인터럽트를 보내고 → 키보드 드라이버는 운영체제에게 이벤트를 보냄 → 그럼 운영체제는 Foreground 애플리케이션으로 이 이벤트를 전달 → 애플리케이션에서 해당 키에 맞는 동작을 수행함9-3. 하드디스크/Flash Memory(SSD)하드디스크(HDD)동작 원리자기 디스크를 기계적으로 회전헤드로 데이터 읽기/쓰기자기적 방식으로 데이터 저장장점저렴한 가격대용량 저장 가능수명이 긴 편단점느린 속도물리적 충격에 약함소음/발열 발생전력 소비 큼SSD(Solid State Drive)동작 원리반도체(플래시 메모리) 사용전기적 방식으로 데이터 저장기계적 부품 없음장점매우 빠른 속도충격에 강함소음 없음전력 소비 적음단점상대적으로 비쌈수명 제한(P/E 사이클)용량당 가격이 높음섹션 10. 파일시스템10-1. 파일과 파일시스템파일들은 하드디스크나 SSD와 같은 저장장치에 저장됨. 메모리와 마찬가지로 사용자가 직접 저장을 하게 되면 중요한 정보를 훼손할 수 있기에 사용자가 운영체제를 통해 요청하면 운영체제가 안정하제 저장해줌운영체제는 파일을 관리하기 위해 파일관리자를 뒀는데 이를 파일시스템이라고 함파일시스템의 기능파일과 디렉토리 생성파일과 디렉토리 수정/삭제파일 권한 관리 - 다른 사용자로부터 파일을 보호하기 위해 접근 권한을 관리함. 요즘 운영체제는 다중 사용자기능을 지원하기 때문에 파일을 보호하기 위해 꼭 필요한 기능무결성 보장 - 파일의 내용이 손상되지 않도록 무결성 보장백업과 복구 - 예기치 못한 사고로부터 백업과 복구를 함암호화 - 파일을 암호화해 파일을 보호하는 것파일 시스템은 하드 디스크나 Flash Memory 같은 저장장치에 저장되기 때문에 전송 단위가 블록임저장장치의 전송 단위는 블록이지만 사용자는 바이트 단위로 파일에 접근이 가능해야함. 이는 파일 관리자가 중간에서 관리해줌운영체제는 파일을 관리하기 위해 정보를 보관하는 파일제어블록(File Control Block, FCB)을 가지고 있는데 이를 파일 디스크립터(File Descriptor)라고 부름. 파일 디스크립터는 파일마다 독립적으로 존재하고 저장장치에 존재하다가 파일이 오픈되면 메모리로 이동함. 파일 디스크립터는 파일시스템(운영체제)이 관리하고 사용자가 직접 참조할 수는 없음파일은 데이터의 집합으로 볼 수 있는데 이 데이터의 집합을 어떻게 구성하느냐에 따라 종류를 나눌 수 있음순차파일구조 - 파일의 내용이 연속적으로 이어진 형태장점: 모든 데이터가 순서대로 기록되기 때문에 공간의 낭비가 없고 구조가 단순함단점: 특정지점에 바로 이동이 어려워 데이터를 삽입하거나 삭제하려면 탐색하는데 시간이 많이 걸림직접 파일구조 - 저장하려는 데이터를 해시함수를 통해 저장위치를 결정하는 파일구조장점: 해시함수를 이용하기에 데이터 접근이 굉장히 빠름단점: 해시함수의 선정이 굉장이 중요하기에 해시함수를 잘 골라야 한다는 점과 저장공간이 낭비될 수 있다는 점. 예를 들어 흔히 쓰이지 않는 성씨가 있다면 해당 성씨에 저장되는 데이터는 굉장히 적음인덱스 파일구조 - 인덱스 파일구조는 순차접근과 직접접근 방식의 장점을 취한 것으로 두 가지 방식 모두 가능함10-2. 디렉토리파일을 하나의 공관에만 보관하면 파일이 많아지면서 굉장히 복잡해짐. 그래서 관련있는 파일을 모아둘 수 있도록 디렉토리가 등장함. 디렉토리는 1개 이상의 파일을 가질 수 있고 자식 디렉토리도 가질 수 있음디렉토리는 여러 층으로 구성되는데 최상위에 있는 디렉토리를 루트 디렉토리라고 부름. 유닉스나 리눅스의 경우 루트 디렉토리를 “/”로 표시. 윈도우는 보통 “C:”으로 표시디렉토리도 파일임. 단지 일반 파일에는 데이터가 저장되어있고 디렉토리에는 파일 정보가 저장되어있음다단계 디렉토리는 어떠한 디렉토리에서도 하위 디렉토리를 만들 수 있는 트리구조우리가 쓰는 운영체제에서는 트리 구조에서 순환이 생기는데 그 이유는 바로가기 기능이 있기 때문윈도우즈에서는 바로가기를 통해 특정 디렉토리에서 다른 디렉토리로 바로 이동할 수 있기에 순환이 있는 트리구조10-3. 파일과 디스크파일시스템은 페이징과 같이 전체 디스크 공간을 일정한 크기로 나누고 그 공간에 주소를 할당해 관리함일정한 크기로 나눈 공간을 메모리에선 페이지라 부르고 파잀시스템에선 블록이라고 부름. 한 블록의 크기는 1~8kb 정도. 파일시스템은 파일정보를 파일테이블로 관리하는데 여기엔 파일이 시작하는 블록의 위치정보도 담겨있음하나의 파일은 여러 개의 블록으로 이루어져 있는데 이 블록들을 어떻게 연결하는지에 따라 연속할당, 불연속할당으로 나뉨연속할당: 파일을 구성하는 블록들을 디스크에 연속적으로 저장하는 방식파일의 시작 블록만 알면 파일의 전체를 찾을 수 있음. 이 방식은 메모리에서 세그멘테이션 기법처럼 외부 단편화가 발생하기 때문에 실제로 사용되지 않는 방식불연속할당: 디스크에 비어있는 공간에 데이터를 분산해 저장하는 방식이 분산된 블록은 파일시스템이 관리. 불연속방식으로는 “연결 할당”과 “인덱스 할당”이 있음연결 할당연결리스트로 구성하여 하나의 노드의 포인터를 이용해 다른 노드로 이동하여 모든 노드를 순환할 수 있음. 연결 할당은 파일에 속한 데이터를 연결리스트로 관리. 파일테이블에는 시작 블록에 대한 정보만 저장하고 나머지는 연결리스트를 이용해 다른 블록에 접근하는 방식인덱스 할당인덱스 할당방식은 테이블의 블록 포인터가 데이터 블록에 직접 연결하는 것이 아니라 데이터들의 인덱스를 가지고 있는 인덱스 블록을 연결함. 인덱스 할당은 데이터가 많아서 테이블이 꽉 찬 경우 인덱스 블록을 더 만들어 연결하기에 테이블을 확장할 수 있음. 덕분에 파일 크기가 작다면 데이터를 바로 참조하는 블록 포인터를 이용하고 파일의 크기가 크다면 간접 포인터를 이용해 많은 데이터에 접근할 수 있음. 만약 더 큰 데이터가 필요하다면 이중 간접 포인터, 삼중 간접 포인터를 이용할 수 있음. 이 방식은 i-node라는 이름으로 유닉스와 리눅스에서 많이 사용됨알고리즘&자료구조섹션 3. 알고리즘삽입정렬(Insertion Sort)정렬되지 않은 영역에서 데이터를 하나씩 꺼내어 정렬된 영역 내 적절한 위치에 삽입하여 정렬하는 알고리즘장점: 이해와 구현이 간단함단점: 성능이 좋지 않음. 큰 데이터일수록 매우 비효율적임시간복잡도O(n²)병합정렬(Merge Sort)분할해서 정복 하는 방식. 리스트를 절반으로 나누고 정렬한 후 병합하는식으로 진행됨장점: 성능이 좋음. 큰 데이터에도 효율적임단점: 이해와 구현이 어려움. 메모리 공간을 차지함시간복잡도O(n log n)퀵정렬(Quick Sort)분할해서 정복하는 방식. 피벗을 기준으로 재귀를 활용함장점: 병합정렬보다 평균적으로 속도도 빠르고, 메모리 공간도 덜 차지함단점: 피벗 선택에 따라 성능이 변하기에 불안정할 수 있음시간복잡도평균 - O(n log n), 최악 - O(n²)동적 프로그래밍 - 메모이제이션재귀를 사용한 하향식 접근 방법. 이전에 계산한 결과를 저장하여 재사용하는 기법으로 중복 계산을 피해 성능 향상장점: 중복 계산 방지, 직관적인 구현, 필요한 결과만 저장단점: 재귀로인한 스택 오버플로우동적 프로그래밍 - 타뷸레이션하위 문제부터 해결하는 상향식 접근 방법. 반복문을 사용함장점: 메모이제이션에 비해 메모리 사용이 적음단점: 모든 하위 문제를 계산해야함, 덜직관적인 구현, 때에 따라 불필요한 계산이 있을 수 있음회고3주 동안 나름 열심히하여 뿌듯하다.

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

운영체제메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.레지스터: 가장 빠른 기억장소로 CPU 내에 존재하고 있음. 컴퓨터의 전원이 꺼지면 데이터가 사라지기에 휘발성 메모리로 불. 32bit, 64bit는 레지스트리의 크기를 말함. CPU는 계산을 할 때 메인메모리에 있는 값을 레지스터로 가져와 계산함. 계산 결과는 다시 메인메모리에 저장캐시: 휘발성 메모리. 미리 가져온 데이터들을 저장. 캐시는 성능의 이유로 여러 개 두고 사용함. CPU가 값을 요청해 레지스터로 값을 옮겨야 한다면 단계에 따라 가장 속도가 빠른 L1 → L2 → 메인 메모리 순으로 참조함. 즉 빠른 캐시에 있는 값을 먼저 찾으려고 함메인 메모리(RAM): 실제 운영체제와 다른 프로세스들이 올라가는 공간. 전원이 공급되지 않으면 데이터가 지워지기에 휘발성임. HDD, SDD 보다 속도는 빠르지만 가격이 비싸기에 데이터를 저장하기보다는 실행중인 프로그램만 올림보조저장장치(HDD, SSD): 다른 메모리에 비해 비교적 가격이 저렴하고, 전원이 공급되지 않아도 데이터가 지워지지 않는 비휘발성 메모리2. 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요? 경계 레지스터입니다.경계 레지스터란 CPU내에 존재하는 레지스터로 메모리 관리자가 사용자 프로세스가 경계 레지스터의 값을 벗어났는지 검사하고 만약 벗어났다면 그 프로세스를 종료 시키는 역할을 수행. 즉, 사용자 프로그램의 메모리 접근 범위를 제한함3.메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?가변 분할 방식장점내부 단편화가 없음프로세스 크기에 맞게 분할 가능가변적이기에 메모리 할당이 유연함단점외부 단편화 발생오버헤드가 큼고정 분할 방식장점구현이 간단함오버헤드가 적음단점내부 단편화가 발생메모리 할당이 유연하지 못함CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요? 스레싱 입니다.HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요? 이유를 함께 적어주세요.운영체제의 저장: 일단 사용자가 직접 파일을 관리하기엔 여러 위험요소들이 있기에 이를 운영체제에게 전적으로 위탁해야합니다. 따라서 운영체제 파일들을 저장하기 위해 필요합니다.데이터 저장: 휘발성 메모리인 RAM에 비해, HDD와 SSD는 비휘발성이기에 데이터를 저장하기에 용이합니다. 따라서 사용자가 설치한 프로그램, 시스템 설정, 사용자의 데이터 등등의 데이터를 보관하기에 적합합니다.6. 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요? 파일을 삭제한다고 실제 그 데이터들을 삭제하는 것이 아니기 때문입니다. 특정 파일을 삭제한다고 하면 모든 정보를 지우는 것이 아니라 해당 파일의 헤더를 삭제하여 free block list에 추가합니다. 즉, 해당 공간을 비워놓은채로 표시하고 실제 데이터는 삭제가 되지 않은 상태인 것입니다.자료구조와 알고리즘지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.버블정렬장점: 이해와 구현이 간단함단점: 성능이 좋지 않음. 큰 데이터일수록 매우 비효율적임시간복잡도: O(n²)선택정렬장점: 이해와 구현이 간단함단점: 성능이 좋지 않음시간복잡도: O(n²)삽입정렬장점: 이해와 구현이 간단함단점: 성능이 좋지 않음. 큰 데이터일수록 매우 비효율적임시간복잡도: O(n²)병합정렬장점: 성능이 좋음. 큰 데이터에도 효율적임단점: 이해와 구현이 어려움. 메모리 공간을 차지함시간복잡도: O(n log n)퀵정렬장점: 병합정렬보다 평균적으로 속도도 빠르고, 메모리 공간도 덜 차지함단점: 피벗 선택에 따라 성능이 변하기에 불안정할 수 있음시간복잡도: 평균 - O(n log n), 최악 - O(n²)2. 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.메모이제이션계산 결과를 저장해 재사용하는 하향식 접근 방법장점: 재귀를 활용해 어려운 문제를 간단히 해결 가능함, 중복 계산을 하지 않아 속도가 빠름단점: 재귀 호출로 메모리 사용량 증가타뷸레이션작은 문제부터 해결하는 상향식 접근 방법장점: 메모이제이션에 비해 메모리 절약, 속도 또한 빠름단점: 하향식 접근 방법에 비해 덜 직관적임, 계산에 필요한 모든 값들을 전부 계산해야함메모리가 부족한 시스템일 경우 스택 오버플로우가 나지 않는게 1순위 이기에 재귀호출로 인해 메모리 사용량이 증가하는 메모이제이션보단 타뷸레이션이 유리할 수 있으나 특정 상황에선 메모이제이션이 더 유리할수도 있습니다. 하향식 접근 방법인 타뷸레이션의 경우 모든 하위 문제를 계산하여 결과값을 들고 있기에 모든 하위 문제의 결과값이 필요하다면 타뷸레이션이 나은 접근방법이지만, 특정 결과값만 필요한 경우 메모이제이션이 더 나은 접근방법입니다. 따라서 주어진 메모리 내에서 재귀로 쉽게 구현이 가능하다면 메모이제이션을 선택할 것이고,메모이제이션을 선택하여 스택 오버플로우가 난다면 반복문을 사용하는 타뷸레이션을 선택할 것입니다.

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

운영체제FIFO 스케줄링의 장단점이 뭔가요?장점관리가 용이하고, 오버헤드가 적습니다.프로세스가 순서대로 처리되기에 예측 가능성이 높습니다.단점버스트 타임이 긴 프로세스가 처리중이면 대기중인 프로세스들이 오래 대기해야합니다.그에 따라 평균 대기 시간이 길어질 수 있습니다.SJF를 사용하기 여러운 이유가 뭔가요? 이론적으로 본다면 버스트 타임이 짧은 프로세스를 먼저 처리해 전체적인 대기 시간이 감소하고, 평균 대기 시간을 줄이기 용이합니다.실질적으로는 어떤 프로세스가 얼마나 실행될지 예측하기가 힘들고, 버스트 타임이 짧은 프로세스들이 많거나 중간중간 계속 발생된다면 버스트 타임이 긴 프로세스들은 영원히 실행되지 않을 수도 있습니다.RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요? 타임 슬라이스를 작게 설정하는 경우 사용자의 입장에서는 동시에 실행되는 느낌을 받을 수 있지만 컨텍스트 스위칭을 처리하는 양이 훨씬 많아져서 오버헤드가 너무 커지게 됩니다.운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요? 할당된 타임 슬라이스를 전부 사용하거나, 오버해서 사용하다 스케줄러에 의해 반납하는 상황, I/O 요청이 적은 경우 CPU Bound Process일 확률이 높습니다.반면, CPU 사용시간이 짧아 스스로 반납하거나, 타임 슬라이스를 다 쓰기 전에 I/O 요청이 생기는 경우 I/O Bound Process일 확률이 높습니다.공유자원이란 무엇인가요? 프로세스간 통신을 할 때 공동으로 이용하는 변수나 파일 등입니다.동시에 사용하면 문제가 발생할 수 있기에 상호배제가 필요한 자원입니다.교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요? 교착상태의 필요조건 4가지상호배제 - 자원은 한 번에 한 프로세스에서만 사용 가능합니다. 다른 프로세스가 사용중인 자원은 사용 불가능합니다.비선점 - 이미 사용중인 자원은 다른 프로세스가 빼앗을 수 없습니다.점유와 대기 - 프로세스가 하나의 자원을 보유한 상태에서 다른 자원을 추가로 요청해야 합니다.원형 대기 - 점유와 대기를 하는 프로세스들의 관계가 서로 원형을 이루고 있습니다.자료구조와 알고리즘재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요? 함수가 계속해서 호출되기에, 콜 스택에 호출된 함수들이 계속 쌓여 메모리 한계에 도달합니다.메모리 한계에 도달한 이후 프로그램은 강제 종료됩니다.0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n){ let sum = 0; for (let i = 0; i 다음 코드는 매개변수로 주어진 파일 경로(.는 현재 디렉토리)에 있는 하위 모든 파일과 디렉토리를 출력하는 코드입니다. 다음 코드를 재귀 함수를 이용하는 코드로 변경해보세요const fs = require('fs'); // 파일을 이용하는 모듈 const path = require('path'); // 폴더와 파일의 경로를 지정해주는 모듈 function traverseDirectory1(directory) { const files = fs.readdirSync(directory); // 인자로 주어진 경로의 디렉토리에 있는 파일or디렉토리들 for (const file of files) { // 현재 디렉토리의 모든 파일or디렉토리 순회 const filePath = path.join(directory, file); //directory와 file을 하나의 경로로 합쳐줌 const fileStatus = fs.statSync(filePath); // 파일정보 얻기 if (fileStatus.isDirectory()) { // 해당 파일이 디렉토리라면 console.log('디렉토리:', filePath); traverseDirectory1(filePath); } else { // 해당 파일이 파일이라면 console.log('파일:', filePath); } } } traverseDirectory1('.'); // 현재 경로의 모든 하위 경로의 파일, 디렉토리 출력

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

운영체제섹션 4. 프로세스 동기화4-1. 프로세스간 통신프로세스는 독립적으로 실행되기도 하지만, 다른 프로세스와 데이터를 주고받으며 통신을 하는 경우도 있음프로세스 통신의 종류파일과 파이프를 이용하는 방법(프로세스 간 통신 방법)파일: 통신하려는 프로세스들이 하나의 파일을 이용해 읽고 쓰는 방법파이프: 운영체제가 생성한 파이프를 이용해 데이터를 읽고 쓰는 방법쓰레드를 이용하는 방법(프로세스 내 쓰레드 간 통신 방법)쓰레드는 코드, 데이터, 힙 영역을 공유하고 스택만 각자 지니고 있음데이터 영역의 전역변수나 힙을 이용하면 통신이 가능함네트워크를 이용하는 방법운영체제가 제공하는 소켓 통신RPC(원격 프로시저 호출)를 이용한 통신: 다른 컴퓨터에 있는 함수를 호출하는 방법4-2. 공유자원과 임계구역프로세스 간 통신을 할 때 공동으로 이용하는 변수나 파일들을 공유자원 이라고 일컬음공유자원은 여러 프로세스가 공유하고 있기 때문에 각 프로세스의 접근 순서에 따라 결과가 달라질 수 있음. 또한 컨텍스트 스위칭으로 시분할 처리를 하기 때문에 어떤 프로세스가 먼저 실행되고 어떤 프로세스가 나중에 실행되는지 예측하기가 힘듦따라서 연산결과를 예측하기가 힘들고, 여기서 발생한 문제를 동기화 문제라고 부름따라서 여러 프로세스가 동시에 사용하면 안되는 영역이 임계 구역(Critical Section)임공유자원을 서로 사용하기 위해 경쟁하는 것은 경쟁조건(Race Condition)임계구역 문제를 해결하기 위해서는 상호 배제(Mutual Exclusion) 메커니즘이 필요함상호 배제의 요구사항임계구역엔 동시에 하나의 프로세스만 접근한다.여러 요청에도 하나의 프로세스의 접근만 허용한다.임계구역에 들어간 프로세스는 빠르게 나와야한다.4-3. 세마포어상호배제 메커니즘 중 하나. 여러 프로세스나 스레드의 공유 자원 접근을 제어하는 동기화 도구로써 정수형 변수로 이루어짐.4-4. 모니터세마포어의 단점을 해결한 상호배제 메커니즘운영체제가 처리하는 것이 아닌 프로그래밍 언어 차원에서 지원하는 방법모니터의 구현만 완벽하다면 프로그래머는 세마포어처럼 wait(), signal() 함수를 임계영역에 감싸지 않아도 돼서 편리하고 안전하게 코드를 작성할 수 있음섹션 5. 데드락5-1. 데드락이란?(feat. 식사하는 철학자)교착상태(데드락) 이란 여러 프로세스가 서로 다른 작업이 끝나기를 기다렸다가 아무도 작업을 진행하지 못하는 상태공유자원 때문에 교착상태가 발생함교착상태의 필요조건 4가지상호배제 - 어떤 프로세스가 한 리소스를 점유했다면, 그 리소스는 다른 프로세스에게 공유가 되면 안됨비선점 - 프로세스 A가 리소스를 점유하고 있는데, 프로세스 B가 리소스를 뺏을 수 없어야함점유와 대기 - 어떤 프로세스가 리소스A를 가지고 있는 상태에서 리소스 B를 원하는 상태여야 함원형 대기 - 점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있음이중에 한가지라도 충족하지 않는다면 교착상태는 발생하지 않음.5-2. 데드락 해결(feat. 은행원 알고리즘)교착상태 회피(Deadlock avoidance)란 프로세스들에게 자원을 할당할 때 어느정도 자원을 할당해야 교착상태가 발생하는지 파악해서 교착상태가 발생하지 않는 수준의 자원을 할당하는 것 교착상태 회피는 전체 자원의 수와 할당된 자원의 수를 기준으로 안정상태(Safe state), 불안정 상태(Unsafe state)로 나눔. 불안정상태에 있더라도 무작정 교착상태에 빠지는것이 아니라, 교착상태에 빠질 확률이 높아짐운영체제는 프로세스들에게 자원을 할당하기 전에 자기가 가지고 있는 전체 자원의 수를 알고 있어야함. 이가 시스템의 총 자원.그리고 프로세스들은 각자 자기가 필요한 자원의 최대숫자를 운영체제에게 알려줘야 함.이가 최대 요구 자원.불안정 상태에 있더라도 모든 프로세스가 최대 자원을 요청하지 않는다면 교착상태에 빠지지 않을 수도 있지만 불안정상태에 빠지지 않도록 유지하는게 좋음은행원 알고리즘은 교착상태를 피하는 좋은 방법이지만 비용이 비싸고, 비효율적임그래서 교착상태는 허용하지만, 발생했을때 이를 해결하는 방식을 연구함교착상태 검출 방식가벼운 교착 상태 검출타이머를 이용하는 방식. 프로세스가 일정시간 동안 작업을 진행하지 않는다면 교착상태가 발생했다고 간주하고 교착상태를 해결함해결법 - 일정 시점마다 체크포인트를 만들어 작업을 저장하고 타임아웃으로 교착상태가 발생했다면 마지막으로 저장한 체크포인트로 롤백함무거운 교착 상태 검출자원 할당 그래프를 이용하는 방식. 현재 운영체제에서 프로세스가 어떤 자원을 사용하는지 지켜보고 교착상태가 발생하면 해결함해결법 - 교착상태가 검출되면 교착상태를 일으킨 프로세스를 강제종료 시킴. 그리고, 다시 실행시킬 때 체크포인트로 롤백 시킴. 이 방식은 운영체제가 지속적으로 “자원 할당 그래프”를 유지하고 검사해야 하기에 오버헤드가 발생함. 하지만 가벼운 교착 상태 검출에서 발생할 수 있는 억울하게 종료되는 프로세스가 발생되지 않음섹션 6. 쉬어가기6-1. 컴파일과 프로세스컴파일 언어: 컴파일 과정에서 개발자가 문법 오류를 일으켰는지 검사를 하고, CPU에서 처리 가능한 기계어로 실행파일을 만들어 놓기에 속도가 빠름인터프리터 언어: 인터프리터 언어는 개발자가 작성한 코드를 미리 기계어로 만들지 않고, 실행 시 코드를 한 줄씩 해석해 실행하는 언어. 미리 검사하지 않기 때문에 실행할 때 오류가 날 수도 있고, 속도도 컴파일 언어와 비교하면 느림컴파일 과정전처리 단계: 전처리 구문 처리컴파일러 단계: 기계어에 가까운 어셈블리어로 변환어셈블러 단계: 오브젝트 파일로 변환. 0과 1로 된 기계어로 구성링커 단계: 모든 오브젝트 파일을 하나의 코드영역과 데이터영역으로 묶음. 실제로 실행될 주소를 매핑시킴. 링커까지 거친 후 .exe 실행 파일 생성섹션 7. 메모리7-1. 메모리 종류레지스터: 가장 빠른 기억장소로 CPU 내에 존재하고 있음. 컴퓨터의 전원이 꺼지면 데이터가 사라지기에 휘발성 메모리로 불림. 32bit, 64bit는 레지스트리의 크기를 말함. CPU는 계산을 할 때 메인메모리에 있는 값을 레지스터로 가져와 계산함. 계산 결과는 다시 메인메모리에 저장캐시: 휘발성 메모리. 미리 가져온 데이터들을 저장. 캐시는 성능의 이유로 여러 개 두고 사용함. CPU가 값을 요청해 레지스터로 값을 옮겨야 한다면 단계에 따라 가장 속도가 빠른 L1 → L2 → 메인 메모리 순으로 참조함. 즉 빠른 캐시에 있는 값을 먼저 찾으려고 함메인 메모리(RAM): 실제 운영체제와 다른 프로세스들이 올라가는 공간. 전원이 공급되지 않으면 데이터가 지워지기에 휘발성임. HDD, SDD 보다 속도는 빠르지만 가격이 비싸기에 데이터를 저장하기보다는 실행중인 프로그램만 올림보조저장장치(HDD, SSD): 다른 메모리에 비해 비교적 가격이 저렴하고, 전원이 공급되지 않아도 데이터가 지워지지 않는 비휘발성 메모리.7-2. 메모리와 주소운영체제는 메모리를 관리하기 위해서 1바이트 크기로 구역을 나누고 숫자를 매김.이 숫자는 곧 “주소”. 각 CPU의 bit는 레지스터 크기, ALU, 버스의 크기가 동일함.물리주소와 논리주소0x0번지부터 시작하는 주소공간 = 물리 주소 공간사용자 관점에서 바라본 주소공간 = 논리 주소 공간사용자는 물리 주소를 몰라도 논리 주소로 물리 주소에 접근할 수 있음.운영체제는 특별하기에 메모리에 따로 공간을 마련해둠.그래서 하드웨어적으로 운영체제 공간과 사용자 공간을 나누는 경계 레지스터를 만듦.경계 레지스터는 CPU내에 존재하는 레지스터로 메모리 관리자가 사용자 프로세스가 경계 레지스터의 값을 벗어났는지 검사하고 만약 벗어났다면 그 프로세스를 종료 시킴.절대주소와 상대주소개발자는 프로그램을 만들 때 프로그램이 실행될 주소를 신경쓰지 않고 개발함. 이는 컴파일러가 컴파일을 할 때 메모리 0번지에서 실행한다고 “가정”하기 때문.7-3. 메모리 할당방식메모리 오버레이란? 유니프로그래밍 환경에서 메모리보다 더 큰 프로그램을 실행시키기 위해 큰 프로그램을 메모리에 올릴 수 있도록 잘라 당장 실행시켜야 할 부분만 메모리에 올리고, 나머지는 하드디스크에 저장하는 기법.현대의 멀티프로그래밍 환경에서 메모리를 나누는 방식가변 분할 방식: 가변 분할 방식이란 프로세스의 크기에 따라 메모리를 나누는 방식고정 분할 방식: 프로세스 크기와 상관없이 메모리를 할당가변 분할 방식한 프로세스가 메모리에 연속된 공간에 할당되기에 연속 메모리 할당이라고 함가변 분할 방식은 프로세스의 크기에 딱 맞게 할당되기에 낭비되는 공간인 “내부 단편화”가 없음단점으로는 “외부 단편화”가 발생함고정 분할 방식프로세스가 쪼개져 할당되어 여러곳에 할당됨고정 분할 방식의 장점은 구현이 간단하고 오버헤드가 적음단점으로는 작은 프로세스도 큰 영역에 할당돼서 공간이 낭비되는 “내부 단편화”가 발생버디 시스템가변 분할 방식과 고정 분할 방식을 혼합해 단점을 최소화함버디 시스템은 2의 승수로 메모리를 분할해 메모리를 할당하는 방식프로세스가 종료후 해제되도, 근접한 메모리 공간을 합치기 쉬움알고리즘&자료구조섹션 3. 알고리즘재귀(Recursion)함수가 자기 자신을 호출하는 프로그래밍 방식큰 문제를 동일한 형태의 작은 문제로 나누어 해결재귀 함수를 사용하기 위해서는 기저 조건(탈출 조건)이 필요함팩토리얼(Factorial)n!로 표시1부터 n까지의 모든 양의 정수를 곱한 값하향식 계산큰 문제 → 작은 문제로 분할가장 작은 문제(기저 조건)까지 내려감결과를 다시 위로 올라가며 조합버블정렬(Bubble Sort)앞에 있는 숫자와 옆에 숫자를 비교해 자리를 바꾸는 알고리즘장점: 이해와 구현이 간단함단점: 성능이 좋지 않음시간복잡도O(n²)선택정렬(Selection Sort)배열에서 최솟값을 찾아 맨 앞으로 이동하는 정렬. 정렬되지 않은 부분에서 가장 작은 요소를 선택하여 정렬된 부분의 끝에 추가함장점: 이해와 구현이 간단함단점: 성능이 좋지 않음시간복잡도O(n²)회고복습이 조금 부족했던거 같다. 발자국을 정리하면서 그나마 회고하는 시간을 가져서 좋았다.

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

1주차 미션운영체제 while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }1. 위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?폴링 방식을 사용하게 되면 플레이어가 스킬을 사용하기 전까지 매번 체크 후 1초를 멈추기를 반복하게 됩니다.플레이어가 언제 스킬을 사용할지 모르는 시점에서 오버헤드가 크기에, 인터럽트(Interrupt) 방식이 적절해 보입니다.인터럽트 방식을 사용하게 되면 CPU 사용량을 과하게 사용하지 않고, 플레이어가 스킬을 사용한 시점에 대응이 가능합니다.2. 프로그램과 프로세스가 어떻게 다른가요?프로그램저장장치에 존재하는 파일(정적)메모리에 로드되지 않음 프로세스 프로그램이 실행된 상태(동적)프로그램이 메모리에 할당되어 실행중인 상태 3. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티 프로그래밍하나의 CPU로 여러 프로세스를 번갈아가며 실행CPU 사용 극대화속도가 빨라 동시에 실행되는 것 처럼 보이나, 시분할 방식으로 번갈아가면서 실행됨 멀티 프로세싱 여러 개의 CPU로 여러 프로세스를 동시에 실행여러 CPU를 이용해 프로세스를 병렬적으로 실행하여 동시에 처리 가능각 프로세스마다 독립적이기에 다른 프로세스에 영향을 주지 않음4. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?PCB(Process Control Block)을 사용합니다.프로세스의 모든 정보를 담고 있으며,주요 포함 정보로는프로세스 ID (PID)프로세스 상태프로그램 카운터CPU 레지스터CPU 스케줄링 정보메모리 관리 정보입출력 상태 정보가 있습니다.5. 컨텍스트 스위칭이란 뭔가요? 현재 실행 중인 프로세스의 상태를 저장하고, 다음 실행할 프로세스의 상태를 복원하는 작업입니다. 자료구조&알고리즘여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.해시테이블을 사용하겠습니다. 학번을 Key 값으로 사용한다면 O(1)의 시간 복잡도로 읽기, 삽입, 수정, 삭제가 가능합니다.여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.큐(Queue)를 사용하겠습니다. 주문이 들어온 순대로 순차적으로 처리돼야 한다면 FIFO(First In First Out)인 큐가 적합합니다.우리가 구현한 스택은 0번 인덱스, 즉 입구쪽으로 데이터가 삽입되고 나오는 구조입니다. 반대로 마지막 인덱스, 즉 출구쪽으로 데이터가 삽입되고 나오는 구조로 코드를 변경해주세요.스택(Stack)의 자료구조를 활용해 FILO(First In Last Out)을 활용해 데이터 삽입시 가장 마지막에, 데이터를 꺼낼 때도 가장 마지막에 있는 데이터를 꺼낼 수 있도록 변경 했습니다.class StackReverse { constructor() { this.list = new LinkedList(); } push(data) { this.list.insertLast(data); } pop() { if (this.isEmpty()) { return null; } return this.list.deleteLast().data; } peek() { if (this.isEmpty()) { return null; } return this.list.getNodeAt(this.list.count - 1).data; } isEmpty() { return this.list.count === 0; } printStack() { this.list.printAll(); } } const stack = new StackReverse(); stack.push(1); stack.push(2); stack.push(3); stack.printStack(); // [1, 2, 3] console.log(stack.pop()); // 3 console.log(stack.pop()); // 2 console.log(stack.pop()); // 1 console.log(stack.pop()); // null해시테이블의 성능은 해시 함수에 따라 달라집니다. 수업 시간에 등번호를 이용해 간단한 해시 함수를 만들어봤습니다. 이번엔 등번호가 아닌 이름을 이용해 데이터를 골고루 분산시키는 코드로 수정해주세요. 힌트: charCodeAt() 함수를 이용 예시: name1 = "이운재"; name1.charCodeAt(0); // 51060 이운재의 0번 인덱스 ‘이’의 유니코드 출력newHashFunction(name) { let hash = 0; for (let i = 0; i

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

운영체제프로그램과 프로세스프로그램: 저장장치에 저장된 정적인 코드프로세스: 실행 중인 프로그램 (메모리에 로드됨)멀티프로그래밍과 멀티프로세싱멀티프로그래밍: 여러 프로그램을 메모리에 동시에 올려두고 실행멀티프로세싱: 여러 프로세서(CPU)가 여러 프로세스 동시 처리프로세스 상태생성(New): 프로세스 생성됨준비(Ready): CPU 할당 대기실행(Running): CPU 할당받아 실행 중대기(Waiting): I/O 등 이벤트 대기 종료(Terminated): 실행 완료컨텍스트 스위칭실행 중인 프로세스를 바꾸는 작업PCB 정보 저장/복원 필요오버헤드 발생쓰레드프로세스 내의 실행 단위특징:같은 프로세스의 자원 공유빠른 생성과 컨텍스트 스위칭병렬 처리 가능PCB (Process Control Block)프로세스 관리를 위한 정보 저장 블록포함 정보:프로세스 ID프로세스 상태프로그램 카운터레지스터 정보메모리 정보CPU 스케줄링목표 리소스 사용률: CPU 사용률을 높이는 것을 목표로 할 수도 있고, I/O 디바이스의 사용률을 높이는 것을 목표로 할 수도 있음오버헤드 최소화공평성: 모든 프로세스에게 공평하게 CPU 할당. 특정 프로세스에게만 CPU가 계속 할당되지 않게처리량: 같은 시간내에 더 많은 처리를 할 수 있는 방법을 목표로 함대기시간: 작업을 요청하고 실제 작업이 수행되기까지 대기하는 시간이 짧은 것을 목표로 함응답시간: 사용자의 요청에 얼마나 빨리 반응하는지 서로 상반되는 목적을 지니기 때문에 목적에 따라 적절히 목표를 변경해야함주요 알고리즘FIFO(First In First Out)먼저 들어온 프로세스가 완전히 끝나야 다음 프로세스 실행SJF(Shortest Job First)어떤 프로세스가 얼마나 실행될지 예측하기가 힘듦Burst Time이 긴 프로세스는 아주 오랫동안 실행되지 않을 수도 있음RR(Round Robin)FIFO의 경우 시분할 처리 시스템에서 사용하기 힘들고, SJF 알고리즘은 프로세스의 종료시간을 예측하기가 힘듦.FIFO 알고리즘에서 단점을 해결하기로 함프로세스에 정해진 시간만큼만 할당할 수 있게 함(타임 슬라이스, 타임 퀀텀)타임 슬라이스를 작게 설정하는 경우 동시에 실행되는 느낌을 받을 수 있지만 컨텍스트 스위칭을 처리하는 양이 훨씬 커져 비효율적임(오버헤드가 너무 커짐)MLFQ(Multi Level Feedback Queue)RR 알고리즘의 업그레이드 된 버전CPU 사용률과 I/O 사용률 전체를 생각하면 타임 슬라이스가 더 작은 값이 좋음MLFQ는 기본적으로 CPU 사용률과 I/O 사용률이 좋게 나오는 작은 크기의 타임 슬라이스를 선택함CPU Bound Process에는 타임 슬라이스를 크게 주고,I/O Bound Process에는 타임 슬라이스를 작게 줌.알고리즘&자료구조시간복잡도알고리즘의 성능을 평가하는 척도입력 크기(n)에 따라 알고리즘이 실행되는 시간을 나타냅니다.빅오(Big-O) 표기법을 주로 사용합니다.배열 (Array)연속된 메모리 공간에 데이터 저장인덱스로 빠른 접근 가능 (O(1))크기가 고정적연결리스트 (Linked List)노드가 다음 노드를 가리키는 구조삽입/삭제가 용이 (O(1))접근은 처음부터 순차적으로 (O(n))스택 (Stack)LIFO (Last In First Out) 큐 (Queue)FIFO (First In First Out) 덱 (Deque)양쪽 끝에서 삽입/삭제 가능스택과 큐의 기능 모두 수행 가능해시테이블 (Hash Table)키-값 쌍으로 데이터 저장평균적으로 빠른 검색/삽입/삭제 (O(1))셋 (Set)중복을 허용하지 않는 컬렉션빠른 검색과 중복 제거합집합, 교집합 등 집합 연산 가능회고과제도 생각보다 시간이 걸려서 다음엔 좀 더 넉넉잡아 시작해야할거 같다.노션에 따로 정리해놓은 것도 중요한 내용들만 간략하게 정리해놓았다 보니 누락되는 것들이 있어 과제와 회고때 더 디테일하게 작성하지 못한 점이 아쉽다.