IT LAB

조성호 님의 "쉽게 배우는 운영체제" 책을 정리한 포스팅 입니다 1. 이벤트 드리븐시스템이나 애플리케이션에서 발생하는 이벤트를 중심으로 동작하는 방식이벤트 발생 시, 콜백 함수가 호출되어 이벤트가 처리됨비동기적 방식으로 동작여러 이벤트가 동시에 발생해도, 각 이벤트를 각각의 스레드에서 처리함다른 이벤트에 영향을 미치지 않음입출력 장치는 자신의 작업이 완료되면, 인터럽트 신호를 발생시켜 CPU에 작업을 요청함 2. 종류동기적 인터럽트 (사용자 인터럽트)실행중인 명령어로 인해 발생 종류프로그램상의 문제 때문에 발생 (Divide By Zero)프로세스를 의도적으로 중단하기 위해 발생주변장치의 조작에 의해 발생 비동기적 인터럽트하드웨어적인 오류로 인해 발생하는 인터럽트입출력 장치에 의해 트리거됨 3. 인터럽트..

조성호 님의 "쉽게 배우는 운영체제" 책을 정리한 포스팅 입니다 1. 스케줄링 단계고수준 스케줄링시스템 내의 전체 작업 수 조절동시에 실행 가능한 프로세스의 총 개수를 제한어떤 프로세스를 실행 대기열에 추가할지 결정 중간 수준 스케줄링시스템의 활성 프로세스 수를 조절함스왑, 프로세스 상태 전환 의 방법 사용메모리 자원 관리 및 시스템 부하 조절 저수준 스케줄링준비 상태에 있는 프로세스 중에서 어떤 것을 실행할지 결정스케줄링 알고리즘 사용CPU 자원 할당 최적화프로세스 상태 관리프로세스의 상태 간의 전환을 관리 2. 스케줄링 종류선점형 스케줄링OS가 실행중인 프로세스의 CPU를 강제로 빼앗을 수 있는 방식대부분의 저수준 스케줄러가 채택함 인터럽트CPU가 OS로부터 인터럽트를 받으면, 현재 실행 중인 작업을..

조성호 님의 "쉽게 배우는 운영체제" 책을 정리한 포스팅 입니다 1. 스레드프로세스 내에서 실행되는 작업 단위같은 프로세스 내에서 메모리와 자원을 공유 (Light Weight Process)서로 간에 직접적으로 데이터를 주고받을 수 있음데이터를 공유하므로 메모리를 효율적으로 사용할 수 있음 2. 멀티 태스킹CPU 할당 시간을 slicing하여 배분하는 기법 (시분할 시스템)운영체제가 여러 작업을 동시에 처리하는 것처럼 보이게 하는 기법 3. 멀티 스레딩단일 프로세스 내에서 여러 개의 스레드를 생성하여 병렬 처리하는 방식 모델커널 스레드커널이 멀티스레드를 지원하는 방식한 스레드가 블록되어도 다른 스레드는 계속 실행 가능 사용자 스레드사용자 공간에서 구현된 스레드운영체제가 멀티스레드를 지원하지 않을 때 사..

조성호 님의 "쉽게 배우는 운영체제" 책을 정리한 포스팅 입니다 1. 개요프로그램 vs 프로세스프로그램어떤 데이터를 사용하여 어떤 작업을 할지 절차를 적어놓은 것저장장치에 저장되어 있는 정적인 상태 프로세스작업이 진행되고 있는 프로그램메모리에 올라온 동적인 상태 프로세스로의 전환프로그램을 메모리에 로드PCB 생성프로세스를 관리하기 위한 핵심 데이터 구조PID, Process state, Process Number, Program Counter, Register, Memory limitsFDT (오픈된 파일을 식별하기 위한 File Descriptor 정보 테이블)커널은 시스템 전체에서 오픈된 파일을 System open-file table로 관리함커널은 Active vnode table로 파일 시스템의 ..

1. Prefix Sum0~i까지 구간의 합 2. Suffix Sumn~i까지 구간의 합 3. Target SubtotalKadane's Algorithm최대 부분 배열 합을 효율적으로 찾기 위한 알고리즘 동적 프로그래밍i번째 까지 원소의 최대 배열 부분 합을 관리dp[i-1] + 현재 방문한 원소 or 현재 방문한 원소 대소 비교를 통해 dp[i]를 갱신해감 시간복잡도O(n)최대값을 선형으로 찾을 수 있음  출처Wiki - Prefix SumWiki - Maximum subarray problem

