블로그

왜 CS 전공지식은 ‘개발자 기본기’로 꼽힐까?

컴퓨터 구조, 자료구조, 알고리즘, 운영체제, 네트워크, 데이터베이스 등은 컴퓨터공학 및 컴퓨터과학, 소프트웨어공학 등의 전공에서 반드시 배우는 주제로 꼽힙니다. 학교나 학과마다 커리큘럼에 차이는 있더라도 내용 자체는 모두 동일한 개념을 배우게 되는데요.이러한 CS 전공 지식은 컴퓨터 관련 학과에서의 전공 이해를 좌우할 뿐만 아니라, 개발자 채용을 위한 기술 면접 과정에서 주로 검증하는 핵심 개념이기도 합니다. 가령 서비스 개발자라면 비즈니스 로직을 구축하는 등, 프로그램의 구조를 만들고 문제를 해결하는 바탕이 되기 때문입니다. 이미 실무에 진출한 개발자들조차도 CS 전공 지식을 강조하는 이유가 여기에 있죠.다시 말해 CS 전공 지식은 개발자로서 필요한 문제 해결 역량을 결정하는 기본기 역할을 합니다. 대학생, 취업 준비생, 주니어 개발자 등을 막론하고 실력 있는 프로그래머가 되기 위한 든든한 뿌리가 필요하다면 CS 전공 지식에 주목해야 합니다.•••기술 면접 전, 실무 프로젝트 전 빠르게 기초를 정리하고 싶으신가요?지금 인프런 프리즘 [CS 전공 지식 로드맵]을 통해 학습해보세요. https://www.inflearn.com/roadmaps/643•••인프런 프리즘 브랜드 스토리 읽어보기 >>

개발 · 프로그래밍 기타CS전공지식컴퓨터구조알고리즘자료구조운영체제네트워크데이터베이스컴퓨터공학인프런프리즘InflearnPrism

하얀종이개발자

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

운영체제 3주차 학습 요약 가상메모리컴퓨터의 물리적 메모리의 크기를 확장하기 위해 사용되는 기술운영체제가 각 프로세스마다 독립적인 메모리공간을 할당할 수 있게 해줌이때문에 프로그래머는 프로그램이 메모리 어디에 위치하는지 신경쓰지 않고, 0부터 시작된다고 생각하고 프로그래밍 함동적주소변환 (DAT)메모리관리자가 가상메모리의 논리주소를 물리주소로 변환하는 것을 말함세그멘테이션 분할 방식에서 논리 주소를 물리주소로 변환메모리관리자는 CPU에서 받은 논리주소를 세그멘테이션 테이블을 이용하여 물리주소를 찾음페이징 분할 방식에서 논리 주소를 물리주소로 변환메모리관리자는 CPU에서 받은 논리주소를 페이지 테이블을 이용하여 물리주소를 찾음페이지드 세그멘테이션 분할 방식에서 논리 주소를 물리주소로 변환세그멘테이션 테이블의 속성값으로 페이지 테이블의 인덱스를 추가할 수 있게하여 세그멘테이션, 페이지 테이블을 모두 이용해서 물리주소를 찾음가상메모리는 세그멘테이션으로 분할되어 있고, 물리메모리는 페이징으로 분할되어 있어 각 분할방식의 장점을 취할 수 있게 함메모리 접근권한세그멘테이션 테이블에 메모리의 특정번지에 권한을 부여하는 속성을 추가하여, 메모리 접근시 권한을 검사할 수 있음디멘드 페이징 정책조만간 필요할 것 같은 데이터를 메모리에 가져오고 쓰이지 않을 것 같은 데이터는 스왑영역으로 보내는 정책필요한 데이터를 언제 메모리로 가져올지를 결정하는 것페이지 테이블 엔트리접근비트, 변경비트, 유효비트, 권한비트 (프레임번호만 있는게 아님)페이지 폴트프로세스가 가상메모리에 접근요청했을때 물리메모리에 데이터가 없을때 발생하는 인터럽트페이지 폴트가 발생하면 보조저장장치의 스왑영역에 접근하여 스왑영역에 있는 데이터를 메모리에 올리는 작업을 함페이지 교체정책스왑영역에서 데이터를 찾아 메모리에 올리려고 했는데, 이미 메모리가 가득찼을때 조회할 데이터를 메모리에 추가하기위해 데이터를 남기거나 스왑영역으로 보내는 정책무작위, FIFO, Optimum, LRU, Clock Algorithm, Enhanced Clock Algorithm스레싱과 워킹셋스레싱제한된 물리 메모리에 프로그램을 많이 올려 스왑 영역에 데이터가 많이 저장되고 Page Fault가 자주 발생하게 되면 CPU 사용률이 떨어짐. 스케줄러에 의해 운영체제는 CPU 사용률을 올리기 위해 더 많은 프로세스를 메모리에 올리게 되고 이를 반복하게 되면 CPU 사용률이 0에 가깝게 떨어지는데 이를 스레싱이라고 함워킹셋현재 메모리에 올라온 페이지는 다시 사용할 확률이 높기에 하나의 세트로 묶어서 메모리에 올리는데 이를 워킹셋이라고 함입출력장치주변장치(I/O 디바이스, 저장장치)들은 메인보드에 있는 버스로 연결되어 있음각 하드웨어에 맞게 외부 인터페이스가 존재캐릭터 디바이스, 블록디바이스 입출력 제어기는 두 개의 채널, 시스템 버스와 입출력 버스로 구분파일과 파일시스템운영체제가 파일을 관리하기 위한 파일 관리자파일을 관리하는 하드디스크나 Flash Memory(SSD)는 블록 디바이스, 파일 시스템은 전송 단위는 블록이지만, 사용자는 바이트 단위로 파일에 접근이 가능해야 함, 파일 관리자가 이를 중간에서 관리파일의 종류순차파일구조, 직접파일구조, 인덱스파일구조디렉토리관련있는 파일을 모아둘 수 있도록 하는 장치알고리즘 & 자료구조 3주차 학습 요약 삽입 정렬 (Insertion Sort)정렬되지 않은 영역에서 데이터를 하나씩 꺼내서 정렬된 영역 내 적절한 위치에 "삽입"해서 정렬하는 알고리즘삽입하려는 데이터를 정렬된 영역의 원소를 역순으로 순회하면서 비교O(n²)장점 : 작은 데이터나 거의 정렬된 데이터에 대해 매우 효율적단점 : 속도가 느려서 대규모 데이터에 비효율적 병합 정렬 (Merge Sort)정렬하려고 하는 배열을 잘게 쪼갠다음, 순서에 맞게 재배열하는 알고리즘 (재귀)O(n log n) 장점 : 속도가 빠르며 대규모 데이터에서도 일정한 성능을 보임 단점 : 추가 메모리 공간이 필요하며, 메모리 효율이 떨어질 수 있음퀵 정렬 (Quick Sort)배열의 숫자중 하나를 피벗으로 설정하고, 피벗의 왼쪽에는 작은값, 피벗의 오른쪽에는 큰값을 정렬하는 알고리즘분할시 왼쪽과 오른쪽의 포인트가 교차하면 피벗과 오른쪽 포인트의 값과 교환하여 피벗값을 정렬해나감평균 O(n log n), 최악 O(n²) 장점 : 평균적으로 매우 빠르고, 메모리 사용이 적음 단점 : 피벗 선택에 따라 성능이 달라지며, 최악의 경우 속도가 느려질 수 있음 (그러나 최악이 되는 경우는 거의 없음)동적프로그래밍메모이제이션계산 결과를 따로 기억해서 여러 번 중복 계산하지 않도록 하는 기법하향식 계산 방식으로 활용타뷸레이션계산에 필요한 모든 값을 전부 계산 후 테이블에 저장하는 기법상향식 계산 방식으로 활용 회고스터디의 마지막 주차가 되었네요. 나름 정리도 하고 CS전공지식 스터디 내부에서 다른분들이랑 모여 발표 스터디도 하면서 열심히 학습하면서 많이 배운시간이 었던거 같아요. 특히나 알고리즘을 직접 구현해보면서 각 알고리즘의 장.단점을 외우지 않아도 조금만 생각해보면 장.단점을 도출할 수 있게 되어서 좋았어요.스터디 발표 & 정리 자료 캡쳐빠르게 끝나 아쉬움반 후련함반이 있지만, 계속 복습하고 부족한 부분 채워나가면서 열심히 해나가겠습니다.많이 배웠습니다. 즐거웠어요.

백엔드CS전공지식그림으로쉽게배우는자료구조와알고리즘그림으로쉽게배우는운영체제인프런워밍업클럽2기감자

Taeho

인프런 워밍업 클럽 - CS Week 2

AlgorithmRecursion(재귀)어떠한 것을 정의할 때 자기 자신을 참조하는 것을 의미한다.재귀함수 : 재귀적으로 정의된 함수재귀함수는 콜스택이라는 메모리 가득차게 되는 경우 자동으로 종료된다.기저 조건 : 재귀함수가 종료될 수 있는 탈출 조건기저 조건이 반드시 있어야 정상적으로 수행할 수 있다.재귀함수는 함수를 호출할 때마다 Call Stack이라는 메모리 공간에 호출정보가 저장된다.→ 재귀함수는 Loop문보다 더 많은 메모리 공간을 차지한다.Call Stack(= Stack)함수가 호출되면서 올라가는 메모리 영역함수가 종료되면 콜스택에서 제거된다.FILO(First-In Last-Out)재귀함수를 사용하는 이유Loop를 대신한다기 보다는 더 복잡한 문제를 쉽게 해결하기 위해 사용된다.ex) Factorial재귀함수를 쉽게 작성하는 방법재귀함수 내에서 자기 자신을 호출할 때 해당 함수가 벌써 구현이 되어있다고 가정한다.재귀 사용하는 패턴단순 반복문반복문으로 구현했을 때보다 이점이 되는 부분이 없음Call Stack에 공간을 많이 차지해 성능이 반복문보다 좋지 않다.하향식 계산하향식 계산 : 하위문제의 결과를 기반으로 현재 문제를 계산하는 방식재귀가 반복문보다 성능이 좋은 경우큰 문제를 해결하기 위해 작은 재귀 함수를 호출한다.재귀를 사용해서만 구현이 가능하다.상향식 계산 : 하위 문제를 모아서 현재 문제를 계산하는 방식반복문으로 구현한 것보다 성능이 좋지 않음반복문이나 재귀를 사용해서 구현할 수 있다.하노이의 탑하향식 계산 방식의 좋은 예시→ 재귀함수의 좋은 예시제약 조건한 번에 하나의 원반을 움직일 수 있다.가장 위에 있는 원반만 옮길 수 있다.아래에 작은 원반이 올 수 없다. Bubble Sort인접한 두 원소를 비교하여 두 원소의 위치를 교환한다.과정배열을 처음부터 끝까지 순회하며 인접한 두 원소를 비교한다.왼쪽 원소가 오른쪽 원소보다 크면 두 원소를 교환한다.이 과정을 배열이 정렬될 때까지 반복한다.시간 복잡도O(n^2)장점이해와 구현이 간단한다.단점성능이 좋지 않다.Selection Sort배열에서 최솟값을 찾아 맨 앞으로 이동시킨다.과정정렬되지 않은 부분에서 최솟값을 찾는다.찾은 최솟값을 정렬되지 않은 부분의 첫 번째 원소와 교환한다.정렬된 부분을 한 칸 늘리고, 정렬되지 않은 부분에서 위 과정을 반복한다.시간 복잡도O(n^2)장점이해와 구현이 간단하다.단점성능이 좋지 않다.참고 : https://visualgo.net/en/sortingCPU Scheduling AlgorithmSJF(Shortest Job First)Burst Time이 짧은 작업부터 CPU를 할당한다.문제점어떤 프로세스가 얼마나 실행될지 예측하기 힘들다.→ 예측하는 것이 거의 불가능하다.Burst Time이 긴 프로세스는 아주 오랫동안 실행되지 않을 수 있다.→ Burst Time이 긴 프로세스는 Burst Time이 짧은 프로세스에게 계속해서 우선순위가 밀린다.⇒ 사용되지 않는다.RR(Round Robin)하나의 프로세스에게 일정 시간만 CPU를 할당하고 할당된 시간이 지나면 강제로 다른 프로세스에게 일정시간만큼 CPU를 할당하는 방식→ 강제로 CPU를 뺏긴 프로세스는 Queue의 가장 마지막으로 밀려난다.Time Slice(=Time Quantum) : 프로세스에게 할당하는 일정 시간Time Slice에 따라서 RR의 성능이 좌지우지된다.Time Slice를 작게 만드는 경우 Context Switching이 빈번하게 발생된다.→ Context Switching이 빈번하게 발생함에 따라 성능이 떨어진다.Time Slice가 큰 경우 FIFO와 동일하게 동작한다.Time Slice 예시Window Time Slice : 20msUnix Time Slice : 100ms단점Context Switching이 존재한다.→ 평균 대기시간이 FIFO와 동일하다면 FIFO가 더 성능이 좋다.MLFQ(Multi Level Feedback Queue)RR의 업그레이드 버전주로 사용되는 CPU 스케줄링 알고리즘CPU Bound Process : CPU를 할당받은 시간을 대부분 CPU 연산을 수행하는 프로세스CPU 사용률과 처리량이 중요I/O Bound Process : 대부분의 시간을 I/O 작업에 수행하고 적은 시간만 CPU 연산을 하는 프로세스- 응답시간이 중요MLFQ는 기본적으로 CPU 사용률과 I/O 사용률이 좋게 나오는 작은 크기의 Time Slice를 사용한다.CPU Bound Process에게는 CPU 사용률을 높이기 위해 Time Slice를 높게 할당한다.I/O Bound Process에게는 I/O 사용률을 높이기 위해 Time Slice를 낮게 할당한다.OS는 어떻게 CPU Bound Process와 I/O Bound Process를 구분할까?CPU를 사용하는 프로세스가 실행하다가 스스로 CPU를 반납하는 경우 CPU 사용률이 낮음→ I/O Bound Process일 확률이 높음CPU를 사용하는 프로세스가 실행하다가 CPU 스케줄러에 의해 강제로 CPU를 뺏기는 상황인 경우 CPU 사용률이 높음→ CPU Bound Process일 확률이 높음구현 방법우선순위를 갖는 큐를 여러개 준비한다.우선순위가 높으면 Time Slice가 작다.우선순위가 낮아질수록 Time Slice가 커진다.Process간 통신하나의 컴퓨터 내에서 프로세스간 통신하는 방법Pipe운영체제가 생성한 파이프를 이용해 데이터를 읽고 쓰는 방법File통신을 하려는 프로세스들이 하나의 파일을 이용해 읽고 쓰는 방법Thread를 이용한 통신하나의 프로세스 내에서 쓰레드간 통신하는 방법쓰레드는 코드, 데이터, 힙 영역을 공유한다.(스택 영역만 별도로 갖는다.)데이터 영역의 전역 변수나 힙 영역을 이용하여 통신할 수 있다.NetworkOS가 제공하는 Socket 통신RPC(Remote Procedure Call)다른 컴퓨터의 함수를 호출하는 방법공유자원과 임계구역공유자원 : 프로세스간 통신을 할 때 공용으로 이용하는 변수나 파일여러 프로세스가 공유하기 때문에 각 프로세스의 접근 순서에 따라서 결과가 달라질 수 있다.컨텍스트 스위칭으로 시분할 처리를 하기 때문에 프로세스간의 실행 순서를 예측하기 어렵다.⇒ 동기화 문제가 발생할 수 있다.임계규역 : 여러 프로세스가 동시에 사용하면 안되는 영역상호배제 메커니즘을 통해 해결할 수 있다.경쟁조건 : 공유자원을 사용하기 위해 서로 경쟁하는 것상호배제 요구사항임계영역엔 동시에 하나의 프로세스만 접근한다.여러 요청에도 하나의 프로세스의 접근만 허용한다.임계구역에 들어간 프로세스는 빠르게 나와야한다.Semaphore상호배제 메커니즘의 한 종류Semaphore :  정수 값을 가지는 변수로, 공유 자원에 접근할 수 있는 프로세스/스레드의 수를 나타낸다.세마포어를 갖고 있는 프로세스가 실행되고 세마포어를 반납한다.기본 연산wait(S): 세마포어 값을 감소시킨다.값이 0이면 프로세스/스레드를 대기 상태로 만든다.signal(S): 세마포어 값을 증가시킵니다.대기 중인 프로세스/스레드가 있다면 깨운다.종류이진 세마포어: 0과 1 두 가지 값만 갖는다.(뮤텍스와 유사하게 사용한다.)카운팅 세마포어: 0 이상의 정수 값을 갖는다.(여러 자원을 관리할 때 사용된다.)장단점장점: 여러 프로세스/스레드 간의 복잡한 동기화 문제를 해결할 수 있다.단점잘못 사용하면 교착 상태나 기아 상태를 유발할 수 있다.ex) 세마포어를 획득하는 함수와 세마포어를 반납하는 함수의 위치 잘못 사용Mutex(MUTual EXclusion)뮤텍스는 이진 세마포어의 특수한 경우여러 스레드가 공유 자원에 동시에 접근하는 것을 방지하는 기술기본 연산Lock: 스레드가 임계 영역에 진입할 권한을 획득Unlock: 임계 영역 사용을 마치고 다른 스레드가 진입할 수 있게 한다.뮤텍스와의 차이세마포어는 여러 프로세스/스레드의 접근을 허용할 수 있지만, 뮤텍스는 하나의 프로세스/스레드만 접근을 허용한다.Monitor세마포어의 단점을 보완한 상호배제 메커니즘OS가 처리하는 것이 아니라 프로그래밍 언어단에서 지원하는 기능ex) Java : synchronized 키워드한 번에 하나의 프로세스/스레드만 실행할 수 있다.교착상태여러 프로세스가 서로 다른 프로세스의 작업이 끝나길 기다리다가 아무 작업도 수행되지 않는 상태발생 원인상호 배제 : 공유 자원은 한 번에 하나의 프로세스만 사용할 수 있다.비선점 : 다른 프로세스가 사용 중인 자원을 강제로 빼앗을 수 없다.점유와 대기 : 프로세스가 이미 자원을 보유한 상태에서 다른 자원을 요청하며 대기한다.원형 대기 : 점유와 대기를 하는 프로세스들의 관계가 원형이다.하나라도 충족하지 않으면 교착상태가 발생하지 않는다.→ 교착 상태를 예방하는 것을 구현하기는 매우 어려워서 교착 상태를 해결하는 방향으로 발전됐다.해결방법교착상태 회피프로세스들에게 자원을 할당할 대 어느 정도 자원을 할당해야 교착상태가 발생하는지 파악해서 교착상태가 발생하지 않는 수준의 자원을 할당한다.전체 자원의 수와 할당된 자원의 수를 기준으로 안정상태와 불안정 상태로 나뉜다.OS는 안정상태를 유지하려 한다.안전 상태: 모든 프로세스가 요구한 최대 자원을 할당받아 실행을 완료할 수 있는 상태불안정상태에 있더라도 무조건 교착상태에 들어가는 것이 아니라 교착상태에 빠질 확률이 높아지는 것이다.은행원 알고리즘작동 원리프로세스가 자원을 요청할 때, 그 요청이 시스템을 안전 상태로 유지할 수 있는지 확인한다.안전 상태를 유지할 수 있는 요청만 수락하고, 불안정한 상태를 초래할 수 있는 요청은 거절한다.주요 개념최대 요구량(Max Need): 프로세스가 실행을 완료하기 위해 필요한 최대 자원 양할당량(Allocation): 현재 프로세스에 할당된 자원 양필요량(Need): 최대 요구량에서 현재 할당량을 뺀 값가용량(= 시스템 총 자원, Available): 시스템에서 현재 사용 가능한 자원 양단점비용이 비싸고 비효율적이다.교착상태 검출가벼운 교착 상태 검출타이머를 이용하는 방식프로세스가 일정시간 동안 작업을 진행하지 않는다면 교착상태가 발생했다고 간주하고 교착상태를 해결한다.교착상태 해결 방법일정 시점마다 체크포인트를 만들어 작업을 저장하고 타임아웃으로 교착상태가 발생했다면 마지막으로 저장했던 체크포인트로 롤백한다.무거운 교착 상태 검출자원 할당 그래프를 이용하는 방식OS가 자원 할당 그래프를 유지하고 검사해야 하기 때문에 오버헤드가 발생한다.But. 가벼운 교착 상태 검출에서 발생할 수 있는 억울하게 종료되는 프로세스가 발생하지 않는다.OS에서 프로세스가 어떤 작업을 사용하는지 지켜보고 교착상태가 발생했다면 해결한다.Programming LanguageCompile Language개발자가 코드를 작성하고 컴파일을 수행하여 0과 1로된 기계어로 실행파일을 만든다.→ 기계어로 되어 있어 실행 속도가 인터프리터 언어에 비해 빠르다.컴파일 과정에서 개발자의 문법오류를 체크한다.ex) C, C++, C#Interpreter Language개발자가 작성한 코드를 미리 기계어로 만들어 놓지 않고 실행시 코드를 한줄씩 해석해 실행하는 언어→ 미리 검사를 하지 않기 때문에 실행할 때 오류가 발생할 수 있고, 컴파일 언어보다 느리다.ex) Javascript, Python, Ruby프로세스의 영역코드 영역실행해야 할 코드가 들어간다.데이터 영역전역 변수나 배열이 들어가는 영역스택 / 힙프로세스가 실행될 때 할당되는 메모리스택 : 지역변수와 함수 관련 값들이 저장힙 : 실행 중에 메모리 공간을 할당할 수 있는 유동적인 공간Compile 언어가 Process가 되는 방법개발자가 코드 작성전처리 단계 실행개발자가 작성한 코드를 확인하고 전처리 구문을 처리한다.C에서는 #이라는 키워드로 선언된다.ex) #include<stdio.h>, #define MY_NUMBER 100코드에 있는 모든 주석은 삭제된다.결과물로 .i 파일이 생성된다.전처리기에서 나온 결과파일을 컴파일러가 처리한다.컴파일러는 .i 파일을 기계어에 가까운 어셈블리어로 변환시킨다.결과물로 .s 파일이 생성된다.어셈블러 작업이 수행된다.오브젝트 파일.o로 변환된다.오브젝트 파일은 0과 1로 구성되어 있다.코드영역과 데이터 영역이 나뉘어져 있다.링커 작업이 수행된다.모든 오브젝트 파일을 하나의 코드 영역과 데이터 영역으로 묶어준다.실제로 실행될 주소를 매핑시켜준다.결과물로 .exe 파일이 생성된다.사용자가 .exe파일을 실행시키면 OS가 프로세스를 생성한다.OS는 파일에 있는 코드 영역과 데이터 영역을 가져와 프로세스의 코드 영역과 데이터 영역에 넣어주고, 빈 상태의 스택과 힙을 할당한다.PCB를 만들어 프로세스를 관리가 가능하게 한다.PC(프로그램 카운터)에 다음 실행할 명령어의 주소를 생성한 프로세스의 코드영역의 첫번째 주소로 설정한다.→ OS의 CPU 스케줄링에 따라서 프로세스가 실행되다가 작업을 마친다.메모리 종류레지스터가장 빠른 기억장소, CPU 내에 존재한다.휘발성 메모리CPU를 나타내는 값에서 32bit, 64bit를 의미하는 것이 레지스터의 크기이다.CPU는 계산을 수행할 때 메인 메모리에 있는 값을 레지스터로 가져와서 계산한다.계산 결과는 메인 메모리에 저장한다.캐시휘발성 메모리속도가 매우 빠른 레지스터와 레지스터에 비해 상대적으로 느린 메인 메모리 사이의 속도 간극을 메우기 위해 필요한 데이터를 미리 가져와 저장하는 저장소성능의 이유로 여러 개가 존재한다.L1, L2, L3→ 숫자가 커질 수록 느린 캐시CPU가 값을 요청해 레지스터로 값을 옮겨야 한다면 빠른 캐시를 순차적으로 확인하고, 캐시에 데이터가 없으면 메인 메모리를 조회한다.ex) L1 → L2 → L3 → 메인 메모리보조 저장장치(HDD, SSD)비휘발성 메모리메인 메모리실제 운영체제와 다른 프로세스들이 올라가는 공간휘발성 메모리데이터를 저장하기 보다는 실행중인 프로그램만 저장한다.OS는 메모리를 관리하기 위해서 1Byte 크기로 구역을 나누고 숫자(주소)를 매긴다.32bit CPU, 64bit CPU32bit CPU레지스터, ALU, Data Bus : 32bit메모리 : 2^32 = 4GB64bit CPU레지스터, ALU, Data Bus : 64bit메모리 : 2^64 = 16384PiB64bit CPU가 32bit CPU 보다 한번에 처리할 수 있는 양이 많기 때문에 속도가 더 빠르다.물리 주소 & 논리 주소물리 주소 공간 : 0x0부터 시작하는 주소 공간논리 주소 : 사용자 관점에서 바라 본 주소 공간사용자는 물리 주소를 몰라도 논리 주소로 물리 주소에 접근할 수 있다.OS를 위한 공간은 따로 확보한다.경계 레지스터H/W적으로 OS 공간과 사용자 공간을 나누는 레지스터CPU 내에 존재하는 레지스터메모리 관리자가 사용자 프로세스가 경계 레지스터의 값을 벗어났다면 검사하고, 벗어났다면 해당 프로세스를 종료시킨다.절대 주소 & 상대 주소개발자가 프로그램이 실행될 주소를 신경쓰지 않고 개발할 수 있는 이유→ 컴파일러가 컴파일을 할 때 메모리 0번지에서 실행한다고 가정하기 때문절대 주소 : 메모리 관리자가 바라본 프로세스가 올라간 물리 주소상대 주소 : 사용자가 바라보는 논리 주소재배치 레지스터프로그램의 시작 주소가 저장되어 있다.사용자가 요청한 논리 주소의 데이터를 물리 주소로 치환해준다.사용자가 메모리에 접근할 때마다 논리 주소를 물리 주소로 치환해준다.메모리 할당 방식메모리 오버레이메모리보다 용량이 큰 프로그램을 실행시키는 방법큰 프로그램을 메모리에 올릴 수 있을 정도로 분할하여 일부만 실행하고, 실행되지 않은 프로그램은 HDD의 스왑 영역에 저장하는 방식Swap스왑영역에 있는 데이터 일부를 메모리로 가져오고 메모리에 있는 데이터를 스왑영역으로 옮기는 것가변 분할 방식(= Segmentation, 세그멘테이션)프로세스의 크기에 따라 메모리를 나누는 방식하나의 프로세스가 메모리에 연속된 공간에 할당된다.→ 연속 메모리 할당이라고 한다.장점메모리에 연속된 공간에 할당된다.→ 내부 단편화가 없다.단점외부 단편화가 발생한다.고정 분할 방식(= Paging, 페이징)프로세스의 크기와는 상관없이 정해진 크기로 나누는 방식하나의 프로세스가 메모리에 분산되어 할단된다.→ 비연속 메모리 할당이라고 한다.장점구현이 간단하고 오버헤드가 적다.단점작은 프로세스도 큰 영역에 할당되어 내부 단편화가 발생한다.내부 단편화프로세스에 필요한 메모리보다 더 큰 고정 크기의 메모리 블록이 할당될 때 발생한다.할당된 메모리와 실제 사용된 메모리 사이의 차이로 인해 메모리 공간이 낭비된다.고정 크기 분할 방식에서 주로 발생한다.해결 방법은 딱히 없고, 분할되는 크기를 조절하여 내부 단편화를 최소화한다.외부 단편화메모리 할당과 해제를 반복하면서 작은 빈 공간들이 메모리 곳곳에 흩어져 생기는 현상전체 가용 메모리는 충분하지만, 연속된 큰 블록을 할당할 수 없는 상황을 만든다.가변 분할 방식에서 주로 발생한다.조각모음외부 단편화가 발생한 공간을 합쳐주는 작업현재 메모리에서 실행되고 있는 프로세스들의 작업을 일시 주징하고, 메모리 공간을 이동시켜야 한다.→ 오버헤드가 발생한다.버디 시스템가변 분할 방식 + 고정 분할 방식오늘날의 OS가 채택한 메모리 할당 방식2의 제곱으로 메모리를 분할하여 할당하는 방식→ 근접한 메모리 공간을 합치기 쉽다.→ 조각 모음보다 훨씬 간단하다.장점가변 분할 방식처럼 프로세스 크기에 따라 할당되는 메모리 크기가 달라지고, 외부 단편화를 방지하기 위해 메모리 공간을 확보하는 것이 간단하다.내부 단편화가 발생할 수 있지만 고정 분할 방식에 비해 많은 공간이 낭비되지는 않는다.Retrospect잘한 점매일매일 빠지지 않고 강의를 들은 점매일 들은 강의 내용을 요약/정리하고 그 주차의 내용들을 하나의 게시글로 정리한 것

