블로그

최신순
인기순
좋아요순

[인프런 워밍업클럽 CS 2기] 3주차 미션

마지막 3주차 미션! 시작합니다 운영체제메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.레지스터 - 가장 빠른 기억장소로 CPU에 있어요. 휘발성 메모리입니다.캐시 - 레지스터와 메인 메모리 사이에 있는 휘발성 메모리입니다. 메인메모리에 있는 데이터를 미리 저장합니다.(메인)메모리 - 실제 운영체지와 다른 프로세스들이 올라가는 공간으로 휘발성 메모리입니다.보조기억장치(하드디스크,SSD) - 가격이 (상대적으로) 저렴하며 비휘발성메모리입니다. 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?경계 레지스터가 있어서 사용자 프로세스가 메모리의 운영체제 영역에 침범하게 되면 프로세스를 강제종료 시킬 수 있어요. 메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?가변분할 방식은 프로세스 크기에 맞는 메모리공간을 할당하는 방식입니다.내부단편화는 일어나지 않는다는 장점이 있지만 외부단편화가 발생할 수 있다는 단점이 있어요.고정분할 방식은 프로세스 크기에 상관없이 정한 크기만큼 공간을 할당하는 방식입니다.구현이 간단하고 오버헤드가 발생하지 않지만 내부단편화가 발생할 수 있다는 단점이 있어요. CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?스레싱이라고 합니다. 메모리 부족으로 페이지 폴트가 많이 발생하게 되어 대부분의 시간에 스왑을 하게 되는 현상입니다. HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요?이유를 함께 적어주세요.꼭 필요하다고 할 수는 없습니다. 일반적으로 HDD나 SSD에 운영체제를 설치하고 컴퓨터 부팅할 때 불러와서 동작을 합니다. 그러나 HDD나 SSD에서만 이러한 동작을 할 수 있는 것은 아니기 때문에 꼭 필요하지는 않습니다. 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?파일을 삭제하게 되면 파일시스템은 파일의 모든 정보를 지우는 것이 아니라 파일테이블의 헤더를 삭제하고 free block list에 추가합니다. 사용했던 블록을 이 리스트에 추가하기 때문에 사용했던 블록의 데이터는 그대로 남아있게 됩니다. 그렇기 떄문에 포렌식으로 파일을 복구할 수 있는 것입니다. 자료구조와 알고리즘지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.버블정렬, 선택정렬, 삽입정렬위 세 정렬은 구현이 쉽고 직관적이지만 성능이 좋지 않습니다.(O(n^2))병합정렬큰 문제를 작은 문제로 쪼개서 해결하기 때문에 성능이 좋습니다(O(nlogn). 그러나 정렬할 배열을 넣을 메모리가 필요하다는 것이 단점입니다.퀵정렬공간효율적이고 캐시친화적이며 병렬화도 가능합니다. 정렬 알고리즘 중 우수한 성능을 보입니다.(O(nlogn)에 근접한 성능)그러나 피벗을 잘못 선택한다면 성능이 저하되어 최악의 경우 성능이 O(n^2)이 될 수도 있습니다. 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요. 재귀로 쉽게 구현할 수 있다면 메모이제이션이 좋지만 메모이제이션은 메모리를 많이 사용한다는 문제가 있습니다. 메모리가 부족한 이슈가 있기 때문에 결과적으로는 타뷸레이션을 사용할 것 같습니다.

cs･자료구조･운영체제･미션

[발자국] 인프런 워밍업클럽 CS 2기 3주차 발자국

학습 했던 내용 요약자료구조 및 알고리즘 버블정렬장점 : 이해와 구현이 간단하다.단점 : 성능이 좋지 않다.시간 복잡도 : O(n²)선택 정렬장점 : 이해와 구현이 간단하다.단점 : 성능이 좋지 않다.시간 복잡도 : O(n²)삽입 정렬장점 : 이해와 구현이 간단하다.단점 : 성능이 좋지 않다.시간 복잡도 : O(n²)병합 정렬장점 : O(nlog n) 성능으로 버블, 선택 , 삽입 정렬보다 성능이 훨씬 좋다.단점 : 재귀적인 기법으로 이해하기 어렵고, 구현하기 어렵다.시간 복잡도 : O(n logn)퀵 정렬장점 : 성능이 좋고, 병합 정렬보다도 적은 메모리 공간을 차지해 더 좋은 알고리즘으로 평가 받는다.단점 : 재귀적인 기법으로 이해하기 어렵고, 구현하기 어렵다.시간복잡도 : O(n logn)메모이제이션계산 결과를 저장해서 여러번 계산하지 않도록 하는 기법계산 결과를 해시 테이블에 저장하고 재사용해 속도가 빠르다 .하향식 계산 방식으로 문제를 해결한다. 타뷸레이션계산에 필요한 모든 값을 전부 계산 후 테이블에 저장하는 기법상향식 계산 방식으로 문제를 해결한다. 운영체제가상메모리컴퓨터의 물리적 메모리의 크기를 확장하기 위해 사용되는 기술 동적주소변환 (Dynamic Address Translation)메모리 관리자가 물리 메모리와 스왑 영역을 합쳐서, 프로세스가 사용하는 가상 주소를 물리 주소로 변환하는 것가변분할 방식을 이용하는 세그멘테이션 기법메모리 관리자내에 있는 Segment Table Base Register를 이용해 세그멘테이션 테이블 찾아내고, 이를 이용해 논리 주소를 물리 주소로 변환한다. 메모리를 가변적으로 분할 할 수 있지만, 가변 분할의 단점인 외부 단편화가 발생한다 .고정분할 방식을 이용한 페이징 기법메모리를 할당 할 때 정해진 크기의 페이지의 나누는 기법으로 메모리 관리자 내에 Page Table Base Register를 이용해서 물리 메모리에 있는 페이지 테이블을 찾고 , 이를 이용해 논리 주소를 물리 주소로 변환한다. 페이징은 외부 단편화가 발생하지 않는 대신, 내부 단편화가 발생한다. 페이지드 세그멘테이션 세그멘테이션과 페이징을 혼합해 장점을 취한 방식으로물리 메모리에 접근하기 위해서 메모리에 접근을 두 번 해야 한다는 단점이 있다. 1. 세그멘테이션 테이블을 참조할 때 2. 페이지 테이블을 참조할 때디맨드 페이징 (가져오기 정책)조만간 필요할 것 같은 데이터를 메모리로 가져오고, 쓰이지 않을 것 같은 데이터는 스왑영역으로 이동시키는 정책페이지 테이블 엔트리 PTE 페이지 테이블을 이루고 있는 한 행페이지 테이블 엔트리는 프레임 넘버로 구성되어 있는데, 실제로는 접근 비트, 변경 비트, 유효 비트, 읽기-쓰기-실행 비트 등 더 많은 비트 들이 있다.Page Fault Page Fault는 프로세스가 가상 메모리에 있는 페이지에 접근하려고 할 때, MMU가 페이지 테이블을 참조하여 해당 페이지가 물리 메모리에 존재하는지 확인하는 과정에서, 물리 메모리에 해당 페이지가 없는 경우 발생하는 인터럽트다.페이지 교체 정책페이지 교체 정책은 메모리에 빈 공간이 없을 때, 어떤 페이지를 선택해서 스왑 영역으로 보낼지(스왑 아웃)를 결정하는 운영체제의 정책이다.스왑 인은 스왑 영역에서 물리 메모리로 페이지를 가져오는 것이고, 스왑 아웃은 물리 메모리에서 스왑 영역으로 페이지를 보내는 것이다. 이러한 스왑 인과 스왑 아웃의 적절성은 운영체제가 판단한다.Random 무작위로 선택하는 방법FIFO 메모리에 들어온 지 가장 오래된 페이지를 선택하는 방법 Optimum 앞으로 가장 오랫동안 쓰이지 않을 페이지를 선택하는 방법LRU (Least Recently Used) 최근에 가장 사용이 적은 페이지를 선택하는 방법 Clock 알고리즘 : 접근비트 하나만 이용하고, 일정 시간 간격마다 모든 페이지의 접근비트를 0으로 초기화 한다.Enhanced Clock Algorithm : 변경 비트까지 보는 향상된 Clock 알고리즘2차 기회 페이지 교체 알고리즘 : FIFO 방식에서 자주 사용되는 페이지에게는 또 한 번의 기회를 주는 것. FIFO 방식과 동일하게 동작하지만, 만약 Page Fault 없이 페이지 접근에 성공했다면, 해당 페이지를 큐에 맨 뒤로 이동시켜 수명을 연장시켜주는 방식스레싱CPU 사용률을 높이려 했지만 오히려 더 떨어지는 상황이 나오는 것워킹셋현재 메모리에 올라온 페이지는 다시 사용할 확률이 높기 때문에 하나의 세트로 묶어서 메모리에 올리는 것 워킹셋은 프로세스가 준비 상태에서 실행 상태가 되는 컨텍스트 스위칭을 할 때 사용된다.회고일주일 동안 스스로 칭찬하고 싶은 점일주일치 진도대로 인강을 다 수강하고, 미션과 발자국도 기한내에 진행한 점. 아쉬웠던 점며칠은 복습이 잘 되었고, 며칠은 복습은 잘 하지 못한 점 보완하고 싶은 점 이해가 어려웠던 부분들은 더 찾아보면서 이해해보기 다음주 학습 목표한번 배웠다고 끝내는 것이 아니라 계속해서 복습을 진행하기 출처 : 그림으로 쉽게 배우는 운영체제 - 감자 , 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)- 감자

알고리즘 · 자료구조･워밍업클럽･알고리즘･cs･운영체제･자료구조

[인프런 워밍업클럽 CS 2기] 2주차 미션

