CS 전공지식 스터디 발자국 02

CS 전공지식 스터디 발자국 02 운영체제Ch401 프로세스 간 통신(1) 같은 컴퓨터 내의 프로세스끼리파이프 이용 - 운영체제가 생성한 파이프를 이용해 데이터를 읽고 씀쓰레드 이용 - 데이터나 힙 영역을 이용한 통신 (한 프로세스 내에서)(2) 다른 컴퓨터의 프로세스끼리네트워크 이용 - 소켓 통신, RPC(Remote Procedure Call)02 공유자원과 임계구역공유자원 - 프로세스 간 통신을 할 때 공동으로 이용하는 파일 - 동기화 문제 발생 (동시에 실행됐을 때 발생)임계구역(Critical Section) - 여러 프로세스가 동시에 사용해서는 안 되는 영역Race Condition - 공유자원을 사용하기 위해 경쟁하는 것임계구역의 상호배제 메커니즘(1) 임계영역에는 동시에 하나의 프로세스만 접근(2) 여러 요청에도 하나의 프로세스 접근만 허용(3) 임계구역에 들어간 프로세스는 최대한 빠르게 나올 것03 세마포어(Semaphore)대기 큐 - 공유자원을 쓰기 위한 프로세스들이 대기하는 공간열쇠관리자 - 운영체제, 열쇠 - 세마포어(정수형 변수), 여러 개 가질 수 있음int s = 1; // semaphore wait(s) // lock int currentHP = GetHealth(); health = currentHP - 10; signal(s); // return 세마포어의 단점 - 잘못 사용할 가능성이 있음 (wait - signal 짝이 아닌 wait-wait, signal-signal 등)04 모니터세마포어의 단점을 보완한 상호배제 메카니즘: 프로그래밍 언어 차원에서 지원하는 방법ex) java의 synchronized Ch5데드락여러 프로세스가 서로 작업이 끝나는 상태를 기다리다가 아무런 프로세스도 작업을 진행하지 못하는 상태(ex) 식사하는 철학자교착상태의 필요조건 (모두 충족해야 교착상태 발생)(1) 상호배제 - 어떤 프로세스가 리소스를 차지하였다면 그 리소스는 다른 프로세스에 공유되어서는 안 됨(2) 비선점 - 다른 프로세스가 리소스를 빼앗을 수 없어야 함(3) 점유와 대기(4) 원형대기 - 점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있음교착상태 해결 방법교착상태 회피전체 자원, 할당 자원의 수를 기준으로 안정 / 불안정 상태를 가짐불안정(교착 상태에 빠질 확률이 높아짐)(ex) 은행원 알고리즘 - 누구에게도 돈을 빌려주지도 못하고 받지도 못하는 교착상태를 방지하기 위함자원을 할당하기 전, 전체 자원의 수 파악 (시스템의 총 자원)프로세스가 필요한 자원 (최대 요구 자원)→ 요청이 예상되는 자원을 파악하여 자원을 빌려 줌 (안정 상태)→ 현재 사용 가능한 자원이 요청 예상 자원보다 적음 (불안정 상태)비싸고, 비효율적인 알고리즘 ⇒ 교착상태를 해결하는 방식을 연구 (먼저 교착상태 여부를 파악)(1) 가벼운 교착상태 검출 - 일정시간 작업을 진행하지 않을 때, 교착상태로 간주 → 마지막 체크포인트로 롤백(2) 무거운 교착상태 검출 - 자원할당 그래프를 통해 교착상태를 일으킨 프로세스 강제종료, 체크포인트로 롤백 Ch7메모리 종류(1) 레지스터휘발성 메모리, 32bit / 64bit (레지스터의 크기),(2) 메인메모리실제 프로세스들이 올라가는 공간(3) 캐시메인메모리에 있는 값을 옮길 때, 미리 저장 (L1, L2 캐시 등 속도에 따라)(4) 보조저장장치(HDD, SSD)비휘발성메모리, 저장장치메모리와 주소주소 (메모리 관리를 위해 설정)(1) 물리주소와 논리주소사용자가 인식하는 것(논리주소)(2) 경계레지스터운영체제 보호를 위해 설정(3) 절대주소와 상대주소컴파일러(상대주소), 실제 메모리 관리자가 확인하는 공간(절대주소)재배치 레지스터(메모리 관리자)메모리 할당 방식메모리보다 더 큰 프로그램을 실행시키는 방법?필요한 부분만 잘라서 실행, 일부는 하드디스크에 저장 - 오버레이가변분할방식(세그멘테이션)프로세스의 크기에 따라 메모리를 할당내부단편화는 없으나 외부단편화(연속되지 않은 공간) 발생고정분할방식(페이징)고정된 크기에 따라 메모리를 할당오버헤드 X, 작은 프로세스도 큰 영역에 할당돼서 공간이 낭비내부단편화 발생(연속되지 않은 공간, 내부에서 발생하는 공간 낭비)버디시스템2의 승수로 메모리를 할당(내부단편화 최소화)조립하기 쉬움(외부단편화 최소화) 알고리즘재귀(Recursion)재귀: 어떤 것을 정의할 때 자기 자신을 참조하는 것재귀함수: 재귀적으로 정의된 함수function myFunction(number){ if(number >10) return; // 기저조건 console.log(number); myFunction(number+1); } myFunction(1) // 메모리가 꽉 찰 때까지 출력탈출조건(기저조건)이 있어야 사용할 수 있음콜스택 (FILO)함수 A 호출 - A 내부에서 B 호출 - B 실행 (콜스택에서 제거) - A 끝 (콜스택에서 제거)(ex)function factorial(nubmer){ if(number ==1 || number == 0){ return 1}; else { return number* factorial(number-1) } } 재귀적으로 생각하기재귀의 패턴 (1) 반복실행 (반복문에 비해 이점이 없음)재귀의 패턴 (2) 하위 문제의 결과를 기반으로 현재를 개선 (ex) 팩토리얼 함수 구현 (하향식 계산)상향식 계산 (반복문으로도 가능)Q1. 배열의 합(1) 하위문제 파악 (2) 바탕으로 현재 구현식 작성 (3) 기저조건 추가function sumArray(arr){ if(arr.length ==1) return arr[0] return sumArray(arr.slice(0, -1)) + arr[arr.length -1]; }Q2. 문자열의 길이function strLength(arr){ if(arr[0]==null) return 0; return strLength(arr.slice(0, -1))+1; }Q3. 지수함수function power(x, n){ if(n==0) return 1; return power(x, n-1)*x; }Q4. 하노이 탑(1) 하위문제 파악 (2) 바탕으로 현재 구현식 작성 (3) 기저조건 추가목표: 가장 큰 원판을 기둥 C로 옮기기 - 다른 원판들을 기둥 B로 옮기기 (하향식 접근)function hanoi(count, from, to, temp){ if(count ==0) return; hanoi(count -1, from, temp, to) // 기둥 B로 나머지를 옮기는 부분 hanoi(count -1, temp, to, from) // 나머지를 다시 기둥 C로 옮기는 부분 } hanoi(3, "A", "C", "B")