알고리즘 · 자료구조워밍업클럽CS전공지식Week2

Taeho

인프런 워밍업 클럽 - CS Week 1

그림으로 쉽게 배우는 자료구조와 알고리즘(기본편)자료구조 & 알고리즘자료구조 : 데이터가 어떤 구조로 저장되고, 어떻게 사용되는지를 나타낸다.자료구조에 따라서 결과를 얻기 위한 처리 방법이 달라진다.알고리즘 : 어떤 문제를 해결하기 위한 확실한 방법시간 복잡도특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간Bit-Ω : 최선의 시간 복잡도Big-O : 최악의 시간 복잡도가장 많이 사용된다.Big-θ : 평균의 시간 복잡도ADT(Abstract Data Type)데이터의 논리적인 동작을 정의한다.구현 방법을 명시하지 않고, 자료구조의 특성과 연산만을 설명한다.내부 구현 세부사항은 숨기고 인터페이스만을 제공한다.Array배열의 인덱스 참조는 길이에 상관없이 한 번에 가져온다.삽입, 삭제의 성능이 좋지 않다.Linked List배열의 단점인 삽입, 삭제의 성능을 보완하기 위한 자료구조특정 데이터를 찾고 싶다면 노드를 순차적으로 순회해야 한다.저장하려는 데이터들을 메모리에 분산하여 할당하고, 해당 데이터를 서로 연결한다.노드를 사용하여 데이터들을 저장하고, 각 노드가 다음 노드를 가리키도록 한다.첫 노드의 주소만 알고 있으면 그 이후의 모든 노드에 접근할 수 있다.StackLIFO(Last-in First-out)단방향 Linked List를 사용하여 구현할 수 있다.head를 사용하여 스택을 간단하게 구현할 수 있다.데이터 삽입을 무조건 첫 번째 인덱스에 수행한다.QueueFIFO(First-in First-out)양방향 Linked List를 사용하여 구현할 수 있다.Deque데이터의 삽입과 제거를 head와 tail에서 자유롭게 할 수 있는 자료구조Hash TableHash Function해시 함수는 키(key)를 입력받아 해당 키의 저장 위치(버킷 또는 인덱스)를 결정하는 계산을 하는 함수좋은 해시 함수 ⇒ 데이터를 골고루 분배시켜주는 함수 Hash Collision해시 충돌은 해시 함수가 서로 다른 두 개 이상의 입력 값에 대해 동일한 해시 값을 출력하는 상황을 의미Hash 충돌이 발생한 곳의 Value들을 연결리스트로 구성하여 데이터들을 연결한다.기존값과 새로운 값을 동시에 저장할 수 있다.찾고자 하는 Value가 나올 때까지 연결리스트를 탐색한다.→ O(n)의 성능을 갖는다.Set데이터의 중복을 허용하지 않는 자료구조HashTable을 사용하여 구현할 수 있다.→ HashTable을 사용하기 때문에 HashSet이라고도 한다.→ HashTable의 value 값은 사용하지 않고 key만 사용하여 구현한다.(key가 key와 value의 역할을 수행한다.)그림으로 쉽게 배우는 운영체제OS가 하는 일프로세스 관리 : 여러 개의 프로그램들을 동시에 수행할 수 있게 한다.메모리 관리 : 모든 프로그램은 메모리에 올라가서 동작한다.H/W 관리 : 사용자가 직접 H/W에 접근하는 것을 막는다.File System 관리Program저장장치에 저장된 명령문의 집합체저장 장치만 사용하는 수동적인 존재Process실행중인 프로그램저장장치에 저장된 프로그램이 메모리에 올라갔을 대 프로세스라고 한다.메모리, CPU, I/O 작업을 수행하는 능동적인 존재Multi-Programming메모리 관점메모리에 여러개의 프로세스가 올라온 상태Multi-ProcessingCPU 관점CPU가 여러 개의 프로세스를 처리하는 것을 의미PCB(Process Control Block)프로세스가 만들어지면 운영체제는 해당 프로세스의 정보를 갖고 있는 PCB를 만들고 저장한다.PCB들은 연결 리스트로 저장된다.운영체제는 프로세스가 종료되면 연결리스트에서 해당 프로세스의 PCB를 제거한다.Context Switching프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행중인 프로세스의 상태를 저장하고, 다른 프로세스의 상태값으로 전환하는 작업작업 과정에서 PCB의 내용(프로세스 상태, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보 등)이 변경된다.Process의 생성OS가 부팅되고 0번 프로세스가 생성될 때 딱 한 번만 수행된다.→ 그 이후에 생성되는 프로세스는 fork()를 사용하여 복사해서 사용된다.→ 새로 생성하는 것보다 복사를 하는 것이 더 빠르기 때문좀비 프로세스부모 프로세스가 자식 프로세스보다 먼저 종료되거나 자식 프로세스가 비정상적으로 종료돼 exit()신호를 주지 못해서 Exit Status를 읽지 못해 메모리에 계속 살아있는 상태Thread프로세스 내에 존재하고, 1개 이상이 존재할 수 있다.하나의 프로세스 내에 있는 쓰레드들은 프로세스의 PCB, Code, Data, Heap 영역을 공유한다.Stack은 공유하지 않고, 쓰레드 마다 하나씩 갖고 있다.OS에서 작업을 처리하는 단위이다.Process vs Thread안정성Process는 독립적이기 때문에 서로 영향을 받지 않는다.Thread는 하나의 Process를 공유하기 때문에 하나의 Thread에 이상이 생기면 다른 Thread에도 이상이 전파될 수 있다.⇒ Process가 유리속도와 자원각각의 Process는 서로 고유한 자원을 갖는다.코드, 데이터, 힙, 스택 영역을 전부 따로 두고 있다.Process간에 통신을 하려면 IPC를 사용해야 해서 오버헤드가 크고 속도가 느리다.쓰레드는 하나의 Process의 자원을 스택 영역을 제외한 영역을 모두 공유하기 때문에 오버헤드가 느리다.CPU Scheduling목표목표들을 전부 만족할 수는 없다.→ 목표들에 따라 Trade-Off가 있기 때문ex) 처리량 ↑ ⇒ CPU 오래 할당, 응답시간 ↓ ⇒ 여러 프로세스에 CPU를 골고루 할당⇒ 처리량과 응답시간 사이에 Trade-Off가 발생한다.리소스 사용률CPU 사용률 높이기I/O 디바이스의 사용률 높이기오버헤드의 최소화Context Switching시에 발생하는 오버헤드를 최소화하는 것공평성모든 프로세스에게 우선순위에 따라 공평하게 CPU가 할당되어야 한다.처리량같은 시간내에 더 많은 처리를 할 수 있게 하는 것대기시간작업을 요청하고 실제 작업이 실행되기 전까지 대기하는 시간이 짧은 것응답시간사용자의 요청이 얼마나 빨리 요청하는지Retrospect아쉬운 점커리큘럼을 잘못 봐서 운영체제 쪽은 쉬는 날에 몰아서 들었다.커리큘럼을 명확하게 파악하고 당일에 들을 강의들을 정확히 정리해야겠다.잘한 점매일매일 빠지지 않고 강의를 들은 점매일 들은 강의 내용을 요약/정리하고 그 주차의 내용들을 하나의 게시글로 정리한 것

알고리즘 · 자료구조워밍업클럽CS전공지식Week1

하얀종이개발자

인프런 워밍업 클럽 2기 - CS 전공지식 스터디 특별미션

