전체 글

멀티프로세서 스케줄링에는 다음의 세 가지 설계 이슈들이 있다.프로세스를 어느 처리기에 할당할 것인가?각 처리기에서 멀티프로그래밍을 지원할 것인가?다음번 실행 프로세스로 어떤 프로세스를 고를 것인가? Processor Affinity (처리기 친화성)- 준비상태의 쓰레드를 그 쓰레드가 전에 실행되었던 처리기에 스케줄링하는 것이 합리적이다. - Processor Affinity는 처리기 전용 지역 캐시(local caches) 때문에 중요하다. 스레드가 수행할 때 수행되었던 처리기 전용 캐시에 데이터가 여전히 남아 있을 수 있기 때문에 성능이 개선될 수 있다.다른 처리기에 변경되어 수행되는 것은 필요한 데이터가 새로운 처리기에 다시 로드되어야 하고 지난 처리기의 캐시 라인들이 무효화되어야 한다는 것을 의미한..

Scheduling 처리기 스케줄링의 목적을 한마디로 표현하면 "응답 시간이나, 처리량, 효율성을 증대시키기 위해 처리기가 다음에 실행할 프로세스를 선택하는 것" 이다. (응답시간 ↓, 처리량 ↑, 효율성 ↑) 대기 큐의 구조를 최적화하는 문제도 스케줄링의 성능에 중요한 요소일 것이다. Types of Scheduling  Long - Term Scheduling- Batch System- 프로세스를 시스템으로 진입시킬지 말지를 결정한다.- 멀티프로그래밍의 정도를 제어하는 역할- 프로세스가 많아질수록, 자기 순서에 할당받게 될 실행시간은 짧아진다.- 시분할 시스템에서 대화형 프로그램의 경우에는 실질적인 프로세스 생성 요청이 장기 스케줄러로 들어온다. 프로세스는 언제 생성되는가?- 각 프로세스들이 종료될 ..

트라이는 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조이다. 트라이의 핵심이론트라이는 일반적으로 단어들을 사전의 형태로 생성한 후 트리의 부모 자식 노드 관계를 이용해 검색을 수행한다.N진 트리 : 문자 종류의 개수에 따라 N이 결정된다. 예를 들어 알파벳은 26개의 문자이므로 26진 트리로 구성된다.루트 노드는 항상 빈 문자열을 뜻하는 공백 상태를 유지한다. https://www.acmicpc.net/problem/14425  코드1import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { public st..

Principles of Deadlock교착상태(deadlock)이란 프로세스들의 집합이 더 이상 진행을 못하고 영구적으로 블록되어 있는 상태로 정의된다.    Reusable Resources(재사용 가능한 자원) - 프로세스의 사용에 의해 없어지지 않는 자원 - 프로세스가 사용한 후 다른 프로세스가 다시 사용할 수 있도록 반납하게 된다. - 처리기, 입출력 채널, 주/보조 메모리, 장치, 파일이나 데이터베이스나 세마포어와 같은 자료 구조들이 재사용 가능한 자원의 대표적인 예이다. - Deadlock(교착 상태)은 자원을 가지고 있는 한 프로세스가 다른 자원을 요청할 때 발생한다.   예시1 만약 수행 순서가 위와 같이 p0 -> p1 -> q0 -> q1 -> p2 -> q2 순서로 되면 교착 상태가..

Node 와 Link 데이터 링크 계층에서 통신은 Node-to-Node라고 표현한다. 둘중에 하나는 분명 데이터를 보내는 쪽을 가리킬거고, 다른 node는 데이터를 받는 쪽을 가리킬것이다. 그리고 데이터는 node들을 연결해주는 link를 통해 전송된다.  Two Categories of Links데이터 링크 계층은 통신 전달되는 수단(케이블, 공기등의 매체)이 사용되는 방식을 제어한다. 무슨 뜻이냐면, 데이터 링크 계층은 medium이 가진 모든 용량(대역폭)을 다 사용할수도 있꼬, 일부만 사용할 수도 있다는 말이다. 이런 매체를 어떻게 제어하는가에 따라 point-to-point link(1대 1로 연결, 매체의 일부 용량 사용) 나 broadcast link(1 대 전체, 매체의 전체 용량 사용)..

