복습노트 복습노트

Basic Concepts CPU의 효율을 높이기 위해 우리는 multiprogramming을 사용합니다. 그러나 CPU가 1개이면 오직 1개의 process만 작동할 수 있습니다. 이는 CPU scheduling이 필요합니다. process는 CPU burst와 I/O burst를 왔다갔다 하면서 프로그램을 실행합니다. CPU burst는 cpu 명령을 실행하는 것이고 I/O burst는 i/o를 요청한 다음 기다리는 시간입니다. process는 CPU bound process와 I/O bound process 로 나눌 수 있습니다. CPU burst가 큰 process가 CPU bound process I/O burst가 큰 process를 I/O bound process 라고 합니다. 우리가 대부분..

Asymtotic Notation(점근적 표기법) 세타 표기법 평균 ex:7n^3 n^3 오메가 표기법 최소 시간 (가장 최선의 시간) ex: 7n ^ 3 n ^3, n ^2, n^1 모두 true 빅오 표기법 최대 시간 (가장 최악의 시간) ex:7n^3 n^3, n^4, n^5 모두 true

Insertion sort INSERTION-Sort(A, n) for i = 2 to n key = A[i] //Insert A[i] into the sorted subarray A[1 : i-1]. j = i - 1 while j>0 and A[j] > key A[j+1] = A[j] j = j-1 A[j+1] = key A[1 : i-1] 까지는 loop invariant(루프 불변성) 이 성립됩니다. 적은 수의 원소를 정렬할 때는 효율적임 Merge Sort Merge(A, p, q, r) n_l = q - p + 1 //중간점 p를 중심으로 왼쪽 n_r = r - q // 중간점 p + 1부터 q까지 오른쪽 새 배열 L[0..n_l - 1] and R[0 : n_r-1] for i = 0 to ..

Analog and Digital Data 정보를 전송하기 위해서 전자기 신호 형태의 에너지로 변환도어야 함 즉, 정보를 신호로 변환 데이터는 아날로그 또는 디지털일 수 있음 아날로그는 연속적인 정보(목소리) 디지털은 이산값을 갖는 정보(0과 1의 형태로 컴퓨터의 memory에 저장되는 데이터) Periodic and Nonperiodic 주기신호 주기라는 연속적으로 반복된 패턴으로 구성 사이클(cycle)은 하나의 완성된 패턴을 의미 신호의 주기(T)는 초 단위로 표현 비주기 신호 시간에 따라 반복된 패턴이나 사이클이 없이 항상 변함 신호는 반복된 패턴이 없음 Periodic Analog Signal simple과 composite로 구분 simple periodic analog signal은 sine..

Protocol Layering protocol 이란 송신자, 수신자, 모든 중간 장치들이 효과적인 통신을 위해 지켜야 할 규칙입니다. protocol 은 매우 복잡해 여러 계층을 나누어 서로 다른 계층간에 임무를 나눌 수 있습니다. Principle of Protocol Layering 첫번째 원칙(Bidirectional communication) : 양방향 통신을 원한다면 각 계층은 한 가지씩 상반되는 두 가지 작업을 수행할 수 있어야 합니다. (듣기/말하기, 암/복호화, 편지 주고/받기) 두번째 원칙(Logical communication) : 각 계층의 객체는 동일해야 합니다. Logical Connections 각 계층 간 논리적인 연결은 계층 대 계층 통신을 갖는다는 의미입니다. logica..

data communication은 두개의 장치간의 media를 통한 data 교환입니다. 데이터 전송방식은 simplex : 한쪽 방향 (라디오, 티비) half duplex : 두 개의 장치간의 한번에 하나씩 전속 (동시에 전송 불가) (무전기) full duplex : 두개의 장치 동시에 전송 가능 (핸드폰) 네트워크 란 장치 간의 상호연결을 의미합니다. 장치는 host(컴퓨터, 데스크 탑, 핸드폰)가 될 수 도 있고 connecting device가 될 수 있습니다. (라우터, 스위치, 모뎀(데이터의 형태를 바꿔줌) 네트워크 기준 성능, 의존성, 보안 네트워크 형태 크기, geographical coverage(커버할 수 있는 범위), ownership 에 따라 구분 LAN 가정 집, 아파트에 주..

여러 process들은 동시에 실행될 경우 서로의 공유 데이터에 접근할 수 있으므로, 동기화가 꼭 필요합니다. Possibility of Interleaving process 끼리 동기화를 제대로 안해주면 interleaving 현상이 발생합니다. 예를 들어 counter 변수를 늘리는 producer와 줄이는 consumer process가 있다고 가정하면 counter ++ 와 counter -- 는 위에 보듯이 다음과 같은 기계어로 실행됩니다. 이를 동시에 실행하면 interleaving 이 발생할 수 있습니다. interleaving 현상은 producer와 consumer가 누가 먼저 실행되는가에 달렸습니다. 예를 들어 counter = 5라고 가정 먼저 producer에서 counter을 +1..

What is Thread ? thread는 process의 작업 흐름을 말합니다. 하나의 process가 하나의 작업만 하는 것을 single thread 라고 하며, 하나의 process가 동시에 여러 작업을 수행하는 것은 multi thread라고 합니다. 각 개인의 thread는 최소 자신만의 register를 갖고, stack을 소유할 수 있습니다. multi thread는 한 process의 code, address space 그리고 여러 resource들을 공유합니다. 그냥 단순히 process를 여러개 돌리면 되는데 우리는 보통 multi thread 방식을 선호합니다. process 끼리 통신하는 IPC 방식은 많은 overhead와 성능을 저하 시킵니다. 비록 thread 전환에도 co..