특별미션 특별 미션) 실수로 워밍업 클럽 출석을 빼먹었는데 우연히 데이터를 수정할 수 있는 권한이 주어졌습니다. 러너분의 이름(name)과 출석수(count)가 저장된 배열에서 여러분(나)의 데이터를 퀵정렬을 이용해 오름차순 정렬하고 가장 첫 번째 데이터인 여러분의 출석수를 변경하도록 코드를 작성해주세요. (퀵정렬 구현 부분도 변경) import java.util.Arrays; public class QuickSort { public static void main(String[] args) { User[] arr = { new User("홍길동", 5), new User("임꺽정", 4), new User("이순신", 3), new User("나", 1), new User("짱구", 5) }; System.out.println("===== 정렬 전 ====="); System.out.println(Arrays.toString(arr)); // 퀵정렬 실행 quickSort(arr, 0, arr.length - 1); // 첫 번째 나의 데이터의 출석수 변경 arr[0].count = 5; System.out.println("===== 정렬 후 ====="); System.out.println(Arrays.toString(arr)); } // 퀵정렬 함수 static void quickSort(User[] arr, int left, int right) { // 기저조건 if (left >= right) { return; } int pivotIndex = divide(arr, left, right); quickSort(arr, left, pivotIndex - 1); quickSort(arr, pivotIndex + 1, right); } // 배열을 나누고 피벗의 위치를 반환하는 함수 static int divide(User[] arr, int left, int right) { int pivot = arr[left].count; // 피벗은 첫 번째 원소의 count 값 int leftStartIndex = left + 1; int rightStartIndex = right; while (leftStartIndex <= rightStartIndex) { // 피벗보다 큰 값을 찾을 때까지 왼쪽에서 오른쪽으로 이동 while (leftStartIndex <= right && arr[leftStartIndex].count <= pivot) { leftStartIndex++; } // 피벗보다 작은 값을 찾을 때까지 오른쪽에서 왼쪽으로 이동 while (rightStartIndex >= left + 1 && arr[rightStartIndex].count >= pivot) { rightStartIndex--; } // 인덱스가 교차하지 않았으면 값 교환 if (leftStartIndex < rightStartIndex) { swap(arr, leftStartIndex, rightStartIndex); } } // 피벗과 rightStartIndex 교환 swap(arr, left, rightStartIndex); return rightStartIndex; } // 두 원소의 값을 교환하는 함수 static void swap(User[] arr, int index1, int index2) { User temp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = temp; } } class User { String name; int count; User(String name, int count) { this.name = name; this.count = count; } @Override public String toString() { return "{name: '" + name + "', count: " + count + "}"; } }  문제를 해결하기 위한 퀵정렬을 수행하고 나의 출석수를 변경하는 코드를 Java로 작성했습니다.count 기준으로 정렬하고, 정렬된 배열의 첫 번째 데이터인 나의 출석수를 5로 변경하는 로직입니다.개인 일정때문에 첫번째 OT를 빠졌었는데, 구제될 수 있는 기회가 생겼네요.감사합니다.!!

백엔드인프런워밍업클럽2기CS전공지식특별미션

Taeho

인프런 워밍업 클럽 - CS Week 3

AlgorithmInsertion Sort영역을 2개로 나누어서 정렬을 수행하는 알고리즘정렬된 영역정렬되지 않은 영역정렬되지 않은 영역에서 데이터를 하나씩 꺼내서 정렬된 영역 내의 적절한 위치에 삽입하여 정렬하는 알고리즘시간 복잡도 : O(n^2) 장점구현이 간단하고 이해하기 쉬움추가적인 메모리 소비가 적다.단점데이터의 상태에 따라 성능 편차가 크다.최선 : O(n)최악 : O(n^2)Merge Sort재귀로 구현하는 정렬 알고리즘시간 복잡도 : O(n log n)Divide & Conquer복잡한 문제를 더 작고 관리하기 쉬운 하위 문제들로 나누어 해결하는 알고리즘 설계 기법구현 방법분할(Divide): 정렬할 배열을 거의 같은 크기의 두 부분 배열로 나눈다.정복(Conquer): 각 부분 배열을 재귀적으로 정렬한다.결합(Combine): 정렬된 부분 배열들을 하나의 정렬된 배열로 병합한다.장점속도가 빠르다.단점병합 과정에서 임시 배열이 필요하여 추가적인 메모리 공간을 사용한다.이해와 구현이 어렵다.Quick SortPivot을 사용하여 정렬하는 알고리즘시간 복잡도평균 케이스: O(n log n)최악의 케이스: O(n^2)최선의 케이스: O(n log n)구현 방법피벗 선택배열에서 피벗으로 사용할 요소를 선택일반적으로 첫 번째, 마지막, 또는 중간 요소를 선택분할 (Partition)피벗을 기준으로 배열을 두 부분으로 나눈다.피벗보다 작은 요소들은 왼쪽으로, 큰 요소들은 오른쪽으로 이동재귀 호출분할된 두 부분 배열에 대해 Quick Sort를 재귀적으로 적용한다.종료 조건부분 배열의 크기가 1 이하가 될 때까지 재귀를 반복한다.결합정렬된 부분 배열들이 자동으로 하나의 정렬된 배열로 합친다.장점공간 효율성: 추가 메모리 공간을 거의 필요로 하지 않는 제자리 정렬 알고리즘캐시 친화적: 지역성이 좋아 캐시 성능이 우수병렬화 가능: 분할 정복 접근 방식으로 인해 병렬 처리에 적합단점불안정 정렬: 동일한 키 값을 가진 요소들의 상대적 순서가 보존되지 않을 수 있다.최악의 경우 성능: 피벗 선택이 잘못되면 O(n^2)의 시간 복잡도를 가질 수 있다.재귀적 특성: 재귀 호출로 인해 스택 오버플로우가 발생할 수 있다.Memoization중복되는 연산을 저장하고, 같은 계산이 필요할 때 저장된 결과를 사용한다.재귀 호출로 구현한다.재귀 함수에 비해 함수 호출 수가 줄어들어 성능이 비교적 우수하다.분할 정복을 해결할 때 재귀가 더 직관적인 경우에 사용한다.Tabulation상향식 계산 방식계산에 필요하지 않을 수 있는 값도 미리 계산해 테이블에 저장하는 방식재귀가 직관적이지 않은 경우에 사용한다.OS가상 메모리물리 메모리가 처리할 수 없는 용량을 프로세스들이 요구할 때 물리 메모리 내용의 일부를 하드 디스크에 있는 스왑 영역으로 옮기고 처리가 필요할 때 물리 메모리로 가져와서 처리한다.→ 물리 메모리가 처리할 수 없는 용량의 작업들을 처리할 수 있게 한다.메모리 관리자는 가상주소와 물리 주소를 1: 1 매핑 테이블로 관리한다.가상 메모리 시스템에서는 OS 영역을 제외한 나머지 영역을 일정한 크기로 나누어서 프로세스에게 할당한다.Segmentation(가변 분할 방식)세그멘테이션 테이블이라는 테이블이 존재Base AddressBound Address⇒ 두 주소를 사용하여 물리 메모리 주소를 계산한다.AddressBase Address프로세스나 세그먼트의 물리 메모리 상 시작 주소를 나타낸다.MMU의 base register에 저장되어 주소 변환에 사용Bound Address (또는 Limit)프로세스나 세그먼트의 크기를 나타낸다.MMU의 bound/limit register에 저장되어 메모리 보호에 사용된다.STBR(Segment Table Base Register)OS는 컨텍스트 스위칭을 할 때마다 메모리 관리자내의 Segment Table Base Register를 해당 프로세스의 것으로 값을 바꿔줘야 한다.→ Context Switching이 고비용 작업인 이유장점메모리를 가변적으로 분할할 수 있다.코드 영역, 데이터 영역, 스택 영역, 힙 영역을 모듈로 처리할 수 있어 공유와 각 영역에 대한 메모리 접근보호가 편리하다.단점외부 단편화 발생Paging(고정 분할 방식)세그멘테이션 기법의 외부 단편화를 해결하기 위해 고안된 배치 정책페이징은 메모리를 할당할 때 정해진 크기의 페이지로 나눈다.→ 외부 단편화가 발생되지 않는다.Page : 일정한 크기로 균일하게 나뉘어진 논리주소공간Frame : 일정한 크기로 균일하게 나뉘어진 물리주소공간Page Table가상 주소를 물리 주소로 변환하는데 사용하는 테이블각 프로세스의 가상 페이지 번호(VPN)을 물리 프레임 번호(PFN)로 매핑한다.각 프로세스마다 독립적인 Page Table을 갖는다.페이지 테이블에 Invalid로 되어 있으면 스왑영역에 저장되어 있는 상태Page Table Base Register(PTER)각 프로세스의 PCB에 위치하며, 해당 프로세스의 Page Table의 시작 주소를 가리킨다.OS는 컨텍스트 스위칭을 할 때마다 메모리 관리자내의 Segment Table Base Register를 해당 프로세스의 것으로 값을 바꿔줘야 한다.장점메모리를 효율적으로 관리할 수 있다.단점내부 단편화 발생세그멘테이션의 외부 단편화와 비교하면 많은 공간을 비교하지 않는다.Segmentation vs Paging세그멘테이션은 논리적인 영역별로 세그먼트를 나눈다.→ 세그먼트마다 크기를 다르게 나눌 수 있다.→ 크도 영역, 데이터 영역, 스택 영역, 힙 영역을 나눌 수 있다.페이징은 페이지의 크기가 고정되어 있어 논리적인 영역을 나눌 수 없다.→특정 영역만 떼어내서 공유하거나 권한을 부여하기 어렵다.Paged SegmentationSegmentation + PagingSegmentation Table과 Page Table을 결합하여 사용한다.메모리 접근 권한메모리의 특정 번지에 부여된 권한Read, Write, Execute각 프로세스는 코드 영역, 데이터 영역, 힙 영역, 스택 영역이 존재한다.→ 각 영역마다 접근 권한이 있다.코드 영역 : 프로그램 자체 ⇒ 읽기/실행 권한데이터 영역 : 일반변수, 전역변수, 상수로 선언한 변수 저장 ⇒ 읽기/(쓰기-Optional) 권한힙 영역 : 읽기/쓰기 권한스택 영역 : 읽기/쓰기 권한메모리 접근 권한 검사는 가상주소에서 물리주소로 변환될 때마다 일어난다.권한을 위반하는 경우 에러를 발생시킨다.DAT(Dynamic Address Translation, 동적 주소 변환)메모리 관리자가 물리 메모리와 스왑영역을 합쳐서 프로세스가 사용하는 가상주소를 물리주소로 변환하는 과정DAT를 거치면 프로세스는 마음대로 사용자 데이터를 물리 메모리에 배치할 수 있다.Page Table Entry(PTE)페이지 테이블을 이루고 있는 행접근 비트페이지가 메모리에 올라온 후 데이터에 접근이 있었는지 알려주는 비트1 : 메모리에 읽기나 실행 작업을 수행한 경우변경 비트페이지가 메모리에 올라온 후 데이터에 변경이 있었는지 알려주는 비트1 : 쓰기 작업을 수행한 경우유효 비트페이지가 물리 메모리에 있는지 알려주는 비트1 : 페이지가 스왑영역에 위치0 : 페이지가 물리 메모리에 위치권한 비트해당 메모리에 접근권한이 있는지 검사하는 비트Page Fault프로세스가 가상 메모리에 접근요청을 했을 때 MMU(메모리 관리자)는 페이지 테이블을 보고 물리 메모리의 프레임을 찾아낸다.물리 메모리에 프레임이 없다면 MMU는 Page Fault라는 인터럽트를 발생시킨다.Page Fault가 발생하면 스왑영역에 접근하고 해당 프로세스는 대기 상태가 된다.→ 스왑 영역의 데이터가 메모리로 올라가는 작업을 수행한다.→ 데이터가 물리 메모리로 올라가는 경우 해당 프로세스가 실행 상태로 변경된다.스레싱프로세스들이 실제 실행되는 시간보다 페이지를 교체하는 데에 더 많은 시간을 사용하고 있는 현상⇒ 페이지 부재(page fault)가 과도하게 발생하여 CPU 이용률이 급격히 떨어지는 현상다중 프로그래밍의 정도가 높아져 각 프로세스에 할당된 메모리가 부족해지면서 발생CPU 이용률 저하 → 운영체제의 다중 프로그래밍 증가 → 페이지 부재 증가의 악순환이 반복근본적인 원인 : 물리 메모리의 크기가 부족한 것→ 메모리의 크기를 늘려서 해결(H/W 수준)할 수 있다.S/W 수준의 해결 방법프로세스가 실행되면 일정량의 페이지를 할당한다.→ Page Fault가 빈번하게 발생하는 경우 : 더 많은 용량의 페이지를 할당한다.→ Page Fault가 거의 없는 경우 : 적은 용량의 페이지를 할당한다.File데이터 집합 구성에 따른 분류순차파일구조파일의 내용이 연속적으로 이어진 형태ex) 카세트테이프장점모든 데이터가 순차적으로 기록되기 때문에 공간의 낭비가 없고, 구조가 단순하다.단점특정지점에 바로 이동이 어려워 데이터를 삽입하거나 삭제하려면 탐색하는데 시간이 오래 걸린다.직접파일구조저장하려는 데이터의 위치를 해시 함수를 통해 결정하는 구조자료구조에서 Hash Table이라고 불린다.ex) JSON장점해시 함수를 사용하기 때문에 데이터 접근이 굉장히 빠르다.단점해시함수의 선정이 굉장히 중요하다.저장공간이 낭비될 수 있다.인덱스 파일 구조순차접근과 직접접근 방식의 장점을 취한 구조 <탐색키, 레코드 포인터> 쌍으로 구성데이터 파일과는 별도로 저장되며, 빠른 검색을 위해 사용된다.File Descriptor(= File Control Block)OS가 파일을 제어하기 위한 정보를 보관하는 Block파일마다 독립적으로 존재한다.저장장치에 존재하다가 파일이 오픈되면 메모리로 이동한다.OS가 관리하고 사용자가 직접 참조할 수 없다.사용자는 File Descriptor를 사용하여 File에 접근할 수 있다.파일의 맨 앞에 위치해서 사용자가 쓰거나 읽기를 시작하면 처음부터 진행한다.느낀점회사에서 프로젝트와 병행하면서 '오늘 하루는 괜찮지 않을까...?' 라는 안일한 생각을 했었지만 디스코드 커뮤니티에서 다들 열심히 일하는 모습을 보고 자극 받아 하루도 빠짐없이 완강하게 될 수 있었다.스터디를 하는게 강제성이 부여되는 것 같아서 안일한 생각을 뿌리칠 수 있었다.개발을 하다가 상사분들이 하는 얘기를 잘 따라가지 못했었는데 CS 강의를 듣고 나니 '아~ 이래서 그런 얘기를 하신거구나'라는 생각이 들게 되었다.다음번에도 스터디가 있으면 적극적으로 참여해야겠다. 

알고리즘 · 자료구조워밍업클럽CS전공지식Week3

Taeho

인프런 워밍업 클럽 - CS 3주차 과제

운영체제1. 메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.레지스터가장 빠른 기억장소CPU 내에 존재휘발성 메모리CPU를 나타내는 값에서 32bit, 64bit가 레지스터의 크기를 의미한다.CPU는 계산을 수행할 때 메인 메모리에 있는 값을 레지스터로 가져와서 계산한다.캐시휘발성 메모리레지스터와 메인 메모리 사이의 속도 간극을 메우기 위한 저장소필요한 데이터를 미리 가져와 저장하는 저장소성능의 이유로 여러 개가 존재한다.ex) L1, L2, L3CPU가 값을 요청해 레지스터로 값을 옮겨야 하는 경우 빠른 캐시를 순차적으로 확인하고, 캐시에 데이터가 없으면 메인 메모리를 조회한다.메인메모리휘발성 메모리OS와 다른 프로세스들이 올라가는 공간데이터를 저장하기 보다는 실행중인 프로그램만 저장한다.2. 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?경계 레지스터H/W적으로 OS 공간과 사용자 공간을 나누는 레지스터CPU 내에 존재한다.메모리 관리자가 사용자 프로세스가 경계 레지스터의 값을 벗어났다면 검사하고, 벗어났다면 해당 프로세스를 종료시킨다.3. 메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?가변 분할 방식 장점메모리를 가변적으로 분할할 수 있다.코드 영역, 데이터 영역, 스택 영역, 힙 영역을 모듈로 처리할 수 있어 공유와 각 영역에 대한 메모리 접근보호가 편리하다.가변 분할 방식 단점외부 단편화가 발생한다.고정 분할 방식 장점메모리를 효율적으로 관리할 수 있다.고정 분할 방식 단점내부 단편화가 발생한다.But. 가변 분할 방식의 단점인 외부 단편화에 비해 많은 공간을 차지하지 않는다.4. CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?쓰레싱5. HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요?필요하다고 생각한다.컴퓨터가 부팅될 때 ROM에 저장된 바이오스가 실행되고, 바이오스는 주요 하드웨어에 이상이 없는지 체크한다. 이 때 저장장치에 문제가 있다면 부팅이 정상적으로 이뤄지지 않는다.OS는 주로 HDD나 SSD에 설치되고 저장되고, 부팅시에 주요 장치에 이상이 없다면 HDD나 SSD의 마스터 부트 레코드에 저장된 부트로더를 메모리로 가져와서 실행시킨다.위의 2가지 이유 때문에 HDD와 SSD가 없어서는 안된다고 생각한다.6. 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?파일시스템은 효율적인 공간 관리를 위해 Free Block List라는 목록을 관리한다.파일이 지워질 때 파일 시스템이 파일의 모든 정보를 지우는 것이 아니라 파일 테이블의 헤더를 삭제하고 Free Block List에 추가한다.→ 실제로 파일의 데이터를 지우는 것이 아니다.이러한 특성으로 인하여 포렌식으로 파일을 복구할 수 있는 것이다.자료구조와 알고리즘1. 지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.버블 정렬장점이해와 구현이 간단하다.단점성능이 좋지 않다.시간 복잡도O(n^2)선택 정렬장점이해와 구현이 간단하다.단점성능이 좋지 않다.시간 복잡도최악 : O(n^2) - 배열이 역순으로 정렬되어 있는 경우삽입 정렬장점구현이 간단하고 이해하기 쉽다.추가적인 메모리 소비가 적다.단점성능이 좋지 않다.데이터의 상태에 따라 성능 편차가 크다.최선 : O(n)최악 : O(n^2)시간 복잡도O(n^2)병합 정렬장점속도가 빠르다.단점병합 과정에서 임시 배열이 필요하기 때무넹 추가적인 메모리 공간을 사용한다.이해와 구현이 복잡하다.시간 복잡도O(n log n)퀵 정렬장점공간 효율성: 추가 메모리 공간을 거의 필요로 하지 않는 제자리 정렬 알고리즘캐시 친화적: 지역성이 좋아 캐시 성능이 우수병렬화 가능: 분할 정복 접근 방식으로 인해 병렬 처리에 적합단점불안정 정렬: 동일한 키 값을 가진 요소들의 상대적 순서가 보존되지 않을 수 있다.최악의 경우 성능: 피벗 선택이 잘못되면 O(n^2)의 시간 복잡도를 가질 수 있다.재귀적 특성: 재귀 호출로 인해 스택 오버플로우가 발생할 수 있다.시간 복잡도평균 케이스: O(n log n)최악의 케이스: O(n^2)최선의 케이스: O(n log n)2. 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.타뷸레이션을 사용할 것 같다.메모이제이션의 경우 재귀호출이기 때문에 메모리를 많이 사용하기 때문에 메모리가 부족한 시스템에서 사용하는 것은 적합하지 않다.

알고리즘 · 자료구조워밍업클럽CS전공지식3주차미션

하얀종이개발자

인프런 워밍업 클럽 2기 - CS전공지식 스터디 미션 03 입니다.

CS전공지식 미션 2운영체제메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.레지스터CPU 내부에 있는 가장 빠른 메모리로 CPU가 계산하기위해 데이터를 임시로 저장CPU가 직접 접근할 수 있으며, 64bit 32bit CPU라는 말도 CPU의 연산단위이면서 레지스터의 크기를 나타냄캐시L1, L2, L3 캐시등이 있으면 CPU와 메모리 사이의 속도차이를 줄이기 위해 임시로 데이터를 저장하는 공간메인 메모리일반적으로 RAM을 의미하며 포노이만 구조의 CPU가 연산하기위해 프로세스를 올리는 공간전원이 꺼지면 데이터도 사라지는 휘발성 메모리임보조저장장치SSD, HDD 등으로 데이터를 영구적으로 저장할 수 있음, 메모리보다 속도가 느림전원이 꺼져도 데이터가 남아있는 비휘발성 메모리임 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?경계레지스터 : CPU내부에 존재해서 맨 앞에 저장하고 있는 운영체제 영역의 최대 범위를 기록하고 있어, 침범하지 못하게 함, 만약 경계 레지스터의 값을 넘긴 프로세스가 있으면 해당 프로세스를 종료시킴메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?가변분할방식은 프로세스의 크기에 맞춰 메모리를 분할하는 방식으로 프로세스의 영역별로 메모리를 분할 할 수 있어, 메모리 접근권한이나 메모리 공유를 할 수 있음, 그러나 외부단편화가 발생하여 메모리낭비가 생길 수 있음 고정분할방식은 고정된 크기로 메모리를 분할 하는 방식으로 가변분할방식의 외부단편화를 제거할 수 있음, 그러나 고정된 크기에 프로세스를 나눠서 할당하기 때문에 내부 단편화가 발생할 수 있고, 프로세스 영역별로 나눌수 없어 메모리 접근권한이나 공유하는데 어려움이 있음CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?스레싱많은 프로그램을 메모리에 올리면 스왑이 빈번하게 일어날 수 있음이때 CPU가 실제 작업을 처리하지 못하고 스왑 작업에만 몰두하게 되어 CPU를 사용하지 못하는 현상을 말함HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요?꼭 필요하지는 않음컴퓨터가 실행되기 위해서는 RAM이 필요하지만, HDD나 SSD는 데이터의 영구적 저장을 위한 보조 장치임만약 시스템이 네트워크 기반 부팅을 사용하거나 RAM 디스크를 활용하는 경우, HDD나 SSD 없이도 컴퓨터를 실행할 수 있음. 다만 RAM은 전원이 꺼지면 데이터가 모두 사라지기 때문에 일반적으로는 운영체제를 포함한 데이터를 저장하기 위해 HDD나 SSD가 필요파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?파일을 삭제하더라도 실제로 데이터는 즉시 삭제되지 않고, 파일 시스템에서 해당 파일의 참조만 제거됨실제 데이터는 디스크에 그대로 남아 있기 때문에 포렌식 도구를 이용해 복구할 수 있음.완전한 삭제를 위해서는 데이터를 덮어쓰는 과정을 거쳐야 함자료구조와 알고리즘지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.버블 정렬 (Bubble Sort)O(n²)장점 : 단순한 구조로 이해 & 구현이 쉬움, 거의 정렬된 배열에서는 빠르게 종료될 수 있음단점 : 속도가 느리고, 다른 효율적인 정렬 알고리즘에 비해 많이 사용되지 않음선택 정렬 (Selection Sort)O(n²)장점 : 메모리 사용이 적고, 단순한 구조로 이해 & 구현이 쉬움단점 : 속도가 느리고, 다른 효율적인 정렬 알고리즘에 비해 많이 사용되지 않음삽입 정렬 (Insertion Sort)O(n²)장점 : 작은 데이터나 거의 정렬된 데이터에 대해 매우 효율적단점 : 속도가 느려서 대규모 데이터에 비효율적병합 정렬 (Merge Sort)O(n log n)장점 : 속도가 빠르며 대규모 데이터에서도 일정한 성능을 보임단점 : 추가 메모리 공간이 필요하며, 메모리 효율이 떨어질 수 있음퀵 정렬 (Quick Sort)평균 O(n log n), 최악 O(n²)장점 : 평균적으로 매우 빠르고, 메모리 사용이 적음단점 : 피벗 선택에 따라 성능이 달라지며, 최악의 경우 속도가 느려질 수 있음 (그러나 최악이 되는 경우는 거의 없음)메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.메모이제이션(Memoization)재귀를 사용하면서 이미 계산된 값을 기억하고 활용하는 방식으로, 필요할 때 계산된 값을 바로 반환해서 사용재귀 구조를 그대로 유지하면서도 중복 계산을 피할 수 있음타뷸레이션(Tabulation)문제를 하위 문제부터 점진적으로 해결하는 방식으로, 반복문을 사용해 값을 채워나가는 방식메모리 부족한 상황이라면 타뷸레이션을 사용할 것 같습니다.타뷸레이션은 스택 오버플로우 위험이 없고, 재귀 호출에 따른 추가적인 메모리 오버헤드가 발생하지 않기 때문에 메모리를 더 효율적으로 사용할 수 있습니다. 

