전체 글
CPU 스케쥴링 알고리즘(2) - SJF, Priority, Round-Robin
1. SJF(Shortest-Job-First) SJF란 CPU 시간이 적게 드는 순으로 처리하는 스케쥴링 방식이다. 1) 특징 Probably optimal : AWT를 최소화하는데 가장 적합한 방법이다. Not realistic, prediction may be needed : 실제로 프로세스가 얼마나 CPU 시간을 사용할 지 모르기 때문에 비현실적인 방법이다. 그래서 CPU 시간이 얼마나 들지 예상해서 순서를 정해야 한다. Preemptive or Non-preeptive : 선점으로도, 비선점으로 구현할 수 있다. cf. Shortest-Remaining-Time-First(최소잔여시간우선) : Preeptive SJF 의 방법 중 하나이다. 2) Example 다음 프로세스를 SJF의 선점방식,..
CPU 스케쥴링 알고리즘(1) - FCFS
1. CPU Scheduing CPU 스케쥴링이란 메인 메모리에 올라와 있는 프로세스들이 CPU의 자원을 할당받기 위해 Ready Queue에 줄서있는 것을 말한다. 1) Preemptive vs Non-preemptive (선점 : 비선점) 실행 중인 프로세스를 도중에 끄고 스케쥴링하는 방법을 Preemptive라 한다. Non-preemptive 이면 하나의 프로세스가 모두 끝날때까지 다른 프로세스들은 계속 기다려야만 한다. 2) Scheduling criteria 어떤 스케쥴링 방식이 더 좋은가 판단하는 척도에는 다섯 가지가 있다. CPU Utilization(CPU 이용률) : CPU가 얼마나 놀지 않고 일하는가 Throughput(처리율) : 단위 시간당 몇개의 작업을 처리하는가 Turnarou..
프로세스 관리 (Process Management)
CPU 자원을 어떻게 효과적으로 나눠주는가 1. 프로세스 1) 프로세스의 정의 프로그램 vs 프로세스(program vs process) 프로세스(process)는 task, job으로도 불린다. 실행 중인 프로그램을 프로세스라고 한다.(program in execution : text+data+stack,pc,sp,registors...) => 무덤 속 프로그램, 살아 움직이는 프로세스 2) 프로세스 상태 프로세스 상태에는 new, ready, running, wating, terminated가 있다. New : 하드디스크에서 메인메모리로 프로그램이 올라온 상태 Ready : 프로세스가 초기화를 마치고 실행 준비 중인 상태 Running : 프로세스가 실행 중인 상태 Waiting : 프로세스가 I/O..
M:N 관계
M:N 관계 M:N 관계는 관계를 가진 양쪽 당사자 모두에서 1:M관계가 존재할 때 나타나는 모습이다. 학생과 과목의 관계를 예로 들 수 있다. 학생 입장에서는 여러 과목을 수강할 수 있고, 과목 입장에서 보면 여러 학생이 하나의 과목을 선택할 수 있다. 즉, 어느 쪽에서 봐도 다:다 관계가 성립된다. 이 관계는 선천적으로는 테이블과 테이블 사이에 특별한 관계가 없다. 각 테이블은 스스로 존재할 뿐이다. 그런데 이들 사이에 어떤 관계를 맺어 줌으로써 관계가 형성된다. 1. M:N 관계의 문제점 M:N 관계를 그림으로 그려보면 다음과 같다. 위 그림을 보면 각 테이블마다 PK가 존재하는 걸 볼 수 있다. 그러나 테이블 간의 관계가 성립되려면 PK 이외에도 FK가 존재해야 한다. FK를 생성한 테이블은 다음..
1:M 재귀적 관계
트리구조처럼 무한히 확장해나가는 모델을 데이터베이스로 어떻게 표현할까? 1:M 재귀적 관계 분류체계 또는 Directory 구조와 같이 1:M 관계가 끊임없이 나아가는 모델이 있다. 이럴 경우에 자식 테이블을 무한히 만들어주어야만 할까? 테이블 안에 PK와 FK를 같이 만들어 줌으로써 해결할 수 있다. 회사와 부서 관계를 예시로 들어보자. 회사에는 여러 부서가 있고, 부서 속에 또 여러 부서가 존재할 수 있다. (EX. 삼성전자 > 총무부 > 총무1팀 > 총무1과...) 이 경우 '상위부서ID'란 Column을 만든 뒤 PK인 부서 ID를 참조함으로써 무한히 확장해나가는 1:M 관계를 표현할 수 있다. 결국 하나의 테이블 안에 모든 부서 간의 1:M 관계를 표현할 수 있게 된다. 이렇게 설계된 테이블을 ..
1:M 관계
1:M 관계 1:M 관계는 한쪽이 관계를 맺은 쪽의 여러 객체를 갖는 것을 의미한다. 1:M 관계는 가장 흔하게 나타나는 매우 일반적인 형태이다. 대표적인 예로 부모와 자식 관계, 컴퓨터 Directory 구조가 있다. 테이블은 서로 선천적으로 관계를 갖고 있다.(RDBMS) 1:M 관계는 부모와 자식 관계와 같다. 부모는 자식이 없어도 되고, 자식이 1명 또는 여러명일 수도 있다. 그러나 자식은 부모가 단 한명이어야 하며, 부모없는 자식은 존재하지 않는다. 데이터베이스에서 1:M 관계를 설정하면 부모없는 자식이 생기는 것을 막아준다. 학년 테이블과 반 테이블을 예로 들어볼 수 있다. 여기서 학년 테이블이 부모, 반 테이블이 자식이 된다. 학년테이블의 PK인 학년번호가 반 테이블의 FK인 학년번호와 연결..
주 식별자 (Primary Key) 설계
Primary Key 설계 고려사항 목록 1. 유일하고 모든 레코드에 NOT NULL 일 수 있는 컬럼을 찾는다. 2. 후보 식별자가 없는 경우 임의의 식별자를 만들어 부여한다. (인조 식별자) 3. PK의 데이터 타입을 결정한다. 1) 레코드의 발생 가능한 최대 수를 예측한다. 예) 1년에 몇개 정도 발생하는가? 한 달에 몇개 정도 발생하는가? 처리해야 하는 대상이 대략 몇개정도 되는가? 4. 발생 가능한 최대 레코드 수를 커버할 수 있는 데이터 타입을 선정한다. 1) 만일 대상 레코드가 수십 만개 정도라면 999,999로 커버할 수 있다. 따라서 32bit int(2,147,483,647)를 사용할 수 있다. varchar(6)을 사용해서 '999999' 까지 처리할 수 있다. 5. PK의 데이터 타..
[SWEA] 1249. 보급로 자바(Java) 풀이
1. 문제 접근방법 dfs, bfs로 풀 수 있는 문제입니다. 그러나 완전탐색으로 모든 지점을 방문하면 시간초과가 발생합니다. 그렇기에 조건에 부합하지 않는 경우의 수를 가지치기 해야만 합니다. 2. 문제풀이 1. 각 좌표의 깊이를 2차원 배열인 supply에 담는다. 2. 2차원 배열인 map을 만든 뒤, -1로 초기화한다. 3. supply 배열을 (0, 0) 에서 시작하여 bfs를 한다. 대신 조건에 맞는 경우에만 큐에 담는다. 3-1) 다음 가려고 하는 지점이 한번도 방문하지 않았을 경우 큐에 담는다. (if (map[nx][ny] == -1)) 3-2) 다음 가려고 하는 지점이 이미 방문했으나 그동안 지나온 깊이의 합보다 클 경우 방문한다. else if (map[nx][ny] > cur.sum..