CS 전공지식 스터디 미션 02

CS 전공지식 스터디 미션 02 운영체제1. FIFO 스케줄링의 장단점?장점: 단순하고 직관적 (먼저 온 프로세스가 먼저)단점: 먼저 들어온 프로세스의 작업이 다 끝나야 다음 작업이 실행2. SJF를 사용하기 어려운 이유?Short Job First, 실행 시간이 짧은 프로세스만 실행되기 때문에 긴 작업들이 끝없이 미뤄지는 사태 발생프로세스 종료 시간 예측 어려움3. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?컨텍스트 스위칭에 많은 시간이 할당되어, 오버헤드가 커짐4. MLFQ에서 CPU Bound Process와 I/O Bound Process 구분법스스로 CPU를 반납하면 CPU 사용률이 적은 것이니 I/O 바운드 프로세스일 확률이 높음 (CPU 사용률에 따라 구분)5. 공유자원이란?프로세스 간 통신을 할 때 공동으로 이용하는 파일- 동기화 문제 발생 (동시에 실행됐을 때 발생)6. 교착상태에 빠질 수 있는 조건?(1) 상호배제 - 어떤 프로세스가 리소스를 차지하였다면 그 리소스는 다른 프로세스에 공유되어서는 안 됨(2) 비선점 - 다른 프로세스가 리소스를 빼앗을 수 없어야 함(3) 점유와 대기(4) 원형대기 - 점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있음 알고리즘1. 재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 발생하는 문제점? 함수가 무한히 실행되거나 의도치 않게 종료될 수 있음2. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수 작성function sumOdd(n) { if(n%2 == 0) { return sumOdd(n-1) } else { if(n==1) return 1; return sumOdd(n-2)+n } } console.log(sumOdd(10))

CS 전공지식 스터디 발자국 01

