시냅스

스레드 스케줄링 Thread Scheduling 스케줄 되는 대상은 프로세스가 아니라 커널 수준 스레드이다. 유저 스레드는 라이브러리에 의해 관리되고 커널은 유저 스레드의 존재를 알지 못한다. 경쟁 범위 Contention Scope 유저 스레드는 LWP 상에서 스케줄하기 때문에 동일한 프로세스에 속한 스레드들 사이에서 CPU 경쟁을 프로세스 경쟁 범위 (PCS)로 알려져 있다. LWP상에서 스케줄 한다고 해도 실행 중이라는 것을 의미하지 않는다. 실제 실행을 위해서는 LWP의 커널 스레드를 물리적인 CPU 코어로 스케줄 하는 것을 필요로 하기 때문 CPU 상에 어느 커널 스레드를 CPU 코어로 스케줄할 지 결정하기 위해서 시스템 경쟁 범위 (SCS)를 사용한다. 주석 : LWP가 경쟁하면 -> PSC,..

스케줄링 알고리즘 (Scheduling algorithm) 준비 큐에 있는 어느 프로세스에 CPU 코어를 할당할 것인지를 결정 CPU Scheduling 문제점의 Solution FCFS : First come, Fist Seerved SJF : Shortest Job First (SRTF : Shortest Remaning Time First) RR : Round Robin, Time Sharing Priority Based MLQ : Multi Level Queue MLFQ : Multi Level Feedback Queue FCFS 가장 간단, 먼저 요청 -> 먼저 할당 CPU burst time 에 따라서 Waiting time이 달라짐 Nonpreemptive Convoy Effect : 하나의..

CPU 스케줄링 CPU Scheduling 멀티프로그래밍의 목적 CPU 이용률 최대화 단일 코어라면, 빨간 박스의 상태에서 CPU는 I/O 요청이 완료될 때까지 유휴상태를 갖는다. -> 비효율적! 대기 시간 최소화 CPU - I/O 버스트 사이클 CPU Scheduler CPU가 유휴 상태가 될 때마다 Ready queue에 있는 프로세스를 하나 선택한다. 선택 절차는 CPU Scheduler에 의해 선택된다. Queue에 있는 레코드들은 일반적으로 PCB이다. 선택 방법 FIFO Queue Linked list, Binary list Priority Queue Preemptive(선점형) vs Nonpreemptive(비선점형) preemptive 조건에 의해서 스케쥴러가 context switch를 ..

이중 연결 리스트 (Doubly Linked list) 이중 연결 리스트의 구조는 단일 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다. 탐색에서는 단일 연결 리스트보다 시간적 우위를 지닌다. 기준에 따라 Head에서 출발하거나, Tail에서 출발하는 것이 가능하다. 단, 각 노드의 관리에 유의해야 하기 때문에, 작업량이 많아지고 자료구조의 크기와 사용 메모리가 증가한다. 특징 탐색에 용이하다. 자료구조의 크기가 증가한다. 메모리 사용량이 증가한다. 단일 연결 리스트보다 관리에 유의해야 한다. 이 외에는 단일 연결 리스트와 비슷한다. 단일 연결 리스트 구현 리스트 생성 원소 추가 원소 반환 원소 제거 리스트 제거 리스트 생성 typedef stru..

원형 연결 리스트 원형 연결 리스트는 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다. 단일 연결 리스트와 동일한 특징을 갖지만, 가장 첫 노드와 끝 노드가 연결된다는 특징을 갖는다. 원형 연결 리스트는 Cpu scheduling 에서 Ready queue나 스트림 버퍼를 구현하는 데에 많이 사용된다. 단, header는 tail과 동일하여 list의 0번째 node는 header의 다음 node가 된다. 특징 노드를 탐색하면서 순회에 용이하다. 반복적인 순회에서 끝을 확인해야할 필요가 없음. header 다음 node가 0번째 node가 된다. 이외에는 단일 연결리스트와 동일하다. 단일 연결 리스트 구현 리스트 생성 원소 추가 원소 반환 원소 제거 리스트 제거 리스트 ..