Cyclic codes codeword가 회전하는 형태이다. 예를 들어, 1011000이라는 codeword가 있다면, left-shift 하여 0110001로 만드는 것이다. 최상위 비트가 다시 다시 최하위 비트로 들어간 것을 확인할 수 있다. Cyclic code는 CRC (Cyclic Redundancy Check)라고도 불린다.  위의 표는 4개의 비트를 가진 dataword에 대한 7개의 비트를 가지는 codeword이다. 이 비트를 계산하는 방법에 대해 알아보자. Codeword의 길이는 7이기 때문에 3개의 비트를 추가해야하며,그림에서 추가된 3개의비트는 다음과 같은 과정에 의해 만들어진다. 1. 먼저 어떤 값(Divisor)으로 나눌것인지를 정한다.Divisor의 길이는 만들고자 하는 co..

트리(Tree)노드와 에지로 연결된 그래프의 특수한 형태 순환 구조를 지니고 있지 않고, 1개의 루트 노드가 존재한다.루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다.트리의 부분 트리 역시 트리의 모든 특징을 따른다. 예제1https://www.acmicpc.net/problem/11725import java.util.*;import java.io.*;public class Main { static int N; static boolean[] visited; static ArrayList tree[]; static int answer[]; public static void main(String[] args) { Scanner sc = new Scanner(S..

/** * 편리한 축약 애노테이션 * @GetMapping * @PostMapping * @PutMapping * @DeleteMapping * @PatchMapping */ /** * method 특정 HTTP 메서드 요청만 허용 * GET, HEAD, POST, PUT, PATCH, DELETE */package hello.springmvc.basic.requestmapping;import org.slf4j.Logger;import org.slf4j.LoggerFactory;import org.springframework.web.bind.annotation.*;@RestControllerpublic class MappingController { private Logger log = Logge..

Semaphore - 시그널을 위해 세마포어라고 불리는 특수 변수들을 사용한다.- 시그널이 전달될 때까지 프로세스는 suspend가 된다.  Semaphore는 integer 변수 s로 나타내며 가능한 연산은 다음과 같다. - Initialization : 음수가 아닌 값으로 초기화 - Wait : 세마포어 값을 감소, 만일 값이 음수가 되면 semWait을 호출한 프로세스는 블록, 음수가 아니라면 프로세스는 계속 수행 - Signal : 세마포어 값을 증가, 값이 양수가 아니면(0이거나 음수면), semWait 연산에 의해 블록된 프로세스들을 깨운다.        예시1프로세스 A,B,C를 세마포어를 사용해 구현한 것이다.  1. 세마포어가 1이기 때문에 A에서 Semwait()을 호출하면 lock 값..

Mutual Exclusion: Hardware Support Interrupt Disabling (인터럽트 금지) 단일처리기에서 병행 처리되는 프로세스들은 오버래핑되는 것이 아닌 인터리빙된다.즉, 실제로 동시에 수행되는 것이 아니라 프로세서를 번갈아 가며 실행한다. 또한 프로세스는 운영체제 서비스를 호출하거나 인터럽트될 때까지 계속 실행하게 된다. 인터럽트가 발생하지 않으면 그 동안은 한 프로세스의 계속적인 실행을 보장할 수 있다. 임계 영역에서는 인터럽트가 발생할 수 없기 때문에 상호 배제가 보장된다. - 수행 효율이 감소된다.- 멀티프로세서 시스템에서는 상호 배제를 보장할 수 없다.     Special Machine Instructions (특별한 기계 명령어)이 명령어가 수행되는 동안에는 같은 ..