1. Edit Distance두 문자열 간의 최소 편집 거리를 계산하는 문제입니다.한 문자열을 다른 문자열로 변환하기 위해 필요한 최소 편집 연산의 수를 의미합니다. 연산삽입: 문자 삽입삭제: 문자 삭제교체: 한 문자를 다른 문자로 교체DP 테이블 정의dp[i][j]i~j까지 최소 편집 연산 수 점화식A[i-1]  == B[j-1]dp[i][j] = dp[i-1][j-1]문자가 같으므로 편집 필요 없음 A[i-1]  != B[j-1]삽입, 삭제, 교체 중, 최소값을 선택삽입A에 문자를 삽입하여 B와 같아지게 함 dp[i][j-1] + 1삭제A에 문자를 삭제하여 B와 같아지게 함 dp[i-1][j] + 1교체A의 문자를 다른 문자로 교체하여 B와 같아지게 함dp[i-1][j-1] + 1  출처Wiki -..

1. Longest Palindrome Substring (LPS)주어진 문자열의 부분문자열에서 가장 큰 팰린드롬 문자열의 길이 구하기 Dynamic Programming시간 복잡도: O(n^2)공간 복잡도: O(n^2)더보기public static void main(String... args) throws IOException { br = new BufferedReader(new InputStreamReader(System.in)); bw = new BufferedWriter(new OutputStreamWriter(System.out)); input = br.readLine().toCharArray(); size = input.length; isPalindrome = new..

3. 모듈러컴퓨팅에서 한 숫자를 다른 숫자로 나눈 후, 나머지를 반환한 값 a mod n(유클리드 나눗셈의) 나머지a: 피제수n: 제수a mod b = a - b * (a/b) 성질덧셈 법칙뺄셈 법칙곱셈 법칙분배 법칙 응용큰 수 연산암호학해시 함수: 데이터를 고정된 크기의 값으로 매핑할 떄 사용됨주기성 확인: 반복되는 패턴을 찾는 데 사용됨 고급페르마의 소정리소수로 모듈러 연산하였을 때 결과를 구하는 공식소수 p와 p에 나누어 떨어지지 않는 정수 a가 있을 때a^(p) = a (mod p)a^(p-1) = 1  (mod p)a^(p-2) = 1/a  (mod p)a^(p-2)는 a의 모듈러 역원a * a^(p-2) = 1 (mod p) 이므로 a^-1 (mod p) = a^(p-2) (mod p) 확장 ..

약수어떤 수를 나누어 떨어지게 하는 수 입니다.약수끼리 곱이 N이 되게끔 짝을 지을 수 있습니다. 최대공약수 (GCD)두 개 이상의 정수의 공통된 약수 중에서 가장 큰 수를 뜻합니다. 구현유클리드 알고리즘 (구현)두 수의 최대공약수는 작은수와 두 수를 나눈 나머지의 최대공약수와 같음더보기더보기더보기int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b);} 재귀적 구현이 가능합니다.가장 효율적입니다. 고급베주 항등식ax + by = gcd(a, b)위 식을 만족하는 x, y쌍이 항상 존재 (1개 이상)

1. Floyd-Warshall모든 정점 쌍 간의 최단 경로를 찾는 알고리즘 입니다. 가중치가 양수 혹은 음수인 그래프에서 사용됩니다. (단, 음의 사이클에는 사용 불가) Dynamic Programming인접행렬을 사용하여 각 정점 쌍 간의 최단 거리를 반복적으로 갱신합니다. 2. 동작 원리모든 정점을 경유지로 설정하고, 최단 경로가 경유지를 거쳐 더 짧아질 수 있는지 확인하며 최단 경로 갱신 초기화모든 정점 쌍에 대해, 직접 연결된 경로의 거리 초기화자기 자신으로 가는 경로 = 0연결되지 않은 경로 = infinit 경유지 검사i->j 로 가는 최단 경로가 i -> k -> j로 가는 경로를 통해 더 짧아질 수 있는지 검사 (정점 k를 경유지로 설정)모든 정점에 대하여 반복 3. 구현int[][] d..