백엔드CS전공지식그림으로쉽게배우는자료구조와알고리즘그림으로쉽게배우는운영체제인프런워밍업클럽2기감자

하얀종이개발자

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

운영체제 2주차 학습 요약 CPU 스케쥴링 알고리즘SJF (Shortest Job First)짧은 작업 시간을 가진 프로세스에 먼저 CPU를 할당하는 방식버스트 타임이 긴 프로세스는 계속 실행되지 않을 수 있고, 어떤 프로세스가 얼마나 실행될지 예측이 어려움RR (Round Robin)시간을 균등하게 분배하여 각 프로세스에 순차적으로 CPU를 할당하는 방식컨텍스트 스위칭으로 인해 처리량이 늘어남MLFQ (Multi Level Feedback Queue)프로세스의 우선순위를 동적으로 조절하여 CPU를 효율적으로 할당하는 방식오늘날 운영체제에서 가장 일반적으로 사용됨프로세스 동기화여러 프로세스가 공유 자원에 동시에 접근할 때 순서를 정하여 데이터의 일관성을 유지하는 것프로세스간 통신의 종류한 컴퓨터 내에서 프로세스간 통신하는 방법 : 파일 or 파이프를 이용한 프로세스 내에서 쓰레드간 통신하는 방법 : 데이터 or 힙영역을 이용네트워크를 이용하여 통신하는 방법 : 소켓통신, RPC공유자원과 임계영역공유자원은 프로세스 혹은 스레드간 통신할 때 공동으로 이용하는 변수나 파일 같은 것들공유자원은 여러 프로세스가 공유하고 있기 때문에 각 프로세스의 접근 순서에따라 결과가 달라질 수 있음임계영역은 프로세스 혹은 스레드가 동시에 사용하면 안되는 영역 (접근 순서등의 이유로 결과가 달라지는 영역)경쟁조건은 공유자원을 서로 사용하기 위해 경쟁하는 것임계구역 문제를 해결하기 위한 조건상호배체임계영역엔 하나의 프로세스만 접근해야 함한정대기기다리는 프로세스는 언제가는 임계영역에 접근 할 수 있어야함진행의 융통성한 프로세스가 다른 프로세스의 일을 방해해서는 안됨세마포어 & 모니터뮤텍스는 공유자원을 lock()과 unlock()을 이용하여 프로세스의 접근을 제어하는 메커니즘여러 프로세스의 접근을 관리할 수 있으면 세마포어 (뮤텍스는 동기화 대상이 오직 하나임)세마포어는 잘못된 사용으로 임계영역을 보호받지 못할 수 있음 (세마포어를 사용하지 않고 임계구역에 들어간 경우)이를 해결한 방식이 모니터모니터는 공유자원을 숨기고 접근에 대한 인터페이스만 제공하여 공유자원에 안전하게 접근하게 하는 메커니즘운영체제가 처리하는게 아니라 프로그래밍 언어차원에서 지원하는 방법임교착상태 (데드락)두개 이상의 프로세스들이 서로가 가진 자원을 기다리다 아무도 작업을 진행하지 못하는 상태데드락 필요조건상호배제비선점점유대기원형대기은행원 알고리즘총 자원의 양과 현재 할당한 자원의 양을 기준으로 안정 또는 불안정 상태로 나누고, 교착상태가 발생하지 않는 수준이 되도록 자원을 할당하는 알고리즘검출 & 회복교착상태는 어떻게 검출하지?가벼운 교착상태 검출 (타이머)일정시간마다 작업을 조작하고 교착상태가 발생하면 체크포인트로 롤백무거운 교착상태 검출 (순환구조)교착상태를 일으킨 프로세스를 강제 종료시키고 다시 실행 시킬때 체크포인트로 롤백오버헤드가 발생하지만 억울하게 종료되는 프로세스는 발생하지않음메모리레지스터 (32bit 또는 64bit)캐시CPU와 메인메모리 속도 차이 때문에 미리 데이터를 저장하는 임시공간메인메모리 (RAM)프로세스를 로드, 휘발성보조기억장치 (SSD, HDD)디스크 저장, 비휘발성물리 주소 - 물리적인 메모리 주소논리 주소 - 사용자 관점에서 본 상대적 주소, 사용자는 논리 주소를 통해 물리 주소로 접근메모리 할당방식가변분할방식메모리에 연속해서 프로세스를 할당단점으로 외부 단편화가 발생할 수 있음고정분할방식메모리를 정해진 크기로 나누어 프로세스를 할당단점으로 내부 단편화가 발생할 수 있음버디시스템메모리를 2의 제곱 수로 분할하여 할당하는 방식가변분할방식과 고정분할방식을 합친 방법 알고리즘 & 자료구조 2주차 학습 요약 재귀 & 재귀적으로 생각하기재귀는 자기 자신을 다시 호출하는 함수를 말함어떤 문제를 해결하기 위해 문제의 부분 문제를 같은방식으로 해결하는 과정하향식 풀이에서 활용됨 (하위 문제를 기반으로 해결)하노이탑 구현하기세개의 기둥과 서로 다른 크기의 원반들이 있을때 가장 큰 원반이 아래에 있고 위로 갈수록 작은 원반으로 이루어져있음하나의 기둥에 있는 원반들을 다른 기둥으로 옮겨야 함기둥 A에 있는 원반을 기둥 C로 옮기기 (하향식 접근으로 풀이)  처음 시작 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편) 캡쳐  모두 옮김그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편) 캡쳐자바코드public class HanoiTop { void hanoi(int count, String from, String to, String temp){ if(count == 0) return; hanoi(count - 1, from, temp, to); System.out.printf("원반 %d를 %s에서 %s로 이동\n", count, from, to); hanoi(count - 1, temp, to, from); } public static void main(String[] args) { HanoiTop hanoiTop = new HanoiTop(); hanoiTop.hanoi(3, "A", "C", "B"); } } 버블정렬앞에 있는 숫자와 옆에 있는 숫자를 비교해서 자리를 바꾸는 알고리즘자바코드public class BubbleSort { void bubbleSort(int[] arr) { // 사이클 - 자리교체는 (배열의 갯수 - 1) 번 수행함 for (int i = 0; i < arr.length - 1; i++) { // 횟수 - 정렬이 된 원소의 이전 원소보다 하나 이전의 원소까지 순회 // 시작점이 (arr.length-i-1)번 임 for (int j = 0; j < (arr.length - i - 1); j++) { // 앞의 데이터가 뒤에 데이터보다 더 크다면? if (arr[j] > arr[j + 1]) { // 데이터 자리변경 int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } public static void main(String[] args) { int[] arr = {2, 3, 1, 4}; // 정렬 전 - arr = [2, 3, 1, 4] System.out.println("정렬 전 - arr = " + Arrays.toString(arr)); BubbleSort bubbleSort = new BubbleSort(); bubbleSort.bubbleSort(arr); // 정렬 후 - arr = [1, 2, 3, 4] System.out.println("정렬 후 - arr = " + Arrays.toString(arr)); } } 선택정렬정렬되지 않은 배열의 첫번째 원소를 시작으로 마지막 원소까지 탐색하여 가장 작은 값을 정렬되지 않은 첫번째 배열로 가져오는 알고리즘자바코드public class SelectionSort { void selectionSort(int[] arr) { // 1 사이클의 순회는(배열의 갯수 - 1) 번 수행됨 for (int i = 0; i < arr.length - 1; i++) { int minValueIndex = i; // 가장 작은 값을 탐색하기위해 순회 for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[minValueIndex]) { // 작은값 저장 minValueIndex = j; } } // 자리 변경 int temp = arr[i]; arr[i] = arr[minValueIndex]; arr[minValueIndex] = temp; } } public static void main(String[] args) { int[] arr = {4, 2, 1, 3}; // 정렬 전 - arr = [4, 2, 1, 3] System.out.println("정렬 전 - arr = " + Arrays.toString(arr)); SelectionSort selectionSort = new SelectionSort(); selectionSort.selectionSort(arr); // 정렬 후 - arr = [1, 2, 3, 4] System.out.println("정렬 후 - arr = " + Arrays.toString(arr)); } }  회고2주차 스터디를 진행하면서 정해진 진도도 학습하면서, 스터디안에 발표스터디에 참여해서 복습도 하는 과정이었어요. 적어보였던 운영체제의 내용이 생각보다 많아서 정리하는데 은근 시간이 오래 걸리더라구요. 그래도 스터디안의 발표 스터디에 참여하여 정리내용을 발표하고 다른 스터디원들의 발표내용도 듣고 헷갈리는 부분도 토론해서 도움이 많이 되었던 한 주 였던것 같습니다.스터디 발표 정리 자료 캡쳐그리고 이번 알고리즘 강의에서는 항상 어렵게 느꼈던 재귀에 대해 조금은 이해한게 너무 좋았습니다.어떤 문제를 해결하기 위해 문제의 부분 문제를 같은 방식으로 분해하여 해결한다.!! 재귀함수 내에서 자기 자신을 호출할 때 이 함수가 벌써 구현이 되어있다고 가정하고 재귀함수를 구현한다.!! 많이 연습해봐야겠지만 그래도 재귀적으로 생각하는 방법을 느낄 수 있었던 것 같습니다.마지막 1주가 남았는데, 끝까지 열심히 해서 끝까지 완주해야겠네요. 화이팅

백엔드인프런워밍업클럽2기CS전공지식2주차발자국감자

Taeho

인프런 워밍업 클럽 - CS 2주차 과제

운영체제FIFO 스케줄링의 장단점이 뭔가요?장점구현이 간단하고 이해하기 쉽다공정성이 보장된다 - 모든 프로세스가 동등하게 처리된다.기아 현상이 발생하지 않는다.기아 현상 : 특정 프로세스의 우선 순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태단점긴 대기 시간을 초래할 수 있다.CPU 사용률이 낮아질 수 있다Burst Time이 짧은 프로세스가 Burst Time이 긴 프로세스 보다 늦게 들어온 경우에 Busrt Time이 짧은 프로세스가 오래 기다려야 한다. SJF를 사용하기 여러운 이유가 뭔가요?어떤 프로세스가 얼마나 실행될지 예측하기 힘들다.→ 예측하는 것이 거의 불가능하다.Burst Time이 긴 프로세스는 아주 오랫동안 실행되지 않을 수 있다.→ Burst Time이 긴 프로세스는 Burst Time이 짧은 프로세스에게 계속해서 우선순위가 밀린다. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?Time Slice를 작게 만드는 경우 Context Switching이 빈번하게 발생된다.→ CPU에서 프로세스가 실행되는 것보다 Context Switching이 빈번하게 발생함에 따라 성능이 떨어진다. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?CPU를 사용하는 프로세스가 실행하다가 스스로 CPU를 반납하는 경우 CPU 사용률이 낮음→ I/O Bound Process일 확률이 높음CPU를 사용하는 프로세스가 실행하다가 CPU 스케줄러에 의해 강제로 CPU를 뺏기는 상황인 경우 CPU 사용률이 높음→ CPU Bound Process일 확률이 높음 공유자원이란 무엇인가요?공유자원 : 여러 프로세스나 스레드가 동시에 접근하고 사용할 수 있는 컴퓨터 자원여러 프로세스가 공유하기 때문에 각 프로세스의 접근 순서에 따라서 결과가 달라질 수 있다.컨텍스트 스위칭으로 시분할 처리를 하기 때문에 프로세스간의 실행 순서를 예측하기 어렵다.⇒ 동기화 문제가 발생할 수 있다. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?상호 배제 : 공유 자원은 한 번에 하나의 프로세스만 사용할 수 있다.비선점 : 다른 프로세스가 사용 중인 자원을 강제로 빼앗을 수 없다.점유와 대기 : 프로세스가 이미 자원을 보유한 상태에서 다른 자원을 요청하며 대기한다.원형 대기 : 점유와 대기를 하는 프로세스들의 관계가 원형이다.자료구조와 알고리즘재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?무한 재귀가 발생하여 스택 오버플로우 오류가 발생할 수 있다. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n){ if (n < 1) { return 0; } if (n % 2 != 0) { return n + sumOdd(n - 2) } return sumOdd(n - 1) } console.log(sumOdd(10)) // 25

알고리즘 · 자료구조워밍업클럽CS전공지식2주차미션

Taeho

인프런 워밍업 클럽 - CS Day 6

AlgorithmRecursion(재귀)어떠한 것을 정의할 때 자기 자신을 참조하는 것을 의미한다.재귀함수 : 재귀적으로 정의된 함수재귀함수는 콜스택이라는 메모리 가득차게 되는 경우 자동으로 종료된다.기저 조건 : 재귀함수가 종료될 수 있는 탈출 조건기저 조건이 반드시 있어야 정상적으로 수행할 수 있다.재귀함수는 함수를 호출할 때마다 Call Stack이라는 메모리 공간에 호출정보가 저장된다.→ 재귀함수는 Loop문보다 더 많은 메모리 공간을 차지한다.Call Stack(= Stack)함수가 호출되면서 올라가는 메모리 영역함수가 종료되면 콜스택에서 제거된다.FILO(First-In Last-Out)재귀함수를 사용하는 이유Loop를 대신한다기 보다는 더 복잡한 문제를 쉽게 해결하기 위해 사용된다.ex) Factorial재귀함수를 쉽게 작성하는 방법재귀함수 내에서 자기 자신을 호출할 때 해당 함수가 벌써 구현이 되어있다고 가정한다.5! = 5 * 4 * 3 * 2 * 1 5 * factorial(4) 4! = 4 * 3 * 2 * 1 4 * factorial(3) → factorial(number) = number * factorial(number - 1) OSCPU Scheduling AlgorithmSJF(Shortest Job First)Burst Time이 짧은 작업부터 CPU를 할당한다.문제점어떤 프로세스가 얼마나 실행될지 예측하기 힘들다.→ 예측하는 것이 거의 불가능하다.Burst Time이 긴 프로세스는 아주 오랫동안 실행되지 않을 수 있다.→ Burst Time이 긴 프로세스는 Burst Time이 짧은 프로세스에게 계속해서 우선순위가 밀린다.⇒ 사용되지 않는다.RR(Round Robin)하나의 프로세스에게 일정 시간만 CPU를 할당하고 할당된 시간이 지나면 강제로 다른 프로세스에게 일정시간만큼 CPU를 할당하는 방식→ 강제로 CPU를 뺏긴 프로세스는 Queue의 가장 마지막으로 밀려난다.Time Slice(=Time Quantum) : 프로세스에게 할당하는 일정 시간Time Slice에 따라서 RR의 성능이 좌지우지된다.Time Slice를 작게 만드는 경우 Context Switching이 빈번하게 발생된다.→ Context Switching이 빈번하게 발생함에 따라 성능이 떨어진다.Time Slice가 큰 경우 FIFO와 동일하게 동작한다.Time Slice 예시Window Time Slice : 20msUnix Time Slice : 100ms단점Context Switching이 존재한다.→ 평균 대기시간이 FIFO와 동일하다면 FIFO가 더 성능이 좋다.MLFQ(Multi Level Feedback Queue)RR의 업그레이드 버전주로 사용되는 CPU 스케줄링 알고리즘CPU Bound Process : CPU를 할당받은 시간을 대부분 CPU 연산을 수행하는 프로세스CPU 사용률과 처리량이 중요I/O Bound Process : 대부분의 시간을 I/O 작업에 수행하고 적은 시간만 CPU 연산을 하는 프로세스- 응답시간이 중요MLFQ는 기본적으로 CPU 사용률과 I/O 사용률이 좋게 나오는 작은 크기의 Time Slice를 사용한다.CPU Bound Process에게는 CPU 사용률을 높이기 위해 Time Slice를 높게 할당한다.I/O Bound Process에게는 I/O 사용률을 높이기 위해 Time Slice를 낮게 할당한다.OS는 어떻게 CPU Bound Process와 I/O Bound Process를 구분할까?CPU를 사용하는 프로세스가 실행하다가 스스로 CPU를 반납하는 경우 CPU 사용률이 낮음→ I/O Bound Process일 확률이 높음CPU를 사용하는 프로세스가 실행하다가 CPU 스케줄러에 의해 강제로 CPU를 뺏기는 상황인 경우 CPU 사용률이 높음→ CPU Bound Process일 확률이 높음구현 방법우선순위를 갖는 큐를 여러개 준비한다.우선순위가 높으면 Time Slice가 작다.우선순위가 낮아질수록 Time Slice가 커진다.

알고리즘 · 자료구조워밍업클럽CS전공지식DAY6

Taeho

인프런 워밍업 클럽 - CS 1주차 미션

운영체제while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 } 위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?Interrupt 방식프로그램과 프로세스가 어떻게 다른가요?Program저장장치에 저장된 명령문의 집합체저장 장치만 사용하는 수동적인 존재Process실행중인 프로그램저장장치에 저장된 프로그램이 메모리에 올라갔을 때 프로세스라고 한다.메모리, CPU, I/O 작업을 수행하는 능동적인 존재멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?Multi-Programming메모리에 여러개의 프로세스가 올라온 상태메모리 관점으로 정의Multi-ProcessingCPU 관점으로 정의CPU가 여러 개의 프로세스를 처리하는 것을 의미한다.운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?PCB(Process Control Block)과 CPU Scheduling을 사용해서 프로세스를 관리한다.컨텍스트 스위칭이란 뭔가요?프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행중인 프로세스의 상태를 저장하고, 다른 프로세스의 상태값으로 전환하는 작업Context Switching이 발생할 때 PCB의 내용이 변경된다.프로세스 상태, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보 등이 변경된다.자료구조와 알고리즘여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.선택한 자료구조 : List | HashTable교실의 학생 정보가 항상 일정하다고 생각하지 않기 때문이다.교실에 새로운 학생이 전학을 온다던가 기존에 있던 학생이 전학을 간다고 한다면 고정된 사이즈를 갖고 있는 Array의 경우 삽입/삭제 처리가 어려울 것이라고 생각된다.만일 전학이 빈번하지 않는다고 한다면 Array를 사용하는 편이 더 효율적이라고 생각한다.한명의 학생에게 고유한 학번을 부여하고, 해당 학번에 학생을 매핑해 놓는다고 한다면 가장 성능이 좋을 것이라고 생각한다.여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.선택한 자료구조 : Queue먼저 주문을 한 고객부터 순서대로 주문을 처리해야 하기 때문이다.

