인프런 워밍업 클럽 스터디 2기 CS 3주차 과제

운영체제메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.레지스터휘발성 메모리컴퓨터의 bit는 레지스터의 크기를 말한다메인메모리의 값을 가져와서 레지스터에서 연산 후 다시 메인메모리로 저장캐시레지스터와 메인메모리 속도 차이 때문에 미리 데이터를 가져오는 곳여러개이다메인메모리(RAM)실제 운영체제와 다른 프로세스들이 올라오는 공간휘발성 메모리가격이 비싸다보조저장장치(HDD, SSD)파일 저장 공간비휘발성 메모리사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요? 경계 레지스터주소 처음에는 운영체제를 두는 공간이 있는데 만약 사용자가 악의적은 프로세스를 넣어서 침범한다면 위험하다이런 이유로 물리적으로 분리하는 경계 레지스터를 만들었다.경계 레지스터는 프로세스가 할당받지 않은 주소를 침범했다면 종료시킨다.메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?가변 분할 방식메모리에 연속해서 프로세스를 집어넣는 것연속 메모리 할당장점낭비되는 공간 없음단점외부 단편화만약 프로세스가 끝나면 빈 공간이 생긴다빈 공간이 여러개일 때 합치면 프로세스에게 줄 크기더라도 연속돼있지 않으면 사용이 불가능하다합칠 수는 있지만 다른 프로세스들을 정지키시고 해야 하기 때문에 힘들다고정 분할 방식프로세스의 크기에 상관없이 메모리를 정해진 크기로 나눈다.프로세스도 그 크기에 맞춰서 넣는다비연속 메모리 할당장점구현이 간단하다오버헤드가 적다단점공간이 남는 상황이 있다 CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?스레싱HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요?컴퓨터가 부팅되려면 HDD나 SSD와 같은 저장장치가 필수적입니다.허나 둘 중에 하나만 있어도 작동은 가능합니다.파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?삭제된 파일의 데이터가 실제로는 물리적 디스크에 그대로 남아 있기 때문입니다.자료구조와 알고리즘지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.- 버블정렬가장 쉬운 정렬이지만 성능이 좋지 않다바로 옆의 숫자와 비교해서 정렬하는 방식걸리는 시간은 O(n^2)이다.장점이해와 구현이 간단하다단점O(n^2)로 성능이 그리 좋지 않다- 선택 정렬이해와 구현이 간단하지만 역시 성능이 아쉽다배열의 모드 값을 비교 후 가장 작은 값을 첫번째 원소로 가져온다그 이후 정렬된 영역 뒤부터 다시 가장 작은 원소를 첫번째로 가져온다걸리는 시간 또한 O(n^2)이다.버블정렬과 같이 시간이 오래 걸린다.장점이해와 구현이 간단하다단점O(n^2)로 성능이 그리 좋지 않다- 삽입정렬삽입 정렬은 두 영역으로 나눠서 진행된다.시간복잡도 : O(n^2)장점 : 구현하기 쉽다단점 : 시간이 오래 걸린다- 병합정렬정렬해야 할 것을 아주 잘게 나눈 다음 정렬하고 병합하고를 반복하는 정렬방법이다.시간복잡도 : O(nlogn)장점 : 성능이 훨씬 좋다단점 : 이해와 구현이 어려움- 퀵 정렬배열의 값 중 한가지를 피벗으로 설정(설정방법은 여러가지)맨 왼쪽, 맨 오른쪽, 양쪽 이동값 만들기왼쪽 이동값이 피벗보다 크면 정지 -> 오른쪽 이동값이 피벗보다 작으면 정지 -> 둘다 정지하면 교환 -> 둘이 만나면 오른쪽 이동값 위치에 피벗값 변경-> 이후 피벗값 기준 좌우 따로 정렬시간복잡도 : O(nlogn), O(n^2)장점 : 성능이 훨씬 좋다단점 : 이해와 구현이 어려움메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.타뷸레이션메모리제이션은 호출 스택이 깊어질 경우 스택 오버플로우가 발생할 위험이 있다.타뷸레이션은 반복문을 사용해 순차적으로 계산하기 때문에 오버헤드가 적고 더 빠르게 동작한다.타뷸레이션은 메모리 사용량이 명확히 정해져 있고, 일반적으로 문제 크기에 따라 고정된 크기의 테이블을 사용하기 때문이다.

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

