블로그

대롱대롱

[인프런 워밍업클럽 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

seongmin kim

인프런 워밍업 클럽 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)로 데이터를 저장셋 : 데이터의 중복을 허용하지 않는 자료구조  운영체제운영체제는 언제 한번 공부하고 싶었던 부분인데 좋은 기회로 듣게되어 오히려 자료구조보다 더 빨리 들었던 것 같다.운영체제의 구조는 어떻게 되어있는지 하드웨어가 뭔지 아직까지 처음 듣는 내용이지만서도 재밌게 듣고있다.회고칭찬하고 싶은 점ㅎㅎ ;; 아직 없다 ..아쉬웠던 점내일배움캠프와 같이 진행중이라, 시간이 많지않아 강의를 매일매일 챙겨보지못해 밀리는게 매우 아쉽다.또한 아직까지 기본적인 개념이 자리잡지 않은 것 같은 느낌이 들었다.보완할 점새벽까지하더라도 밀리지 않게 강의를 듣는게 좋을 것 같다. 또한 내용은 여러번 반복해서 !평일에 밀리지 않게 들은 후 주말에는, 저번 주에 들었던 내용 + 이번 주 내용 배속으로 한번 더 듣는걸로 해야겠다.

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

하얀종이개발자

인프런 워밍업 클럽 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자료구조알고리즘운영체제

채널톡 아이콘