알고리즘 · 자료구조워밍업클럽CS전공지식1주차미션

하얀종이개발자

인프런 워밍업 클럽 2기 - CS전공지식 스터디 미션 01 입니다.

CS전공지식 미션 1 운영체제while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?스스로가 체크하지 않고, 플레이어가 스킬을 사용하면 스킬이 활성화되었다고 알려주는 인터럽트 방식을 사용할 것 같습니다. 인터럽트 방식은 다른 작업을 수행하고 있다가 하고있는 동작을 멈추고 인터럽트 서비스 루틴을 실행하여 그 인터럽트를 처리하는 방식입니다. 프로그램과 프로세스가 어떻게 다른가요?프로그램은 저장장치에 저장된 명령어의 집합으로 이루어진 애플리케이션이나 .exe 실행파일을 말하는데, 어떠한 트리거에 의해 프로그램이 저장장치에서 메모리에 올라가 운영체제 관리하에 놓이면 프로세스라고 합니다. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티프로그래밍은 메모리에 여러개의 애플리케이션이 올라가는 것을 말하고, 멀티 프로세싱은 CPU가 여러개의 프로세스를 처리하는 것을 말합니다. 메모리의 관점에서 여러개를 처리하느냐, CPU의 관점에서 여러개를 처리하느냐로 나눌 수 있습니다. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?운영체제는 프로세스를 관리하기 위해 프로세스 컨트롤 블록(PCB)를 활용합니다. PCB는 각 프로그램이 메모리에 올라오면 각각 생성되어 연결리스트로 연결되어 저장됩니다. 각 PCB는 프로세스의 식별자, 프로그램카운터, 레지스터 정보등을 담고 있습니다. CPU가 여러개의 프로세스를 번갈아가면서 처리할때 작업중이던 프로세스는 PCB의 정보를 업데이트하고 다른 프로세스는 PCB에서 정보를 읽어서 명령어를 실행합니다. 컨텍스트 스위칭이란 뭔가요?컨텍스트 스위칭은 CPU가 스케쥴링에 의한 시분할 처리로 프로세스를 실행하는 중에 다른 프로세스를 실행하기위해 실행중인 프로세스를 잠시 저장하고 다른 프로세스의 상태값으로 교체하는 작업을 말합니다. 이때 기존 실행중이던 프로세스의 작업내용을 PCB에 저장하고, 실행될 프로세스는 PCB에서 읽어와 CPU에 프로그램카운터 등 레지스터값이 세팅됩니다. 자료구조와 알고리즘여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.학생정보를 저장하기 위해서는 해시 테이블구조를 선택하겠습니다. 학생정보는학생을 식별할 수 있어야하고 학생의 여러 속성정보들을 가져야하기 때문에 학생의 식별자를 key로 가지고 학생의 정보를 value로 가지고 있으면 학생을 검색하는데에도 빠르고 O(1), 데이터를 추가하는데도 용이하기 때문입니다. 다만 해시테이블 구조는 메모리가 많이 필요하기때문에 유의해야합니다.자바 코드로 예시를 작성해봤습니다. public class Student { String name; // 이름 int age; // 나이 String major; // 전공 int grade; // 학년 // 생성자 public Student(String name, int age, String major, int grade) { this.name = name; this.age = age; this.major = major; this.grade = grade; } public static void main(String[] args) { // HashMap 생성 (키는 학생 고유 번호, 값은 학생 정보) HashMap<Integer, Student> studentMap = new HashMap<>(); // 학생 정보 추가 studentMap.put(101, new Student("김미소", 20, "컴퓨터공학", 2)); studentMap.put(102, new Student("이고은", 21, "인문학", 3)); studentMap.put(103, new Student("박현성", 19, "경영학", 1)); // 모든 학생 정보 출력 for (Integer id : studentMap.keySet()) { System.out.println("학생 고유 번호: " + id + ", " + studentMap.get(id)); } } }  여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.주문은 들어온 순서대로 처리되기 때문에 선입선출(First In First Out)방식인 구조인 큐를 선택하겠습니다. 큐는 가장 먼저 들어온 주문이 먼저 처리되고 제거되기 때문에 순서대로 처리하는 방식에 적합합니다.

알고리즘 · 자료구조그림으로쉽게배우는기초컴퓨터과학(CS)감자CS전공지식인프런워밍업클럽

Taeho

인프런 워밍업 클럽 - CS Day 14

Algorithm재귀가 성능에 영향을 미치는 경우Call Stack중복되는 연산→ 중복되는 연산을 저장하고, 같은 계산이 필요할 때 저장된 결과를 사용한다.→ 함수 호출 수가 줄어듦.→ 성능이 좋아진다.Memoization계산 결과를 저장해서 여러 번 계산하지 않도록 하는 기법단점속도를 위해서 메모리(저장 공간)를 사용한다.재귀 함수이기 때문에 Call Stack을 차지하는 단점은 변하지 않는다.Tabulation상향식 계산 방식계산에 필요하지 않을 수 있는 값도 미리 계산해 테이블에 저장하는 방식Memoization vs TabulationMemoization : 해결하기 힘든 문제를 하향식으로 접근하여 복잡한 문제를 쉽게 해결할 수 있다.분할 정복을 해결할 때 재귀가 더 직관적인 경우에 유리Tabulation재귀가 직관적이지 않은 경우에 유리OSFile저장장치에 저장된다.구조Header파일의 속성이 담겨있다.Data데이터의 집합데이터 집합 구성에 따른 분류순차파일구조파일의 내용이 연속적으로 이어진 형태ex) 카세트테이프장점모든 데이터가 순차적으로 기록되기 때문에 공간의 낭비가 없고, 구조가 단순하다.단점특정지점에 바로 이동이 어려워 데이터를 삽입하거나 삭제하려면 탐색하는데 시간이 오래 걸린다.직접파일구조저장하려는 데이터의 위치를 해시 함수를 통해 결정하는 구조자료구조에서 Hash Table이라고 불린다.ex) JSON장점해시 함수를 사용하기 때문에 데이터 접근이 굉장히 빠르다.단점해시함수의 선정이 굉장히 중요하다.저장공간이 낭비될 수 있다.인덱스 파일 구조순차접근과 직접접근 방식의 장점을 취한 구조 <탐색키, 레코드 포인터> 쌍으로 구성데이터 파일과는 별도로 저장되며, 빠른 검색을 위해 사용된다.File System파일을 관리하기 위해 OS가 둔 파일 관리자파일 테이블을 이용하여 파일을 관리한다.기능파일과 디렉토리 생성파일과 디렉토리 수정/삭제파일 권한 관리무결성 보장백업과 복구암호화동작블록 저장장치에 저장 → 전송 단위 : 블록사용자가 바이트 단위로 파일에 접근이 가능하도록 지원한다.File Descriptor(= File Control Block)OS가 파일을 제어하기 위한 정보를 보관하는 Block파일마다 독립적으로 존재한다.저장장치에 존재하다가 파일이 오픈되면 메모리로 이동한다.OS가 관리하고 사용자가 직접 참조할 수 없다.사용자는 File Descriptor를 사용하여 File에 접근할 수 있다.파일의 맨 앞에 위치해서 사용자가 쓰거나 읽기를 시작하면 처음부터 진행한다.Directory1개 이상의 파일과 자식 디렉토리를 가질 수 있다.운영체제 마다 가장 최상단의 디렉토리 명칭이 다르다.Windows : Partition Name(ex : C:)Unix, Linux : Root('/')디렉토리도 파일정보가 저장되어 있는 하나의 파일이다.구조디렉토리 헤더 : 디렉토리 정보가 시작하는 위치를 가리킨다.다단계 디렉토리어떠한 디렉토리에서도 하위 디렉토리를 만들 수 있는 트리 구조File & Disk전체 디스크 공간을 블록(일정한 크기를 갖는 공간)으로 나누고, 그 공간에 주소를 할당해 관리한다.- 일반적으로 한 블록의 크기는 1 ~ 8KB이다.- 하나의 파일은 여러개의 블록으로 이루어진다.파일시스템은 파일정보를 파일테이블로 관리한다.파일이 시작하는 블록의 위치정보가 담겨있다.블록 연결 방식에 따른 분류연속할당파일을 구성하는 블록들을 디스크에 연속적으로 저장하는 방식파일의 시작 블록만 알면 파일의 전체를 알 수 있다.외부 단편화가 발생하여 실제로 사용하지 않는다.불연속할당디스크의 비어있는 공간에 데이터를 분산하여 저장하는 방식- 분산된 블록은 파일시스템이 관리한다.연결 할당파일에 속한 데이터를 연결리스트를 사용하여 관리한다.파일테이블에는 시작 블록에 대한 정보만 저장하고 나머지는 연결리스트를 이용해 다른 블록에 접근한다.인덱스 할당테이블의 블록 포인터가데이터 블록에 직접 연결하는 것이 아니라 데이터들의 인덱스를 갖고 있는 인덱스 블록을 연결한다.데이터가 많아서 테이블이 꽉 찬경우 인덱스 블록을 더 만들어 연결하기 때문에 테이블 확장에 용이하다.파일 크기가 작다면 데이터를 바로 참조하는 블록 포인터를 이용한다.파일의 크기가 크다면 간접 포인터를 이용해 많은 데이터에 접근할 수 있다.i-node라는 방식으로 유닉스와 리눅스에서 많이 사용되고 있다.Free Block List파일시스템이 효율적인 공간 관리를 위해 빈 공간을 모아둔 목록파일 시스템은 파일의 모든 정보를 지우는 것이 아니라 파일 테이블의 헤더를 삭제하고 Free Block List에 추가한다.→ 포렌식을 통해 데이터를 복구할 수 있다.

알고리즘 · 자료구조워밍업클럽CS전공지식DAY14

Taeho

인프런 워밍업 클럽 - CS Day 13

Algorithm한 번 정렬이 진행될 때마다 피벗이 정렬되고 정렬될 배열을 좌우로 나눠 재귀호출하여 모든 원소를 정렬한다.Quick Sort구현 방법피벗 선택배열에서 피벗으로 사용할 요소를 선택일반적으로 첫 번째, 마지막, 또는 중간 요소를 선택분할 (Partition)피벗을 기준으로 배열을 두 부분으로 나눈다.피벗보다 작은 요소들은 왼쪽으로, 큰 요소들은 오른쪽으로 이동재귀 호출분할된 두 부분 배열에 대해 Quick Sort를 재귀적으로 적용한다.종료 조건부분 배열의 크기가 1 이하가 될 때까지 재귀를 반복한다.결합정렬된 부분 배열들이 자동으로 하나의 정렬된 배열로 합친다.시간 복잡도평균 케이스: O(n log n)최악의 케이스: O(n^2)최선의 케이스: O(n log n)장점공간 효율성: 추가 메모리 공간을 거의 필요로 하지 않는 제자리 정렬 알고리즘캐시 친화적: 지역성이 좋아 캐시 성능이 우수병렬화 가능: 분할 정복 접근 방식으로 인해 병렬 처리에 적합단점불안정 정렬: 동일한 키 값을 가진 요소들의 상대적 순서가 보존되지 않을 수 있다.최악의 경우 성능: 피벗 선택이 잘못되면 O(n^2)의 시간 복잡도를 가질 수 있다.재귀적 특성: 재귀 호출로 인해 스택 오버플로우가 발생할 수 있다.OS주변 장치여러 주변장치는 메인보드 내의 버스로 연결된다.- 기존에는 하나의 버스로 연결되었음→ CPU가 I/O 작업을 수행할 때 다른 작업을 할 수 없음→ I/O Controller(입출력 제어기)와 여러 개의 버스가 추가되었다.입출력 제어기입출력 버스에서 온 데이터를 메모리로 옮긴다.→ 메모리는 CPU의 명령으로 움직인다.→ 입출력 제어기가 메모리에 접근하기 위해선 CPU가 필요하다.→ 입출력 제어기가 CPU의 도움이 필요 없도록 DMA(Direct Memory Access) 제어기가 추가되었다.DMA 제어기를 통해 데이터를 직접 메모리에 저장하거나 가져올 수 있다.CPU와 DMA가 사용하는 메모리가 겹치지 않도록 구분한다.(=Memory Mapped I/O)입출력 버스세부적으로 느린장치와 빠른장치를 구분하기 위해 두개의 채널로 나뉜다.고속 입출력 버스저속 입출력 버스→ 속도 차이로 인한 병목현상을 해결한다.시스템 버스고속으로 작동하는 CPU와 메모리가 사용한다.입출력 버스주변장치가 사용한다.그래픽 카드매우 대용량의 데이터를 다룬다.→ 고속 입출력 버스도 감당할 수 없다.→ 시스템 버스에 바로 연결해 사용한다.내부 구조메인보드에 있는 버스로 연결된다.하나의 버스는 Address 버스, Data 버스, Control 버스로 구성되어 있다.→ I/O 디바이스는 세 세가지 버스를 따로 받을 수 있다.H/W에 맞게 외부 인터페이스가 존재한다.레지스터 : 입출력 작업을 할 때 데이터를 저장하는 역할을 수행CPU 작업을 위해 메모리로 값이 이동하기도 한다.데이터의 전송단위에 따른 분류캐릭터 디바이스상대적으로 적은 양의 데이터를 전송한다.마우스, 키보드, 사운드 카드, 직렬/병렬 포트, etc..블록 디바이스많은 양의 데이터를 전송한다.HDD, SSD, 그래픽 카드, etc...광학 마우스마우스 하단부의 작은 카메라가 초당 1500회 이상의 사진을 찍어 마우스의 디바이스 컨트롤러 내의 DSP(Digital Signal Processor)로 전송한다.DSP는 사진을 분석해 마우스의 x, y축 움직임을 캐치한다.DSP가 마우스의 움직임과 클릭같은 데이터를 감지하면 디바이스 컨트롤러는 CPU에게 인터럽트를 보내고 마우스 드라이버가 동작해서 데이터를 읽어간다.마우스 드라이버는 OS에게 이벤트를 주고, OS는 이벤트를 Foreground 애플리케이션으로 전달한다.키보드사용자가 키보드를 누르면 키보드의 디바이스 컨트롤러가 어떤 키를 입력받았는지 알아낸다.디바이스 컨트롤러가 CPU에게 인터럽트를 보낸다.키보드 드라이버는 OS에게 이벤트를 보낸다.OS는 이벤트를 Foreground 애플리케이션으로 전달한다.HDD블록 디바이스의 한 종류구조Spindle : 막대Platter : 자기화된 원판여러 개의 track으로 구성표면에 자성이 있다.N극 : 0S극 : 1→ 자석을 갖다대면 데이터가 손상된다.일반적으로 플래터 수는 2개 이상Read/Write Head : 플래터의 표면을 읽는다.Cylinder : 여러 개의 플래터에 있는 같은 트랙의 집합Track : Platter를 구성하고 있는 부분Sector : Track을 구성하는 부분HDD의 가장 작은 단위Disk Arm : Read/Write Head가 붙어 있는 장치데이터를 읽는 방법User Process가 HDD의 특정 섹터에 접근 요청실린더 C로 가서 트랙 B에 있는 섹터 D를 읽어들여라.Seek 동작 수행디스크 암은 헤드를 실린더 C로 이동시킨다.Seek Time 헤드를 실린더로 이동시키는 걸리는 시간→ HDD가 느린 이유트랙B의 섹터D가 Read/Write Head에 닿을 때 까지 스핀들을 회전시킨다.헤드에 섹터D가 읽히면 작업 완료Flash Memory(SSD)블록 디바이스의 종류전기적으로 데이터를 읽어들인다.특정한 지점에 데이터를 쓰면 덮어쓰기가 불가능하다.데이터를 지우기 가능한 횟수가 정해져있다.→ 같은 지점에 지우기를 자주 사용하면 망가져 사용할 수 없다.

알고리즘 · 자료구조워밍업클럽CS전공지식DAY13

Taeho

인프런 워밍업 클럽 - CS Day 12

