ImYena

CPU 스케줄링 목적 공평성 효율성 확장성 사용자의 반응시간 보장 무한연기(기아현상) 방지 CPU burst : 프로세스가 CPU를 쓰는 시간 I/O burst : 프로세스가 I/O 작업을 하는 시간 > 대부분 프로세스가 IO bound Process이다! 선점형 vs 비선점형 선점형 : 하나의 프로세스가 실행 중일 때 다른 프로세스가 CPU를 선점할(빼앗을) 수 있는 경우 비선점형 : 하나의 프로세스사 실행 중일 때 다른 프로세스는 대기해야 하는 경우 디스패처(Dispatcher) : Ready 상태의 프로세스를 Running 상태로 상태전이 시키는 것을 dispatch라고 하는데, 해당 역할을 진행하는 것을 Dispatcher라고 함 스케줄러와 디스패처 차이 스케줄러 : CPU가 해야할 일을 계획하는..

멀티 프로세스 환경 한 대의 컴퓨터에 여러 개의 프로세스(서비스)를 띄워 사용하는 방식 각 프로세스는 독립적인 메모리를 할당 받기 떄문에, 메모리 공유를 위해서는 IPC를 사용해야 함 IPC(Inter Process Communication) 프로세스 혹은 스레드가 데이터를 교환하는 기법 공유 메모리(Shared Memory) 여러 프로그램이 동시에 접근할 수 있는 메모리 성능은 좋지만, 동기화 문제 발생 메시지 교환(Messaging Passing) 커널(운영체제)가 프로세스간 서로 자원에 접근이 불가능하기 때문에 대리 전달해주는 것 안전하고 동기화 문제가 없는 대신, 성능이 떨어짐 RPC(Remote Procedure Call) 별도의 원격 제어를 위한 코딩 없이 다른 주소 공간에서 리모트의 함수나 ..

운영체제(OS, Operating System) 시스템 하드웨어 관리와 응용 소프트웨어를 실행하기 위한 하드웨어 추상화 플랫폼과 공통 시스템 서비스를 제공하는 시스템 소프트웨어 > 한정된 자원으로 효율적인 일처리를 하도록 편하게 도와주는 소프트웨어 사용 목적 편리성 CUI GUI 효율성 시스템 보호 프로세스와 쓰레드 관리 구조 커널(Kernel) 운영체제의 핵심으로 메모리에 상주하여 가장 빈번하게 사용되는 기능 담당 프로세스, 메모리 관리 등 핵, 관리자 프로그램, 상주 프로그램, 제어 프로그램이라고도 함 시분할 시스템(Time Sharing System) 여러 사용자가 시스템 및 가상 메모리 관리 사용자 지향적(User-oriented) 장점 응답시간 단축 생산성 향상, 프로세서 유휴 시간 감소 단점 ..

힙(Heap) 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)의 시간복잡도 소요, 이에 반해 힙은 O(logn) 소요 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용 힙 구조 최대값을 구하기 위한 구조(최대 힙, Max Heap)와 최소값을 구하기 위한 구조(최소 힙, Min Heap)로 분류 할 수 있음 힙의 두 가지 조건 각 노드의 값이 최대 힙의 경우 해당 노드의 자식 노드가 가진 값보다 크거나 같고, 최소 힙의 경우 작거나 같아야 함 완전 이진 트리 ..

큐(Queue) 구조 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조 예) 줄 서는 행위 FIFO(First-In, First-Out) 방식 또는 LILO(Last-In, Last-Out) 방식 기능 Enqueue(인큐) 큐에 데이터를 넣는 기능 Dequeue(디큐) 큐에서 데이터를 꺼내는 기능 특징 운영체제 혹은 인터넷/네트워크에서 자주 사용 스택과 꺼내는 순서가 반대 배열과 같이 특정 위치가 정해진 것이 아니라 데이터의 입력과 출력만 존재! 그렇기 때문에 큐는 특정 데이터를 정해서 출력하는 것이 불가능! 참고 : 어디에 큐가 많이 쓰일까? - 멀티 태스킹을 위한 프로세스 스케줄링 방식을 구현하기 위해 많이 사용(운영체제 참조) - 큐의 경우에는 장단점 보다는(특별히 언급되는 장단점이 없음), ..