운영체제섹션8- 가상메모리 개요 컴퓨터마다 메모리의 크기는 다르다.만약 운영체제 혹은 프로세스가 4GB메모리를 기준으로 만들었다면 그 이하의 메모리를 가진 컴퓨터에서는 실행되지 않을 것이다.위와 같은 문제를 가상메모리는 완벽히 해결하였다.프로세스(프로그램)를 만드는 개발자는 물리적인 메모리의 크기를 생각하지 않고 개발한다.그 이유는 프로세스 관리자가 서로를 연결시키기 때문에 직접적인 연결을 생각할 필요가 없는 것이다.이론적으로 가상메모리는 크기가 무한대이지만 거의 2^(CPU의 비트수)로 생각한다.만약 4GB 메모리가 4GB짜리 5개의 프로세스를 실행시킨다면 일반적으론 부족할것이다.하지만 물리메모리에 있는 스왑영역을 통해 그때마다 필요한 프로세스만 가져와서 실행시키고 다시 넣는다면 4GB메모리로도 모두 실행시킬 수 있다.메모리 관리자는 물리영역+스왑영역을 합쳐서 가상주소를 물리주소로 바꾼다. 이 과정을 DAT(동적주소변환)이라고 한다.메모리를 사용하기 위해 가변 분할 방식(세그멘테이션)과 고정 분할 방식(페이징)이 있다.각각의 단점과 장점이 있기 때문에 둘이 합친 혼용기법을 사용한다.매핑 테이블로 관리되면 프로세스와 메모리+스왑영역이 1:1 느낌으로 관리된다.3주차에 시작된 질문항1. 세그멘테이션과 페이징이 뭐지2.뭔가 그림으로 보면 어느정도 이해가 되기는 하는데 글로 혼용기법을 서술을 못하겠다...- 세그멘테이션(배치정책)세그멘테이션에서 프로그램은 함수나 모듈등으로 세그먼트를 구성한다.사용자 관점에서 보면 코드 세그먼트, 데이터가 들어있는 데이터 세그먼트 등으로 있다.사용자,프로세스,CPU관점에서는 모두 논리주소를 사용한다. MMU가 논리주소를 물리주소로 바꾸는 것이다.MMU는 세그멘테이션 테이블을 통해 알맞는 물리 메모리에 할당한다.MMU는 CPU에게서 받은 논리주소(세그멘테이션 테이블)가 Bound address보다 작다면 둘이 더해 물리주소를 구하고 아니라면 메모리 침범으로 생각해서 에러를 낸다.세그멘테이션은 여러 영역을 모듈로 처리할 수 있다는 장점이 있고 공유와 메모리 접근보호가 편리하다.단점으로 외부 단편화가 있다.1. 진지하게 외부 단편화가 기억이 안난다.. 다시 보고 와야겠다2.어째서 메모리 침범인지 까먹었다..- 페이징(배치정책)메모리를 할당할 때 메모리를 일정한 페이지로 나눈다.일정하게 나누기 때문에 외부단편화가 일어나지 않는다.논리주소공간 : 사용자와 프로세스가 바라보는 주소공간물리주소공간 : 실제 메모리에서 사용되는 공간페이징에서 논리주소공간을 일정하게 나누는 것을 페이지라고 부른다.물리주소공간도 페이지와 동일한 크기로 나뉘는데 이것은 프레임이라고 부른다.여기도 메모리 관리자가 테이블을 가지고 있는데 이를 페이지 테이블이라고 부른다.CPU요청->MMU확인->메모리의 테이블 참조->프레임 번호 알아내기->물리주소 변환페이지 테이블에 invalid로 써있으면 스왑영역에 있다는 뜻이다.예를 들어 4GB메모리면 16mb씩 256개의 페이지가 생긴다.그 뒤 물리주소공간도 16mb로 나눈다.페이지 테이블에는 페이지 배열의 인덱스가 된다, 해당 인덱스로 가면 프레임을 얻을 수 있다.페이지 넘버 = 논리주소 / 페이지 크기오프셋 = 논리주소 % 페이지 크기 둘의 차이점페이지의 크기1. 자꾸 앞내용을 까먹어서 무슨 단어였지 찾아보는 상황이 많아지고 있다...2. 뭔가 이해가 되기는 하는데 각각의 이론끼리 연결되는 느낌이 들지가 않는다..-페이지드 세그멘테이션(배치정책)세그멘테이션과 페이징은 각각의 장단점이 있다.메모리 접근권한 : 메모리에 부여된 권한으로 읽기, 쓰기, 실행이 있다.프로세스에서 각 영역마다 권한이 다르다.세그멘테이션 테이블과 페이지 테이블을 합쳐 페이지드 세그멘테이션이 만들어진다.세그멘테이션 테이블에 권한 비트가 추가되고 Base address가 페이지 넘버로 바뀌고 Bound Address가 페이지 개수로 바뀐다.만약 접근 권한을 위반한 요청을 하면 프로세스를 종료시킨다. - 디맨드 페이징(가져오기 정책)90:10이라는 법칙이 있다, 이것은 작동시간의 90%가 10%의 코드에서 사용된다는 법칙이다.지역성 이론ㄴ공간의 지역성 : 현재 위치와 가까운 데이터에 접근할 확률이 높음ㄴ시간의 지역성 : 최근 접근했던 데이터가 오래 전에 접근했던 데이터보다 접근할 확률이 높음지역성 이론은 쓰일 것 같은 데이터를 메모리에 두고 아닌 데이터는 스왑 영역에 두는 것이다.레지스터디멘드 페이징은 자주 쓰일 것 같은 데이터를 스왑영역(보조저장장치)에 넣는 것을 줄이는 것이다.가상메모리의 크기는 메인메모리+스왑영역이다메인->스왑은 스왑아웃이라 하고스왑->메인을 스왑인이라고 한다.페이지 테이블을 통해 물리메모리와 스왑영역에서 호출된 데이터를 가져오는 과정(스왑인, 스왑아웃)을 결정하는 것은 페이지 교체 알고리즘에 따라 결정된다.1.스왑인과 스왑아웃을 사용하는 과정을 서술하려고 했는데 머릿속에서 정리가 되지를 않는다..- 페이지 교체정책 page fault가 생겼고 현재 메모리가 가득 차있을 때 메모리에서 스왑 영역으로 페이지를 넣고 가져와야 한다.이 과정에서 어떤 페이지를 스왑영역으로 옮길지를 결정하는 것이 페이지 교제정책이다.정책도 여러가지가 있다.랜덤 -> 당연히 성능이 좋지 않다가장 오래된 페이지 선택 -> FIFO가 여기서는 적절하지 않다 -> 하지만 성능이 무난하고 구현이 간단해서 약간 변형해서 쓰인다앞으로 가장 쓰이지 않을 페이지 선택 -> 구현은 불가능하지만 성능 비교용으로 쓰인다최근 가장 사용이 적은 페이지 선택(LRU) -> 3번에 가장 가까운 성능을 보인다 -> 허나 지역성이 없으면 성능이 떨어진다LRU : 이론상 시간 기록용으로 비트를 많이 사용해야하지만 실제로는 구현할 때 접근비트를 이용한다성능은 확실히 LRU가 좋지만 시간을 기록하는 비트의 수가 너무 많이 필요하기도 하고 시간이 지나면 언젠가는 오버플로우가 생기기에 사용이 힘들다.대신 Clock Algorithm을 사용한다Clock Algorithm은 접근비트를 사용하며 일정 시간 간격마다 접근 비트를 0으로 초기화한다.만약 페이지가 참조되었다면 1로 초기화한다.Clock Algorithm은 페이지를 원형으로 연결한다.스왑 영역으로 옮길 페이지를 Clock hand라고 한다.page fault가 발생하면 Clock hand는 계속 시계방향을 돌아가며 값이 0인 페이지를 만날때까지 돈다.만약 발견하면 최근에 접근하지 않았다는 뜻이니 스왑영역으로 옯긴다.Enhanced Clock Algorithm라는 것도 있는데 변경비트와 접근비트 둘 다 사용한다.무조건 LRU만 사용할수는 없다. 만약 하드웨어에서 접근비트를 지원하지 않는다면 FIFO를 사용할 수도 있다.FIFO의 개선점인 2차 기회 페이지 교체 알고리즘도 있다. - 스레싱과 워킹셋운영체제는 CPU사용량을 늘리려고 한다.운영체제는 사용량을 늘리려고 멀티프로그래밍 정도를 늘리려고 하는데 무작정 늘려버리면 오히려 스왑작업이 많아져서 사용량이 줄어들게 된다. -> 이런 상황을 스레싱이라고 한다.스레싱의 원인은 물리메모리의 크기가 작은 것이다.물론 물리메모리를 늘리면 해결이 되긴 하지만 무작정 늘린다고 해결되지는 않는다.페이지가 많든 적든 항상 문제는 있다.해결방법은 만약 page fault가 있으면 페이지를 추가하면 되고 page fault가 너무 적게 발생하면 메모리가 낭비되는 상황이 벌어진다고 생각되서 페이지가 줄어든다.적정 페이지수가 결정되었다면 어떤 페이지를 유지할지 결정해야 한다.현재 사용중인 페이지들은 자주 사용될 확률이 높기 때문에 이를 통째로 메모리에 올리는데 이를 워킹셋이라고 부른다.섹션9-주변장치(I/O 디바이스, 저장장치)그래픽카드,SSD,마우스 등 여러가지가 있다.주변장치들은 메인보드에 있는 버스로 연결된다.하나의 버스는 Adress, Data, Control버스로 이루어져 있다.각 하드웨어에 맞게 외부인터페이스가 존재하고 레지스터, 컨트롤러, 로직 등이 있다.주변장치는 두가지로 나눌 수 있다.캐릭터 디바이스 - 마우스, 키보드, 사운드 카드 등블록 디바이스 - 하드디스크, SSD, 그래픽카드 등캐릭터 디바이스 - 적은 양의 데이터 전송블록 디바이스 - 많은 양의 데이터 전송옛날에는 버스 하나에서 썼었는데 주변장치 하나 확인하면 다른 장치를 못써서 현재는 여러개의 버스가 추가되었다.시스템 버스 ->입출력 제어기 -> 주변장치 구조이지만 그래픽카드는 시스템버스에 직접적으로 연결한다.메모리가 입출력 제어기에 직접 연결하기 위해 DMA를 추가하고 사용하는데 이를 Memory Mapped I/O라고 한다.-마우스/키보드마우스는 현재는 바닥에 달린 마우스가 초당 1500회 가까히 사진을 찍은 후 마우스 안에 DSP가 사진을 분석하여 X,Y자표를 분석한다. 그 후 마우스 드라이버에게 값을 보내고 드라이버가 운영체제에게 값과 안터럽트를 보낸다.키보드도 동일하게 작동한다.-하드디스크/Flash Memory(SSD)하드디스크에는spindle이라고 하는 막대가 있고 그곳에는 platter라는 원판들이 붙어있다.disk arm이 platter의 값을 읽는다.platter > track > sector구조로 되어있다.Flash Memory요즘은 하드디스크보다 플래시 메모리를 많이 사용한다Flash Memory는 읽기도 빠르고 자석 및 충격으로 인한 손상이 거의 없다.대신 덮어쓰기의 횟수가 정해져 있다.섹션10-파일과 파일시스템사용자가 메모리를 직접 접근해서 데이터를 저장한다면 중요한 공간도 침범당할 수 있어서 사이에 운영체제를 둔다.사용자가 요청하면 운영체제가 안전하게 저장한다.운영체제는 파일을 관리하기 위해 파일 관리자(파일 시스템)를 두었다.관리자는 파일 테이블을 이용해서 저장하고 찾는다.파일 시스템의 기능파일과 디렉토리 생성파일과 디렉토리 수정/삭제파일 권한 관리무결성 보장백업과 복구암호화파일 시스템은 블록디바이스에 블록 단위로 저장한다.사용자는 바이트 단위로 볼려고 하기에 파일 관리자가 중간에 있다.윈도우즈는 유닉스와 다르게 파일 확장자가 있고 항상 다르다.파일은 헤더와 데이터로 나누어져있다.헤더에는 파일의 속성들이 들어있다.운영체제는 파일 제어 블록을 가지고 있다.파일 제어 블록은 모든 파일마다 있고 오픈되면 메모리로 이동한다.파일 제어 블록은 운영체제가 관리하고 사용자는 접근할 수 없다.순차파일구조카세트테이프들어온 순서대로 작동하기에 공간의 낭비가 없고 구조가 단순하다.허나 특정지점으로 바로 이동이 어렵다. 집접파일구조해시함수를 통해 저장위치를 정하는 방식json도 이 방식데이터 접근이 매우 빠르다해시함수를 잘 골라야 하며 저장공간이 낭비될 수 있다. 인덱스 파일구조앞선 두 가지 방식을 합친 것노래 재생목록 같은 경우 -디렉토리파일을 하나에 공간에 저장하면 너무 복잡할 것이다.그렇기에 디렉토리가 생겼다.디렉토리는 파일을 가질 수 있고 자식 디렉토리도 가질 수 있다.가장 위에 있는 디렉토리를 루트 디렉토리라고 한다.루트 디렉토리를 "/"로 표현하고 디렉토리를 구분할때도 /를 사용한다.윈도우즈는 루트 디렉토리를 C:로 표현하며 \로 구분한다.디렉토리도 파일이며 일반 파일에는 데이터가 있고 디렉토리에는 파일 정보가 저장되어 있다.디렉토리 구조처음에는 루트 디렉토리에만 하위 디렉토리를 만들 수 있었으나 디렉토리가 너무 많아져서 결국 다단계 디렉토리가 생겼다.현재는 다단계 디렉토리를 사용하며 트리구조에서 순환이 생긴다.바로가기 기능 때문에 순환이 생긴다.-파일과 디스크파일시스템은 공간을 나누고 주소로 관리한다는 면에서 메모리와 비슷하다.파일시스템은 블록 단위로 나누는데 이는 1~8kb정도이다.파일시스템은 파일테이블로 관리하는데 여기에는 파일의 시작 위치 정보도 있다.파일은 블록을 어떤 방식으로 연결하냐에 따라 연속할당과 불연속할당으로 나누어진다.연속할당 : 블록들을 디스크에 연속적으로 저장하는 방식, 시작블록만 알면 나머지도 알 수 있으나 내부단편화가 발생한다.->그래서 사용을 안한다.불연속할당 : 디스크의 비어있는 공간에 집어넣고 파일시스템이 두가지 방식으로 관리한다.불연속할당(연결할당) : 연결리스트 구조불연속할당(인덱스할당) : 데이터들의 인덱스를 가지고 있는 인덱스 블록을 연결한다, 테이블의 크기가 부족할 경우 사용하기 좋다.(유닉스와 리눅스에서 사용)디스크는 블록으로 단위가 나뉜다, 여기도 블록의 크기에 따라 외부단편화가 생기거나 관리해야할 블록의 수가 많아진다.빈공간을 찾을 때 항상 모든 공간을 찾는것보다는 빈공간 리스트를 만들고 삭제한 후에 리스트에 빈 공간의 주소를 추가하는 방식이 좋다. 알고리즘https://github.com/asdf1596/cs_inflearn_club/tree/main/dev섹션3- 삽입정렬삽입 정렬도 두 영역으로 나눠서 진행된다.5|1,3,2,45,5|3,2,4 (1)1,5|3,2,41,5,5|2,4(3)1,3,5|2,41,3,5,5|4(2)1,3,3,5|4(2)1,2,3,5|41,2,3,5,5(4)1,2,3,4,5삽입정렬 - 구현function InsertionSort(arr) { for (let i = 1; i = 0; j--) { if (arr[j] > insertingData) { arr[j + 1] = arr[j]; } else { break; } } arr[j + 1] = insertingData; } } let arr = [4, 1, 6, 3, 5, 2]; console.log(arr); InsertionSort(arr); console.log(arr);시간복잡도 : O(n^2)장점 : 구현하기 쉽다단점 : 시간이 오래 걸린다- 병합정렬정렬해야 할 것을 아주 잘게 나눈 다음 정렬하고 병합하고를 반복하는 정렬방법이다.병합정렬 - 구현function MergeSort(arr, leftIndex, rightIndex) { if (leftIndex midIndex) { for (let i = rightAreaIndex; i 시간복잡도 : O(nlogn)장점 : 성능이 훨씬 좋다단점 : 이해와 구현이 어려움- 퀵 정렬배열의 값 중 한가지를 피벗으로 설정(설정방법은 여러가지)맨 왼쪽, 맨 오른쪽, 양쪽 이동값 만들기왼쪽 이동값이 피벗보다 크면 정지 -> 오른쪽 이동값이 피벗보다 작으면 정지 -> 둘다 정지하면 교환 -> 둘이 만나면 오른쪽 이동값 위치에 피벗값 변경-> 이후 피벗값 기준 좌우 따로 정렬function quicksort(arr, left, right) { if (left = arr[leftStartIndex]) { leftStartIndex++; } while (rightStartIndex >= left + 1 && pivot 시간복잡도 : O(nlogn), O(n^2)장점 : 성능이 훨씬 좋다단점 : 이해와 구현이 어려움- 동적 프로그래밍-메모이제이션앞선 방법들은 재귀를 통해 문제를 나누어서 해결했었다.하지만 재귀는 콜스택을 차지하는 단점 외에도 다른 단점이 있다.예 :피보나치 수열이라는 것이 있다.현재 수와 이전 수를 더해서 다음 수를 만들어내는 구조의 수열이다.(1,1,2,3,5,8,13....)function fibonacci(n) { if (n == 1 || n == 0) return n; return fibonacci(n - 2) + fibonacci(n - 1); } console.log(fibonacci(5));만약 이 수열을 간단한 재귀로 구현한다면 겹치는 계산이 너무 많다.(O(n^2))해결방법을 결과를 계산하고는 저장해서 적재적소에 사용하도록 코딩하는 것이다.function fibonacci1(n) { if (n == 1 || n == 0) return n; return fibonacci1(n - 2) + fibonacci1(n - 1); } function fibonacci2(n, memo) { if (n == 1 || n == 0) return n; if (memo[n] == null) { memo[n] = fibonacci2(n - 2, memo) + fibonacci2(n - 1, memo); } return memo[n]; } let start = new Date(); console.log(fibonacci1(5)); let end = new Date(); console.log(end - start); let start2 = new Date(); console.log(fibonacci2(5, {})); let end2 = new Date(); console.log(end2 - start2);시간복잡도 : O(n)속도는 빠르긴 하지만 메모리를 차지한다.- 동적 프로그래밍-타뷸레이션메모이제이션 - 하향식 계산 방식으로 어려운 문제를 간단하게 해결할 수 있으며 중복 계산을 하지 않아서 속도가 빠르다.타뷸레이션 - 상향식 계산 방법으로 계산에 필요한 모든 값을 전부 계산 후 테이블에 저장해둠상황에 따라 둘을 적절하게 사용이 가능하다.메모이제이션 - 메모리를 사용하면서 성능을 향상시킨다. 재귀가 직관적일때는 메모이제이션이 유리하다.타뷸레이션 - 재귀가 직관적이지 않을 때 유리하다.