AlgorithmMerge Sort재귀로 구현하는 정렬 알고리즘Divide and Conquer복잡한 문제를 더 작고 관리하기 쉬운 하위 문제들로 나누어 해결하는 알고리즘 설계 기법구현 방법분할(Divide): 정렬할 배열을 거의 같은 크기의 두 부분 배열로 나눈다.정복(Conquer): 각 부분 배열을 재귀적으로 정렬한다.결합(Combine): 정렬된 부분 배열들을 하나의 정렬된 배열로 병합한다.1 ~ 3을 부분 배열의 크기가 1이 될 때까지 반복한다.시간 복잡도분할 과정: 배열을 반으로 나누는 과정이 log n번 일어납니다.병합 과정: 각 단계에서 n개의 요소를 비교하고 병합합니다.→ 전체 시간 복잡도 : O(n) * O(log n) = O(n log n)장점속도가 빠르다.시간 복잡도 : O(n log n)단점병합 과정에서 임시 배열이 필요하여 추가적인 메모리 공간을 사용한다.이해와 구현이 복잡하다.OS지역성 이론(90 : 10 법칙)프로그램이 실행될 때 90%의 시간이 10%의 코드에서 소요된다.조만간 쓸 데이터만 메모리로 올리고 당분간 필요하지 않을 것 같은 데이터는 스왑영역으로 보내 성능을 향상시킨다.디맨드 페이징필요할 것 같은 데이터를 메모리로 가져오고, 쓰이지 않을 것 같은 데이터는 스왑영역으로 이동시키는 정책지역성 이론을 구현한 정책메모리에서 데이터를 가져오는 정책Swap in스왑 영역에서 물리 메모리로 데이터를 가져오는 과정Swap out물리 메모리에서 스왑 영역으로 데이터를 보내는 과정Page Table Entry(PTE)페이지 테이블을 이루고 있는 행접근 비트페이지가 메모리에 올라온 후 데이터에 접근이 있었는지 알려주는 비트메모리에 읽기나 실행 작업을 했다면 1로 변경된다.변경 비트페이지가 메모리에 올라온 후 데이터에 변경이 있었는지 알려주는 비트메모리에 쓰기 작업을 했다면 1로 변경된다.유효 비트페이지가 물리 메모리에 있는지 알려주는 비트유효비트 1 : 페이지가 스왑영역에 있음유효비트 0 : 페이지가 물리 메모리에 있음읽기/쓰기/실행 비트(권한 비트)해당 메모리에 접근권한이 있는지 검사하는 비트Page Fault프로세스가 가상 메모리에 접근요청을 했을 때 MMU(메모리 관리자)는 페이지 테이블을 보고 물리 메모리의 프레임을 찾아낸다.물리 메모리에 프레임이 없다면 MMU는 Page Fault라는 인터럽트를 발생시킨다.Page Fault가 발생하면 스왑영역에 접근하고 해당 프로세스는 대기 상태가 된다.→ 스왑 영역의 데이터가 메모리로 올라가는 작업을 수행한다.→ 데이터가 물리 메모리로 올라가는 경우 해당 프로세스가 실행 상태로 변경된다.공간의 지역성현재 위치와 가까운 데이터에 접근할 확률이 높다.시간의 지역성최근 접근했던 데이터가 오래 전에 접근했던 데이터보다 접근할 확률이 높다.페이지 교체 정책메모리가 꽉찼을 때 어떤 페이지를 스왑영역으로 보낼지 결정하는 정책무작위로 교체하는 방법지역성을 고려하지 않는다.자주 사용되는 페이지가 선택될 수 있어 성능이 좋지 않다.→ 거의 사용되지 않는다.FIFO(First-In First-Out)메모리에 들어온지 가장 오래된 페이지를 교체한다.→ 자주 사용하는 페이지가 교체될 수 있다.구현이 간단하고 성능이 나쁘지 않아 변형해서 사용된다.H/W 적으로 접근비트를 지원하지 않는다면 FIFO를 사용해야 한다.Belady's AnomalyPage Fault를 줄이려고 메모리를 더 늘려서 프레임의 수를 늘렸는데 오히려 Page Fault가 더 많이 발생하는 현상FIFO에서만 발생한다.2차 기회 페이지 교체 알고리즘FIFO 방식에서 자주 사용하는 페이지에게는 또 한번의 기회를 준다.FIFO와 동일하게 동작하지만 Page Fault 없이 페이지 접근에 성공했다면 해당 페이지를 큐의 맨 뒤로 이동시켜 수명을 연장시켜 준다.Optimum앞으로 가장 오랫동안 사용되지 않을 페이지를 교체한다.→ 이후에 어떤 요청이 들어올지 알고 있어야 한다.→ 사실상 구현이 불가능한 이론적인 방법다른 알고리즘과 성능 비교를 할 때 참고용으로 사용된다.LRU(Least Recently Used)시간의 지역성에 따르면 최근 사용한 데이터가 앞으로도 사용될 확률이 높기 때문에 최근에 가장 사용을 적게한 페이지가 앞으로도 사용될 확률이 적다.Optimum 알고리즘에 근접한 성능을 갖는다.프로그램이 지역성을 띄지 않을 때는 성능이 떨어진다.PTE에 시간을 기록하려면 비트가 많이 필요하다.→ 비트를 많이 사용하는 것은 어렵기 때문에 접근비트를 이용하여 LRU에 근접하게 구현한다.Clock Algorithm접근 비트 하나만을 사용하여 구현하는 알고리즘일정 시간 간격마다 모든 페이지의 접근 비트를 0으로 초기화한다.페이지가 참조되는 경우 1로 설정된다.⇒ 일정 시간 간격마다 페이지가 참조되었는지 참조되지 않았는지 알 수 있다.페이지를 원형으로 연결한다.Page Fault가 발생해서 스왑영역으로 보내야 하는 경우클락 핸드는 현재 참조하고 있는 접근 비트를 본다.해당 비트가 1인 경우 해당 비트를 0으로 변경하고 다음 비트를 바라본다.접근 비트가 0인 페이지를 발견하면 해당 페이지를 스왑 영역으로 보낸다.Clock Hand스왑영역으로 옮길 페이지를 가르키는 포인터시계 방향으로 돈다.Enhanced Clock Algorithm접근 비트만 이용하는 것이 아니라 변경 비트도 함께 사용하는 알고리즘스왑 영역으로 보내지는 가장 우선순위접근 비트 : 0, 변경 비트 : 0접근 비트 : 0, 변경 비트 : 1접근 비트 : 1, 변경 비트 : 0접근 비트 : 1, 변경 비트 : 1스레싱프로세스들이 실제 실행되는 시간보다 페이지를 교체하는 데에 더 많은 시간을 사용하고 있는 현상⇒ 페이지 부재(page fault)가 과도하게 발생하여 CPU 이용률이 급격히 떨어지는 현상다중 프로그래밍의 정도가 높아져 각 프로세스에 할당된 메모리가 부족해지면서 발생CPU 이용률 저하 → 운영체제의 다중 프로그래밍 증가 → 페이지 부재 증가의 악순환이 반복근본적인 원인 : 물리 메모리의 크기가 부족한 것→ 메모리의 크기를 늘려서 해결(H/W 수준)할 수 있다.S/W 수준의 해결 방법프로세스가 실행되면 일정량의 페이지를 할당한다.→ Page Fault가 빈번하게 발생하는 경우 : 더 많은 용량의 페이지를 할당한다.→ Page Fault가 거의 없는 경우 : 적은 용량의 페이지를 할당한다.워킹셋프로세스가 일정 시간 동안 자주 참조하는 페이지들의 집합프로그램의 지역성(Locality) 특성을 이용한 개념자주 참조되는 워킹셋을 주기억장치에 유지함으로써 페이지 부재와 교체를 줄인다.시간에 따라 자주 참조하는 페이지들의 집합이 변화하므로 워킹셋도 동적으로 변한다.컨텍스트 스위칭에서 사용된다.

알고리즘 · 자료구조워밍업클럽CS전공지식DAY12

Taeho

인프런 워밍업 클럽 - CS Day 11

Algorithm영역을 2개로 나누어서 정렬을 수행하는 알고리즘정렬된 영역정렬되지 않은 영역정렬되지 않은 영역에서 데이터를 하나씩 꺼내서 정렬된 영역 내의 적절한 위치에 삽입하여 정렬하는 알고리즘시간 복잡도O(n^2) : 배열이 역순으로 정렬되어 있는 경우장점구현이 간단하고 이해하기 쉽다.추가적인 메모리 소비가 적다.단점시간 복잡도가 O(n^2)로 느리다.데이터의 상태에 따라 성능 편차가 크다.최선의 경우 : O(n)최악의 경우 : O(n^2)OS가상 메모리프로세스는 OS 영역이 어디있는지, 물리 메모리의 크기가 얼마나 큰지 몰라도 된다.→ 프로그래머는 물리 메모리의 크기와 프로세스가 메모리에 어느위치에 신경쓰지 않고 0x0번지에서 시작한다고 가정하고 프로그래밍을 한다.프로세스는 메모리 관리자를 통해서 메모리에 접근한다.직접 메모리에 붙지 않는다.가상 메모리의 크기이론적 무한대실제 : 물리 메모리 크기 + CPU 비트 수ex) 32bit → 표현 가능한 주소값 : 2^32 = 4GB가상 메모리 시스템은 물리 메모리가 처리할 수 없는 용량을 프로세스들이 요구할 때 물리 메모리 내용의 일부를 하드 디스크에 있는 스왑 영역으로 옮기고 처리가 필요할 때 물리 메모리로 가져와서 처리한다.→ 물리 메모리가 처리할 수 없는 용량의 작업들을 처리할 수 있게 한다.메모리 관리자는 가상주소와 물리 주소를 1 : 1 매핑 테이블로 관리한다.가상 메모리의 프로세스 할당 방법가상 메모리 시스템에서는 OS 영역을 제외한 나머지 영역을 일정한 크기로 나누어서 프로세스에게 할당한다.가변 분할 방식(Segmentation)프로그램은 함수나 모듈 등으로 세그먼트를 구성한다.각 세그먼트들이 인접해 위치할 필요는 없다.But. 프로세스 입장에서는 코드 영역, 데이터 영역, 힙 영역, 스택 영역을 서로 인접한 것 처럼 바라본다.MMU(메모리 관리자)가 논리주소로 물리주소로 변환해주는 방법세그멘테이션 테이블이라는 테이블이 존재Base AddressBound Address⇒ 두 주소를 사용하여 물리 메모리 주소를 계산한다.AddressBase Address프로세스나 세그먼트의 물리 메모리 상 시작 주소를 나타낸다.MMU의 base register에 저장되어 주소 변환에 사용Bound Address (또는 Limit)프로세스나 세그먼트의 크기를 나타낸다.MMU의 bound/limit register에 저장되어 메모리 보호에 사용된다.논리주소 → 물리주소CPU에서 논리 주소 전달MMU는 해당 논리 주소가 몇 번 세그먼트 인지 확인MMU내의 Segment Table Base Register 내에 있는 세그멘테이션 테이블을 찾는다.세그먼트 번호를 인덱스로 Base Address와 Bound Address를 찾는다.MMU는 CPU에서 받은 논리주소와 Bound Address의 크기를 비교한다.논리주소가 Bound Address보다 작은 경우논리주소와 Base Address를 더해 물리 주소를 더한다.논리주소가 Bound Address보다 큰 경우메모리를 침범했다고 간주하고 에러를 발생시킨다.STBR(Segment Table Base Register)OS는 컨텍스트 스위칭을 할 때마다 메모리 관리자내의 Segment Table Base Register를 해당 프로세스의 것으로 값을 바꿔줘야 한다.→ Context Switching이 고비용 작업인 이유장점메모리를 가변적으로 분할할 수 있다.코드 영역, 데이터 영역, 스택 영역, 힙 영역을 모듈로 처리할 수 있어 공유와 각 영역에 대한 메모리 접근보호가 편리하다.단점외부 단편화 발생고정 분할 방식(Paging)세그멘테이션 기법의 외부 단편화를 해결하기 위해 고안된 배치 정책페이징은 메모리를 할당할 때 정해진 크기의 페이지로 나눈다.→ 외부 단편화가 발생되지 않는다.Page : 일정한 크기로 균일하게 나뉘어진 논리주소공간Frame : 일정한 크기로 균일하게 나뉘어진 물리주소공간가장 신경써야 하는 점페이지 테이블의 크기각 프로세스마다 테이블을 갖는다.→ 프로세스가 많아질 수록 페이지 테이블도 많아진다.→ 프로세스가 실제로 사용할 수 있는 메모리 영역이 줄어든다.페이지 테이블 크기가 너무 큰 경우 : 사용자 영역이 부족하다.Page Table가상 주소를 물리 주소로 변환하는데 사용하는 테이블각 프로세스의 가상 페이지 번호(VPN)을 물리 프레임 번호(PFN)로 매핑한다.각 프로세스마다 독립적인 Page Table을 갖는다.페이지 테이블에 Invalid로 되어 있으면 스왑영역에 저장되어 있는 상태Page Table Entry(PTE)페이지 기본 주소 (Page base address)유효 비트 (Valid bit): 페이지가 메모리에 있는지 여부보호 비트 (Protection bit): 읽기/쓰기/실행 권한참조 비트 (Reference bit): 페이지 접근 여부수정 비트 (Dirty bit): 페이지 내용 변경 여부Page Table Base Register(PTER)각 프로세스의 PCB에 위치하며, 해당 프로세스의 Page Table의 시작 주소를 가리킨다.OS는 컨텍스트 스위칭을 할 때마다 메모리 관리자내의 Segment Table Base Register를 해당 프로세스의 것으로 값을 바꿔줘야 한다.논리주소 → 물리주소CPU에서 논리주소 전달MMU는 논리주소가 몇번 페이지인지 오프셋은 어떻게 되는지 확인MMU에서 Page Table Base Register를 이용하여 물리 메모리에 있는 페이지 테이블을 찾는다.페이지 번호를 인덱스로 프레임 번호를 알아낸다.오프셋을 사용하여 물리 주소로 변환한다.장점메모리를 효율적으로 관리할 수 있다.단점내부 단편화 발생세그멘테이션의 외부 단편화와 비교하면 많은 공간을 비교하지 않는다.Segmentation vs Paging차이점페이지의 크기세그멘테이션은 프로세스마다 크기가 달라 Bound Address를 갖는다.페이징은 모든 페이지의 크기가 동일해서 크기를 표현하는 Bound Address가 필요없다.세그멘테이션은 논리적인 영역별로 세그먼트를 나눈다.→ 세그먼트 마다 크기를 다르게 나눌 수 있다.→ 코드 영역, 데이터 영역, 스택 영역, 힙 영역을 나눌 수 있다.페이징은 페이지의 크기가 고정되어 있어 논리적인 영역을 나눌 수 없다.→ 특정 영역만 떼어내서 공유하거나 권한을 부여하기 어렵다.Paged Segmentation세그멘테이션 - 페이징 혼용 기법각각의 장점을 혼합한 기법세그멘테이션 테이블과 페이지 테이블을 결합하여 사용한다.메모리 접근 권한메모리의 특정 번지에 부여된 권한상태값 : Read, Write, Execute각 프로세스는 코드 영역, 데이터 영역, 힙 영역, 스택 영역이 존재한다.→ 각 영역마다 접근 권한이 있다.코드 영역 : 프로그램 자체 ⇒ 읽기/실행 권한데이터 영역 : 일반변수, 전역변수, 상수로 선언한 변수 저장 ⇒ 읽기/(쓰기-Optional) 권한힙 영역 : 읽기/쓰기 권한스택 영역 : 읽기/쓰기 권한메모리 접근 권한 검사는 가상주소에서 물리주소로 변환될 때마다 일어난다.권한을 위반하는 경우 에러를 발생시킨다.주소 변환 과정세그먼트 번호로 세그먼트 테이블에 접근하여 세그먼트 길이와 해당 세그먼트의 페이지 테이블 시작 주소를 얻는다.해당 세그먼트가 메모리 접근 권한을 위반하는지 검사한다.접근 권한 위반 시 프로세스 종료세그먼트의 페이지 테이블 시작 주소에 세그먼트 내 페이지 번호를 더해 페이지 테이블 항목에 접근한다.페이지 테이블에서 프레임 번호를 얻는다.프레임 번호에 페이지 내 오프셋을 더해 최종 물리 주소를 얻는다.단점물리 메모리에 접근하기 위해 메모리에 두 번 접근해야 한다.세그멘테이션 테이블 참조페이지 테이블 참조→ 페이징과 페이지드 세그멘테이션 기법을 적절히 섞어서 사용한다.DAT(Dynamic Address Translation, 동적 주소 변환)메모리 관리자가 물리 메모리와 스왑영역을 합쳐서 프로세스가 사용하는 가상주소를 물리주소로 변환하는 과정DAT를 거치면 프로세스는 마음대로 사용자 데이터를 물리 메모리에 배치할 수 있다.

알고리즘 · 자료구조워밍업클럽CS전공지식Day11

Taeho

인프런 워밍업 클럽 - CS Day 9

Algorithm참고 : https://visualgo.net/en/sortingBubble Sort인접한 두 원소를 비교하여 두 원소의 위치를 교환한다.과정배열을 처음부터 끝까지 순회하며 인접한 두 원소를 비교한다.왼쪽 원소가 오른쪽 원소보다 크면 두 원소를 교환한다.이 과정을 배열이 정렬될 때까지 반복한다.시간 복잡도O(n^2)장점이해와 구현이 간단한다.단점성능이 좋지 않다.Selection Sort배열에서 최솟값을 찾아 맨 앞으로 이동시킨다.과정정렬되지 않은 부분에서 최솟값을 찾는다.찾은 최솟값을 정렬되지 않은 부분의 첫 번째 원소와 교환한다.정렬된 부분을 한 칸 늘리고, 정렬되지 않은 부분에서 위 과정을 반복한다.시간 복잡도O(n^2)장점이해와 구현이 간단하다.단점성능이 좋지 않다.OSProgramming LanguageCompile Language개발자가 코드를 작성하고 컴파일을 수행하여 0과 1로된 기계어로 실행파일을 만든다.→ 기계어로 되어 있어 실행 속도가 인터프리터 언어에 비해 빠르다.컴파일 과정에서 개발자의 문법오류를 체크한다.ex) C, C++, C#Interpreter Language개발자가 작성한 코드를 미리 기계어로 만들어 놓지 않고 실행시 코드를 한줄씩 해석해 실행하는 언어→ 미리 검사를 하지 않기 때문에 실행할 때 오류가 발생할 수 있고, 컴파일 언어보다 느리다.ex) Javascript, Python, Ruby프로세스의 영역코드 영역실행해야 할 코드가 들어간다.데이터 영역전역 변수나 배열이 들어가는 영역스택 / 힙프로세스가 실행될 때 할당되는 메모리스택 : 지역변수와 함수 관련 값들이 저장힙 : 실행 중에 메모리 공간을 할당할 수 있는 유동적인 공간Compile 언어가 Process가 되는 방법개발자가 코드 작성전처리 단계 실행개발자가 작성한 코드를 확인하고 전처리 구문을 처리한다.C에서는 #이라는 키워드로 선언된다.ex) #include<stdio.h>, #define MY_NUMBER 100코드에 있는 모든 주석은 삭제된다.결과물로 .i 파일이 생성된다.전처리기에서 나온 결과파일을 컴파일러가 처리한다.컴파일러는 .i 파일을 기계어에 가까운 어셈블리어로 변환시킨다.결과물로 .s 파일이 생성된다.어셈블러 작업이 수행된다.오브젝트 파일.o로 변환된다.오브젝트 파일은 0과 1로 구성되어 있다.코드영역과 데이터 영역이 나뉘어져 있다.링커 작업이 수행된다.모든 오브젝트 파일을 하나의 코드 영역과 데이터 영역으로 묶어준다.실제로 실행될 주소를 매핑시켜준다.결과물로 .exe 파일이 생성된다.사용자가 .exe파일을 실행시키면 OS가 프로세스를 생성한다.OS는 파일에 있는 코드 영역과 데이터 영역을 가져와 프로세스의 코드 영역과 데이터 영역에 넣어주고, 빈 상태의 스택과 힙을 할당한다.PCB를 만들어 프로세스를 관리가 가능하게 한다.PC(프로그램 카운터)에 다음 실행할 명령어의 주소를 생성한 프로세스의 코드영역의 첫번째 주소로 설정한다.→ OS의 CPU 스케줄링에 따라서 프로세스가 실행되다가 작업을 마친다.메모리 종류레지스터가장 빠른 기억장소, CPU 내에 존재한다.휘발성 메모리CPU를 나타내는 값에서 32bit, 64bit를 의미하는 것이 레지스터의 크기이다.CPU는 계산을 수행할 때 메인 메모리에 있는 값을 레지스터로 가져와서 계산한다.계산 결과는 메인 메모리에 저장한다.캐시휘발성 메모리속도가 매우 빠른 레지스터와 레지스터에 비해 상대적으로 느린 메인 메모리 사이의 속도 간극을 메우기 위해 필요한 데이터를 미리 가져와 저장하는 저장소성능의 이유로 여러 개가 존재한다.L1, L2, L3→ 숫자가 커질 수록 느린 캐시CPU가 값을 요청해 레지스터로 값을 옮겨야 한다면 빠른 캐시를 순차적으로 확인하고, 캐시에 데이터가 없으면 메인 메모리를 조회한다.ex) L1 → L2 → L3 → 메인 메모리보조 저장장치(HDD, SSD)비휘발성 메모리메인 메모리실제 운영체제와 다른 프로세스들이 올라가는 공간휘발성 메모리데이터를 저장하기 보다는 실행중인 프로그램만 저장한다.OS는 메모리를 관리하기 위해서 1Byte 크기로 구역을 나누고 숫자(주소)를 매긴다.32bit CPU, 64bit CPU32bit CPU레지스터, ALU, Data Bus : 32bit메모리 : 2^32 = 4GB64bit CPU레지스터, ALU, Data Bus : 64bit메모리 : 2^64 = 16384PiB64bit CPU가 32bit CPU 보다 한번에 처리할 수 있는 양이 많기 때문에 속도가 더 빠르다.물리 주소 & 논리 주소물리 주소 공간 : 0x0부터 시작하는 주소 공간논리 주소 : 사용자 관점에서 바라 본 주소 공간사용자는 물리 주소를 몰라도 논리 주소로 물리 주소에 접근할 수 있다.OS를 위한 공간은 따로 확보한다.경계 레지스터H/W적으로 OS 공간과 사용자 공간을 나누는 레지스터CPU 내에 존재하는 레지스터메모리 관리자가 사용자 프로세스가 경계 레지스터의 값을 벗어났다면 검사하고, 벗어났다면 해당 프로세스를 종료시킨다.절대 주소 & 상대 주소개발자가 프로그램이 실행될 주소를 신경쓰지 않고 개발할 수 있는 이유→ 컴파일러가 컴파일을 할 때 메모리 0번지에서 실행한다고 가정하기 때문절대 주소 : 메모리 관리자가 바라본 프로세스가 올라간 물리 주소상대 주소 : 사용자가 바라보는 논리 주소재배치 레지스터프로그램의 시작 주소가 저장되어 있다.사용자가 요청한 논리 주소의 데이터를 물리 주소로 치환해준다.사용자가 메모리에 접근할 때마다 논리 주소를 물리 주소로 치환해준다.메모리 할당 방식메모리 오버레이메모리보다 용량이 큰 프로그램을 실행시키는 방법큰 프로그램을 메모리에 올릴 수 있을 정도로 분할하여 일부만 실행하고, 실행되지 않은 프로그램은 HDD의 스왑 영역에 저장하는 방식Swap스왑영역에 있는 데이터 일부를 메모리로 가져오고 메모리에 있는 데이터를 스왑영역으로 옮기는 것가변 분할 방식(= Segmentation, 세그멘테이션)프로세스의 크기에 따라 메모리를 나누는 방식하나의 프로세스가 메모리에 연속된 공간에 할당된다.→ 연속 메모리 할당이라고 한다.장점메모리에 연속된 공간에 할당된다.→ 내부 단편화가 없다.단점외부 단편화가 발생한다.고정 분할 방식(= Paging, 페이징)프로세스의 크기와는 상관없이 정해진 크기로 나누는 방식하나의 프로세스가 메모리에 분산되어 할단된다.→ 비연속 메모리 할당이라고 한다.장점구현이 간단하고 오버헤드가 적다.단점작은 프로세스도 큰 영역에 할당되어 내부 단편화가 발생한다.내부 단편화프로세스에 필요한 메모리보다 더 큰 고정 크기의 메모리 블록이 할당될 때 발생한다.할당된 메모리와 실제 사용된 메모리 사이의 차이로 인해 메모리 공간이 낭비된다.고정 크기 분할 방식에서 주로 발생한다.해결 방법은 딱히 없고, 분할되는 크기를 조절하여 내부 단편화를 최소화한다.외부 단편화메모리 할당과 해제를 반복하면서 작은 빈 공간들이 메모리 곳곳에 흩어져 생기는 현상전체 가용 메모리는 충분하지만, 연속된 큰 블록을 할당할 수 없는 상황을 만든다.가변 분할 방식에서 주로 발생한다.조각모음외부 단편화가 발생한 공간을 합쳐주는 작업현재 메모리에서 실행되고 있는 프로세스들의 작업을 일시 주징하고, 메모리 공간을 이동시켜야 한다.→ 오버헤드가 발생한다.버디 시스템가변 분할 방식 + 고정 분할 방식오늘날의 OS가 채택한 메모리 할당 방식2의 제곱으로 메모리를 분할하여 할당하는 방식→ 근접한 메모리 공간을 합치기 쉽다.→ 조각 모음보다 훨씬 간단하다.장점가변 분할 방식처럼 프로세스 크기에 따라 할당되는 메모리 크기가 달라지고, 외부 단편화를 방지하기 위해 메모리 공간을 확보하는 것이 간단하다.내부 단편화가 발생할 수 있지만 고정 분할 방식에 비해 많은 공간이 낭비되지는 않는다.