유클리드 호제법/유클리드 알고리즘(Euclidean Algorithm) 2개의 자연수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 알고리즘 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같음 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수 시간복잡도 O(logN) 기존의 하나씩 나누어서 구하는 방식으로 최대공약수를 구하게 될 경우 시간복잡도 O(N) 예시) 78696과 19332의 최대공약수 78696 ＝ 19332×4 ＋ 1368 19332 ＝ 1368×14 ＋ 18..

그리디/탐욕 알고리즘 Greedy Algorithm 최적해를 구하는 데에 사용되는 근사적인 방법 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방법 조건 탐욕스런 선택 조건(greedy choice property) 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이 최적 부분 구조 조건(optimal substructure) 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것 예시 Good Case 가장 단 기간에 서울에서 부산까지 도착하는 거리를 구하려면 그 순간 순간 가장 빠른 최단 경로를 구하면 된다. 즉, 서울에서 대구까지의 최적의 거리, 대구에서 부산까지의 최적의 거리를 구하는 것이 그리디 알고리즘이라고 할 수 있다. 또한, 각각의 선택이..

스케줄링(Scheduling) 여러개의 프로세스가 시스템 내 존재하는 다중 프로그래밍에서 자원 할당을 위한 프로세스를 선택하는 과정 자원 관리에 대한 분류 시간 분할(Time Sharing) 관리 하나의 자원을 여러 스레드가 번갈아 가며 사용 ex) 프로세서(Processor) - 프로세스 스케줄링 공간 분할(Space Sharing) 관리 하나의 자원을 분할하여 동시에 사용 ex) 메모리(Memory) 스케줄링의 목적 시스템 성능(Performance) 향상 시스템 성능 지표 응답시간(Response Time): 작업 요청(Submission)으로부터 응답을 받을 때까지의 시간 Interactive System 대화식 시스템 / Real-time System 실시간 시스템 작업 처리량(Throughpu..

스레드 관리(Thread Management) 1. 프로세스(Process)와 스레드(Thread) 프로세스 어떠한 목적을 위해 연산을 하는 과정 자원을 할당받고 그 자원을 제어 스레드 프로세스가 돌아가는 과정 중 "제어" 부분 의미 하나의 프로세스에 여러 개의 스레드 존재 가능 스레드는 프로세스와 다르게 하나의 자원을 여러 스레드가 공유 가능 2. 스레드(Thread) LWP, Light Weight Process 프로세서(CPU) 활용의 기본 단위 구성요소 Thread ID Register set : 제어를 위해 알고 있어야 하는 정보 Stack: 자신만의 작업 영역 스레드의 장점 사용자 응답성 (Responsiveness) 일부 스레드 처리가 지연되어도, 다른 스레드는 작업을 계속 처리할 수 있다...

프로세스 관리(Process Management) 1. 프로세스(Process) 프로세스의 정의 실행 중인 프로그램 실행을 위해 시스템(커널)에 등록된 작업 시스템 성능 향상을 위해 커널에 의해 관리됨 각종 자원들을 요청하고 할당 받은 개체 능동적인 개체(active entity) 실행 중에 각종 자원을 요구, 할당, 반납하며 진행 Abstraction for CPU sharing CPU를 공유하는 여러 작업 간의 구분을 위한 단위로 사용 각 프로세스는 컴퓨터 시스템을 독점해서 사용하는 것으로 인식 프로세스의 구성 CPU 상태 register 프로그램이 CPU에 올라가야 프로세스, 즉 CPU의 래지스터에 올라가야 함 메모리 Text (프로그램 코드 저장) Data (프로그램 초기 데이터 저장) Heap ..