단일 연결 리스트 (Singly Linked List) 단일 연결 리스트는 각 노드들이 한 줄로 연결되어 있는 자료구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다. 연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다. (다만, 오늘 구현할 것은 tail을 갖지 않는 linked list로 1번의 반복문을 거치게 된다.) 다만, 기존 링크를 해제하거나 삽입할 때에는 기존 링크의 전이나 다음 노드 관리에 대해 유의해야 한다. 또한 배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 갖고 있다. 특히 단일 연결 리스트는..

배열 리스트 (Array List) 배열리스트는 자료를 순서대로 저장하는 자료구조로, 논리적 순서(저장)와 물리적 순서(저장)가 동일하다. 원소의 위치 인덱스는 0부터 시작하고, 정적배열로 최대 갯수가 정해져 있고,이는 배열과 동일하다. C에서는 라이브러리로 배열리스트를 지원하지 않기 때문에, 개발자가 직접 구현해야하는 기능으로는, 리스트 생성 원소 추가 원소 추가 가능 여부 판단 원소 반환 원소 제거 리스트 초기화 리스트 삭제 를 꼽을 수 있다. 특징 저장순서가 순차적이기 때문에 Index가 곧 위치로, 탐색(O(1))에 용이하지만, 배열이 공백을 허용하지 않아 삽입이나 삭제 시에는 노드가 끊기지 않아야 하기 때문에, 삽입이 됐을 떄에는 기존 노드를 뒤로 미루거나, 삭제가 됐을 때에는 원래 노드들을 앞..

멀티 쓰레딩 cpu를 넘나들 수 없음, 커널 support 없음 user thread : e.g. Java Kerner thread 코어에서 직접 쓰레딩을 할 수 있게 관리 한다. 운영체제가 직접 manage 다중 쓰레드 Multithreading models many to one : 가장 기본, 여러 유저 쓰레드 대 하나의 커널 쓰레드 one to one many to many 스레드 라이브러리 Threads Library 스레드 create manage하는 API 제공 POSIX Pthreads Windows thread Java thread : 운영체제에 따라 POSIX Pthread or Windows thread, 운영체제에 종속적이다. 암묵적 스레딩 implitcit threading 병행, ..

파일 디스크립터 (File Descriptor) Unix OS에서 모든 것은 파일로 관리되는데 이러한 파일에 접근할 때 파일 디스크립터 라는 개념을 이용한다. 파일은 일반적인 정규 파일, 디렉토리, 소켓, 파이프, 블록 디바이스, 캐릭터 등등 모든 객체들을 파일이라 칭한다. 0을 포함한 양수인 정수만을 값으로 하고, 0 : 표준 입력 (Standard Input, STDIN_FILENO) 1 : 표준 출력 (Standard Output, STDOUT_FILENO) 2 : 표준 에러 (Standard Error, STDERR_FILENO) 를 기본적으로 할당 받는다. FD는 숫자로, FD 테이블의 인덱스를 의미하기 때문에 FD가 3으로 반환됐을 경우, File Descriptors table에 3번 항목이..

구조체 구조체는 여러 정보들을 한 데 묶어주는 역할을 한다. 기본적인 use case 는 아래와 같다. struct Person { // 구조체 char name[10]; // 구조체 멤버 int age; char address[100]; } /* struct Person { // 구조체 char name[10]; // 구조체 멤버 int age; char address[100]; } p1; 위와 같이 p1을 붙여 줄 경우 바로 p1이라는 변수를 선언한 것 */ struct Person p1; // 구조체 변수 선언 strcpy(p1.name, "김명수"); // 구조체 멤버에 값 할당 p1.age = 1; strcpy(p1.address, "서울특별시 강남구") typedef를 통해 struct 키워드..