알고리즘 · 자료구조워밍업클럽CS전공지식DAY9

Taeho

인프런 워밍업 클럽 - CS Day 8

Algorithm하노이의 탑하향식 계산 방식의 좋은 예시→ 재귀함수의 좋은 예시제약 조건한 번에 하나의 원반을 움직일 수 있다.가장 위에 있는 원반만 옮길 수 있다.아래에 작은 원반이 올 수 없다.OS교착상태여러 프로세스가 서로 다른 프로세스의 작업이 끝나길 기다리다가 아무 작업도 수행되지 않는 상태발생 원인상호 배제 : 공유 자원은 한 번에 하나의 프로세스만 사용할 수 있다.비선점 : 다른 프로세스가 사용 중인 자원을 강제로 빼앗을 수 없다.점유와 대기 : 프로세스가 이미 자원을 보유한 상태에서 다른 자원을 요청하며 대기한다.원형 대기 : 점유와 대기를 하는 프로세스들의 관계가 원형이다.하나라도 충족하지 않으면 교착상태가 발생하지 않는다.→ 교착 상태를 예방하는 것을 구현하기는 매우 어려워서 교착 상태를 해결하는 방향으로 발전됐다.해결방법교착상태 회피프로세스들에게 자원을 할당할 대 어느 정도 자원을 할당해야 교착상태가 발생하는지 파악해서 교착상태가 발생하지 않는 수준의 자원을 할당한다.전체 자원의 수와 할당된 자원의 수를 기준으로 안정상태와 불안정 상태로 나뉜다.OS는 안정상태를 유지하려 한다.안전 상태: 모든 프로세스가 요구한 최대 자원을 할당받아 실행을 완료할 수 있는 상태불안정상태에 있더라도 무조건 교착상태에 들어가는 것이 아니라 교착상태에 빠질 확률이 높아지는 것이다.은행원 알고리즘작동 원리프로세스가 자원을 요청할 때, 그 요청이 시스템을 안전 상태로 유지할 수 있는지 확인한다.안전 상태를 유지할 수 있는 요청만 수락하고, 불안정한 상태를 초래할 수 있는 요청은 거절한다.주요 개념최대 요구량(Max Need): 프로세스가 실행을 완료하기 위해 필요한 최대 자원 양할당량(Allocation): 현재 프로세스에 할당된 자원 양필요량(Need): 최대 요구량에서 현재 할당량을 뺀 값가용량(= 시스템 총 자원, Available): 시스템에서 현재 사용 가능한 자원 양단점비용이 비싸고 비효율적이다.교착상태 검출가벼운 교착 상태 검출타이머를 이용하는 방식프로세스가 일정시간 동안 작업을 진행하지 않는다면 교착상태가 발생했다고 간주하고 교착상태를 해결한다.교착상태 해결 방법일정 시점마다 체크포인트를 만들어 작업을 저장하고 타임아웃으로 교착상태가 발생했다면 마지막으로 저장했던 체크포인트로 롤백한다.무거운 교착 상태 검출자원 할당 그래프를 이용하는 방식OS가 자원 할당 그래프를 유지하고 검사해야 하기 때문에 오버헤드가 발생한다.But. 가벼운 교착 상태 검출에서 발생할 수 있는 억울하게 종료되는 프로세스가 발생하지 않는다.OS에서 프로세스가 어떤 작업을 사용하는지 지켜보고 교착상태가 발생했다면 해결한다.

알고리즘 · 자료구조워밍업클럽CS전공지식DAY8

Taeho

인프런 워밍업 클럽 - CS Day 7

Algorithm재귀 사용하는 패턴단순 반복문반복문으로 구현했을 때보다 이점이 되는 부분이 없음Call Stack에 공간을 많이 차지해 성능이 반복문보다 좋지 않다.하향식 계산하향식 계산 : 하위문제의 결과를 기반으로 현재 문제를 계산하는 방식재귀가 반복문보다 성능이 좋은 경우큰 문제를 해결하기 위해 작은 재귀 함수를 호출한다.재귀를 사용해서만 구현이 가능하다.상향식 계산 : 하위 문제를 모아서 현재 문제를 계산하는 방식반복문으로 구현한 것보다 성능이 좋지 않음반복문이나 재귀를 사용해서 구현할 수 있다.OSProcess간 통신하나의 컴퓨터 내에서 프로세스간 통신하는 방법Pipe운영체제가 생성한 파이프를 이용해 데이터를 읽고 쓰는 방법File통신을 하려는 프로세스들이 하나의 파일을 이용해 읽고 쓰는 방법Thread를 이용한 통신하나의 프로세스 내에서 쓰레드간 통신하는 방법쓰레드는 코드, 데이터, 힙 영역을 공유한다.(스택 영역만 별도로 갖는다.)데이터 영역의 전역 변수나 힙 영역을 이용하여 통신할 수 있다.NetworkOS가 제공하는 Socket 통신RPC(Remote Procedure Call)다른 컴퓨터의 함수를 호출하는 방법공유자원과 임계구역공유자원 : 프로세스간 통신을 할 때 공용으로 이용하는 변수나 파일여러 프로세스가 공유하기 때문에 각 프로세스의 접근 순서에 따라서 결과가 달라질 수 있다.컨텍스트 스위칭으로 시분할 처리를 하기 때문에 프로세스간의 실행 순서를 예측하기 어렵다.⇒ 동기화 문제가 발생할 수 있다.임계규역 : 여러 프로세스가 동시에 사용하면 안되는 영역상호배제 메커니즘을 통해 해결할 수 있다.경쟁조건 : 공유자원을 사용하기 위해 서로 경쟁하는 것상호배제 요구사항임계영역엔 동시에 하나의 프로세스만 접근한다.여러 요청에도 하나의 프로세스의 접근만 허용한다.임계구역에 들어간 프로세스는 빠르게 나와야한다.Semaphore상호배제 메커니즘의 한 종류Semaphore :  정수 값을 가지는 변수로, 공유 자원에 접근할 수 있는 프로세스/스레드의 수를 나타낸다.세마포어를 갖고 있는 프로세스가 실행되고 세마포어를 반납한다.기본 연산wait(S): 세마포어 값을 감소시킨다.값이 0이면 프로세스/스레드를 대기 상태로 만든다.signal(S): 세마포어 값을 증가시킵니다.대기 중인 프로세스/스레드가 있다면 깨운다.종류이진 세마포어: 0과 1 두 가지 값만 갖는다.(뮤텍스와 유사하게 사용한다.)카운팅 세마포어: 0 이상의 정수 값을 갖는다.(여러 자원을 관리할 때 사용된다.)장단점장점: 여러 프로세스/스레드 간의 복잡한 동기화 문제를 해결할 수 있다.단점잘못 사용하면 교착 상태나 기아 상태를 유발할 수 있다.ex) 세마포어를 획득하는 함수와 세마포어를 반납하는 함수의 위치 잘못 사용Mutex(MUTual EXclusion)뮤텍스는 이진 세마포어의 특수한 경우여러 스레드가 공유 자원에 동시에 접근하는 것을 방지하는 기술기본 연산Lock: 스레드가 임계 영역에 진입할 권한을 획득Unlock: 임계 영역 사용을 마치고 다른 스레드가 진입할 수 있게 한다.뮤텍스와의 차이세마포어는 여러 프로세스/스레드의 접근을 허용할 수 있지만, 뮤텍스는 하나의 프로세스/스레드만 접근을 허용한다.Monitor세마포어의 단점을 보완한 상호배제 메커니즘OS가 처리하는 것이 아니라 프로그래밍 언어단에서 지원하는 기능ex) Java : synchronized 키워드한 번에 하나의 프로세스/스레드만 실행할 수 있다.

알고리즘 · 자료구조워밍업클럽CS전공지식DAY7

Taeho

인프런 워밍업 클럽 - CS Day 4

그림으로 쉽게 배우는 자료구조와 알고리즘(기본편)StackLIFO(Last-in First-out)가장 먼저 들어온 데이터가 가장 나중에 나가는 자료 구조가장 나중에 들어온 데이터가 가장 먼저 나가는 자료 구조Linked List를 사용하여 Stack을 구현할 수 있다.출처 : https://www.geeksforgeeks.org/stack-data-structure/?ref=header_outindLinked List를 사용한 구현head를 사용하여 스택을 간단하게 구현할 수 있다.데이터 삽입을 무조건 첫 번째 인덱스에 수행한다.⇒ 한쪽으로만 데이터를 삽입하고, 삭제하면 간단하게 구현할 수 있다.Stack을 사용하는 상황웹 브라우저 방문 기록 (뒤로 가기 기능)프로그램의 실행 취소(Undo) 기능 구현역순 문자열 만들기수식의 괄호 검사후위 표기법 계산함수 호출 관리 (프로그램의 함수 호출 스택)깊이 우선 탐색(DFS) 알고리즘 구현Stack ADTpush() - 데이터 삽입pop()- 데이터 제거peek() - 데이터 참조isEmpty() - 비었는지 체크QueueFIFO(First-in First-out)가장 먼저 들어온 데이터가 가장 먼저 나가는 자료 구조가장 나중에 들어온 데이터가 가장 나중에 나가는 자료 구조Linked List를 사용하여 Queue를 구현할 수 있다.출처 : https://www.geeksforgeeks.org/queue-data-structure/Linked List를 사용한 구현head를 사용하여 Queue를 간단하게 구현할 수 있다.데이터를 뒤에서 제거하는 것을 구현해야 한다.→ 단방향 Linked List의 경우에는 가장 마지막에 있는 Node에 접근하기 위해서는 head에서부터 순차적으로 접근해야 한다.→ O(n)의 시간이 소요된다.⇒ tail을 사용하여 가장 마지막의 노드 정보를 저장한다.→ tail을 사용하더라도 가장 마지막의 노드 정보를 갱신하기 위해서는 head에서부터 순차 접근해야 한다.→ O(n)의 시간이 소요된다.⇒ 이중 연결 리스트를 사용하여 구현하면 O(n)을 O(1)로 개선할 수 있다.Queue를 사용하는 상황프린터의 인쇄 대기열 관리OS에 작업 요청이 들어오면 들어온 순서대로 큐에 넣고, CPU가 순서대로 꺼내서 처리한다.→ FIFO 스케쥴링네트워크의 데이터 패킷 전송 관리실시간 시스템의 인터럽트 처리너비 우선 탐색(BFS) 알고리즘 구현캐시(Cache) 구현은행 창구와 같은 대기열 시스템 모델링동시성 프로그래밍에서의 작업 큐Queue ADTenqueue() - 데이터 삽입dequeue() - 데이터 제거front() - 데이터 참조(Tail 참조)isEmpty() - Queue가 비었는지 확인Deque데이터의 삽입과 제거를 head와 tail에서 자유롭게 할 수 있는 자료구조Deque을 사용하여 Stack과 Queue를 구현할 수 있다.출처 : https://www.geeksforgeeks.org/deque-in-python/?ref=header_outindDeque ADTprintAll() - 리스트의 모든 데이터 출력addFirst() - head에 데이터 삽입removeFirst() - head에서 데이터 제거addLast() - tail에 데이터 삽입removeLast() - tail에서 데이터 제거isEmpty() - 리스트가 비었는지 체크그림으로 쉽게 배우는 운영체제Context Switching프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행중인 프로세스의 상태를 저장하고, 다른 프로세스의 상태값으로 전환하는 작업Context Switching이 발생할 때 PCB의 내용이 변경된다.프로세스 상태, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보 등이 변경된다.발생하는 이유CPU 점유 시간의 종료I/O 요청인터럽트가 발생한 경우프로세스 생성OS가 부팅되고 0번 프로세스가 생성될 때 딱 한 번만 수행된다.→ 그 이후에 생성되는 프로세스는 fork()를 사용하여 복사해서 사용된다.→ 새로 생성하는 것보다 복사를 하는 것이 더 빠르기 때문실행 파일(.exe)실행OS는 해당 프로그램의 코드 영역과 데이터 영역을 메모리에 로드빈 스택과 빈 힙을 만들어 공간을 확보프로세스를 관리하기 위한 PCB 생성 및 초기화exec()부모를 복사한 자식 프로세스의 코드와 데이터 영역을 원하는 값으로 덮어쓸 수 있다.→ 부모 프로세스와 다른 방식으로 동작할 수 있다.좀비 프로세스부모 프로세스가 자식 프로세스보다 먼저 종료되거나 자식 프로세스가 비정상적으로 종료돼 exit()신호를 주지 못해서 Exit Status를 읽지 못해 메모리에 계속 살아있는 상태Thread프로세스 내에 존재하고, 1개 이상이 존재할 수 있다.하나의 프로세스 내에 있는 쓰레드들은 프로세스의 PCB, Code, Data, Heap 영역을 공유한다.Stack은 공유하지 않고, 쓰레드마다 하나씩 갖고 있다.OS에서 작업을 처리하는 단위Thread 구분자Thread IDTCB(Thread Control Block)Process vs Thread안정성Process는 독립적이기 때문에 서로 영향을 받지 않는다.Thread는 하나의 Process를 공유하기 때문에 하나의 Thread에 이상이 생기면 다른 Thread에도 이상이 전파될 수 있다.⇒ Process가 유리속도와 자원각각의 Process는 서로 고유한 자원을 갖는다.코드, 데이터, 힙, 스택 영역을 전부 따로 두고 있다.Process간에 통신을 하려면 IPC를 사용해야 해서 오버헤드가 크고 속도가 느리다.쓰레드는 하나의 Process의 자원을 스택 영역을 제외한 영역을 모두 공유하기 때문에 오버헤드가 느리다.

알고리즘 · 자료구조DAY3워밍업클럽CS전공지식

Taeho

인프런 워밍업 클럽 - CS Day 5

Hash TableHash Function해시 함수는 키(key)를 입력받아 해당 키의 저장 위치(버킷 또는 인덱스)를 결정하는 계산을 하는 함수좋은 해시 함수 ⇒ 데이터를 골고루 분배시켜주는 함수장점빠른 데이터 읽기, 삽입, 삭제단점메모리를 많이 차지한다.좋은 해시 함수의 구현이 필수적이다.Hash Collision해시 충돌은 해시 함수가 서로 다른 두 개 이상의 입력 값에 대해 동일한 해시 값을 출력하는 상황을 의미Hash 충돌이 발생한 곳의 Value들을 연결리스트로 구성하여 데이터들을 연결한다.기존값과 새로운 값을 동시에 저장할 수 있다.찾고자 하는 Value가 나올 때까지 연결리스트를 탐색한다.→ O(n)의 성능을 갖는다.해결 방법체이닝 (Chaining)각 버킷에 연결 리스트를 사용하여 충돌된 항목들을 저장한다.장점: 구현이 간단하고, 해시 테이블의 확장이 필요 없다.단점: 최악의 경우 검색 시간이 O(n)이 될 수 있다.개방 주소법 (Open Addressing)충돌 발생 시 다른 빈 버킷을 찾아 데이터를 저장한다.유형:선형 탐사 (Linear Probing)제곱 탐사 (Quadratic Probing)이중 해싱 (Double Hashing)장점: 추가적인 메모리 사용이 없다.단점: 클러스터링 현상이 발생할 수 있다.재해싱 (Rehashing)해시 테이블의 크기를 동적으로 조정하여 충돌 가능성을 줄인다.Tip.Java의 HashMap의 경우에는 기본적으로 체이닝 방식을 사용한다.But. 성능 최적화를 위해 다음과 같이 구현된다.- 하나의 버킷에 8개 이상의 항목이 저장되면 연결 리스트를 트리 구조로 변환한다.- 버킷의 항목 수가 6개 이하로 줄어들면 다시 연결 리스트로 변환한다.참조 : https://d2.naver.com/helloworld/831311시간 복잡도읽기, 삽입, 수정, 삭제 : Key만 알고 있으면 Value에 O(1)로 읽기가 가능HashTable ADTset() - 데이터 삽입get() - 데이터 읽기remove() - 데이터 삭제Set데이터의 중복을 허용하지 않는 자료구조HashTable을 사용하여 구현할 수 있다.→ HashTable을 사용하기 때문에 HashSet이라고도 한다.→ HashTable의 value 값은 사용하지 않고 key만 사용하여 구현한다.(key가 key와 value의 역할을 수행한다.)Set ADTadd(data) - 데이터 삽입isContain(data) - 데이터 체크remove(data) - 데이터 제거clear() - 셋 비우기isEmpty() - 셋이 비었는지 확인printAll() - 모든 데이터 출력CPU Scheduling스케줄러가 고려해야 할 사항어떤 프로세스에게 CPU를 할당해야 하는가?CPU를 할당받은 프로세스가 얼마의 시간동안 CPU를 점유해야 하는가?→ 컴퓨터의 성능에 굉장히 큰 영향을 미친다.CPU BurstCPU를 할당받아 실행하는 작업I/O BurstI/O 작업목표목표들을 전부 만족할 수는 없다.→ 목표들에 따라 Trade-Off가 있기 때문ex) 처리량 ↑ ⇒ CPU 오래 할당, 응답시간 ↓ ⇒ 여러 프로세스에 CPU를 골고루 할당⇒ 처리량과 응답시간 사이에 Trade-Off가 발생한다.리소스 사용률CPU 사용률 높이기I/O 디바이스의 사용률 높이기오버헤드의 최소화Context Switching시에 발생하는 오버헤드를 최소화하는 것공평성모든 프로세스에게 우선순위에 따라 공평하게 CPU가 할당되어야 한다.처리량같은 시간내에 더 많은 처리를 할 수 있게 하는 것대기시간작업을 요청하고 실제 작업이 실행되기 전까지 대기하는 시간이 짧은 것응답시간사용자의 요청이 얼마나 빨리 요청하는지다중 Queue프로세스가 대기하고 있는 준비상태와 대기상태는 Queue라는 자료구조로 관리된다.OS는 해당 프로세스의 우선순위를 보고, 그에 맞는 준비 큐에 PCB를 넣는다.CPU 스케줄러는 준비상태의 다중 큐에 들어있는 프로세스들 중에 프로세스를 선택해서 실행상태로 전환시킨다.프로세스가 실행상태에서 I/O 요청을 받아 대기상태로 전환되는 경우 I/O 작업 종류에 따라 분류된 큐에 PCB가 들어간다.I/O 작업이 완료되어 인터럽트가 발생되면 분류된 큐에서 프로세스를 꺼낸다.FIFO(First-In First-Out)먼저 들어온 작업이 먼저 나간다.스케쥴링 큐에 들어온 순서대로 CPU를 할당받는 방식단점먼저 들어온 프로세스가 완전히 종료되어야만 다음 프로세스가 실행될 수 있다.→ I/O 작업이 발생하면 CPU는 I/O 작업이 끝날 때까지 쉬기 때문에 CPU 사용률이 떨어진다.→ 작업이 빠르게 종료될 수 있는 간단한 프로세스가 작업이 무거운 프로세스 뒤에 들어오면 무거운 프로세스가 완료될 때까지 기다려야 한다.프로세스의 Burst Time에 따라 성능의 차이가 심하게 나기 때문에 현대 OS에서 사용되지 않고, 주로 일괄 처리 시스템에서 사용된다.스케줄링의 성능평균 대기 시간스케줄링 성능 평가의 척도프로세스 여러개가 실행될 때 해당 프로세스들이 모두 실행되기까지 대기시간의 평균값ex)