2주차 미션 시작합니다. 운영체제FIFO 스케줄링의 장단점이 뭔가요?FIFO 스케줄링은 스케줄링 큐에 들어온 순서대로 CPU를 할당받는 방식입니다.장점단순하고 직관적입니다.(들어온 순서대로 실행되고 나가면 끝!)단점실행시간이 짧은데 늦게 온 프로세스는 실행시간이 길고 먼저 온 프로세스를 기다려야 합니다. 순서대로 실행되어야 하기 때문이죠.만약에 입출력 작업이 먼저 와 있다면 입출력 작업이 끝날 때까지 CPU가 쉬어야해서 CPU 사용률이 감소한다는 단점이 있습니다. SJF를 사용하기 여러운 이유가 뭔가요?SJF(Shortest Job First)는 짧은 작업을 먼저 실행하는 알고리즘입니다.SJF에는 2개의 문제점이 있습니다.1) 어떤 프로세스가 얼마나 실행될지 예측하기 어렵다는 점2) Burst time이 짧은 프로세스가 중간에 계속 들어오면 긴 프로세스는 계속 뒤로 밀려 아주 오랫동안 실행되지 않을 수 있다는 점이런 문제점 때문에 SJF는 사용하기 어렵습니다. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?RR스케줄링에서 타임슬라이스가 아주 작으면 앱이 동시에 동작하는 것처럼 느낄 수 있습니다.그러나 단점으로는 오버헤드가 너무 커진다는 것입니다. Context Switching 처리량이 실행되는 프로세스 처리량보다 많기 때문에 이런 일이 발생하게 됩니다. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?CPU bound process는 대부분의 시간에 CPU연산을 하는 프로세스입니다.CPU를 많이 사용하기 때문에 CPU사용하는 프로세스가 실행하다가 CPU스케줄러에 강제로 CPU를 빼앗긴다면 운영체제는 CPU bound process로 판단합니다.I/O bound process는 대부분의 시간을 I/O작업으로 보내고 CPU연산을 조그맣게 합니다. CPU 사용이 적기 때문에 CPU사용하는 프로세스가 스스로 CPU를 반납한다면 운영체제는 CPU I/O process로 판단합니다. 공유자원이란무엇인가요?공유자원이란 프로세스 간 통신을 할 때 '공동으로 이용'하는 변수나 파일들을 의미합니다. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?교착상태에 빠지기 위해서는 아래 4가지로 이 조건들을 모두 충족해야 합니다.1) 상호배제한 프로세스가 한 리소스를 점유했다면 그 리소스는 다른 프로세스에서 공유될 수 없습니다.2) 비선점한 프로세스가 리소스를 점유할 때 다른 프로세스가 리소스를 뺏을 수 없습니다.3) 점유와 대기어떤 프로세스가 한 리소스를 가지고 있는 상태에서 다른 리소스를 원하는 상태입니다.4) 원형대기점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있어야합니다. 자료구조와 알고리즘재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?재귀함수에서 기저조건을 만들지 않거나 잘못 설정하면 재귀함수가 계속 호출되게 되고 메모리가 금방 가득 차서 프로그램 자동 종료되는 상황이 생길 수 있습니다. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.def sumOdd(n): if n<=0: return 0 if n % 2 == 1: #홀수 return n + sumOdd(n-2) else: return sumOdd(n-1) print(sumOdd(10))

미션･운영체제･알고리즘･자료구조･cs

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

