일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- spring
- Inheritance
- Entity Set
- 셀레니움
- Class
- descriptive statistics
- Reference Type
- 리눅스
- Java
- External Scheme
- X.org
- dbms
- preprocessing
- Unity
- Mac
- 자바
- Operator
- X윈도우
- OOP
- python
- BFS
- systemd
- Polymolphism
- selenium
- 리눅스 마스터 1급
- Binary Search
- 백준
- Entity
- literal
- Physical Scheme
- Today
- Total
목록전체 글 (205)
Byeol Lo
뮤텍스 락은 동기화 도구중에 가장 간단하다. 여기서는 뮤텍스 락과 유사하지만 프로세스가 활동을 동기화하는 더 복잡하지만 세밀한 방법을 제공한다. S는 두 원자적 연산인 wait() 와 signal()을 통해서 접근되는 integer 변수다(wait를 P 연산이라고도 하며, signal을 V 연산이라고도 한다).wait(S) { while (S signal(S){ S++;} 위 wait()와 signal() 연산에서 semaphore의 integer 값에 대한 모든 수정은 atomic하게 실행되어야 한다. 즉, 한 프로세스가 세마포어 값을 수정할 때, 다른 프로세스가 동시에 그 같은 세마포어 값을 수정할 수 없다. 또한 wait(S)의 경우, Semaphore의 S의 정수값(S ≤ 0)의 테스트 및 가..
6.4절에서 제시된 임계 영역 문제의 하드웨어 기반 해결책은 복잡하며 일반적으로 응용 프로그래머에게 접근이 어렵다. 대신, OS designer들은 임계 영역 문제를 해결하기 위한 더 높은 수준의 소프트웨어 도구를 구축하여 제공한다. 이러한 도구 중 가장 간단한 것은 Mutex Lock이다(사실 뮤텍스라는 용어는 상호 배제를 나타냄). 우리는 Mutex Lock을 사용하여 임계 영역을 보호하고 이로써 race condition을 방지한다. 즉, 프로세스는 critical section에 들어가기 전에 이 lock 을 acquire()해야 하며, 임계 영역을 나갈 때 lock 을 release() 해야한다. 뮤텍스 락에는 사용 가능 여부를 나타내는 boolean 변수인 available이 있다. 락이 사..
소프트웨어 기반 솔루션은 현대 컴퓨터 아키텍처에서 작동이 보장되지 않는다. 이 섹션에서는 critical section을 해결하기 위한 세 가지 하드웨어 명령을 제시한다. 이러한 원시 작업은 직접 동기화 도구로도 사용될 수도 있고, 더 추상적인 동기화 메커니즘의 기반이 될 수도 있다. 6.4.1 Memory Barriers 코드 재배열 때문에 피터슨 해결책은 잘 작동하지 않기 때문에 다른 방안을 모색해야하는데, 컴퓨터 아키텍처가 응용 프로그램에 어떤 메모리 보장을 제공할 것인지 결정하는 것을 메모리 모델이라고 한다. 일반적으로 메모리 모델은 두 가지 범주 중 하나에 속한다.1. Strongly Ordered: 하나의 프로세서에서 메모리 수정이 즉시 다른 모든 프로세서에게 보이는 경우2. Weakly Or..
이제 critical section 문제를 해결하기 위한 traditional한 방법인 peterson's sol'n을 보자. 현대 컴퓨터 아키텍처가 기본 machine instruction을 수행하는 방식 때문에 peterson's solution이 이러한 아키텍처에서 올바르게 작동할 것이라는 보장이 없다. 하지만, 솔루션은 M.P.B.(Mutual Exclusion, Progress, Bounded Waiting)의 요구사항을 만족하고 소프트웨어 설계의 복잡성을 잘 설명하는 알고리즘을 제안하기 때문에 보고 넘어가자. 피터슨의 솔루션은 두 프로세스가 critical section과 remainder section 사이를 번갈아 가면서 실행하는 경우에만 적용된다. 프로세스는 P0와 P1로 번호가 매겨지며..
프로세스 동기화를 고려할 때, 빼놓을 수 없는 논쟁이 critical-section problem이다. n개의 프로세스가 있다고 치자(P_0, P_1, ..., P_(n-1)) 각 프로세스는 공유 데이터에 접근하고 수정하는 critical section이라는 구역이 있다. 시스템은 이러한 critical section만 무사히 건너기만(하나의 프로세스만 그 section을 실행하도록) 하면 될 것이다. 이를 위해 프로세스 간에 프로토콜을 설계해야 한다. 즉, 프로세스가 이 critical section에 진입하기 위한 허가 요청(request)이 필요하다는 것이다. 이 요청을 구현하는 코드 부분이 진입 섹션(entry section)이라고 하며, 진입이 된 상태면 critical section 을 실행하..
스레드와 프로세스가 어떻게 연결되고 유저 스레드가 LWP를 통해 커널 스레드를 어떻게 할당 받는지, 또 커널스레드 간에 프로세서의 경쟁이 붙어서 multithreading의 아키텍처에서 커널스레드가 I/O burst, CPU burst에 따라 priority, nice, vruntime 등으로 어떤 알고리즘으로 스케줄링 될 수 있는지 보았을 것이다. 이번에는 이 프로세스가 서로서로 협동하는(cooperating process) 관계일 때는 어떻게 되는지 보자. CPU 스케줄러가 프로세스 간에 빠르게 전환하여 동시 실행을 제공하는 방법을 설명했는데, 그게 multithreading이며, 이는 하나의 프로세스가 다른 프로세스가 스케줄될 때까지 실행이 완전히 끝나지 않을 수 있다는 것을 의미한다. 실제로 프로..
이제 특정 시스템에 맞는 스케줄링 알고리즘을 선정해야 할 것이다. 이 전에 다양한 알고리즘을 봤는데 우리가 운용하고 싶은 시스템에 적합한 알고리즘이 어떤 것이 있고 어떤 걸 사용해야 가장 최적인지를 봐야 한다. 우선 알고리즘 선택 기준은 다음과 같다.최대 응답 시간이 300ms라는 제약 조건 하에서 CPU 활용도 극대화처리 시간이 (평균) 총 실행 시간에 선형적으로 비례하도록 처리량 극대화 알고리즘이 선택됐다면 실제 그 알고리즘을 써보고 평가해야 할 것이다. 평가 방법을 보자.5.8.1 Deterministic Modeling Analytic Evaluation 은 주어진 알고리즘과 시스템 작업 부하를 사용하여 해당 작업 부하에 대한 알고리즘의 성능을 평가하기 위한 공식 또는 숫자를 생성한다. Deter..
Linux, Window, Solaris의 스케줄링을 살펴보자(보통 그냥 스케줄링이라고 하면 일반적인 의미에서 process scheduling 용어를 말함). 또한 솔라리스와 윈도우 시스템에서 kernel threads의 스케줄링 및 리눅스 스케줄러에서 task scheduling 도 볼 것이다. 5.7.1 Example: Linux Scheduling 리눅스는 UNIX 스케줄링 알고리즘을 변형하여 사용한다. 하지만 이 알고리즘은 SMP 아키텍처를 고려하여 설계된게 아니기 때문에 다중 프로세서 시스템을 충분히 지원하지 못했다. 리눅스 커널 버전 2.5 에서는 스케줄러가 개편되면서 task 수에 상고나없이 상수 시간에 작동하는 O(1) 스케줄링 알고리즘이 포함되었고, SMP 시스템을 위해 processo..
hierarchical structure 가짐(상하 관계가 있으며, 각 계층마다 level이라고 부름)root node 하나를 가짐, root node도 leaf node가 될 수 있음root 에서 다른 모든 경로가 유일함leaf node 는 edge이 1개 이하sub-tree는 edge 하나를 없앴을 때 나오는 기존 root node를 포함하지 않는 tree를 말함당연하지만 sub-tree도 root에서 다른 모든 경로가 유일함그래프의 일종이며 Undirected Graph 라고 볼 수 있음parent node → child node 의 관계는 one-to-many 관계임node가 n개 있으면 edge은 항상 n-1개임 공통적으로 HashMap의 key를 Generic으로 주어서 범용적으로 쓸 수 있도..
import java.util.StringTokenizer;import java.io.IOException;import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.util.HashMap;import java.util.ArrayList;public class Main { final static BufferedReader BR = new BufferedReader(new InputStreamReader(System.in)); static HashMap> tree; static StringTokenizer st; stat..