알고리즘 · 자료구조워밍업클럽CS전공지식DAY5

Taeho

인프런 워밍업 클럽 - CS Day 3

그림으로 쉽게 배우는 자료구조와 알고리즘(기본편)Array배열의 인덱스 참조는 길이에 상관없이 한 번에 가져온다. → O(1)의 성능을 갖는다.삽입, 삭제의 성능이 좋지 않다. → 데이터를 추가, 제거하려면 내부적으로 필요한 단계가 많다.데이터 추가, 제거 시 내부적으로 수행해야 하는 단계연속된 메모리 할당배열은 메모리상에 연속적으로 저장되어 있다.→ 중간에 요소를 삽입하거나 삭제할 때 문제가 발생요소 이동 필요배열의 중간에 새로운 요소를 삽입하거나 기존 요소를 삭제할 경우, 해당 위치 이후의 모든 요소들을 이동시켜야 한다.→ 오버헤드가 발생한다.고정된 크기정적 배열의 경우 크기가 고정되어 있어, 삽입 시 공간이 부족하면 새로운 더 큰 배열을 생성하고 모든 요소를 복사해야 한다.삽입/삭제 위치에 따른 성능 차이배열의 끝에서 삽입/삭제하는 경우는 O(1)로 빠르지만, 최악의 경우(배열의 시작 부분에서 삽입/삭제) O(n)의 시간이 소요된다.메모리 재할당동적 배열의 경우, 크기를 늘릴 때 새로운 메모리 공간을 할당하고 기존 데이터를 복사해야 하므로 추가적인 시간이 소요된다.JS의 Array상황에 따라서 연속적, 불연속적으로 메모리를 할당한다.일반적으로 불연속적으로 할당한다.불연속적으로 할당된 메모리는 내부적으로 연결해서 사용자에게는 배열처럼 느껴진다.Linked List배열의 단점인 삽입, 삭제의 성능을 보완하기 위한 자료구조저장하려는 데이터들을 메모리(힙 영역)에 분산하여 할당하고, 해당 데이터를 서로 연결한다.노드를 사용하여 데이터들을 저장하고, 각 노드가 다음 노드를 가리키도록 한다.첫 노드의 주소만 알고 있으면 그 이후의 모든 노드에 접근할 수 있다.장점데이터 추가 및 삭제빈 메모리 공간 아무 곳에 데이터를 생성하고, 연결만 해주면 데이터 추가가 완료된다.중간에 데이터가 삽입/삭제 된다고 한다면 배열은 해당 데이터 이후의 모든 데이터들을 이동시켜야 하지만 연결리스트는 해당 데이터와 그 이전, 이후의 데이터만 수정하면 된다.단점특정 데이터를 찾고 싶다면 노드를 순회해야 한다. → O(n)의 성능을 갖는다. Array vs Linked List데이터의 참조가 많은 경우 ⇒ Array 사용데이터의 삽입과 삭제가 많은 경우 ⇒ Linked List 사용추상 자료형(ADT, Abstract Data Type)어떠한 데이터와 그 데이터에 대한 연산을 표기하는 방법→ 데이터의 논리적인 동작을 정의한다.구현 방법을 명시하지 않고, 자료구조의 특성과 연산만을 설명한다.데이터의 타입과 해당 타입에 수행할 수 있는 연산들만을 정의한다.내부 구현 세부사항은 숨기고 인터페이스만을 제공한다.Linked List의 ADT모든 데이터 출력 → printAll()모든 데이터 제거 → clear()인덱스 삽입 → insertAt(index, data)마지막 위치에 데이터 삽입 → insertLast(data)원하는 인덱스의 데이터 삭제 → deleteAt(index)마지막 데이터 삭제 → deleteLast()특정 인덱스 데이터 읽기 → getNodeAt(index)그림으로 쉽게 배우는 운영체제Program(= Application, App)저장장치에 저장된 명령문의 집합체Windows에서는 .exe의 형식저장 장치만 사용하는 수동적인 존재Process실행중인 프로그램저장장치에 저장된 프로그램이 메모리에 올라갔을 때 프로세스라고 한다.메모리, CPU, I/O 작업을 수행하는 능동적인 존재구조Code자신을 실행하는 코드가 저장되어 있는 영역Data전역 변수와 Static 변수가 저장되어 있는 영역Stack지역 변수와 함추 호출을 했을 때 필요한 정보들이 저장되는 영역함수 호출시 매개변수와 돌아갈 주소가 저장된다.Heap프로그래머가 동적으로 메모리를 할당하는 데 사용되는 영역→ 프로그래머가 런타임시 할당할 수 있는 메모리 공간Program → Process가 되는 과정(C 언어 기준)전처리기를 거쳐서 매크로로 정의한 숫자를 치환하고 필요한 파일을 불러온다.전처리기를 거치면 파일의 확장자는 .i가 된다.컴파일러가 컴파일 수행고수준인 C언어를 저수준인 Assembly어로 치환해준다.파일의 확장자는 .s가 된다.어셈블러가 어셈블리어를 기계어로 치환한다.파일의 확장자는 .o가 된다.링커가 링킹을 수행하여 여러 가지 라이브러리나 다른 소스 코드를 연결한다.파일의 확장자는 .exe가 된다.저장장치에 저장된 .exe파일을 실행하면 메모리에 올라가게 된다.→ 프로세스가 된다.프로세스는 운영체제에 의해 관리된다.Uni-Programming메모리에 오직 하나의 프로세스가 올라온 상태메모리 관점으로 정의Multi-Programming메모리에 여러개의 프로세스가 올라온 상태메모리 관점으로 정의Multi-ProcessingCPU 관점으로 정의CPU가 여러 개의 프로세스를 처리하는 것을 의미한다.Swapping메모리에 있는 데이터를 다른 저장장치로 보내고 다른 저장장치에서 데이터를 메모리로 올리는 방법PCB(Process Control Block)프로세스가 만들어지면 운영체제는 해당 프로세스의 정보를 갖고 있는 PCB를 만들고 저장한다.PCB들은 연결리스트라는 자료구조로 저장된다.OS는 프로세스가 종료되면 연결리스트에서 해당 프로세스의 PCB를 제거한다.구조Pointer부모와 자식 프로세스에 대한 포인터할당된 자원에 대한 포인터프로세스의 한 상태에서 다른 상태로 전환될때 저장하는 포인터Process Status현재 프로세스의 5가지 상태를 의미생성, 준비, 실행, 대기, 완료Process ID : 프로세스를 식별하기 위한 숫자Program Counter다음에 실행될 명령어의 주소를 포함한다.특정 프로세스가 CPU를 사용하다가 다른 프로세스에게 CPU를 반납하고 다시 CPU를 사용할 때 이전 상태의 명령어가 실행되어야 하기 때문에 반드시 필요하다.Register Info프로세스가 실행될 때 사용했던 레지스터의 정보PC와 마찬가지로 CPU를 뺏기고 다시 시작할 때 이전에 사용하던 값을 복구하기 위한 용도로 사용Memory Info프로세스가 메모리에 있는 위치 정보경계 레지스터 값이 저장CPU Scheduling InfoCPU 스케줄링에 필요한 우선순위, 최종 실행시간, CPU 점유시간등이 저장된다.Process Status시분할 처리를 위한 5가지 상태값New(생성)PCB를 생성하고 메모리에 프로그램 적재를 요청한 상태메모리에 프로그램 적재를 승인받으면 준비상태로 넘어간다.Ready(준비)CPU를 사용하기 위해 대기하고 있는 상태CPU 스케줄러에 의해 CPU가 할당된다.Waiting(대기)프로세스가 I/O 요청을 하면, I/O가 완료될때까지 기다리는 상태I/O 작업은 무거운 작업이기 때문에 I/O 작업이 완료될 때까지 CPU를 놀리는 것은 비효율적→ I/O 요청을 한 프로세스는 I/O 작업이 완료될 때까지 대기 상태로 두고 다른 프로세스에게 CPU를 할당한다.→ I/O 작업이 완료되면 대기 상태에 있던 프로세스에게 CPU 할당 기회를 준다.Running(실행)준비상태에 있는 프로세스가 CPU 스케줄러에 의해 CPU를 부여된 시간만큼 할당받아 실행되는 상태실행상태에 있는 프로세스의 수는 CPU의 개수이다.부여된 시간이 종료되면 CPU 스케줄러가 강제로 CPU를 빼앗는다.→ 준비 상태로 돌아간다.Terminated(완료)프로세스가 종료된 상태프로세스가 사용했던 데이터를 메모리에서 제거하고 PCB도 제거한다.

알고리즘 · 자료구조워밍업클럽CS전공지식DAY2

Taeho

인프런 워밍업 클럽 - CS Day 2

그림으로 쉽게 배우는 자료구조와 알고리즘(기본편)What is Data Structure?자료구조 : 데이터가 어떤 구조로 저장되고 어떻게 사용되는지를 나타낸다.변수 : 가장 단순한 자료구조배열 : 숫자나 문자열 등을 연속적으로 저장하는 자료구조인덱스를 통해 특정 숫자나 문자열에 접근할 수 있다.자료구조에 따라서 결과를 얻기 위한 처리 방법이 달라진다.What is Algorithm?어떤 문제를 해결하기 위한 확실한 방법문제를 해결할 수 있는 알고리즘은 하나만 존재하는 것이 아니라 여러가지 방법이 있을 수 있다.더 좋은 알고리즘이란?사용자에 따라 다를 수 있음메모리 사용률메모리를 더 사용하더라도 속도가 더 빠른 경우일반적으로 알고리즘 성능의 척도를 시간 복잡도로 표현한다.시간 복잡도란?특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간Bit-Ω : 최선의 시간 복잡도Big-O : 최악의 시간 복잡도가장 많이 사용된다.Big-θ : 평균의 시간 복잡도코드에서 성능에 많은 영향을 주는 부분코드의 속도를 판가름 하는 부분→ 반복문특정 알고리즘의 성능을 평가할 때는 알고리즘의 반복문을 보고 성능을 평가한다.Big-O선형시간 알고리즘입력의 크기(n)에 대비해 걸리는 시간을 그래프로 그렸을 때 정확히 직선이 된다.시간 복잡도 : O(n)입력의 크기가 증가함에 따라 실행 시간이 일정한 비율로 증가하는 알고리즘상수시간 알고리즘입력의 크기와 관계없이 항상 일정한 시간 내에 실행되는 알고리즘시간 복잡도 : O(1) Big-O 표기법은 성능을 정확하게 표기할 수는 없다.→ 해당 알고리즘의 입력이 늘어날 때 단순히 계산량이 얼마나 늘어나는지를 표현하는 방법이기 때문→ 계산에 가장 많은 영향을 끼치는 연산만 표기한다.그림으로 쉽게 배우는 운영체제OS개인용 컴퓨터 : Windows, MacOS대형 컴퓨터 / 서버 : Linux, Unix스마트폰 / 태블릿 : Android, iOS내비게이션, 스마트 워치, 냉장고, 세탁기 등 : 임베디드 운영체제싱글 스트림 배치 시스템한 번에 하나의 작업만 실행한다.사용자는 컴퓨터와 직접 상호작용하지 않는다.작업은 일괄적으로 처리되며, 순차적으로 실행된다.작업 결과는 나중에 출력된다.시분할 시스템여러 사용자가 동시에 컴퓨터 자원을 공유할 수 있게 해주는 방식CPU 시간을 짧은 시간 단위로 나누어 여러 작업에 할당한다.사용자는 시스템과 상호작용할 수 있다.메모리 침범 이슈가 발생UNIXAT&T벨 연구소에서 탄생한 C언어 기반의 OS멀티 프로그래밍, 다중 사용자, 파일 시스템을 지원한 OSOS가 하는 일프로세스 관리프로세스를 관리하지 않는다면 여러 개의 프로그램들을 동시에 수행할 수 없다.메모리 관리모든 프로그램은 메모리에 올라가서 동작한다.H/W 관리사용자가 H/W에 대한 직접 접근을 막는다.File System 관리OS의 핵심 → Kernel커널은 프로세스와 메모리, 저장장치를 관리하는 핵심적인 기능을 담당한다.사용자는 OS의 커널에 직접 접근할 수 없고, Interface를 통해서 접근할 수 있다.Interface : GUI, CLIGUI(Graphic User Interface)Graphic을 통해서 사용자와 커널이 상호작용한다.CLI(Command Line Interface)Unix, Linux가 기본적으로 제공하는 인터페이스Text를 이용하여 사용자와 커널이 상호작용한다.System CallApplication이 커널과 상호작용하기 위한 인터페이스커널에서 제공하는 write()를 사용한다.→ OS가 저장장치의 빈 공간에 자동으로 저장한다.DriverH/W와 Kernel의 인터페이스각각의 H/W에 대한 프로그램을 커널이 전부 알고 있을 수 없음→ H/W 제조사에서 드라이버를 제작하여 커널에 제공한다.폰 노이만 구조현대 컴퓨터의 기본이 되는 중요한 아키텍처로, 그 단순성과 범용성으로 인해 여전히 널리 사용되고 있다.그 한계를 극복하기 위해 캐시 메모리, 병렬 처리 등 다양한 기술이 개발되어 적용되고 있다.CPU와 메모리를 Bus로 연결한다.Bus : 데이터를 전달하는 통로프로그램 내장 방식프로그램은 메모리에 올려서 실행된다.프로그램을 메모리에 내장했다고 하여 프로그램 내장 방식이라고 한다.주요 구성 요소중앙처리장치(CPU)메모리입출력 장치핵심 특징프로그램 내장 방식: 프로그램과 데이터를 동일한 메모리에 저장한다.순차적 처리: CPU가 메모리로부터 명령어를 순차적으로 읽어 실행한다.단일 버스 구조: CPU와 메모리 사이에 하나의 버스를 사용하여 데이터와 명령어를 전송한다.장점범용성: 하드웨어 변경 없이 소프트웨어만 교체하여 다양한 작업을 수행할 수 있음.편의성: 프로그램 변경이 용이하여 컴퓨터의 활용도를 크게 높임단점폰 노이만 병목 현상: 단일 버스 구조로 인해 CPU와 메모리 간의 데이터 전송에 병목 현상이 발생할 수 있다.순차 처리의 한계: 한 번에 하나의 명령어만 처리하므로 CPU 활용이 비효율적일 수 있다.최근의 컴퓨터 H/W메인보드다른 하드웨어를 연결하는 장치장치 간에 데이터를 전송하는 버스가 존재한다.CPUMemoryCPU(Central Processing Unit, 중앙 처리 장치) 구조Control Unit(제어 장치)모든 장치들의 동작을 지시하고 제어한다.ALU(Arithmetic and Logic Unit, 산술논리 연산장치)실제로 데이터 연산을 수행한다.Register프로그램 카운터메모리 주소 레지스터메모리 버퍼 레지스터명령어 레지스터CPU 내에서 계산을 위해 임시로 데이터를 저장한다.Memory 종류RAM(Random Access Memory)랜덤으로 데이터를 읽어도 저장된 위치와 상관 없이 동일한 읽는 속도를 갖는다.전력이 끊기면 데이터를 잃어버린다.메인 메모리로 사용된다.ROM(Read Only Memory)전력이 끊겨도 데이터를 보관할 수 있다.데이터를 한 번 쓰면 수정할 수 없다.BIOS를 저장하는데 주로 사용한다.Computer의 부팅 과정전원 인가ROM에 저장된 BIOS 실행BIOS가 컴퓨터에 연결된 장치들(CPU, RAM, 키보드, 마우스, 저장장치, etc...)에 이상이 없는지 체크한다.이상이 있으면 오류를 반환하면서 부팅이 이루어지지 않는다.H/W에 있는 마스터 부트 레코드에 저장된 부트로더를 메모리로 가져와서 실행시킨다.OS를 메모리로 올린다.CPU의 I/O 작업CPU는 입출력 작업이 들어오면 입출력 관리자에게 입출력 명령을 내린다.PollingCPU는 입출력 명령이 언제 완료될지 알 수 없기 때문에 입출력 관리자에게 주기적으로 신호를 보내어 종료 여부를 확인한다.→ 주기적으로 CPU가 확인해야 해서 성능이 좋지 않다.InterruptPolling 방식의 단점을 해결한 방식CPU가 입출력 관리자에게 명령을 내리고, CPU는 다른 작업을 수행한다.입출력 관리자는 입출력이 완료되었을 때 CPU에게 신호를 준다. CPU는 해당 신호를 받아서 ISR(인터럽트 서비스 루틴)을 실행시켜 작업을 완료한다.비동기적으로 동작하기 때문에 성능에 이점이 있다.ISR(Interrupt Service Routine)특정 인터럽트가 들어오면 해당 인터럽트를 처리하는 함수Interrupt의 종류H/W Interrupt외부 하드웨어 장치(키보드, 마우스, 타이머 등)에 의해 발생시스템 버스를 통해 CPU에 전달됨예기치 못한 상황에 대응하기 위해 사용S/W Interrupt사용자 프로그램에서 발생한 인터럽트프로그램 실행 중 특정 명령어에 의해 발생주로 시스템 콜(system call)을 구현하는 데 사용됨예외 처리나 오류 상황에 대응하기 위해 사용

알고리즘 · 자료구조워밍업클럽CS전공지식DAY1

채널톡 아이콘