인프런 워밍업 클럽 스터디 2기 CS 2주차 과제

운영체제FIFO 스케줄링의 장단점이 뭔가요? 장점선입선출 구조단순하고 구현이 간단하다단점순서가 가장 중요하기에 비효율적인 상황이 생길 수 있다(예시 I/O작업) SJF를 사용하기 어려운 이유가 뭔가요?프로세스의 작동시간을 예측하기 힘든다는 점과 실행시간이 너무 긴 프로세스는 너무 늦게 실행된다는 단점이 있다.RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?RR(RoundRobin)은 정해진 시간마다 프로세스를 돌아가면서 실행시키는 구조이다.타임 슬라이스가 작으면 프로세스를 바꿔서 실행시키는 횟수가 많아져서 오버헤드가 커진다.운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?둘의 구분법은 CPU를 반납하는지 혹은 CPU를 뺏기는 지에 따라 구분한다.공유자원이란무엇인가요?보통은 프로세스들이 사용하는 변수, 메모리, 파일 등을 말한다. 보통 강의에서는 프로세스가 사용하는 한정된 메모리를 뜻한다.교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?상호배제자원을 한 프로세스가 가져갔다면 다른 프로세스에게 공유되서는 안된다.비선점리소스를 강제로 빼앗을 수 없다점유와 대기프로세스가 자원A를 가지고 있는 상태에서 자원 B를 원하는 상태여야 한다.원형 대기점와 대기를 하는 관계가 원형이어야 한다.자료구조와 알고리즘재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?보통은 함수 내에서 끝도 없이 반복되어서 코드가 끝나지 않는다.잘못 설정한 경우에는 무한반복뿐 아니라 의도하지 않은 곳에서 코드가 종료되어서 잘못된 결과가 나올 수도 있다.0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.정석function sumOdd(n) { if (n 뭔가 이상한 정석function sumOdd(n) { return n 뭔가 이상한 pythonsumOdd = lambda n : 0 if n

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

운영체제섹션 3- SJFFIFO는 Burst Time이 짧은 것과 관계없이 실행되어서 효율적이지 않다.그로 인해 Burst Time이 짧은 것부터 실행시키는 Shortest Job First가 생겼다.이론상 FIFO보다 성능이 좋지만 프로세스의 작동시간을 예측하기 힘든다는 점과 실행시간이 너무 긴 프로세스는 너무 늦게 실행된다는 단점이 있다.이러한 이유로 사용되지 않는다.- RR사람들은 생각한 결과 FIFO에서 단점만 해결해보자고 생각이 들었다.운영체제가 프로세스에게 시간을 부여하고 그 시간을 넘으면 강제로 다음 프로세스를 작동시키는 구조로 되었다.프로세스에게 할당하는 시간은 "타임 슬라이스" 혹은 "타임 퀀텀"이라고 부른다.물론 상황에 따라 FIFO가 더 좋은 경우도 있기에 무조건적으로 좋은 것은 아니다.- MLFQMulti Level Feedback QueueRR의 업그레이드 버전이다.프러세스마다 CPU를 더 사용하는지 I/O를 더 사용하는지에 따라 "CPU Bound Process"와 "I/O Bound Process"로 나누어진다."CPU Bound Process"는 CPU사용률과 처리량을 중요하게 생각하고 "I/O Bound Process"는 응답속도를 중요하게 여긴다.작동 구조는 프로세스의 종류에 따라 타임 슬라이스를 다르게 주는 것이다.둘의 구분법은 CPU를 반납하는지 혹은 CPU를 뺏기는 지에 따라 구분한다.섹션 4- 프로세스 간 통신프로세스틑 다른 프로세스와 협업하는 경우도 있다.통신은 같은 컴퓨터나 다른 방식으로 연결된 프로세스와 할 수도 있다.통신의 종류파일와 파이프 이용프로세스들이 하나의 파일을 읽고 쓰는 방식파이프를 이용해 주고받는 방식쓰레드 이용프로세스 간 통신이 아닌 쓰레드 간 통신 방법데이터, 힙에 있는 정보를 공유해서 사용네트워크 이용소켓통신RPC를 통해 통신- 공유자원과 임계구역프로세스 간 통신할 때 공동으로 사용하는 파일들이 있다.이런 파일들을 공유자원이라고 한다.프로세스의 접근 순서에 따라 값이 다를 수 있다.시분할 처리로 인해 뭐가 먼저 실행되는지 예측하기 힘들다.위와 같은 문제를 동기화 문제라고 한다.동기화 문제를 일으키기 때문에 동시에 이용하면 안되는 영역을 임계구역이라고 한다.문제를 해결하기 위해서는 상호배제 매커니즘이 필요하다.요구사항주어진 시간에 하나의 프로세스만 접근이 가능해야 한다여러 요청에도 하나의 프로세스의 접근만 허용한다임계구역에 들어간 프로세스는 빠르게 나와야 한다- 세마포어상호배제 메커니즘 중 한가지이다.예시로는 강의에서 프린터실,열쇠관리자,직원 등으로 예시를 들었다.int swait(s) int currentHealth = GetHealth(); health = currentHealth + 50; signal(s);wait(s) int currentHealth = GetHealth(); health = currentHealth - 10; signal(s);여기서는 예시가 1가지이지만 실제로는 여러가지의 열괴를 가질 수 있다.단점wait과 signal을 잘못 사용하면 꼬일 가능성도 있다.- 모니터세마포어의 단점을 해결한 상호배제 알고리즘운영체제가 아니라 사용하는 언어 차원에서 해결하는 것예 : java의 synchronized, 이 함수를 사용하면 겹쳐서 사용되지 않는다.섹션 5- 데드락이란?프로세스간에 서로 자원을 가지려고 하다가 아무도 사용하지 못하는 상태를 교착상태라고 한다.이런 상태가 일어나는 것은 공유자원 때문이다.예시 : 식사하는 철학자 예시교착상태의 필요조건 4가지상호배제자원을 한 프로세스가 가져갔다면 다른 프로세스에게 공유되서는 안된다.비선점리소스를 강제로 빼앗을 수 없다점유와 대기프로세스가 자원A를 가지고 있는 상태에서 자원 B를 원하는 상태여야 한다.원형 대기점우와 대기를 하는 관계가 원형이어야 한다.이 중 한가지라도 만족되지 않으면 생기지 않는다.연구자들은 예방을 하려고 하였으나 너무 복잡해져서 대신 해결하는 방법을 연구하였다.- 데드락 해결교착상태 회피자원을 할당할 때 교착상태가 생기지 않을 정도만 주는 것을 말한다.은행원 알고리즘자신의 자원 상태에 따라 할당을 적절하게 주는 것운영체제는 자신의 자원 수를 파악한다프로세스는 자신의 최대 요구 자원을 운영체제에게 알려준다현재 자원 요구량에 따라 프로세스에게 자원을 나눠준다그 이후 요구량에 따라서 적절한 순으로 할당과 회수를 반복한다이런 방식은 불편하고 비싸기 때문에 해결 방법을 생각했다.그 이후 교착상태를 검출하는 방법을 고민했다.2가지 방법을 알아냈다.가벼운 교착 상태 검출특정 시간 동안 프로세스가 일을 안하면 교착상태로 판단교착상태가 아니었던 일정 시간 전으로 바꾸기무거운 교착 상태 검출프로세스의 자원 사용량을 보고 판단 이 방법은 정확성은 좋지만 지속적으로 확인해야해서 힘들다섹션 7- 메모리 종류컴퓨터에서는 메모리가 여러 종류가 있다레지스터휘발성 메모리컴퓨터의 bit는 레지스터의 크기를 말한다메인메모리의 값을 가져와서 레지스터에서 연산 후 다시 메인메모리로 저장캐시레지스터와 메인메모리 속도 차이 때문에 미리 데이터를 가져오는 곳여러개이다메인메모리(RAM)실제 운영체제와 다른 프로세스들이 올라오는 공간휘발성 메모리가격이 비싸다보조저장장치(HDD, SSD)파일 저장 공간비휘발성 메모리- 메모리와 주소주소현대의 컴퓨터는 폰 노이만 구조에 따라 모든 프로그램을 메모리에 올려서 실행시킨다운영체제는 멀티프로그래밍 환경 때문에 1바이트 크기로 메모리를 나누고 관리한다.한칸마다 숫자를 지정하는데 그것이 주소이다.주소에서 0x0대로 시작하는 주소가 있는데 그곳을 물리 주소라고 부른다.사용자 관점에서 바라본 주소 공간은 논리 주소라고 부른다.경계 레지스터주소 처음에는 운영체제를 두는 공간이 있는데 만약 사용자가 악의적은 프로세스를 넣어서 침범한다면 위험하다이런 이유로 물리적으로 분리하는 경계 레지스터를 만들었다.경계 레지스터는 프로세스가 할당받지 않은 주소를 침범했다면 종료시킨다.절대주소와 상대주소메모리에는 절대주소와 상대주소가 존재한다.프로그램이 실행되면 컴파일러는 0번지에서 시작한다고 알고있지만 절대주소로는 다른 주소에서 시작한다.만약 사용자가 10번지의 데이터를 가져오라고 한다면 절대주소+10번지의 데이터를 가져온다.- 메모리 할당방식메모리 오버레이유니프로그래밍 환경에서 메모리보다 더 큰 프로램을 실행시키는 방법은 사용되는 곳만 메모리에 넣고 나머지는 하드디스크에 넣는 방식이다현대의 메모리를 나누는 방식가변 분할 방식메모리에 연속해서 프로세스를 집어넣는 것연속 메모리 할당장점낭비되는 공간 없음단점외부 단편화만약 프로세스가 끝나면 빈 공간이 생긴다빈 공간이 여러개일 때 합치면 프로세스에게 줄 크기더라도 연속돼있지 않으면 사용이 불가능하다합칠 수는 있지만 다른 프로세스들을 정지키시고 해야 하기 때문에 힘들다고정 분할 방식프로세스의 크기에 상관없이 메모리를 정해진 크기로 나눈다.프로세스도 그 크기에 맞춰서 넣는다비연속 메모리 할당장점구현이 간단하다오버헤드가 적다단점공간이 남는 상황이 있다 버디 시스템2의 승수로 메모리를 분할해 메모리를 할당하는 방식남는 공간이 최소화되고 사라진 이후에도 붙어있는 공간과 합치기 편리하다알고리즘https://github.com/asdf1596/cs_inflearn_club섹션 3- 재귀재귀란?어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다.프로그래밍에서는 함수를 정의할 때 재귀를 사용하는데 그것이 재귀함수이다프로그래밍function myFunction(number) { if (number > 10) return; console.log(number); myFunction(number); } myFunction(1);기초적인 재귀함수콜스택함수가 호출되면서 올라가는 메모리 영역FILO의 특징을 가지고 있다위쪽 코드에서 return이 없을 경우 콜스택이 꽉 찰 때까지 실행된다.콜스택은 함수가 실행되면 콜스택에 올라오고 실행된다, 실행된 후 만약 끝난다면 사라진다.하지만 종료되지 않고 함수 내에서 다시 호출되면 사라지지 않고 스택에 남아 있는다.그로 인해 콜스택의 크기가 꽉 차게 되고 끝난다. 앞선 내용만 보면 재귀보다 그냥 for문을 쓰는 것이 좋아보이지만 재귀함수를 이용하면 해결하기 힘든 문제를 쉽게 해결할 수 있다. - 예 : 팩토리얼팩토리얼 구현function factorial(number) { if (number == 1 || number == 0) { return 1; } else { return number * factorial(number - 1); } } console.log(factorial(5));- 재귀적으로 생각하기1.단순반복실행ㄴ 단순반복은 오히려 for문보다 좋지 않다2.하위문제를 기반으로 현재 문제 해결ㄴfor문은 처음부터 쭉 올라가서 상향식 계산이라고 한다ㄴ재귀의 경우 하향식 계산이다ㄴ재귀를 쓴다고 다 하향식을 아니다ㄴ쓸모없다 배열의 합 계산하향식 계산 -> 1~5 계산 -> 1~4의 합 + 5 -> 1~4의 합은 1~3의 합에 4를 더한 값이다 -> ...반복구현function sumArray(arr) { if (arr.length == 1) return arr[0]; return sumArray(arr.slice(0, -1)) + arr[arr.length - 1]; } let arr = [1, 2, 3, 4, 5]; let sum = sumArray(arr); console.log(sum);function strLength(arr) { if (arr[0] == null) return 0; return strLength(arr.slice(0, -1)) + 1; } let str = "asdf"; let len = strLength(str); console.log(len);function power(x, n) { if (n == 0) return 1; return power(x, n - 1) * x; } console.log(power(2, 5));- 하노이 탑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");- 버블정렬가장 쉬운 정렬이지만 성능이 좋지 않다바로 옆의 숫자와 비교해서 정렬하는 방식function BubbleSort(arr) { for (let i = 0; i arr[j + 1]) { let temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } let arr = [4, 2, 1, 3]; console.log("=====정렬 전====="); console.log(arr); BubbleSort(arr); console.log("=====정렬 후===="); console.log(arr);걸리는 시간은 O(n^2)이다.간단하지만 확실히 시간이 오래 걸린다.활용 : https://acmicpc.net/problem/23969장점이해와 구현이 간단하다단점O(n^2)로 성능이 그리 좋지 않다- 선택 정렬이해와 구현이 간단하지만 역시 성능이 아쉽다배열의 모드 값을 비교 후 가장 작은 값을 첫번째 원소로 가져온다그 이후 정렬된 영역 뒤부터 다시 가장 작은 원소를 첫번째로 가져온다function SelectionSort(arr) { for (let i = 0; i 걸리는 시간 또한 O(n^2)이다.버블정렬과 같 시간이 오래 걸린다.장점이해와 구현이 간단하다단점O(n^2)로 성능이 그리 좋지 않다

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

운영체제섹션 1- 기초운영체제는 개인용 컴퓨터나 대형 컴퓨터, 스마트폰, 임베디드 등에 들어간다.컴퓨터는 운영체제가 있어야 동작하는가 - NO하지만 운영체제가 없으면 한가지 기능만 가능할 뿐 다양한 기능을 사용 불가능하다.옛날 전화기는 전화만 가능했지만 지금은 스마트폰의 운영체제를 통해 통화를 비롯해 다양한 기능을 사용 가능하다.- 운영체제가 하는 일프로세스 관리 -> 만약 하지 않는다면 하나의 프로세스가 CPU를 혼자 먹어서 다른 프로세스가 동작하지 않을 것이다메모리 관리 ->모든 프로그램은 메모리에 올라와서 동작하는데 다양한 방법으로 메모리를 관리한다하드웨어 관리 -> 운영체제가 판단하여 적절한 위치에 사용자의 프로그램을 저장한다파일 시스템 관리 -> 파일을 효울적으로 관리해준다- 운영체제의 역사1940 -> 애니악1950 초 -> 직접회로가 개발되었다, 펀치카드로 프로그래밍하여 넣으면 라인프린터로 출력되었다.1950 중후반 -> 50년대 초의 인간의 프로그래밍 과정이 너무 오래 걸려서 싱글스트림 배치시스템이 개발되었다.1960 -> 앞선 방법의 한계가 해결되었다, 시분할 시스템을 사용하였다, UNIX가 개발되었다.ㄴ허나 시분할 시스템으로 인해 메모리 침범 문제가 생겼다.1970 이후 -> 개인용 컴퓨터의 시대, 애플의 매킨토시와 마이크로소프트의 MS-DOS가 많이 사용되었다ㄴ매킨토시는 GUI의 적용으로 인기를 끌었다- 운영체제의 구조핵심은 커널이다, 사용자는 인터페이스(GUI,CLI)를 통해 커널에 접근한다.GUI : 그래픽으로 된 인터페이스CLI : 유닉스나 리눅스가 지원하는 인터페이스app은 시스템 콜을 통해 부른다, 시스템 콜 없이 불러져서 어플리케이션이 맘대로 저장소에 저장하면 중요한 데이터를 덮어쓰거나 할 수도 있기 때문에 시스템 콜이 필요하다. 시스템 콜은 write를 통해 저장하는데 자동으로 빈 공간에 저장하는 역할을 한다.하드웨어와 커널의 인터페이스로는 드라이버를 사용한다.운영체제는 다양한 하드웨어를 사용할 수 있어야 하는데 운영체제에 모든 하드웨어에 맞는 프로그램을 가지고 있기는 어려워서 제조사에서 드라이버를 제공하는 편이다.- 컴퓨터 하드웨어와 구조현대의 컴퓨터는 폰 노이만 구조를 하고있다. 애니악 때의 방식이 불편하다고 생각하여 이를 해결하기 위해 CPU와 메모리를 두고 버스로 연결한다.프로그램을 작동하려면 메모리에 올려야 하는데 프로그램을 메모리에 내장했다고 해서 프로그램 내장 방식이라고 한다.메인보드 -> 메인보드는 다른 하드웨어를 연결하는 역할CPU -> 중앙처리장치로 불리며 산술논리연상장치, 제어 장치, 레지스터로 이루어져있다.메모리 종류 -> RAM과 ROM으로 나누어지는데 RAM은 전력이 끊기면 저장된 값을 잃어서 메인 메모리로 사용된다. ROM은 전력이 끊겨도 값이 사라지지 않아서 부팅과 관련된 바이오스를 저장하는데 주로 쓰인다.- 컴퓨터의 부팅과정전원버튼을 통해 전력이 들어가면 바이오스가 켜진다. (바이오스는 주요 하드웨어를 체크한다)이상 없을 시 부트로더를 가져와 RAM으로 실행한다.운영체제를 모니터로 불러오고 우리가 아는 바탕화면이 나온다.- 인터럽트CPU는 입출력을 하려고 하면 입출력 관리자에게 명령을 내린다.CPU는 스스로 입출력을 하지 않기 때문에 관리자에게 지속적으로 확인을 한다.앞선 방식을 폴링 방식이라고 한다.폴링 방식은 너무 자주 신호를 보내서 성능이 좋지 않다.이런 단점을 해결한 것이 인터럽트이다.CPU는 입출력 신호를 보내고 다른 일을 한다, 만약 입출력관리자에게 신호가 온다면 ISR을 실행시킨다.ISR은 특정 인터럽트가 들어오면 그 인터럽트를 해결하는 함수이다.인터럽트는 2개의 방식으로 나누어진다하드웨어 방식 : 앞서 설명한 입출력 같은 인터럽트소프트웨어 방식 : 사용자 프로그램에서 발생한 인터럽트 (유효하지 않은 접근이나 0으로 나누기 등...)섹션 2- 프로그램과 프로세스 프로그램 : 저장장치에 저장된 명령문의 집합체(app등으로 불리고 .exe의 모양을 가지고 있다)프로세스 : 실행중인 프로그램(하드디스크에 있는 앱이 메모리로 가서 작동되면 그것이 프로세스이다)차이점 : 프로그램은 그저 명령문의 집합체인 수동적이 존재이고 프로세스는 메모리에서 CPU도 사용하고 입출력도 하는 능동적인 존재이다.프로세스의 구조는 code,data,stack,heap으로 이루어져 있다.c언어의 컴파일 과정파일 -> 전처리기 -> .i로 변경 -> 컴파일러 -> .s로 변경 -> 어셈블러로 변경 -> .o로 변경 -> 링커 -> .exe로 변경위 과정을 걸쳐 exe파일을 더블클릭하면 메모리로 올라가고 운영체제가 관리를 한다.- 멀티프로그래밍과 멀티프로세싱유니프로그래밍 : 메모리에 오직 하나의 프로세스가 올라온 상황멀티프로그래밍 : 메모리에 여러개의 프로세스가 올라온 상황멀티프로세싱 : CPU가 여러 개의 프로세스를 처리하는 것을 말한다현대에는 멀티프로그래밍과 멀티프로세싱이 있다.옛날에는 메모리의 크기가 작아서 멀티프로그래밍이 불가능해서 유니프로그래밍으로 멀티프로세싱을 했다.유니프로그래밍(옛날) : 메모리에 프로그램 올리기 -> 실행 -> 저장장치에 상태 저장하고 넣기 -> 다른 프로그램 메모리에 두기 -> 새로 가져온 프로그램 실행하기(프로그램을 메모리와 저장장치 사이로 옮기는 것을 스와핑이라고 한다)- PCB(Process Control Block)운영체제는 여러개의 프로세스를 알고리즘에 따라 실행시켜야 한다.프로세스가 만들어지면 해당 프로세스의 정보를 가지고 있는 PCB를 만들고 저장한다.(연결리스트 자료구조의 형이다)운영체제는 프로세스가 종료되면 연결리스트에서 해당 프로세스의 PCB를 제거한다.구조 : 프로세스 구조, 프로세스 ID, 프로그램 카운터, 레지스터 정보 등....- 프로세스 상태사용자가 프로그램을 실행시키면 메모리에 올라가면서 프로세스가 생성된다.운영체제가 프로세스를 관리하기 위해 프로세스 상태라는 것이 존재한다.생성상태 : PCB를 생성하고 메모리에 프로그램 적재를 요청준비상태 : 적재승인 시 적재를 기다리고 있는 상태대기상태 : 프로세스가 입출력 요청을 할 시 입출력이 올 때 까지 대기상태로 변환, 입출력이 끝날 시 준비상태로 이동실행상태 : 실행상태에 있는 프로세스의 수는 CPU의 개수와 같다.(부여된 시간만큼만 CPU사용 가능, 시간이 끝날 시 준비상태로 변함)완료상태 : 프로세스가 종료된 상태- 콘텍스트 스위칭시분할 처리 중 다른 프로세스를 실행하기 위해 현재 프로세스의 상태를 저장하고 다른 프로세스의 상태값으로 바꾸는 작업콘텍스트 스위칭이 일어나면 PCB의 내용이 변경된다.작업중이었던 내용을 PCB에 저장하고 다음 프로세스의 PCB내용을 토대로 CPU의 상태를 바꾼다.발생 이유는 다양하지만 인터럽트나 CPU점유시간이 끝났을 때 일어난다.- 프로세스 생성과 종료프로세스가 생성될때의 가정은 이러하다.exe파일 더블클릭운영체제가 프로그램의 코드영역과 데이터영역을 로드하고 빈 스택과 빈 힙을 만들어 공간을 확보한다.PCB를 만들어서 값을 초기화한다.위 방법은 부팅될때 1번만 실행되고 그 뒤로는 0번 프로세스(1~3번 과정에서 만들어진 프로세스)를 복사하여 사용한다.복사하여 생성되는 프로세스는 자식 프로세스라고 하며 반대로는 부모 프로세스라고 한다.주로 부모 프로세스가 자식프로세스에게 시작 신호를 보내고 자식이 종료 신호를 보내면 부모 프로세스가 자식 프로세스를 종료시킨다.하지만 부모 프로세스가 먼저 사라지거나 자식프로세스가 종료 신호를 보내지 못하고 사라지면 종료되지 못하고 남아있는 좀비 프로세스가 생긴다. 이러한 프로세스는 컴퓨터의 성능 저하를 유발하나 컴퓨터를 껐다가 키면은 사라진다.- 쓰레드운영체제의 작업 처리 단위는 프로세스이다.사용자가 운영체제에게 작업을 요구하면 그만큼 프로세스의 수가 늘어난다.프로세스가 생성되는 PCB가 생성되고 코드,데이터,스택,힙 등의 영역이 생긴다.만약 웹브라우저를 20개 틀면 20번 복제되고 메모리의 사용량이 너무 많아진다.앞선 문제를 해결하기 위해 쓰레드를 고안해냈다.쓰레드는 프로세스 안에 존재하며 여러개가 있을 수 있다.프로세스 내에 쓰레드들은 PCB, 코드, 데이터,힙 영역을 공유한다.쓰레드를 관리하기 위해 ID를 부여하고 TCB도 생겼다.이렇게 되면 운영체제가 작업을 관리하는 단위는 쓰레드가 되었다.이렇게 되면 탭을 생성할 때 최초생성은 프로세스가 생격나지만 탭을 추가하면 프로세스가 아닌 쓰레드가 추가된다.프로세스와 쓰레드의 장단점프로세스는 독립적이어서 하나가 문제가 생겨도 문제가 생기지 않는다.허나 쓰레드는 예를 들어 힙 영역이 문제가 생기면 공유하는 모든 프로세스가 문제가 생긴다--프로세스는 모든 자원을 각각의 프로세스가 가지고 있어서 통신하려면 IPC통신을 사용해야 하는데 오버헤드가 크고 속도가 느리다.반면 쓰레드는 다양한 자원을 공유해서 오버헤드가 굉장히 작다.섹션 3- CPU스케줄링 개요프로그램을 실행하면 메모리에 프로세스가 생기고, 그 안에는 1개 이상의 쓰레드가 있다.프로세스들은 CPU를 사용하기 위해서 운영체제의 명령을 기다린다.운영체제는 모든 프로세스들에게 CPU 할당/해제하는데 이를 CPU스케줄링이라고 한다.오늘날 운영체제는 프로세스들을 시분할 처리방식으로 CPU를 할당한다.- 다중큐프로세스들은 준비 상태에 있다가 운영체제의 명령으로 실행 상태가 된다, 그 후 지정된 시간이 끝나면 준비 상태, I/O가 필요하면 대기 상태, 끝나면 완료 상태로 변한다.이 중 준비와 대기는 큐 자료구도로 작동된다.작동은 선입선출구조이다.(FIFO)운영체제는 준비상태에 프로세스가 있으면 다양한 프로세스 중 우선순위를 보고 그에 맞는 '준비 큐'에 넣는다.또한 대기상태에 있는 프로세스는 동류에 따라 다른 큐에 넣는데 예를 들어 하드디스크를 사용하는 경우에는 HDD큐에 들어가고 키보드를 사용하면 키보드 큐에 넣는다.(자세히는 프로세스 그 자체보다는 PCB가 들어간다)- 스케줄링 목표리소스 사용률CPU 혹은 I/O디바이스 사용률을 높이는 것이 목표이다.오버헤드 최소화공평성처리량 증가대기시간 감소 응답시간 앞선 목표들을 다 맞추기는 힘들다.그 이유는 목표가 서로 상반되는 경우도 있기 때문이다.- FIFOCPU스케줄링 알고리즘 중 하나.가장 정석적인 알고리즘으로 먼저 들어온 순서대로 CPU를 할당받는 방식이다.마트의 계산대와 같은 느낌이다.장점 : 단순하고 직관적단점 : 순서가 가장 중요하기에 비효율적인 상황이 생길 수 있다(예시 I/O작업)스케줄링의 성능은 평균 대기시간으로 정한다.현대 운영체제에서는 잘 쓰이지 않고 일괄처리시스템에 쓰인다.자료구조와 알고리즘섹션 1- 하고 싶은 말알고리즘은 무지성으로 따라하거나 암기하는 것이 아닌 이해하는 것이 문제를 해결 할 때 가장 좋다.- 자료구조와 알고리즘이란자료구조자료구조란 테이터가 어떤 구조로 저장되고 어떻게 사용되는지를 나타냅니다.가장 단순한 자료구조는 변수이다.그 외에도 사용했었던 자료구조는 배열이 있다.a = 87 b = 70 c = 100 average = (a+b+c)/3arr = [87,70,100] average = 0 for i in arr: average+=i average/=len(average)위의 코드 예시처럼 자료구조 간의 사용 방법과 저장된 모양도 다르다알고리즘어떤 문제를 해결하기 위한 확실한 방법예를 들어 평균을 구하는 문제를 풀 때는 알고리즘이 필요하다- 시간 복잡도보통 시간이 가장 적게 걸리는 알고리즘을 좋은 알고리즘이라고 한다.보통 반복문이 시간에 영향을 미쳐서 반복문으로 성능을 확인한다.예를 들어 5개의 리스트에서 특정 숫자를 찾을 때 처음부터 찾는다면 최악의 경우 리스트의 길이만큼 체크한다.이런 경우를 O(n)이라고 한다.상수시간 알고리즘은 O(1)로 표현한다.(문제를 해결할 때 입력과 상관없이 계산량이 같을 때 이다)그 외에도 O(nlogn), O(n^2), O(2^n)등이 있다.섹션 2- 배열일반전인 배열배열을 선언하면 운영체제가 그 크기만큼 빈 공간을 찾아서 순서대로 값을 선언한다.운영체제는 배열의 첫번쨰 주소만 저장한다운영체제는 배열의 시작 주소를 기준으로 가져온다(O(1)의 성능)데이터의 삽입,삭제는 느리다만약 할당된 공간의 크기를 넘기면 운영체제는 새로 빈 공간을 찾는다.물론 처음부터 큰 크기의 배열을 만들면 편하겠지만 메모리 사용량이 너무 크다JS식 배열js배열은 불연속적으로 할당하고 내부적으로 연결한다기능상 배열이라고 부를 수 있다- 연결리스트연결리스트 - 개념개발자들은 배열의 단점을 해결하기 위해 연결리스트를 만들었다연결리스트는 노드로 이루어져있다노드는 다음 노드의 주소를 알고있다. 즉, 처음 노드의 주소만 알면 모든 노드를 찾을 수 있는 것이다장점연결리스트는 새로 삽입하면 주소만 바뀌주면 되서 문제가 없다또한 삭제도 노드를 지우고 주소를 바꾸면 된다단점배열은 데이터 접근이 O(1)의 성능으로 아주 빠르다. 허나, 연결리스트는 1번부터 천천히 가야해서 O(n)의 성능이다.선택참조가 메인이라면 배열삽입&삭제가 메인이라면 연결리스트연결리스트 - 구현import { Node, LinkedList } from "./LinkedList.mjs"; let node1 = new Node(1); let node2 = new Node(2); let node3 = new Node(3); node1.next = node2; node2.next = node3; console.log(node1.data); console.log(node1.next.data); console.log(node1.next.next.data); let list = new LinkedList(); console.log("========= insertAt() 다섯 번 호출 =========="); list.insertAt(0, 0); list.insertAt(1, 1); list.insertAt(2, 2); list.insertAt(3, 3); list.insertAt(4, 4); list.printAll(); console.log("======= clear() 호출=========="); list.clear(); list.printAll(); console.log("======= insertLast() 호출=========="); list.inserLast(0); list.inserLast(1); list.inserLast(2); list.printAll(); console.log("======= deleteAt() 호출=========="); list.deleteAt(0); list.printAll(); list.deleteAt(1); list.printAll(); console.log("======= deleteLast() 호출=========="); list.inserLast(5); list.deleteLast(); list.deleteLast(); list.printAll(); console.log("======= getNodeAt() 호출=========="); list.inserLast(1); list.inserLast(2); list.inserLast(3); list.inserLast(4); list.inserLast(5); let secondNode = list.getNodeAt(2); console.log(secondNode);class Node { constructor(data, next = null) { this.data = data; this.next = next; } } class LinkedList { constructor() { this.head = null; this.count = 0; } printAll() { let currentNode = this.head; let text = "["; while (currentNode != null) { text += currentNode.data; currentNode = currentNode.next; if (currentNode != null) { text += ", "; } } text += "]"; console.log(text); } clear() { this.head = null; this.count = 0; } insertAt(index, data) { if (index > this.count || index = this.count || index = this.count || index -스택스택 - 개념스택이란 단순한 규칙을 가지고 있는 배열작동 구조는 FILO(First In Last Out) (선입후출)예시 : 엘리베이터에 타는 사람들 등구현의 개념삽입은 오직 첫번째에(head 위치)삭제도 오직 첫번째만(head 위치)스택 - 구현import { Stack } from "./stack.mjs"; let stack = new Stack(); console.log("===첫 번째 출력===="); stack.push(1); stack.push(2); stack.push(3); stack.push(4); console.log(stack.pop().data); console.log(stack.pop().data); console.log(stack.pop().data); console.log(stack.pop().data); console.log("===두 번째 출력===="); stack.push(1); stack.push(2); stack.push(3); stack.push(4); console.log(stack.peek().data); stack.pop(); console.log(stack.peek().data); console.log(`isEmpty: ${stack.isEmpty()}`); stack.pop(); stack.pop(); stack.pop(); console.log(`isEmpty: ${stack.isEmpty()}`); console.log(stack.pop()); import { LinkedList } from "./LinkedList.mjs"; class Stack { constructor() { this.list = new LinkedList(); } push(data) { this.list.insertAt(0, data); } pop() { try { return this.list.deleteAt(0); } catch (e) { return null; } } peek() { return this.list.getNodeAt(0); } isEmpty() { return this.list.count == 0; } } export { Stack }; - 큐큐 - 개념리스트의 일종선입선출, FIFO운영체게가 프로세스를 큐에 넣고 CPU가 들어온 순서대로 실행구현의 개념삽입은 head에삭제는 tail에(tail : 마지막 노드 위치)tail삭제 후 이전 노드를 tail로 지정해야하기 때문에 이중연결리스트를 사용큐 - 구현class Node { constructor(data, next = null, prev = null) { this.data = data; this.next = next; this.prev = prev; } } class DoublyLinkedList { constructor() { this.head = null; this.tail = null; this.count = 0; } printAll() { let currentNode = this.head; let text = "["; while (currentNode != null) { text += currentNode.data; currentNode = currentNode.next; if (currentNode != null) { text += ", "; } } text += "]"; console.log(text); } clear() { this.head = null; this.count = 0; } insertAt(index, data) { if (index > this.count || index = this.count || index = this.count || index import { DoublyLinkedList } from "./DoublyLinkedList.mjs"; class Queue { constructor() { this.list = new DoublyLinkedList(); } enqueue(data) { this.list.insertAt(0, data); } dequeue() { try { return this.list.deleteLast(); } catch (e) { return null; } } front() { return this.list.tail; } isEmpty() { return this.list.count == 0; } } export { Queue };import { Queue } from "./Queue.mjs"; let queue = new Queue(); console.log("====== enqueue() 세 번 호출=========="); queue.enqueue(1); queue.enqueue(2); queue.enqueue(3); console.log(queue.front()); console.log("===== dequeue() 네 번 호출 ======"); console.log(queue.dequeue()); console.log(queue.dequeue()); console.log(queue.dequeue()); console.log(queue.dequeue()); console.log(`isEmpty: ${queue.isEmpty()}`); - 덱덱 - 개념덱은 삽입삭제를 head와 tail에서 자유롭게 하는 자료구조이다.덱을 이용하면 스택과 큐를 다 구현할 수 있다.덱 - 구현import { DoublyLinkedList } from "./DoublyLinkedList.mjs"; class Deque { constructor() { this.list = new DoublyLinkedList(); } printAll() { this.list.printAll(); } addFirst(data) { this.list.insertAt(0, data); } removeFirst() { return this.list.deleteAt(0); } addLast(data) { this.list.insertAt(this.list.count, data); } removeLast() { return this.list.deleteLast(); } isEmpty() { return this.list.count == 0; } } export { Deque };import { Deque } from "./Deque.mjs"; let deque = new Deque(); console.log("==== addFirst ====="); console.log(deque.isEmpty()); deque.addFirst(1); deque.addFirst(2); deque.addFirst(3); deque.addFirst(4); deque.addFirst(5); deque.printAll(); console.log(deque.isEmpty()); console.log("\n"); console.log("======== removeFirst ========="); deque.removeFirst(); deque.printAll(); deque.removeFirst(); deque.printAll(); deque.removeFirst(); deque.printAll(); deque.removeFirst(); deque.printAll(); deque.removeFirst(); deque.printAll(); console.log(deque.isEmpty()); console.log("\n"); console.log("========= addList========"); deque.addLast(1); deque.addLast(2); deque.addLast(3); deque.addLast(4); deque.addLast(5); deque.printAll(); console.log(deque.isEmpty()); console.log("\n"); console.log("=====removeLast===="); deque.removeLast(); deque.printAll(); deque.removeLast(); deque.printAll(); deque.removeLast(); deque.printAll(); deque.removeLast(); deque.printAll(); deque.removeLast(); deque.printAll(); console.log(deque.isEmpty()); - 해시테이블해시테이블 - 개념해시테이블은 언어마다 여러가지 이름으로 불린다해시맵해시맵딕셔너리이름처러 해시+테이블인 자료구조이다해시테이블은 key 와 value로 이루어져있고 삽입, 수정 등이 O(1)의 시간이 걸린다.장점빠른 데이터 탐색, 삽입, 삭제 등..단점공간의 효율성이 좋지 않다좋은 해시 함수의 구현이 필수적해시테이블 - 구현import { DoublyLinkedList } from "./DoublyLinkedList.mjs"; class HashData { constructor(key, value) { this.key = key; this.value = value; } } class HashTable { constructor() { this.arr = []; for (let i = 0; i import { HashTable } from "./HashTable.mjs"; let hashTable = new HashTable(); hashTable.set(1, "이운재"); hashTable.set(4, "최진철"); hashTable.set(20, "홍명보"); hashTable.set(6, "유상철"); hashTable.set(22, "송종국"); hashTable.set(21, "박지성"); hashTable.set(5, "김남일"); hashTable.set(10, "이영표"); hashTable.set(8, "최태욱"); hashTable.set(9, "설기현"); hashTable.set(14, "이천수"); console.log(hashTable.get(1)); hashTable.remove(1); console.log(hashTable.get(1)); console.log(hashTable.get(21)); - 셋셋 - 개념셋은 오직 데이터의 중복을 허용하지 않는 자료구조헤시 셋이라고도 불린다셋 - 구현import { HashTable } from "./HashTable.mjs"; class HashSet { constructor() { this.HashTable = new HashTable(); } add(data) { if (this.HashTable.get(data) == null) { this.HashTable.set(data, -1); } } isContain(data) { return this.HashTable.get(data) != null; } remove(data) { this.HashTable.remove(data); } clear() { for (let i = 0; i 0) { empty = false; break; } } return empty; } printAll() { for (let i = 0; i import { HashSet } from "./HashSet.mjs"; let hashSet = new HashSet(); console.log(hashSet.isEmpty()); console.log("=========add========="); hashSet.add(1); hashSet.add(1); hashSet.add(123); hashSet.add(512); hashSet.printAll(); console.log(hashSet.isEmpty()); console.log("=========check========="); console.log(hashSet.isContain(1)); console.log("=========remove========="); hashSet.remove(1); hashSet.printAll(); console.log(hashSet.isEmpty()); console.log("=========check2========="); console.log(hashSet.isContain(1)); console.log("=========clear========="); hashSet.clear(); hashSet.printAll(); console.log(hashSet.isEmpty());

인프런 워밍업 클럽 스터디 2기 CS 1주차 과제

운영체제 1.while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식을 폴링방식입니다.1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?답 : 인터럽트 프로그램과 프로세스가 어떻게 다른가요?답 : 간단하게는 프로그램은 그냥 코드 덩어리에 가깝고 그것을 실행하면 그것이 프로세스이다.자세히는 프로그램은 저장장치에 있으며 작동하지 않는 파일과 같은 수동적인 존재이다, 그 프로그램이 RAM으로 들어가서 실행되면 CPU도 사용하고 입출력 작업을 하여서 능동적인 존재가 된다. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?답 : 멀티프로그래밍은 메모리에 여러개의 프로세스를 올린 것을 뜻하고 멀티프로세싱은 CPU가 메모리에 있는 여러개의 프로세스를 실행하는 것을 뜻한다. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?답 : 운영체제는 프로세스를 관리하기 위해 스케쥴러, PCB, 컨택스트 스위칭, 인터럽트 등을 사용한다.PCB : 프로세스의 중요한 정보를 저장하는 데이터 구조, 프로세스 ID, 상태, 우선순위 등이 있다. 컨텍스트 스위칭이란 뭔가요? 답 : 콘텍스트 스위칭이란 여러개의 프로세스를 실행하는 작업을 말한다. 자세히는 현재 1,2번 프로세스를 실행하고 있다고 가정하였을 때, 일단 CPU에서 1번 프로세스를 실행한다. 언젠가 1번 프로세스가 CPU를 사용하는 시간이 정해진 시간을 초과하면 1번 프로세스의 PCB에 현재 CPU 세팅값을 저장한다, 그 다음 2번 프로세스의 PCB에 저장되어있던 세팅값을 CPU에 넣는다. 그러면 큰 준비 없이 바로 정지해있던 2번 프로세스를 실행 가능하다. 그 후 2번 프로세스도 정해진 사용 시간을 초과하면 PCB에 CPU세팅 값을 저장한 후 1번 PCB값을 가져온다. 이 작업을 컨텍스트 스위칭이라고 한다. 자료구조와 알고리즘여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.답 : 배열이유 : 일반적으로 교실의 학생은 자주 사라지거나 추가되지 않으며 조건이 한 교실이기 때문에 길이가 엄청난것도 아니어서 배열이 더 좋을것이다. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.답 : 큐이유 : 주문은 먼저(first) 들어온(in) 순서대로 먼저(first) 나가는(out) 구조이니 FIFO이다. FIFO를 사용 가능한 구조는 덱과 큐 2개인데 우리는 FIFO말고는 필요가 없으므로 큐를 사용하는 것이 더 좋을 것 같다.