CS 전공지식 스터디 발자국 01 운영체제운영체제 구조커널 - 프로세스, 메모리, 저장장치 관리사용자는 GUI, CLI로 커널에 접근사용자 및 어플리케이션은 시스템 콜을 통해 커널에 접근 (커널을 보호)복잡한 하드웨어 등은 디바이스 드라이버를 설치하여 커널에 접근하여 동작컴퓨터 하드웨어와 구조메모리 내장 방식 - 메모리 위에서 프로그램을 동작CPU, 메모리, 하드디스크, 그래픽카드, 하드웨어CPU (Central Processing Unit) - ALU, Control Unit, Register메모리 종류 - RAM(Random Access Memory), ROM(Read Only Memory)컴퓨터의 부팅 과정ROM (바이오스): 주요장치 이상 확인 - MBR에 저장된 부트로더를 메모리로 가져와서 실행 - 운영체제 로드 - 프로그램은 메모리에 올라와서 운영체제가 관리프로그램 & 프로세스프로그램: 저장장치에 저장된 명령문의 집합체 (.exe)프로세스: 실행 중인 프로그램 (저장된 프로그램이 메모리에 올라갔을 때의 상태) - 능동적인 존재멀티프로그래밍 & 멀티프로세싱멀티프로그래밍: 메모리에 여러 개 프로그램이 올라온 것멀티프로세싱: CPU 관점으로 정의, CPU가 여러 개의 프로세스를 처리하는 것동시에 이용한다 (멀티프로그래밍으로 프로그램을 여러 개 올리고, 멀티프로세싱을 이용해 여러 개의 프로세스를 처리하게 됨)PCBPCB(Process Control Blcok): 연결리스트 구조, 프로세스가 만들어지면 해당 프로세스의 정보를 가지고 있는 PCB가 생성Context Switching하나의 프로세스를 실행하는 도중에 다른 프로세스를 실행하기 위해 다른 프로세스로 전환(인터럽트 발생) 원래 실행 중인 작업을 PCB에 저장하고 실행될 프로세스의 상태대로 다시 CPU 세팅 자료구조 및 알고리즘자료구조: 대량의 데이터를 효율적으로 관리할 수 있는 자료의 구조알고리즘: 문제를 해결하는 방식시간복잡도: 특정 알고리즘이 어떤 문제를 해결하는 데에 걸리는 시간어떻게 평가할까?시간을 측정하는 방식이 아닌, 코드 성능에 많은 영향을 주는 부분(반복문)을 보고 평가Big-O (최악의 경우를 평가)(ex) 배열에서 원하는 숫자를 찾는 알고리즘의 Big-O n번만에 데이터를 찾을 수 있음 → O(n)O(1), O(n), O(log n), O(n!) 등 배열인덱스로 접근하여 데이터 저장연결리스트각 Node가 서로 연결되어 있는 구조 (Head, Tail 존재)스택(LIFO)Last In First Out, 마지막으로 들어온 데이터가 먼저 나가는 구조큐(FIFO)First In First Out, 처음으로 들어온 데이터가 먼저 나가는 구조덱 (양쪽으로 삽입 삭제 가능)앞뒤로 삽입과 삭제가 가능한 구조해시테이블(Key, Value) 구조 - 해시함수를 적용하여 고유한 Index 생성

CS 전공지식 스터디 미션 01

CS 전공지식 스터디 미션 01 운영체제폴링방식을 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?인터럽트: CPU가 입출력 관리자에게 명령을 내리고 하던 일을 계속함(지속적으로 체크할 필요가 없음) - 입출력 관리자는 입출력이 완료됐을 때 CPU에게 신호를 줌 - ISR(인터럽트 서비스 루틴 - 비동기적으로 동작함, 성능이 좋음)프로그램과 프로세스가 어떻게 다른가요?프로그램: 저장장치에 저장된 명령문의 집합체 (.exe)프로세스: 실행 중인 프로그램 (저장된 프로그램이 메모리에 올라갔을 때의 상태) - 능동적인 존재멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티프로그래밍: 메모리에 여러 개 프로그램이 올라온 것멀티프로세싱: CPU 관점으로 정의, CPU가 여러 개의 프로세스를 처리하는 것동시에 이용한다 (멀티프로그래밍으로 프로그램을 여러 개 올리고, 멀티프로세싱을 이용해 여러 개의 프로세스를 처리하게 됨)운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?PCB(Process Control Blcok) 연결리스트 구조, 프로세스가 만들어지면 해당 프로세스의 정보를 가지고 있는 PCB가 생성컨텍스트 스위칭이란 뭔가요?Context Switching하나의 프로세스를 실행하는 도중에 다른 프로세스를 실행하기 위해 다른 프로세스로 전환(인터럽트) 원래 실행 중인 작업을 PCB에 저장하고 실행될 프로세스의 상태대로 다시 CPU 세팅 자료구조 & 알고리즘여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.배열. 학생의 정보를 저장하고 인덱스로 접근이 가능하여 참조가 쉬움.여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.들어온 순서대로 처리해야 하기 때문에, FIFO 구조인 큐를 선택.