지난 일주일 동안의 강의 내용 중 일부를 발췌했습니다. 자세한 내용은 개인 노션 페이지에 타이핑했습니다.자료구조와 알고리즘자료구조: 데이터가 어떤 구조로 저장되고 어떻게 사용되는지를 나타냄 예시: 변수, 배열알고리즘: 어떤 문제를 해결하기 위한 확실한 방법자료구조에 따라 알고리즘이 달라짐. 즉, 자료구조에 많은 영향을 받음같은 자료구조더라도 여러 알고리즘이 있을 수 있음시간 복잡도: 특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간특정 알고리즘의 성능을 평가할 때는 해당 알고리즘의 반복문을 보고 성능을 평가스택: First In Last Out(FILO): 먼저 들어간 데이터가 나중에 나온다.큐: First In First Out(FILO): 먼저 들어간 데이터가 먼저 나온다.덱: 데이터의 삽입과 제거를 head와 tail 두 군데서 자유롭게 할 수 있는 자료구조스택은 head에서만 처리할 수 있고, 큐는 head에서 삽입, tail에서 제거한다.해시테이블: 해시와 테이블이 합쳐진 자료구조테이블의 메모리를 적게 차지하고, 충돌이 덜 일어나도록 데이터를 골고루 분배시키는 좋은 해시 함수의 구현이 필수적운영체제커널프로세스와 메모리, 저장 장치를 관리하는 핵심적인 기능을 담당사용자는 커널에 직접 접근할 수 없으며, GUI/CLI를 통해 접근함 CPU를 구성하는 장치산술 논리 연산 장치: CPU에서 실제로 데이터 연산을 담당하는 장치제어 장치: 모든 장치들의 동작을 지시하고 제어하는 장치레지스터: CPU 내에서 계산을 위해 임시로 보관하는 장치메모리 종류램(RAM): 랜덤으로 데이터를 읽어도 저장된 위치와 상관없이 읽는 속도가 같음. 전력이 끊기면 데이터를 잃어버리기 때문에 메인 메모리로 사용롬(ROM): 전력이 끊겨도 데이터를 계속 보관할 수 있지만, 데이터를 한번 쓰면 수정할 수 없으므로, 컴퓨터의 부팅과 관련된 바이오스를 저장하는데 주로 사용멀티프로그래밍메모리에 여러 개의 프로세스가 올라온 것 멀티프로세싱유니프로그래밍, 멀티프로그래밍을 메모리 관점에서 정의했다면, 멀티프로세싱은 CPU 관점으로 정의한 것CPU가 여러 개의 프로세스를 처리하는 것컨텍스트 스위칭프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행 중인 프로세스의 상태를 저장하고 다른 프로세스의 상태 값으로 교체하는 작업컨텍스트 스위칭이 일어날 때 PCB의 내용이 변경된다.FIFO(First In First Out)먼저 들어온 작업이 먼저 나간다는 뜻으로, 스케줄링 큐에 들어온 순서대로 CPU를 할당받는 방식먼저 들어온 프로세스가 완전히 끝나야만 다음 프로세스가 실행될 수 있다.회고잘한 점강의 계획 일정에 따라 밀리지 않고 들었다. 애매했던 개념을 잘 정리할 수 있어서 좋았다.아쉬운 점정해진 일정의 강의만 생각하다보니 생각의 유연함이나 확장이 부족했다. 주말 동안에 시간을 내서 보충했는데, 평일에 강의를 들으면서 조금만 더 시간을 투자하면 주말엔 다른 공부나 휴식하는 데 쓸 수 있을 듯하다. 목표꾸준히 강의 듣고 학습하기강의를 보면서 타이핑한 내용을 한 번만 보는 게 아니라 두 세번 보면서 이해하기이전에 배웠던 내용도 꾸준히 복습하기미션(https://inf.run/yyYhZ)미션을 해결한 과정한 주 동안의 강의 내용을 정리한 것을 보면서 미션을 해결했다. 강의에서는 나오지 않았지만, 비슷한 예시는 해당 강의를 다시 보면서 힌트를 얻었다. 회고강의와 똑같은 내용이 미션에 나오기보다, 비슷한 유형을 낸 미션이었다. 처음 만났을 땐 막막했지만, 강의 내용을 되새겨보면서 힌트를 얻을 수 있었고, 해결했다. 이후 미션에 어떤 문제가 나올지 모르겠지만, 최대한 적용할 수 있도록 강의를 한 번 보고 끝내는 게 아니라 이해할 수 있도록 노력해야겠다.

발자국･워밍업클럽･cs

[미션] 인프런 워밍업 클럽 2기 CS 1주차

운영체제 인터럽트 방식을 사용하는게 좋을 것 같습니다. 인터럽트 방식을 사용하면 스킬 사용 시점에만 CPU가 작업을 처리하므로 불필요한 반복 체크를 없앨 수 있고, 이벤트가 발생할 때만 즉시 반응하므로 성능에도 효율적으로 사용할 수 있을 것 같습니다.프로그램은 컴퓨터 관점에서 저장장치만 사용하는 수동적인 존재이고, 프로세스는 메모리도 사용하고 CPU도 사용하고 필요에 따라 입출력을 하는 능동적인 존재입니다.멀티프로그래밍은 메모리의 관점에서 메모리에 여러 개의 프로세스가 올라온 것이고,멀티프로세싱은 CPU의 관점으로 CPU가 여러 개의 프로세스를 처리하는 것입니다.프로세스 제어 블록(PCB, Process Control Block)에 저장하고, 이를 프로세스 테이블이라는 데이터 구조로 관리합니다.프로세스를 실행하는 중에 다른 프로세스를 실행하기위해 실행중인 프로세스의 상태를 저장하고 다른 프로세스의 상태값으로 교체하는 작업이다.자료구조와 알고리즘저는 배열을 사용할 것 같습니다, 학생의 정보는 학기 초에 일괄로 받은 후 정리해서 저장을 하기 때문에, 정보가 바뀔 일이 많이 없기 때문입니다. 또한 학생의 수는 정해져 있기 때문에 인덱스로 관리도 용이할 것 같고, 데이터 참조시에는 O(1)의 시간복잡도를 가지고 있기 때문입니다. 크기도 고정이기에 학생의 수가 변동이 크지않기에 배열을 선택하는게 낫다고 생각하였습니다.주문이 들어온 순서대로 처리가 된다면 선입선출의 구조로 되어있는 큐(Queue)를 사용할 것 같습니다. 큐는 말 그대로 먼저 들어 온 것이 먼저 나가기 때문에, 문제의 "들어온 순서대로 처리"에 맞다고 생각합니다.

알고리즘 · 자료구조･알고리즘･자료구조･워밍업클럽･cs･운영체제

[발자국] 인프런 워밍업 클럽 2기 CS 1주차

자료구조와 알고리즘처음에는 막연하게 이해 못했던 것들도 강의를 듣다보니 이해가 되었고, 자료구조의 종류와 장단점을 알 수 있게 된게 좋았던것 같다. 매번 이유없이 그냥 사용했던 것들이 이제는 어떻게 실행이 되고, 어떤식으로 굴러가는지? 이런 상황에서는 어떤 자료구조를 사용해야하는지, 아직은 초반이라 한번 듣고 완전 이해한 건 아니지만 하나하나 공부해가는 재미가 있는 것 같다.배열 : 모든 프로그래밍 언어에서 기본적으로 제공하는 자료구조연결리스트 : 빈 메모리 공간 아무곳에 데이터를 생성하고 연결스택 : FILO(First In Last Out)큐 : FIFO(First In Fast Out)덱 : 양쪽에서 삽입과 삭제가 가능,스택과 큐의 연산을 모두 지원해시테이블 : (Key, Value)로 데이터를 저장셋 : 데이터의 중복을 허용하지 않는 자료구조 운영체제운영체제는 언제 한번 공부하고 싶었던 부분인데 좋은 기회로 듣게되어 오히려 자료구조보다 더 빨리 들었던 것 같다.운영체제의 구조는 어떻게 되어있는지 하드웨어가 뭔지 아직까지 처음 듣는 내용이지만서도 재밌게 듣고있다.회고칭찬하고 싶은 점ㅎㅎ ;; 아직 없다 ..아쉬웠던 점내일배움캠프와 같이 진행중이라, 시간이 많지않아 강의를 매일매일 챙겨보지못해 밀리는게 매우 아쉽다.또한 아직까지 기본적인 개념이 자리잡지 않은 것 같은 느낌이 들었다.보완할 점새벽까지하더라도 밀리지 않게 강의를 듣는게 좋을 것 같다. 또한 내용은 여러번 반복해서 !평일에 밀리지 않게 들은 후 주말에는, 저번 주에 들었던 내용 + 이번 주 내용 배속으로 한번 더 듣는걸로 해야겠다.

알고리즘 · 자료구조･워밍업클럽･운영체제･알고리즘･자료구조･cs･cs스터디

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

운영체제 1주차 학습 요약 운영체제운영체제는 컴퓨터를 유연하게 동작시키기 위해 필요하다.운영체제가 하는일프로세스를 관리 (여러 프로그램을 동작시킴)메모리를 관리 (프로그램은 메모리에 올라감)하드웨어 관리 (사용자의 하드웨어에 대한 직접 접근을 막음)파일 시스템 관리 (하드디스크에 많은 파일들을 효율적으로 저장&관리)운영체제의 구조커널 - 프로세스와 메모리, 저장장치를 관리하는 핵심적인 기능을 담당인터페이스 - 사용자가 시스템과 상호작용을 도와주는 외부 인터페이스시스템 콜 - 커널은 사용자 애플리케이션과 커널이 소통할때 사용되는 내부 인터페이스 (커널을 보호)드라이버 - 하드웨어와 커널간의 인터페이스폰노이만 구조CPU와 메모리를 분리하고 프로그램을 메모리에 올려서 실행하는 구조인터럽트인터럽트는 폴링 방식의 단점을 해결하기위해 CPU가 현재 진행중인 작업을 일시중단하고 외부에서 발생한 이벤트를 처리하기위해 서비스루틴을 실행하는 매커니즘프로세스프로그램이 메모리에 올라가서 CPU 할당의 대상이 되는 능동적인 존재프로세스의 구조코드영역(실제 코드), 데이터영역(전역변수, 정적변수), 스택영역(지역변수, 함수), 힙영역 (객체 등, 런타임시 동적인 메모리를 할당할 수 있는 공간)컴파일 과정test.c -> 전처리기 -> test.i -> 컴파일러 -> test.s(어셈블리어) -> 어셈블러 -> test.o(기계어) -> 링커(라이브러리 연결) -> test.exe프로세스 컨트롤 블록 (PCB)운영체제는 여러개의 프로세스를 관리하고 공평하게 CPU를 할당하기 위해 프로세스 정보를 담은 PCB를 만들고 저장함식별자, 프로세스 상태, 프로그램카운터, 레지스터 정보등을 저장프로세스 상태생성, 준비, 실행, 대기, 완료컨텍스트 스위칭프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행중인 프로세스를 저장하고 다른 프로세스의 상태값으로 교체하는 작업쓰레드한 프로세스 내에서 동시에 각자 실행될 수 있는 작업 흐름의 단위기본적으로 프로세스 1개에는 1개의 쓰레드가 존재쓰레드끼리는 스택영역을 제외한 다른 영역은 공유해서 사용, 프로세스에 할당된 Virtual Memory로 공간이 제약됨공유하는 영역을 통해 메모리 낭비를 줄이고 쓰레드끼리 소통할때 비용이 적게 들지만, 안정성이 떨어짐CPU 스케쥴링운영체제는 CPU를 여러 프로세스에 할당/해제 하는 것을 CPU 스케쥴링이라고 함다중 큐준비, 대기 상태의 프로세스는 다중 큐 자료구조에서 관리다중큐에는 정확하게는 프로세스의 정보를 가진 PCB가 저장CPU 스케쥴링 알고리즘FIFO (First In First Out)스케쥴링 큐에 들어온 순서대로 CPU를 할당 받는 방식한 프로세스가 완전히 끝나야 다음 프로세스가 시작되고, I/O작업시 I/O작업이 끝날때까지 CPU가 대기하는 단점이 있음프로세스의 BURST TIME에 따라 성능차이가 심하게 나기 때문에 잘 쓰이지 않고, 일괄처리 시스템에서 쓰임 알고리즘 & 자료구조 1주차 학습 요약 알고리즘어떤문제를 해결하기 위한 구체적이고 확실한 방법자료구조데이터를 효율적으로 저장하고 사용할 수 있도록 정리하는 방법상황에 맞는 적절한 자료구조를 선택하고 이에 맞는 적절한 알고리즘을 적용할 수 있어야 한다.시간복잡도더 좋은 알고리즘이란 무엇일까? 메모리를 더 적게 사용하는 것? 속도가 빠른 것?입력값이 달라지더라도 동일하게 알고리즘의 속도를 표현하는 방법이 시간복잡도입력값에 따른 변화의 추이를 나타내는 방법중에 최악의 경우를 기준으로 표기하는 빅 오 표기법이 가장 많이 사용됨배열동일한 데이터 타입의 요소들을 연속된 메모리 공간에 저장하는 자료구조읽기, 쓰기와 같은 참조에는 O(1)의 성능을 가짐그러나 데이터 삽입, 삭제에서는 데이터 복사, 이동등이 일어나 비효율적임또한, 고정된 크기로 배열을 생성해야함연결리스트배열의 단점은 연속된 메모리공간이 필요하다는 것과 초기 배열의 크기를 모르면 메모리가 낭비될 수 있다는 점임연결리스트에 데이터를 추가한다면 빈 메모리 공간에 데이터를 생성하고 연결만 해주면 됨연결리스트는 요소 접근시 첫번째 노드부터 이동하면서 찾아야함, O(N)배열 VS 연결리스트배열은 메모리 크기가 고정이고, 연속된 주소에 할당되는 단점, 그러나 인덱스 접근으로 인해 참조는 매우 빠름 연결리스트는 초기 크기를 알 필요없이 데이터를 생성하고 연결만 해주면 됨대신 인덱스 접근이 느림 (첫번째 노드부터 이동하면서 찾아야 함)스택먼저 들어간 데이터가 가장 마지막에 나가는 First In Last Out의 자료구조큐먼저 들어간 데이터가 가장 먼저 나오는 First In First Out의 가료구조덱데이터 삽입과 제거를 앞과 뒤 모두에서 자유롭게 사용할 수 있는 자료구조덱을 이용하면 스택과 큐 모두 구현 가능해시테이블해시 함수에 의해 생성된 해시값을 인덱스로 사용하여, key, value 쌍으로 저장됨해시충돌서로 다른 입력값이 동일한 해시값을 갖는 상황체이닝충돌이 발생한 경우, 동일한 해시값을 갖는 여러개의 항목을 연결리스트로 저장 (실제로는 레드블랙트리) 해시테이블의 장.단점장점 : 빠른 데이터 읽기, 삽입, 삭제 - O(1)의 성능단점 : 메모리를 많이 차지함 (좋은 해시함수는 필수)셋데이터의 중복을 허용하지 않는 자료구조 (순서를 보장하지 않고 중복을 허용하지 않음) 회고1주일동안 CS 전공지식 스터디를 하면서 부족한 것을 채우면서 많이 공부하게 된 것 같아요. 다른사람들이 어떻게 공부하고 있는지, 그리고 미션을 통해 가장 중요하게 알고 넘어가야 하는 부분들을 집어주셔서 확실히 개념이 잡히는 것 같아요.스터디를 진행하면서 전공자임에도 스스로 알고 있다라고 생각했던 것들이, 생각보다 잘 모르고 있구나 라는 반성을 많이 하게 된 것 같습니다. 스터디와 강의로 통해서 개념을 다시 정리할 수 있게되어 너무 좋았어요. 특히, 운영체제 부분 프로세스의 상태 전환 하는 부분에서 많이 배운 것 같네요.개발을 할 때 필요한 기본 지식들, 알고리즘 그리고 자료구조들은 평생 사용하는 것들인데 스터디를 통해 많은 것들을 얻는 것 같아요. 이제 2주 남았는데요. 짧다면 짧은 기간이지만 함께 달려서 완주했으면 좋겠습니다.

백엔드･인프런워밍업클럽2기･cs･발자국

[인프런 워밍업클럽 2기] CS전공지식_Mission01

운영체제while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다.1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요? 이런 풀링 방식의 경우 계속 매초마다 확인을 하니까 효율이 좋지 못하다.이전에 서버에게 클라이언트에서 로그인 인증 됬는지 처리하기 위해 계속 해서 switch 문에 들락날락 처리 되도록 한적이 있는데. 확실히 삑나간적이 있었다.이럴때 필요한게 인터럽트 인데 일종의 대기상태 라고 생각하면 될 것 같다.CPU는 다른 작업을 실행시키거나 하여 잠시 대기시키고 해당 작업이 완료되는 시점에 신호를 받아 완료 시킨다. 언리얼엔진에서도 비슷하게 조건을 주어 매초마다 주는 Tick 발생을 제어하는 것들이 있는데.상태머신에서도 볼 수 있는 현상이다.조건을 주어 다른 것이 실행되게 하고 입력값이 들어오면 그때서야 실행하는 것이다. 인터럽트도 일정 입력이 들어올 때까지 작동하지 않고 들어오면 인터럽트에 의해 다른 업무를 시키고 그 업무로 들어가게 한다. 해결방법인터럽트 핸들러 : 특정이벤트가 발생했을 때 인터럽트가 발생하도록 처리 CPU는 대기상태에서 벗어나서 해당 이벤트를 즉시 실행상태 플러그 : 인터럽트 핸들러에서 상태 플래그를 설정하고 loop에서 이 플래그를 체크하여 작업을 수행하도록 volatile bool skillActivated = false; void interruptHandler() { skillActivated = true; // 인터럽트 발생시 플래그 } while(1) { if (skillActivated) { skillActivated = false; // 플래그 초기화 } // 다른 작업 수행 }우선 순위 관리를 통해 중요한 이벤트 부터 처리타이머 사용 : 주기적인 작업시 타이머 설정해서 일정 시간마다 인터럽트 처리다용도 입출력(GPIO)핀의 변화를 감지해서 인터럽트 발생등등 2. 프로그램과 프로세스가 어떻게 다른가요?프로그램 명령문의 집합체일종의 실행파일같이 .exe 형태로 이루어짐컴퓨터의 관점에서 저장장치만 사용하는 수동적 존재 프로세스실행중인 프로그램저장장치에서 프로그램이 메모리에 올라간 것메모리도 사용하고 운영체제 CPU 스케줄링에 따라 CPU도 사용됨, 능동적인 존재이다. 3. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티 프로그래밍메모리에 여러개의 프로세스가 올라온 것 멀티 프로세싱CPU가 여러개의 프로세스를 처리하는 것 -> 오늘날 멀티프로세싱 프로그래밍이 전부다 쓰인다.메모리에는 여러개의 프로세스가 올라오는 멀티프로그래밍, 시분할 처리로 CPU가 각각의 프로세스를 짧은 시간동안 교대로 실행하는 멀티프로세싱이 있다. (동시에 실행된다는 개념이 아니다) 4. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?운영체제는 프로세스가 만들어지면 해당 프로세스의 정보를 가지고 있는 PCB를 만든다. 이것은 연결리스트 자료구조 마냥 저장되어있는데. 프로세스가 종료되면 해당 리스트에서 프로세스의 PCB를 제거합니다. 그러면서 연결리스트의 구조는 그대로 유지 합니다. PCB의 구조는포인터프로세스 상태프로세스 ID프로그램 카운터레지스터 정보메모리관련정보CPU스케줄링 정보 등 PCB내부에서 여러개의 동작이 실행되어 운영체제에 의해 관리됩니다. 5. 컨텍스트 스위칭이란 뭔가요? 프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행 중인 프로세스를 저장하고 다른 프로세스의 상태값으로 교체는 작업을 - 컨텍스트 스위칭 이라고 한다. 컨텍스트 스위칭은 PCB의 내용이 변경된다.실행중인 프로세스의 작업내용을 PCB에 저장하고 실행될 기존 프로세스의 PCB의 내용대로 CPU가 다시 셋팅 된다. 컨텍스트 스위칭이 발생시 PCB의 변경 값 프로세스 상태프로그램 카운터 : 다음 실행할 명령어 주소레지스터 값 & 메모리관련 정보 : 각종 레지스터의 값 정보 발생 이유 CPU 점유시간이 다 되거나 입출력 요청이 있거나다른 종류의 인터럽트가 있을 때 발생할 때 자료구조와 알고리즘1. 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.학생 정보를 저장하기 위해 구조체와 벡터를 결합해 사용할 수 있을 것 같다. 구조체는 학생 정보를 표현하고, 벡터는 여러 학생 정보를 동적으로 저장할 수 있다. C++에서는 이러한 것이 STL에 컨테이너로 되어 사용가능하다.사용이유구조체 사용 : 학생 정보를 하나의 단위로 묶어 관리하기 위해 구조체를 사용학생의 이름나이학생ID등의 속성을 쉽게 다룰 수 있다. 벡터 사용 : 벡터는 동적 배열로, 학생 수가 변동 될 수 있는 상황에 유용하다. 학생을 추가하거나 삭제할 때 유연하게 대처가능 하다. #include <iostream> #include <iomanip> #include <string> #include <vector> using namespace std; struct Student { // 기본적으로 구조체는 기본적으로 public string name; int age; string studentId; // 구조체 변수 초기화 Student(string n, int a, string id) : name(n), age(a), studentId(id) {} }; class StudentManager { public: void AddStudent(const string& name, int age, const string& studentId) { vStudents.emplace_back(name, age, studentId); // 객체내 인자만받아 함수 내에서 객체 생성해 삽입 - emplace_back 생성자 한번만 호출 } /*width() 또는 iomanip/ setw()로 정리*/ void DisplayStudents() const { for (const auto& student : vStudents) { cout << "| " << "Name: " << student.name << " |" << setw(6) << "Age: " << student.age << " |" << setw(13) << "Student ID: " << student.studentId << " |" << endl; } } private: // 공개가 필요없는 vector<Student> vStudents; }; int main() { StudentManager manager; manager.AddStudent("홍길동", 20, "20230001"); manager.AddStudent("인프런", 21, "20230002"); manager.AddStudent("감자 ", 25, "20230003"); cout << "학생정보: " << endl; manager.DisplayStudents(); return 0; } 2. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.큐(Queue)자료구조를 사용해서 FIFO방식으로 데이터를 처리하므로 주문이 들어온 순서대로 처리할 수 있습니다. STL에 queue를 사용할 수 있습니다.사용이유FIFO : 선입선출 방식, 주문이 들어온 순서대로 처리할 수 있어서 주문관리에 적합합니다. 고객 대기 시간을 최소화할 수 있습니다. (단. 끼어들기 금지)간편한 관리 : C++STL 제공하기에 복잡한 구현없이 간편하게 큐를 관리 확장성 : 새로운 주문 추가또는 기존 주문을 처리하는 과정이 명확해서 확장및 유지보수 용이 /*여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요. */ #include<iostream> #include<queue> #include<string> using namespace std; typedef struct Order { string customerName; // 고객이름 string item; // 주문한 물건 int quantity; // 주문 수량 int price; // 주문 가격 int Sum; // 주문 총 가격 // 각 변수 초기화 Order(string name, string itm, int qty, int pri, int sum) : customerName(name), item(itm), quantity(qty), price(pri), Sum(sum) {} } Orderinfo; class OrderManager { public: void AddOrder(const string& name, const string& item, int quantity, int price, int Sum) { Sum = (price * quantity); orders.emplace(name, item, quantity, price, Sum); // 새로운 주문 객체를 큐에 추가 } void ProcessOrder() // 주문 처리 { // 큐에 주문이 있는가? if (!orders.empty()) { Order currentOrder = orders.front(); // 현재 처리할 주문을 큐의 앞에서 가져온다. orders.pop(); // 주문을 큐에서 제거 // 처리 중인 주문 정보 출력 cout << "Processing order for |"; cout << currentOrder.customerName << ": " << currentOrder.item << ": " << currentOrder.quantity << " | " << currentOrder.price << " | " << currentOrder.Sum << " | " << endl; } else { cout << "No orders to process. " << endl; // 주문이 없을 때 } } // 큐에 주문이 있는지 확인 bool bfHasOrders() const { return !orders.empty(); // 큐가 비어있지 않으면 true반환 } private: // 주문을 저장할 큐 queue<Order> orders; }; int main() { OrderManager manager; // 주문 추가 manager.AddOrder("김감자", "토마토", 2, 3000, NULL); manager.AddOrder("인프런", "바나나", 1, 2000, NULL); while (manager.bfHasOrders()) { manager.ProcessOrder(); // 주문처리 } return 0; }

cs-미션･인프런워밍업클럽2기･빠타박스･인프런･cs･자료구조･알고리즘･운영체제

[인프런 워밍업 클럽_3기 CS] 3주차 운영체제 미션 🐾🐾🐾

1. 메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.레지스터 : CPU 내부의 가장 빠른 기억 장치 (휘발성) • 32bit, 64bit는 레지스터 크기를 의미캐시 : CPU가 미리 가져온 데이터를 저장하는 고속 휘발성 메모리메인 메모리 (RAM) : 운영체제와 프로세스가 올라가는 공간 (휘발성)보조 저장 장치 (HDD, SSD) : 비휘발성 메모리 2. 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?경계 레지스터 (Boundary Register)• CPU 내에 존재하며, 프로세스가 허용된 메모리 경계를 벗어나는지 검사• 벗어나면 프로세스를 종료 3. 메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?1. 가변 분할 방식 (세그멘테이션, Segmentation) 장점 : 프로세스 크기에 맞게 메모리를 할당 단점 : 외부 단편화 발생2. 고정 분할 방식 (페이징, Paging) 장점 : 프로세스 크기와 관계없이 일정한 크기로 메모리를 할당 비연속 메모리 할당 가능 단점 : 내부 단편화 발생 4. CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?스레싱 5. HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요? 이유를 함께 적어주세요.필요하다고 생각을 합니다.운영체제를 저장하고 실행하거나 사용자의 데이터를 비휘발성으로 저장해야하기에 HDD나 SSD가 필요하다고 생각됨. 6. 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?특정 파일을 삭제하는 경우에 파일 시스템은 파일의 모든 정보를 지우는 것이 아니라 파일 테이블의 헤더를 삭제하고 free block list에 추가하기 때문입니다.

인프런워밍업클럽･cs

[인프런 워밍업 클럽_3기 CS] 3주차 자료구조와 알고리즘 미션 🐾🐾🐾

1. 지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요. 버블 정렬 시간 복잡도 : O(n²) 장점 : 이해와 구현이 간단함 단점 : 성능이 좋지 않음선택 정렬 시간 복잡도 : O(n²) 장점 : 이해와 구현이 간단함 단점 : 성능이 좋지 않음삽입 정렬 시간 복잡도 : O(n²) 장점 : 이해가 쉽고 구현이 간단함. 단점 : 성능이 좋지 않음.병합 정렬 시간 복잡도 : O(n log n) 장점 : 성능이 좋음. 단점 : 이해와 구현이 어려움.퀵 정렬 시간 복잡도 : O(n log n) 장점 : 성능이 좋음. 단점 : 이해와 구현이 어려움. 2. 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요. 타뷸레이션을 이용한다.타뷸레이션은 상향식 접근으로 구현되기 때문에 메모리를 절약할 수 있고, 속도가 빠르기 때문에 효율적으로 사용할 수 있을 거 같습니다.

인프런워밍업클럽･cs

[워밍업 클럽 CS 3기] 1주차 발자국

운영체제운영체제에 대해서 운영체제는 프로세스 관리, 메모리 관리, 하드웨어 관리, 파일 시스템 관리 등의 역할을 함커널은 프로세스와 메모리를 관리 역할 (사용자 - 인터페이스, 애플리케이션 - 시스템콜, 하드웨어 - 드라이브)폰 노이만 구조 - CPU와 메모리 사이를 버스(데이터 전달 통로)로 연결하는 구조CPU는 ALU(산술논리연산장치), 제어장치, 레지스터로 구성폴링 방식은 CPU가 주기적으로 확인이 필요, 인터럽트는 입출력 관리자가 작업이 완료되면 ISR을 실행시켜 작업프로세스와 스레드프로그램은 하드 디스크에 저장된 명령문의 집합체, 프로세스는 실행중인(메모리에 올라간 상태) 프로그램프로그램은 수동적이지만, 프로세스는 능동적으로 필요에 따라 CPU를 사용하고 입력 출력을 함.프로세스의 구조(Code, Data, Heap, Stack) 멀티프로그래밍과 멀티프로세싱(유니프로그래밍의 단점 보완)멀티 프로그래밍: 메모리에 여러개의 프로세스 올려서 처리멀티태스킹: 서로 다른 프로세스를 짧게씩 실행하며 동시에 처리하는것처럼 보이게 함CPU가 여러개라면 멀티프로세서, 이렇게 작업하는 건 멀티프로세싱PCB(Process Control Block) - 프로세스의 정보 저장(연결리스트 구조)프로세스의 상태 (생성, 준비, 실행, 대기, 완료)컨텍스트 스위칭다른 프로세스 실행을 위해 프로세스 상태를 저장하고 다른 프로세스 상태값으로 교체프로세스 생성 시에 기존의 프로세스를 fork로 복사해서 사용(자식 프로세스)쓰레드 - 한 프로세스 내에 여러개 있을 수 있으며, PCB, 데이터, 코드, 힙영역을 공유(스택은 고유)TCB(Thread Control Block), TID(쓰레드 아이디)프로세스는 독립적이어서 안정적, 쓰레드는 프로세스에 문제가 생기면 전체 문제 생겨서 불안정적프로세스는 고유한 영역, IPC로 통신해 오버헤드 큼, 쓰레드는 데이터 공유가 가능해 오버헤드가 작음CPU 스케쥴링준비, 대기 상태는 큐로 관리PCB는 다중 큐에 들어가서 준비 상태, CPU 스케쥴러가 결정해서 실행 상태로 전화시킴목표: 리소스 사용률, 오버헤드 최소화, 공평성, 처리량, 대기시간, 응답시간스케쥴링 알고리즘FIFO: 먼저 들어온 순서대로 작업(실행시간에 따라 유동적으로는 작업X, I/O작업으로 인한 비효율)SJF(Shortest Job First): 짧은 작업 먼저(시간 예측 힘듦, 긴 프로세스는 너무 오래 대기)RR(Round Robin): 모두 공평한 Time Slice를 쓰고 다음 프로세스에게 뺏김(컨텍스트스위칭 시간 고려 필요)MLFQ(Multi Level Feedback Queue): Time slice를 작게 쓰고, 프로세스의 구분에 따라 다르게 줌자료구조와 알고리즘자료구조와 시간 복잡도자료구조는 데이터가 어떤 구조로, 저장, 사용되는지 나타냄알고리즘은 문제를 해결하기 위한 방법(자료구조에 영향을 받음)시간 복잡도란 특정 알고리즘이 문제를 해결하는데 걸리는 시간 (반복문을 최소화 하는 것이 목표)big-O 표기법은 계산량이 얼마나 늘었는지 표현법이므로 정확하지 않음(상수는 무시, 가장 큰 영향의 숫자만 표기)배열운영체제는 배열의 주소를 기억하고 데이터를 가져옴인덱스 참조는 길이에 상관X, 한번에 가져오기 때문에 높은 효율 -> O(1) 그러나 삽입, 삭제 성능은 좋지않음연결리스트데이터를 분산 저장 후 서로 연결 (노드를 사용)추가, 삭제는 데이터 연결 부분을 수정만 하면 되서 간단, 참조는 다 따라가서 봐야해서 효율 나쁨스택FILO구조, 먼저 들어간 데이터가 나중에 나옴배열, 연결리스트로 구현 가능(head사용)큐FIFO구조, 먼저 들어간 데이터가 먼저 나옴먼저 들어간 데이터 삭제시, head부터 다 따라가야 나오므로, tail추가 해서 구현tail에 있는걸 삭제해도 tail도 업데이트가 필요하므로 양방향 변경 필요덱데이터 삽입, 삭제를 head와 tail에서 자유롭게 가능해시테이블인덱스로 배열에 접근(빈공간 발생 가능), 특정 숫자를 배열에 넣기 위해 하는 연산인 해시 함수 필요하나의 인덱스에 여러개의 데이터 들어가는 문제 발생시, 연결리스트로 해결 가능데이터 삽입, 탐색, 삭제가 효율적이나 공간 효율이 나쁘고 해시 함수 구현이 필수적셋데이터 중복을 허용하지 않는 자료구조value는 사용X, Key만 사용 칭찬할 점: 강의를 여러번 들은 게 잘한 것 같습니다. 2~3번 정도 들으니 머리에 더 잘 들어오는 것 같아요.보완할 점: 목~금에 강의가 좀 밀렸습니다. 앞으론 밀리는 일 없게 오며가며 계속 들어야 할 것 같습니다.다음 주 목표: 다음주에는 자바스크립트 공부를 좀 더 해서 자료구조 부분은 제가 복습하면서 더 활용해보고 싶습니다.

워밍업클럽･cs

[워밍업 클럽 3기 - CS 전공 지식] - Day 9 미션 2

운영체제FIFO 스케줄링의 장단점이 뭔가요?장점단순하고 이해하기 쉽다단점실행 시간(burst time)이 짧은 프로세스는 실행 시간이 길더라도 일찍 도착한 프로세스의 완료를 기다려야한다 SJF를 사용하기 여러운 이유가 뭔가요?A. 프로세스의 실행시간을 예측하기 어렵다. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?A. 컨텍스트 스위칭을 처리하는 비용이 증가한다. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?A. CPU 사용시간에 따라 우선순위 큐에 다르게 배치하면서 구분한다. 예를 들어, CPU 바운드 작업은 타임 슬라이스를 I/O 바운드 작업보다 오래 점유해서 사용하기 때문에, 우선순위가 낮은 큐에 배치시키고, 더 짧게 사용하는 I/O 바운드 프로세스는 우선순위가 더 높은 큐에 배치시킨다. (타임 슬라이스를 사용하는 시간과 요청 빈도에 의한 피드백) 공유자원이란 무엇인가요?A. 프로세스간 통신에서 공통으로 접근해서 이용하게 되는 데이터. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?상호 배제: 자원은 한번에 하나의 프로세스만 사용비선점: 이미 점유한 자원은 다른 프로세스가 뺏어갈 수 없다점유와 대기: 이미 자원을 점유한 프로세스가 추가적인 자원을 기다리는 상태원형 대기: 프로세스들이 서로가 가지고 있는 자원을 기다리며 대기하는 상태자료구조와 알고리즘재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?A. 함수에서 탈출하지 못하기 때문에 무한하게 재귀를 호출하게 되면서 스택 오버플로우(StackOverflow)가 발생한다.0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.A.function sumOdd(n) { if (n <= 0) return 0; // 기저조건 if (n % 2 === 0) return sumOdd(n - 1); return n + sumOdd(n - 2); } console.log(sumOdd(10)) // 25 다음 코드는 매개변수로 주어진 파일 경로(.는 현재 디렉토리)에 있는 하위 모든 파일과 디렉토리를 출력하는 코드입니다. 다음 코드를 재귀 함수를 이용하는 코드로 변경해보세요.import fs from "fs"; import path from "path"; function traverseDirectory1(directory){ const stack = [directory]; // 순회해야 할 디렉토리를 저장할 스택 while (stack.length > 0) { // 스택이 빌 때까지 반복 const currentDir = stack.pop(); // 현재 디렉토리 const files = fs.readdirSync(currentDir); // 인자로 주어진 경로의 디렉토리에 있는 파일or디렉토리들 for (const file of files) { // 현재 디렉토리의 모든 파일or디렉토리 순회 const filePath = path.join(currentDir, file); //directory와 file을 하나의 경로로 합쳐줌 const fileStatus= fs.statSync(filePath); // 파일정보 얻기 if (fileStatus.isDirectory()) { // 해당 파일이 디렉토리라면 console.log('디렉토리:', filePath); stack.push(filePath); } else { // 해당 파일이 파일이라면 console.log('파일:', filePath); } } } } traverseDirectory1("."); // 현재 경로의 모든 하위 경로의 파일, 디렉토리 출력 console.log("------------------------"); function traverseDirectory2(directory){ const files = fs.readdirSync(directory); // 현재 디렉토리의 파일 목록 가져오기 for (const file of files) { const filePath = path.join(directory, file); // 파일 또는 디렉토리의 전체 경로 const fileStatus = fs.statSync(filePath); // 파일정보 얻기 if (fileStatus.isDirectory()) { // 해당 파일이 디렉토리라면 console.log('디렉토리:', filePath); traverseDirectory2(filePath); // 재귀 호출하여 내부 탐색 } else { // 파일인 경우 console.log('파일:', filePath); } } } traverseDirectory2("."); // 현재 경로의 모든 하위 경로의 파일, 디렉토리 출력

워밍업클럽3기･cs･미션

인프런 워밍업 클럽 스터디 3기 - CS 전공지식(운영체제) -2주차 미션-

1. 선입선출(FIFO)의 장단점장점스케쥴링의 이해와 구현이 단순하다.자원의 효율성이 높다.단점실행시간이 긴 프로세스가 앞에서 장시간 독점하는 경우 다른 프로세스들이 오래 대기해야한다.평균 응답 시간이 길어질 수 있다.2. 최소작업 우선 - SJF(Shortest Job First)을 사용하기 어려운 이유준비큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식이다.그러므로 실행 시간이 긴 프로세스들이 무한정 대기하는 현상이 발생한다.3. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?라운드 로빈 스케줄링준비 큐에 가장 먼저 삽입된 프로세스부터 시작하여순서대로 프로세스에 CPU자원을 할당해서 실행실행할 때마다 일정하게 정해진 시간만큼만(time slice) 실행하고 다음 프로세스로 CPU자원을 넘겨주는데, 이 정해진 시간을 너무 작게(짧게) 설정하면 프로세스 간의 CPU 사용 교체가 빈번해져 실행 프로세스 교체에 소요되는 리소스가 과도해짐에 따라 오버헤드가 발생한다.4. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?일반적으로 연산이 많이 필요한 로직은 CPU Bound로컬 파일 시스템 혹은 네트워크 통신이 많은 로직은 I/O Bound 라고 한다.여기서 프로세스 수행과정 중에 CPU burst , I/O burst가 계속 변경, 수행되며 프로세스 작업의 종류에 따라 각자가 일어나는 시간이 달라진다.이 때 CPU burst가 많이 일어나는 작업을 CPU Bound Process라고 하고 I/O burst가 많이 일어나는 작업을 I/O Bound Process라고 한다. 버스트 여기서 버스트란 연속된 신호 또는 데이터의 모임, 어떤 현상이 짧은 시간에 집중적으로 일어하는 현상을 뜻하거나 주기억 장치의 내용을 캐시 기억 장치에 블록 단위로 한꺼번에 전송하는 것을 뜻한다.CPU BoundCPU Bound는 프로세스가 진행될 때, CPU 사용 시간이 I/O Waiting 보다 많은 경우이다. 그러므로 CPU의 성능에 의해 작업 속도가 결정된다.I/O Bound프로세서가 진행될 때 I/O Waiting이 많은 경우이다.파일 쓰기, 디스크 작업, 네트워크 통신을 할 때 주로 나타나며5. 공유자원이란 무엇인가요?시스템 내에서 여러 프로세스나 스레드가 함께 접근할 수 있는 자원이다.메모리, 파일, 데이터 등을 말한다.공유자원은 공동으로 이용되기 때문에 누가 언제 데이터를 읽거나 쓰느냐에 따라 그 결과가 달라질 수 있다.6. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?교착상태는 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다리는데 무한 대기 상태에 빠지는 상황을 일컫는다.즉, 한정된 자원을 여러 곳에서 사용하려고 함으로써 다음 처리를 하지 못하는 상태이다.요약멀티 프로그래밍 환경에서 한정된 자원을 얻기 위해 서로 경쟁한 프로세스가 자원을 점유하고 있다면 동시에 다른 자원이 사용할 수 없는 상황 발생이 때 점유하지 못한 다른 프로세스는 대기 상태로 들어감.대기 상태로 들어간 프로세스들이 실행 상태로 변경될 수 없을 때, 교착 상태 발생발생 조건상호 배제자원 하나 당 한 프로세스만 사용할 수 있다.점유 대기다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존대비선점할당된 자원은 사용이 끝나서 반납될 때까지 강제로 빼앗을 수 없다.순환대기프로세스들의 집합이 점유대기 상태를 순환하는 것

운영체제･cs

[워밍업클럽3기] CS전공지식 2주차

기본편 - Section 03 알고리즘재귀 (recursion)사전적 정의: 어떠한 것을 정의할 때 자기 자신을 참조하는 것.탈출조건(=기저조건)이 필수적으로 있어야함.콜스택함수가 호출되면서 올라가는 메모리 영역FILO의 조건을 가짐스택자료구조를 잘 활용한 대표적 사례재귀함수는, 호출할 때마다 콜스택영역을 차지함탈출조건이 없으면 콜스택에 계속 쌓이기만함-> 메모리부족->자동stopfor문 대신 사용하기보다는, 팩토리얼과 같이 더 쉽게 함수구현을 위한것임.재귀함수내에서 자기자신을 호출할때, 이미 함수가 구현되어있다고 가정함.재귀함수: 나 자신을 호출, 구현할때는 이미 구현된 것을 부르는 것처럼 구현하면 쉬움 재귀적으로 생각하기pattern 01:단순 반복실행반복문으로 구현했을때보다 성능이 떨어짐pattern 02:하위 문제 결과를 기반으로 현재문제 계산팩토리얼을 예를 들으면, return number*factorial(number -1);여기에서 하위문제(=factorial(number-1);)를 기반으로, 현재문제(number*factorial(number-1);)를 해결함for문이용은 상향식 계산, 재귀함수를 이용하는 것은 하향식 계산모든 재귀가 하향식은 아님상향식: for문, 재귀함수 구현가능(상향식에서 재귀함수는 매리트없음)하향식: only 재귀함수만 가능 재귀 - 하노이탑재귀함수의 대표적인 예하향식 계산법의 대표적인 예임!순서대로 예상 스택을 쌓아보면 알수 있음1st stack원반 3 -> 기둥 C원반 2, 1 -> 기둥 B원반 1 -> 기둥 C위에서 1번째를 스택 제일 아래에 놓으면,원반 1 -> 기둥 C 부터 실행하게됨2nd stack원반 2 -> 기둥 C원반 1 -> 기둥 A버블정렬(Bubble sort)배열에 무작위로 섞인 숫자 정렬 방법 중 1개그 중 가장 쉽게 생각 할 수 있는 알고리즘구현 쉬움, but 성능 안좋음[4,2,3,1] -> [2,4,3,1] ->[2,3,4,1]->[2,3,1,4]->[2,3,1,4]->[2,1,3,4]->[2,1,3,4]->[1,2,3,4]버블정렬의 성능알고리즘의 빅오 표기법으로 할때, 숫자로 바꾸어보면 쉬움버블 정렬은 (n-1)+(n-2) ... +2+1 = n(n-1)/2 =(n^2-n)/2b 결과적으로 O(n^2)for문 두개가 중첩되어있으니 O(n^2)이라고 예측이 가능하기도함.버블 정렬의 장단점장점: 이해와 구현이 간단함단점: 성능이 O(n^2)으로 좋지만은 않음. 선택정렬(Selection Sort)버블정렬처럼 간단한 정렬에 속함정렬되지 않은 영역의 첫번째 원소를 시작으로 마지막 원소까지 비교후 가장 작은값을 첫번째 원소로 가져옴정렬이 되지 않은 영역에서 가장 작은수와 가장 큰수 위치 바꿔치기!선택정렬의 성능바깥 for문이 실행될수록 안쪽 for문이 줄어듦 -> 선택 정렬의 성능도 버블정렬과 동일한 O(n^2)선택정렬의 장단점은 버블정렬의 장단점과 동일함.그림으로 배우는 운영체제 Section 04프로세스간 통신프로세스: 독립적이기도 데이터를 주고받기도함한 컴퓨터내의 다른 프로세스 or 네트워크로 연결된 다른 프로세스와 데이터를 주고받기도함종류한컴퓨터 내에서 데이터 주고받음파일을 이용: 여러개의 프로세스가 하나의 파일을 읽고씀파이프 이용: 운영체제가 생성한 파이프를 이용함쓰레드를 이용함: 한프로세스내에서 쓰레드가 주고받음네트워크를 이용함소켓통신RPC(원격 프로시져호출)공유자원: 프로세스가 통신할때 공동으로 이용하는 파일이나 변수각프로세스의 접근 순서에 따라 결과가 달라질 수 있음.컨텍스트 스위칭으로 시분할 처리: 어떤 프로세스가 먼저 실행되는지 예측어려움연산결과 예측 어려움 -> 동기화 문컨텍스트 스위칭(Context Switching): 운영체제(OS)가 여러 개의 프로세스를 실행해야 할 때, 현재 실행 중인 작업을 멈추고 다른 작업으로 전환하는 과정임계구역(Critical Section): 여러 프로세스가 동시에 사용하면 안되는 구역!임계구역 문제 해결을 위한 조건상호배제 메커니즘: 임계영역엔 동시에 하나의 프로세스만 접근, 여러 요청에 도 하나의 프로세스 접근만 허용, 임계구역에 들어간 프로세스는 빠르게 나와야함.세마포어: 상호배제 메커니즘 중 한가지경쟁조건(Race Condition): 공유자원을 차지하기 위한 프로세스의 경쟁?동기화에서 가장 중요한 개념프로세스가 공유자원에 접근하기 위해서 운영체제가 세마포어를 우선순위가 높은 프로세스에게 먼저주고, 프로세스가 일을 다하면 운영체제에게 세마포어를 주고, 다시 운영체제는 세마포어를 대기큐에있던 다른 프로세스에게 전달해주는 식임.쉽게 생각해서 은행줄 같은느낌?손님 = 프로세스, 은행원 = 공유자원, 번호표 기계 = 운영체제, 세마포어 = 번호표세마포어를 이용하면, 공유자원에 여러 프로세스가 동시에 접근하지 않기 때문에 동기화문제가 일어나지 않음.세마포어: 정수형 변수임단점: 함수 순서가 중요함 (모니터를 통해 커버가능) 모니터: 세마포어의 단점을 해결하기 위한 상호배제메카니점프로그래밍 언어 차원에서 지원하는 방법synchronized: 자바에서 이것이 붙으면 동시에 여러 프로세스에서 실행할 수 없음!상호배제가 완벽하게 이루어짐이런 것을 제지해주는 것이 모니터의 역할임실제 모니터아니고 지켜본다의 모니터인듯?Section 05 데드락(교착상태)여러 프로세스가 서로 다른 프로세스의 작업이 끝나기를 기다리다가 아무 작업이 이루어지지않는 상태약간 고집센 상태?교착상태 발생이유: 공유자원을 서로 차지하려다 발생함.교착상태의 필요조건상호배제: 먼저 차지하면 다른 프로세스가 사용할 수 없는 리소스임.비선점: 프로세스가 이미 사용하고 있는 것을 다른 프로세스가 뺒을 수 없음.점유와 대기: 프로세스가 다른 리소스를 기다리는 상태원형대기: 점유와 대기를 하는 프로세스의 관계가 원형을 이룸예로 프로세스 A는 프로세스 B의 리소스를, 프로세스 B는 프로세스 C의 리소스를, 프로세스 C는 프로세스 A 의 리소스를 원하는 상태.교착상태 해결교착상태 회피(Deadlock avoidance)프로세스에 자원을 할당할 때 교착상태가 발생하지 않는 수준의 자원을 할당하는 것.전체 자원과 할당된 자원을 기반으로 안정상태를 유지하려 하는것.불안정 상태 =/= 교착상태. 그저 가능성이 높을 뿐.은행원 알고리즘: 전체자원의 수를 알고 있지 않은 채로 자원을 잘못나눠주면 교착상태가됨최대요구자원: 프로세스가 원하는 자원의 수교착상태 검출 방법가벼운 교착상태 검출: 타이머이용일정시간동안 프로세스가 일을 안함 = 교착상태해결법: 중간저장해서 교착상태되면 중간저장한데로 가는것무거운 교착상태 검출: 자원할당 그래프 이용운영체제가 어떠한 자원을 프로세스가 사용하는지 관찰순환구조가 생기는 그래프 = 교착상태교착상태 발생 -> 강제종료강제 종료된 프로세스를 체크포인트에서 롤업오버헤드가 발생하기도함. Section 06컴파일과 프로세스프로그래밍언어컴파일 언어: 개발자가 코드작성 -> 컴파일을 이용하여 기계어로 변환컴파일 과정: 문법 오류 검증 및 기계어로 변환함.C, C++, C#등이 이에 속함인터프리터언어: 개발자가 작성한 코드를 한줄씩 해석해 기계어로 변환미리 검사하지 않아 실행 시 오류가 발생할 수 있음.컴파일 대비 느림JS, Python, Ruby가 이에 속함프로세스: code, data, stack, heap영역code: 말그대로 코드가 들어감data: 전역변수 or 배열stack: 지역변수나 함수 매개변수, 함수의 리턴 주소저장.heap: 동적 메모리 할당.<컴파일 과정>test.c: 개발자가 C언어로 코딩함.전처리기: 개발자 코딩보고, 전처리부분(C언어에서 #부분)을 코드에 치환시킨 후 주석제거test.i: 전처리 된것 저장컴파일러: C언어 파일을 어셈블리어로 저장함.test.s: 어셈블리어 파일어셈블러: 어셈블리어를 오브젝트 파일로 변환test.o: 0과 1로 된 기계어로 구성된 오브젝트 파일 (코드영역과 데이터 영역이 나누어있음)링커: 오브젝트 파일을 실행파일로 변환.모든 오브젝트 파일을 하나의 데이터영역과 코드영역으로 바꿈실제 실행될 주소 매핑test.exe: 운영체제가 프로세스를 만들어줌. 완벽한 상태의 코드영역과 데이터 영역으로 나누어짐.이후...운영체제 ->exe파일의 코드영역과 데이터영역을 프로세스의 코드영역과 데이터영역에 넣어줌-> 빈상태의 스택과 힙을 할당 ->PCB를 만들어 관리가 가능하게 만들어줌 -> 프로그램 카운터(다음 실행할 명령어의 주소를 생성한 프로세스의 코드를 첫번째 주소로 설정) -> CPU 스케줄링에 맞추어 프로세스 실행후 작업을 마침Section 07메모리의 종류 (1번이 가장 속도가 빠르고 용량이 작으며 비쌈)레지스터: 가장빠른 기억장소, CPU내에 존재휘발성 메모리레지스터의 크기= 32bit, 64 bit메인메모리의 값을 레지스터로 가져와 계산 후 메인 메모리로 옮김캐시: 메인메모리에서 레지스터로 옮길때 미리 가져오는 데이터를 캐시에 옮겨둔다.캐시는 여러개를 둠. 가장 빠른 캐시 = L1.RAM(매인 메모리): 실제 운영체제와 여러 프로세스를 사용실행중인 프로그램만 돌림보조저장장치(HDD, SSD)비휘발성 메모리 메인메모리폰노이만 구조는 모든 프로그램을 메모리에서 실행시킴멀티프로그래밍 환경에서 여러개가 한번에 진행하여야 하기 때문에 복잡하고 어려워짐운영체제 : 1바이트 크기의 주소를 만들어 관리32bit= 레지스터, ALU, 데이터 이동버스 , 사용가능 메모리도 2^34=4Gb64bit = 레지스터, ALU, 데이터 이동버스, 사용가능 메모리는 2^64로 거의 무한대즉, 32bit보다 64bit ram이 더빠름 메모리에는 운영체제 영역이 따로있음.악의적이 프로그램이 운영체제를 침범하면 위험하기 때문에 경계레지스터( CPU내에 존재)를 통하여 보호함.절대주소: 실제 프로그램이 올라가는 주소, 물리 주소공간이라고도함.상대주소: 사용자가 바라보는 주소, 논리 주소라고 하기도함.메모리 할당방식메모리보다 더큰 프로그램은!!!프로그램을 메모리만큼 자른뒤 필요한거 일부 실행, 나머지 일부는 하드디스크내 스왑영역에 두었다가 사용함. = memory overlay멀티 프로그램 환경에서는,가변분할 방식 사용프로세스 크기에 따라 메모리는 나눔한프로세스가 메모리의 연속된 공간에 할당: 연속 메모리 할당단점: 외부단편화 발생장점: 빈공간 없음.고정 분할 방식프로세스 크기 상관없이 메모리 나눔 비연속 메모리할당: 메모리가 잘라서 나누어 들어가기도 하기때문장점: 구현이 간단하고 오버헤드가 적음단점: 내부단편화 발생외부단편화세그멘테이션 = 가변분할방식일부 프로세스가 종료되어 그만큼의 메모리(50+10MB)를 다른 프로세스(60MB필요)가 사용할때, 메모리가 연속으로 붙어있지 않으면 다른 프로세스에 할당이 어려운 것을 외부단편화라 함.해결방법: 조각모음,단점: 사용중 메모리 전부 중단, 메모리 이동해야함 -> 오버헤드 발생내부단편화페이징 = 고정분할 방식일정하게 분할된 메모리(20MB)이지만, 프로세스가 더 많은 메모리(50MB)가 필요하면 불할된 메모리를 프로세스가 필요한 메모리보다 많은 메모리(60MB)를 제공함버디시스템2의 승스로 메모리 분할해 할당함내부단편화가 발생하지만, 크기가작음동일하게 나누었기 때문에 조립하기 쉬움 (조각모음보다 간단함) 2주차 후 소감...확실히, 한글로 배우니까 너무 좋음.자세히 그림으로 설명해주시는것도 너무 좋음...이해 쏙쏙되어서 너무 좋다.학기 시작할때 알고 시작했으면 더 좋았을걸 하는 아쉬움남은 2주 화이팅 :)

cs･전공지식

[워밍업클럽3기] CS전공지식 1주차

그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)Section01. 개요자료구조var (variable, 변수)arr (Array, 배열)index를 이용하여 해당 data에 접근함자료 구조에 따라 배열을 사용하는 것이 편할 수 있음. Algorithm.확실한 방법을 의미함시키는대로 했을 때 답이 나와야함.모호한 방법은 안됨자료구조에 따라 알고리즘이 달라짐특정 자료구조 =/= 하나의 알고리즘시간복잡도더 좋은 알고리즘이란?사용자의 니즈에 따라 다름depend on the memory size, speed or both일반적으로 알고리즘 속도 = 성능속도 = 시간 복잡도시간 복잡도: 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간사용자마다 컴퓨터 사양이 다르기 때문에 실행시간이 무조건 같지는 않음.알고리즘의 평가는 코드에서 성능에 많은 영향을 주는 부분을 찾아 실행시간을 예측하는 것임.코드에서 성능에 많은 영향을 주는 부분 = 반복문빅오 표기법 빅오 표기법이 성능을 정확하게 표현하지 못하는 이유: 단순히 해당알고리즘의 입력이 늘어날 때, 계산량이 얼마나 늘어나는지를 표현하는 방법이기 때문O(n) : 선형시간 알고리즘O(1): 상수시간 알고리즘O(1) > O(logn) > O(n) > O(nlogn) > O(n^2) > O(2^n) > O(n!)계산에 가장 많이 영향을 미치는 차수만 표시함Section02. 자료구조배열 [array]기본적으로 제공하는 자료구조일반적인 배열: 선언시 배열의 크기를 알려줌읽기/쓰기/참조에서 좋은 성능을 보임삽입/ 삭제에서 좋지 않은 성능을 보임이유: 이미 연속된 메모리공간을 선언하였기 때문에 배열의 끝에 새로운 메모리로의 추가가 어렵기 때문에 새로운 사이즈의 배열을 추가할 수 있는 메모리를 찾아야함. (삭제도 같은 이유)배열을 너무 크게할경우, 일시적으로 해결 되는 것처럼 보이지만, 결국 제한적이고 배열의 크기와 메모리의 크기가 비례하기 때문에, 너무 큰 배열은 너무 많은 메모리를 차지하게됨.연결리스트 [linked list]배열의 단점을 해결해줌연결은 노드를 이용함node는 data의 위치 + next node number위와 같은 이유로 node = linked list장점열의 초기 크기를 알아야하는 단점이 없음.삽입과 삭제가 용의함단점데이터들이 떨어져 있어서(노드번호에 따라 위치가 다름) 특정 순서의 데이터로 바로 갈 수 없음.각 노드의 다음노드를 무조건 알아야 하기때문에 O(n)의 성능을 가짐.array의 성능은 O(1)데이터의 참조가 많이 일어나는 경우에는 배열이,데이터의 삽입과 삭제가 많이 일어나는 경우에는 연결리스트가 도움이 됨.스택(Stack)Stack의 사전적의미: 더미, 무더기 인것처럼 무작정 쌓는 개념FILO(First in Last Out)그냥 물건 쌓아두는 개념선입선출과 반대됨 큐(Queue)FIFO (First In First Out)선입선출의 개념임질서를 위해 서는 줄head에 삽입, 제거연결리스트로 구현함.O(n)의 성능이 나옴그렇기 때문에 head는 가장 앞의 노드, tail은 가장 뒤의 노드로 tail 변수추가로 O(1)의 성능이 나오게함일반 연결리스트 아닌 이중 연결리스트 사용. (양방향 연결리스트임)tail의 이전노드를 할당함.enqueue : insert datadequeue : delete datafront : 데이터 참조isEmpty : 비어있는가 확인스택은 위로 쌓아 올려서 위에서 꺼내는 느낌이면큐의 경우 왼쪽에서 데이터 넣고 오른쪽에서 데이터 빼내는 느낌?덱(Deque)삽입과 제거를 head와 tail모두에서 가능하기 때문에 스텍과 큐의 형태 모두 구현가능추상자료형printAll: 모든 데이터 출력addFirst: head에 데이터 삽입removeFirst: head에서 데이터 제거addLast: tail에 데이터 삽입removeLast: tail에서 데이터 제거isEmpty: 리스트가 비어있는지 확인해시테이블(hash Table)해시테이블 (hash table)hash, map, hashmap, dictionary라고도 불림표를 저장하는 가장쉬운방법 = array에 저장index로 접근하다보니 빈공간이 많아지고, 낭비되는 공간이있음메모리 절약을 위해 어떠한 계산을 거쳐 인덱스로 치환함: 어떠한 계산이 해시함수임삽입, 수정, 삭제까지 O(1)의 성능을 가짐문제: 충돌이 발생하기도함해당인덱스를 연결리스트로 구현해 저장함: O(n)의 성능을 가짐이렇기 때문에 해시테이블은 해시함수의 선정이 매우 중요함.장점: 빠른 데이터 읽기, 삽입, 삭제단점: 메모리를 많이 차지함.셋(Set)데이터의 중복을 허용하지 않는 자료구조해시테이블을 이용함hash set이라고도 부름hash table의 key만 사용추상자료형add(data) 데이터 삽입isContain(data) 데이터 체크(boolean)remove(data) 데이터 제거clear() 셋비우기isEmpty() 셋이 비었는지 체크printAll() 모든 데이터 출력 그림으로 쉽게 배우는 운영체제Section1. 운영체제 들어가기운영체제가 하는일프로세스관리멀테가가능하게해줌예시) 게임하는중, 백그라운드로 노래나 인터넷 브라우저를 틀어놓을 수 있음메모리 관리모든 프로그램은 메모리를 사용하드웨어관리운영체제가 판단하여 적절한데 저장하드디스크에 중요한 것이 저장 될 수 있기 때문파일 시스템 관리하드디스크의 효율적인 저장과 관리를 위함운영체제의 구조커널: 프로레스와 메모리, 저장장치를 관리하는 핵심적인 기능사용자는 인터페이스를 통해서만 접근가능함GUI (Graphic user interface)ex. window더블클릭으로 디렉토리 이동 CLI (Command-Line Interface)ex. 리눅스텍스트로 입력해야지만 이동 어플리케이션은 시스템콜을 이용해서 커널에 접근가능하드웨어와 커널의 인터페이스는 드라이버임각각의 하드웨어에 맞는 프로그램을 커널이 다 가질수 없기 때문에, 복잡한 장치는 디바이스 드라이버를 설치해야 사용가능함. 인터럽트입출력작업이 들어오면 관리자에게 오더함주기적으로 확인해야함: polling방식주기적인 확인으로 성능이 좋지 않음cpu가 명령내리고, 입출력 관리자가 다 되었을 때 cpu에 알려줌: 인터럽트방식비동기적임하드웨어입출력등과 같은것소프트웨어방식유효하지 않은 메모리접근과 같은 것.Section2. 프로세스와 쓰레드프로그램명령문의 집합체저장장치만 사용하는 수동적 존재프로세스실행중인 프로그램하드디스크에 저장된 파일이 메모리에 올라갔을때 프로세스라함메모리도 사용하고, cpu도 사용하고, 필요에 따라 입출력도 사용하기에 능동적인 존재임code: 실행코드data: 전역변수와 static(정적) 변수가 저장stack: 지역변수와 함수호출했을 때의 정보가 저장heap영역: 프로그래머가 동적으로 메모리를 할당하는데 쓰임PCB(Process Control Block)운영체제는 프로세스를 공평하게 해야함PCB: linked list라는 자료구조로 저장됨PCB포인터: 효율적인 접근을 위해사용프로세스상태: 생성, 준비, 실행, 대기, 완료를 나타냄프로세스 ID: 프로세스를 실행하기 위한 숫자프로그램 카운터: 다음에 실행될 명령어 주소를 포함레지스터 정보: 프로세스가 실행될때 사용된 레지스터 번호메모리 관련정보: 메모리 위치, 메모리 침범을 막기위한 정보CPU스케줄링 정보: 우선순위, 점유시간 등이 저장됨더 많은 정보가 저장됨컨텍스트 스위칭(context switching)프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행중인 프로세스 상태를 저장, 다른 프로세스 상태로 교체하는 것.PCB에 상태 저장PCB: 프로세스상태, 프로그램 카운터 ,각종 레지스터 정보가 변경됨CPU점유시간이 초과할경우: 인터럽트 실행레지스터값을 저장해둠발생이유cpu 점유시간 초과입출력요청다른 종류의 인터럽트의 발생쓰레드: 프로세스 내에 존재함1개의 프로세스안에 여러개에 존재함code, data, heap영역을 공유하고, stack은 하나씩 가지고 있음.ID도 부여하고 , TCB부여함으로써 운영체제가 구분할 수 있게됨.프로세스장/단점안전성: 다른 프로세스가 영향을 미치지 않음오버헤드가 큼쓰레드 장/단점안전성이 떨어짐 (일부공유하기 때문)오버헤드가 작음Section3. CPU 스케줄링cpu스케줄링이 고려할 점 (컴퓨터의 성능에 많은 영향을 줌)어떤 프로세스에 cpu 사용권을 주어야 하는가 cpu 할당받은 프로세스에 얼만큼의 시간을 주어야 하는가다중큐준비상태와 대기상태는 큐의 자료구조로 관리됨운영체제는 프로세스의 우선순위를 정해서 할당해줌 스케줄링 목표리소스 사용률: cpu사용율 or I/O 디바이스 사용률을 높임오버헤드 최소화: 계산이 너무 복잡하거나, 컨테스트 스위칭을 너무 자주하면 오버헤드 심해짐공평성: 모든 프로세스에게 공평하게 cpu할당을 위함.단 시스템에 따라 달라질 수 있음.예를들어, 자율주행 자동차에서는 안전관련이 제일 중요, 음악재생은 덜함.처리량: 같은 시간내 더 많은 처리를 하는 것을 목표로 삼음대기시간: 최소화를 목표로함응답시간: 짧은 것을 목표로함목표간의 상반되는 것이 있음.처리량과 응답시간의 목표를 동시에 이룰 수 없을 때는 사용자의 시스템에 따라 초점을 맞추어줌.특정한 경우아니고서는 발란스를 이루는 것이 중요. FIFO (First In First Out)장점: 단순, 직관적단점: 순차적이여서 늦게오면 대기시간이 길어짐, I/O시간동안 cpu가 쉬고있기 때문에 cpu사용률이 떨어짐. 스케쥴링 성능은 평균 대기시간으로 평가함!*burst time 계산시에는 대기시간을 총더한값에 프로세스 갯수 나누기이기 때문에, 프로세스 시간이 짧은 것을 먼저 할 경우 대기시간이 짧아짐.SJF(Shortest Job First)FIFO의 단점을 해결하기 위해 고안됨.실제 고안에서 발생 되었던 문제프로세스 종료시간이 어느정도인지 예측어려움burst time이 긴 프로세스는 언제 진행이 될지 모르게됨 = 불공평해짐.RR(Round Robin)FIFO -> SJF -> RRfifo의 단점 해결을 위해 한 프로세스에 일정시간(=할당시간)을 부여하고, 시간이 초과하면 다른 프로세스로 가게 만듬프로세스에게 할당하는 일정시간 = 타임퀀텀, 타임 슬라이스RR algorithm은 컨텍스트 스위칭이 포함됨.타임슬라이스를 너무 작게하면, 컨텍스트 스위칭이 너무 많이 일어나게됨 = 오버헤드가 너무크다.사용자가 버벅거리게 느끼지 않고, 오버헤드가 너무 크지 않고, 동시에 실행되는 것처럼 느끼게하기..MLFQ (Multi Level Feedback Queue)기본적으로 작은 타임슬라이스를 가지지만, cpu작업이 비교적 작은 (ex. I/O bound process) 프로세스가 작은 타임 슬라이스를 가지고, cpu작업이 비교적 큰 프로세스가 타임 슬라이스가 크게 됨.타임슬라이스 기준으로, 우선순위를 정하게됨.

cs･전공기초

워밍업클럽CS2기 2주차 발자국: 자료구조와 알고리즘

자료구조와 알고리즘 재귀재귀어떠한 것을 정의할 때 자기자신을 참조하는 것재귀함수재귀적으로 정의된 함수탈출 조건, 기저조건이 반드시 있어야함for문 vs 재귀함수재귀함수는 for문 대신이 아님재귀함수로 해결하면 더 많은 메모리 공간을 차지하여 비효율적재귀함수는 더 복잡한 문제를 쉽게 해결하기 위해 사용함 ex) 팩토리얼 재귀적으로 생각하기단순한 반복실행재귀함수 이점이 없고 콜스택 공간을 많이 차지해 성능은 for문보다 안 좋음하위 문제의 결과를 기반으로 현재 문제를 계산 (하향식 계산)재귀를 사용하는 이유로 재귀함수에서만 구현할 수 있음ex) 팩토리얼 return number * factorial(number - 1)재귀 - 하노이탑하노이탑한 번에 하나의 원반을 움직일 수 있다.가장 위에 있는 원반만 옮길 수 있다.아래에 작은 원반이 올 수 없다.정렬 - 버블정렬버블정렬앞에 있는 숫자와 옆의 숫자를 비교해서 자리를 바꾸는 알고리즘구현이 쉬우나 성능이 좋진 않음 o(n2)

웹 개발･cs･인프런워밍클럽･자료구조와알고리즘