gnuykob_sw

[출처: 실무로 배우는 빅데이터 기술, 김강원 저]

1. 요구사항 파악

1) 차량의 다양한 장치로부터 발생하는 로그 파일을 수집해서 기능별 상태를 점검한다.

2) 운전자의 운행 정보가 담긴 로그를 실시간으로 수집해서 주행 패턴을 분석한다.

2. 데이터셋 살펴보기

1) 스마트카 상태 정보 데이터

- 스마트카의 각종 센서로부터 발생하는 차량의 상태 정보 데이터셋

- 요구사항 1과 관련, 로그 시뮬레이터를 통해 생성됨

2) 스마트카 운전자 운행 데이터

- 스마트카 운전자의 운전 패턴/ 운행 정보가 담긴 데이터셋

- 요구사항 2와 관련, 로그 시뮬레이터를 통해 생성됨

3) 스마트카 마스터 데이터

- 스마트카 운전자의 프로파일 정보가 담긴 데이터셋

- 요구사항 1, 2와 관련된 분석 데이터셋을 만들 때 활용, 이미 만들어진 샘플 파일 이용

4) 스마트카 물품 구매 이력 데이터

- 스마트카 운전자가 차량 내의 스마트 스크린을 통해 쇼핑몰에서 구입한 차량 물품 구매 목록 데이터셋

- 요구사항 1, 2와 관련된 분석 데이터셋을 만들 때 활용, 이미 만들어진 샘플 파일 이용

3. 파일럿 프로젝트 소프트웨어 아키텍처

- 하둡을 중심으로 앞쪽을 수집/적재 (전처리) 영역, 뒤쪽을 탐색/분석 (후처리) 영역

1) 수집 레이어

- Flume: 차량의 로그 수집

- Storm: 실시간 로그 이벤트 처리

- Kafka: 플럼과 스톰 사이에서 데이터의 안정적인 수집을 위해 버퍼링, 트랜잭션 처리

2) 적재 레이어

- Hadoop, HBase, Redis

- 대용량 로그파일: 플럼 -> 하둡

- 실시간 데이터: 플럼 -> 카프카 -> 스톰 -> HBase/Redis

- 스톰을 통해 실시간 이벤트 분석 -> 결과에 따라 HBase와 레디스로 나누어 적재

3) 처리/탐색 레이어

- 하이브: 하둡에 적재된 데이터 정제/변형/통합/분리/탐색 등의 작업 수행, 데이터를 정형화된 구조로 정규화해 데이터마트 생성

- 스쿱: 가공/분석된 데이터 외부로 제공 + 분석/응용 단계에서도 사용

- 우지: 길고 복잡한 처리/탐색 프로세스를 우지의 워크플로로 구성해 복잡도 낮추고 자동화

4) 분석/응용 레이어

- 임팔라, 제플린: 스마트카 상태 점검과 운전자 운행 패턴 빠르게 분석

- 머하웃, 스파크ML: 스마트카 데이터 분석을 위한 군집, 분류/예측, 추천 등

- R: 통계 분석

- 텐서플로: 딥러닝 모델 생성

- 플라스크: 서비스 API 제공

4. 하드웨어 아키텍처

5. Cloudera Manager (CM)

- 빅데이터 자동화 관리 툴

- 하둡을 포함한 에코시스템 17개 편리하게 설치 및 관리

C언어와 비슷한 문법!

1. if-else문

public class Nested {
	public static void main(String[] args) {
    
    	Scanner sc = new Scanner(System.in);
        System.out.print("정수 입력: ");
        int num = sc.nextInt();
        
        if (num > 0)
        	System.out.println("양수");
        else if (num == 0) 
        	System.out.println("0");
        else
        	System.out.println("음수");
            
    }
}

2. switch문

- 제어식에 숫자, 문자, 문자열 가능

import java.util.*;

public class Score2Grade {
	public static void main(String[] args) {
    	int score, num;
        char grade;
        
        Scanner sc = new Scanner(System.in);
        System.out.print("성적 입력: ");
        score = sc.nextInt();
        num = score / 10;
        
        switch(num) {
        case 10:
        case 9:		grade = 'A';    break;
        case 8:		grade = 'B';	break;
        case 7:		grade = 'C';	break;
        case 6:		grade = 'D';	break;
        default:	grade = 'F';	break;
        }
        System.out.println("학점: " + grade);
    }
}

switch(num) {
	case 10:
	case 9:    return 'a';
    
	case 10, 9 ->    return 'a';
}

// 둘 다 가능

3. for문

- for (초기식; 조건식; 증감식) {

   }

public class Sum {
	public static void main(String[] args) {
    	int sum = 0;
        
        for (int i = 1; i <= 10; i++) {
        	sum += i;
        }
        
        System.out.println("1부터 10까지의 정수의 합 = %d" + sum)l     
    } 
}

4. while문

- while (조건식) {

  }

import java.util.Scanner;

public class GetSum {
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        
        int sum = 0, value = 0;
        
        while (value != -1) {
            sum += value;
            System.out.print("정수 입력: ");
            value = sc.nextInt();
        }
        System.out.println("정수의 합은 " + sum + "입니다.");
    }
}

5. do-while문

- 조건이 참인 동안 do 안의 문장 반복

- 우선 do 문장 한 번 실행하고 조건 확인

import java.util.Scanner;

public class CheckInput {
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        int month;
        do {
            System.out.print("올바른 월을 입력하세요 [1-12]: ");
            month = sc.nextInt();
        } while (month < 1 || month > 12);
        System.out.println("사용자가 입력한 월은 " + month);
    }
}

6. break, continue

- break: 반복문을 벗어남

- continue: 해당 반복을 멈추고 다음 반복으로 넘어감

7. 무한루프

- while문에서 종료 조건을 만들기 까다로운 경우 while(true)를 이용한 후 그 안에서 break문으로 반복을 빠져나가는 것이 좋음

8. 배열 선언과 사용

- 자바에서 배열은 객체

// 배열 생성
int[] s = new int[10];

// 배열 채우기
for (int i = 0; i < s.length; i++) {
	s[i] = i;
}

// 배열 출력
for (int i = 0; i < s.length; i++) {
	System.out.print(s[i] + " ");
} 
// 0 1 2 3 4 5 6 7 8 9

- 배열의 크기: s.length

// 배열 초기화
int [] scores = {10, 20, 30, 40, 50};

9. for-each 루프

int[] list = {1, 2, 3, 4, 5};

for (int e : list) {
	System.out.println(e);
}
// 배열 전부 출력

10. 2차원 배열

// 2차원 배열 생성
int[][] s = new int[3][5];

// 2차원 배열 초기화
int[][] testArray = {
	{10, 20, 30, 1, 2},
	{40, 50, 60, 3, 4},
	{70, 80, 90, 5, 6}
};

// 2차원 배열 출력
for (int i = 0; i < 3; i++) {
	for (int j = 0; j < 5; j++) {
    	System.out.println(s[i][j]);
    }
}

11. 래그드 배열

int[][] ragged = new int[MAX_ROWS + 1][];

for (int r = 0; r <= MAX_ROWS; r++)
	ragged[r] = new int[r+1];

public class RaggedArray {
	public static void main(String[] args) {
    	int[][] ragged = new int[3][];
        ragged[0] = new int[1];
        ragged[1] = new int[2];
        ragged[2] = new int[3];
        
        for (int r = 0; r < ragged.length; r++) {
            for (int c = 0; c < ragged[r].length; c++)
            	ragged[r][c] = c;
        }
    }
}

12. ArrayList

- 배열의 크기 동적 변경하면서 사용 가능

ArrayList<String> list;    // list: 문자열을 저장하는 ArrayList 참조 변수 선언
list = new ArrayList<>();  // ArrayList 생성

list.add("Apple");
list.add("Grape");

import java.util.*;

public class ArrayListTest {
	public static void main(String[] args) {
    	ArrayList<String> list = new Arraylist<>();
        list.add("Anna");
        list.add("Mike");
        list.add("Joy");
        list.add("Lina");
        for (String obj : list)
        	System.out.print(obj + " ");
    }
}
// Anna Mike Joy Lina

1. 클래스

- 객체 지향 언어의 기본적인 빌딩 블록

public class Name {

}

- 자바 소스파일 (.java) 는 항상 public이 붙은 클래스의 이름과 동일해야 함

- 하나의 소스파일 안에 public 클래스가 2개 이상 있으면 오류 발생

2. 메소드

- 특정한 작업을 수행하는 코드의 묶음

public static void main (String[] args) {
	System.out.println("Hello World!");
}

3. 자료형

- 기초형

    - 정수형: byte(1), short(2), int(4), long(8)

    - 실수형: float(4), double(8)

    - 논리형: boolean

    - 문자형: char (2, 유니코드)

- 참조형: 클래스, 인터페이스, 배열

- 리터럴:

    - 소스코드에 직접 쓰여있는 값 (ex, x = 100;)

    - 정수형, 부동소수점형, 문자형 등의 여러 타입 있음

- 상수: 프로그램이 실행되는 동안 값이 변하지 않는 수

4. 형변환

- 산술 연산 전에 피연산자의 타입 통일해야 함

- 강제 형변환

int x = 3;
double y = (double) x;

5. 콘솔에서 입력받기 (Scanner)

- System.in 사용

import java.util.Scanner;
Scanner sc = new Scanner(System.in);

- 키보드로부터 바이트 값 받아서 분리자를 이용하여 토큰으로 분리

- default 분리자는 공백문자 (' ', '\n', '\t')

String name = sc.next();           // 한 단어 입력
int age = sc.nextInt();            // 문자열(토큰)을 정수로 변환하여 반환
double weight = sc.nextDouble();   // 문자열을 실수로 변환하여 반환
String line = sc.nextLine();       // 한 줄 입력

6. 조건 연산자

[초보자를 위한 SQL 200제]

1. 특정 열 선택하기

SELECT empno, ename, sal
  FROM emp;

- 모든 쿼리 끝에 세미콜론

2. 테이블에서 모든 열 출력하기

SELECT *
  FROM emp;

- *: 모든 열 선택
- 모든 열 출력하고 맨 끝에 다시 한 번 특정 컬럼 출력해야 하는 경우) SELECT table.*, column FROM table;
(ex) SELECT dept.*, deptno FROM dept;

3. 컬럼 별칭을 사용하여 출력되는 컬럼명 변경하기

SELECT empno as 사원 번호, ename as 사원 이름, sal as "Salary"
  FROM emp;

- 컬럼명 as 컬럼 별칭(alias)
- 컬럼 별칭에 " " 로 감싸줘야 하는 경우
- 대소문자 구분하여 출력할 때
- 공백문자 출력할 때
- 특수문자 출력할 때 ($, _, # 만 가능)

- 수식을 사용하여 결과 출력할 때 별칭 유용함 -> ORDER BY 절 사용할 때 유용

#(ex) 월급 = sal * (12 + 3000)

SELECT ename, sal * (12 + 3000) as 월급
  FROM emp;

4. 연결 연산자 사용하기 ( || )

SELECT ename || sal
  FROM emp;

- 컬럼과 컬럼 연결하여 출력
- (ex)

SELECT ename || '의 월급은 ' || sal || '입니다.' as 월급정보
  FROM emp;

5. 중복된 데이터 제거해서 출력하기 (DISTINCT)

SELECT DISTINCT job
  FROM emp;
  
SELECT UNIQUE job
  FROM emp;

- 컬럼에 있는 데이터들 중 중복된 것은 하나씩만 출력 (UNIQUE한 값만 출력)

6. 데이터 정렬해서 출력하기 (ORDER BY)

SELECT ename, sal
  FROM emp
  ORDER BY sal asc;

- asc: 오름차순, desc: 내림차순
- ORDER BY 절은 작성 시에도, 실행 시에도 맨 마지막에 실행됨
-> SELECT 절에 사용한 컬럼 별칭을 ORDER BY 절에 사용할 수 있음

SELECT ename, sal as 월급
  FROM emp
  ORDER BY 월급 asc;

- ORDER BY 절에 컬럼 여러개 작성 가능

SELECT ename, deptno, sal
  FROM emp
  ORDER BY deptno asc, sal desc;

-> 먼저 deptno를 오름차순 정렬한 것을 기준으로, 같은 deptno 내에서는 sal 내림차순 정렬
- 컬럼명 대신 숫자로도 작성 가능 -> SELECT 절 컬럼 순서

7. WHERE 절 배우기

(1) 숫자 데이터 검색

ex) 월급이 3000인 직원들의 이름, 월급, 직업 출력

SELECT ename, sal, job
  FROM emp
  WHERE sal = 3000;

- 원하는 검색 조건을 WHERE 절에 작성하여 데이터 검색
- WHERE 절은 FROM 절 다음에 작성
- 비교 연산자

- ORACLE은 FROM절 -> WHERE절 -> SELECT절 순서로 실행하기 때문에 WHERE 절에 컬럼 별칭 사용하면 에러남

(2) 문자와 날짜 검색

(ex) 이름이 SCOTT인 사원의 이름, 월급, 직업, 입사일, 부서번호

SELECT ename, sal, job, hiredate, deptno
  FROM emp
  WHERE ename = 'SCOTT';

(ex) 81년 11월 17일에 입사한 사원의 이름과 입사일

SELECT ename, hiredate
  FROM emp
  WHERE hiredate = '81/11/17';

- 현재 접속한 세션의 날짜 형식에 맞춰 작성

# 현재 접속한 세션의 날짜 형식 확인
SELECT *
  FROM NLS_SESSION_PARAMETERS
  WHERE PARAMETER = 'NLS_DATE_FORMAT';
  
# 현재 접속한 세션의 파라미터 변경
ALTER SESSION SET NLS_DATE_FORMAT = 'YY/MM/DD';

9. 산술 연산자 배우기 (*, /, +, -)

(ex) 연봉이 36000 이상인 사람들의 이름과 연봉 출력

SELECT ename, sal*12 as 연봉
  FROM emp
  WHERER sal*12 >= 36000;

(ex) 부서 번호가 10번인 사람들의 이름, 월급, 커미션, 월급 + 커미션 출력

SELECT ename, sal, comm, sal + comm
  FROM emp
  WHERE deptno = 10;

- 산술식의 컬럼값이 NULL인 경우 결과값도 NULL
- NVL함수: 컬럼값이 NULL이면 0으로 출력하는 함수

10. 비교연산자 배우기

(1) <, >, <=, >=, !=, ^=, <>, =

(ex) 월급이 1200 이하인 사원들의 이름, 월급, 직업, 부서 번호 출력

SELECT ename, sal, job, deptno
  FROM emp
  WHERE sal <= 1200;

(2) BETWEEN AND

(ex) 월급이 1000에서 3000 사이인 사원들의 이름과 월급 출력

SELECT ename, sal
  FROM emp
  WHERE sal BETWEEN 1000 AND 3000;

SELECT ename, sal
  FROM emp
  WHERE (sal >= 1000 AND sal <= 3000);

- BETWEEN 하한값 AND 상한값

# 월급이 1000에서 3000 사이가 아닌 사원들
SELECT ename, sal 
  FROM emp
  WHERE sal NOT BETWEEN 1000 AND 3000;
  
SELECT ename, sal
  FROM emp
  WHERE (sal < 1000 AND sal > 3000);

(ex) 1982년도에 입사한 사원들의 이름과 입사일 출력

SELECT ename, hiredate
  FROM emp
  WHERE hiredate BETWEEN '1982/01/01' AND '1982/12/31';

(3) LIKE

(ex) 이름의 첫 글자가 S인 사원들의 이름과 월급 출력

SELECT ename, sal
  FROM emp
  WHERE ename LIKE 'S%';

- % : 와일드 카드. 0개 이상의 임의의 문자와 일치 -> 'LIKE' 연산자와 함께 쓸 경우!

(ex) 이름 두번째 글자가 M인 사원의 이름 출력

SELECT ename
  FROM emp
  WHRERE ename LIKE '_M%';

- _ : 언더바. 한 자리수의 어떤 철자. 하나의 문자와 일치

(ex) 이름의 끝 글자가 T인 사원의 이름 출력

SELECT ename
  FROM emp
  WHERE ename LIKE '%T';

(ex) 이름에 A 포함하고 있는 사원들의 이름 출력

SELECT ename
  FROM emp
  WHERE ename LIKE '%A%';

(4) IS NULL

- NULL : 데이터가 할당되지 않은 상태. 알 수 없는 값. -> = 연산자로 비교 불가

# 커미션이 NULL인 사원들의 이름과 커미션 출력
SELECT ename, comm
  FROM emp
  WHERE comm IS NULL;

(5) IN

(ex) 직업이 salesman, analyst, manager인 사원들의 이름, 월급, 직업 출력

SELECT ename, sal, job
  FROM emp
  WHERE job IN ('SALESMAN', 'ANALYST', 'MANAGER');

- = 연산자는 하나의 값만 조회, IN 연산자는 여러 리스트의 값 조회 가능

11. 논리 연산자 배우기 (AND, OR, NOT)

(ex) 직업이 SALESMAN이고 월급이 1200 이상인 사원들의 이름, 월급 직업

SELECT ename, sal, job
  FROM emp
  WHERE job = 'SALESMAN' AND sal >= 1200;

[수업출처] 숙명여자대학교 소프트웨어학부 김주균 교수님 운영체제 수업 & [OS? Oh Yes!] 

1. (CPU) 스케줄링

- 시분할 시스템에서 현제 프로세스로부터 다른 프로세스로 CPU를 넘겨주어야 할 때, 기다리는 프로세스들 중에 어떤 프로세스를 선택해야할 지에 대한 방식이나 기준

- 수행 단계에 따라 장기, 중기, 단기 스케줄링

- 장기

    - 어느 작업을 커널에 등록시켜 프로세스로 만들어 줄 것인가 결정

    - 작업 스케줄링

    - 일괄처리) 작업: 디스크 → 일괄처리 큐 대기 → 장기 스케줄러 → 프로세스

    - 시분할) 사용자의 접속 시도를 허용할지 말지 결정하는 단계

    - 요청된 일을 프로세스로 만들어 시스템에 알려진 일거리로 추가하느냐 결정 → 다중 프로그래밍 정도 조절

    - 수행 횟수 적음, 대부분 FIFO 방식

- 중기

    - 보류 상태의 프로세스 중에서 어느 프로세스에 메모리를 할당할 것인지 결정

    - Swap In (or Resume)

- 단기

    - 준비 상태의 프로세스 중에서 어느 프로세스에 CPU를 할당할 것인지 결정

    - 프로세스 스케줄러 (디스패처)라 불리는 것에 의해 수행

    - 입출력, 시간 종료 인터럽트, 시스템 콜 등과 같은 다양한 이유에 의해 가동

    - 자주 수행됨 → 실행 시간 줄여야 함

2. 스케줄링의 목적과 기준

1) 목적

- 사용자 관점

    - 응답시간: 프로세스 요청에 의해 시스템이 최초로 출력을 내주기 시작할 때까지 걸린 시간 → 대화형 시스템

    - 반환시간: 요청으로부터 결과를 돌려받는 데까지 걸린 시간 (일괄처리)

    - 예측가능성: 요청한 일이 얼마 후쯤에는 완료될 수 있을 것이라는 예측

- 시스템 관점

    - 처리량: 단위 시간에 완료된 프로세스의 개수 → 일괄처리 시스템

    - 활용도: 주어진 시간동안 특정 자원이 실제로 가동된 시간의 비율

- 가능한 한 CPU 시간을 공평하게 나누어 주어야 함 (공평성)

- 특정 프로세스가 장기간 CPU를 받지 못하게 되는 경우 최대한 피해야 함

- 시스템에 있는 여러 자원들은 가급적 균형있게 사용되어야 함

- 빠른 응답시간을 주기 위해 스케줄링을 자주 한다면 문맥교환이 자주 일어나게 되고, 이것은 CPU 시간의 상당 부분이 문맥교환에 사용된다는 것을 의미 → 사용자 프로세스를 실행할 시간이 줄어 전체적으로는 처리량 감소

- 주어진 기간 동안에 많은 프로세스 처리하여 처리량을 높이려고 수행 시간이 짧은 프로세스들 주로 처리 → 수행시간이 긴 프로세스는 처리가 늦어져 응답시간이 길어짐

2) 고려해야 할 기준들

- 프로세스의 성격

    - CPU를 사용하는 연산이 입출력에 비해 상대적으로 많은 것: 연산 위주 프로세스 (CPU-bound)

    - 입출력이 상대적으로 많은 것: 입출력 위주 프로세스 (I/O-bound)

    - 목적에 따라 어떤 종류의 프로세스 우대할지 생각

- 시스템이 사용될 환경

    - 응답시간을 우선으로 할지, 처리량을 우선으로 할지

    - 특정 프로세스에게 우선적으로 빠른 응답시간을 보장해야 하는 경우 → 가능케 하는 기능 필요

    - 프로세스 크고 작음에 따라 어떤 것을 우선적으로 처리할 지 기준 필요 (CPU 요구량 & 메모리 요구량)

3. 스케줄링 기법들

[스케줄링이 가동되어야 할 때]

- 실행 상태에서 대기 상태로 전환될 때 (ex 입출력)

- 실행 상태에서 준비 상태로 전환될 때 (ex 시간 종료 인터럽트)

- 대기 상태에서 준비 상태로 전환될 때 (ex 입출력 종료)

- 프로세스 수행 종료

- 비선점 스케줄링: 프로세스가 CPU를 스스로 반납할 때까지 계속 사용

- 선점 스케줄링: 실행 중인 프로세스로부터 CPU를 빼앗아 다른 프로세스에 할당 가능

- 위의 4가지 경우 중 1번과 4번의 경우에만 스케줄링을 하게 되면 비선점 방식이 되고, 

- 2번과 3번에도 적용되는 스케줄링을 선점 방식이라 함

- Average Waiting Time 평균 대기 시간: 준비 큐에 도착한 후 실행될 때까지 걸린 시간, 사용자 만족도의 기준

1) FCFS (First Come First Service = FIFO) 스케줄링 

- 준비 큐에 먼저 도착한 프로세스에게 먼저 CPU 할당

- 비선점 방식

- 프로세스가 CPU를 독점하여 사용하기 때문에 아주 긴 프로세스가 실행될 경우 평균 응답시간이 길어짐

- 대화형 시스템에 적합하지 않음

- 프로세스들의 개수와 크기를 짐작할 수 있다면 각각의 프로세스들이 언제쯤 실행될 지 예측 가능, 공평함

- 실제 시스템에서 바로 사용되기는 어렵지만, 다른 스케줄링 기법의 보조 장치로서 활용 가능

- ex

- P1, P2, P3, P4의 순서로 거의 동시에 도착했을 때

- 평균 응답시간 = (100 + 110 + 120 + 130) / 4 = 115

- 평균 대기시간 = (0 + 100 + 110 + 120) / 4 = 82.5

- P2, P3, P4, P1의 순서로 거의 동시에 도착했을 때

- 평균 응답시간 = (10 + 20 + 30 + 130) / 4 = 47.5

- 평균 대기시간 = (0 + 10 + 20 + 30) / 4 = 15

2) SPN (Shortest Process Next) 스케줄링

- 준비 큐에 있는 프로세스들 중 가장 짧은 프로세스 (CPU 요구량이 가장 적은)를 먼저 실행

- 비선점 방식

- 평균 응답시간을 최소화할 수 있지만, 실행시간이 긴 프로세스가 CPU를 할당받지 못하고 계속 대기하는 무한 대기 현상 발생

    - 긴 프로세스일수록 그 편차가 커져 예측가능성은 감소할 것

    - 무한 대기 가능성을 낮추는 방법으로는 기다린 시간만큼 우선순위를 높여 실행가능성을 높여주는 것이 있음 (Aging)

- 각 프로세스들의 크기를 실행 전에는 정확히 알 수 없음에도 그 크기를 가지고 스케줄을 해야한다는 단점

    - 해결책: 프로세스의 크기를 실행 전에 추정해보는 지수 평균 방법 (Exponential Averaging)

    - 이전에 실행되었을 때의 크기와 그때의 추정 크기로 지금 실행되어질 크기 짐작

    - 이전 단계의 실제 크기 → 다음 추정 크기

    - 추정 크기와 실제 크기의 가중치를 각각 0.5로 설정하고, 추정크기를 a, 실제크기를 b라 했을 때

    - 실제1 = 추정2 = 0.5a + 0.5b

    - 실제2 = 추정3 = 0.5(0.5a + 0.5b) + 0.5b ...

- ex)

- 평균 응답시간 = (10 + 16.5 + 11) / 3 = 12.5

- 평균 대기시간 = (0 + 11.5 + 9) / 3 = 6.84

3) SRT(Shortest Remaining Time) 스케줄링

- SPN을 선점 방식으로 운영하는 것

- 새로 도착하는 프로세스의 실행시간 크기는 완료까지 남은 시간과 같으며, CPU를 할당받아 실행된 양만큼 남은 시간은 줄어들 것

- 준비 큐에서 완료까지 남은 CPU 요구량이 가장 짧은 것을 먼저 실행시켜 주는 방식

- 실행 도중 남은 실행 시간이 더 적은 프로세스가 준비 큐에 들어올 경우 현재 실행 중인 것을 중단하고 새 프로세스에 CPU 할당

- 완료까지 남은 실행시간의 계산, 잦은 문맥교환의 부담 존재

- 반환시간을 기준으로 했을 때 SPN보다 우수

- 위의 예제에 대입해보면

- P1 (0.5s) → P2 (0.5) → P3 (2) → P2 (4.5) → P1 (9.5) 의 순서로 CPU가 할당됨

- 평균 응답시간 = (17 + 7 + 2) / 3 = 8.67

- 평균 대기시간 = (7 + 2 + 0) / 3 = 3

- 이때 실제로는 SPN보다 더 많은 문맥교환이 요구되어 평균 응답시간이 조금 더 길어질 것임을 예상할 수 있음

- 만약 가까운 미래에 도착하게 될 프로세스의 정보를 알 수 있다면, 위의 예제에서 1초 뒤에 P3가 들어올 것을 알 수 있다면 P1을 할당하는 대신 1초를 기다렸다가 SPN을 적용하여 평균 응답시간을 줄일 수 있음 

→ 반복적인 시스템에서는 사용할 수 있겠지만 사실 어려움. idea 차원의 개념. Future-knowledge 스케줄링

- 잦은 문맥교환을 줄이는 방법

- SRT 스케줄링을 위한 임계값을 정해두고 두 프로세스의 남은 시간 차이가 임계값을 넘지 않을 경우에는 다음 프로세스의 실행시간이 더 짧더라도 선점되지 않도록 함

4) HRRN (Highest Response Ratio Next) 스케줄링

- 수행시간이 긴 프로세스의 무한 대기 현상을 방지하기 위한 기법

- 준비 큐에 있는 프로세스들 중에서 응답률이 가장 높은 우선순위를 줌

- 비선점 방식

- 응답률 = (대기시간 + CPU 요구량) / CPU 요구량

- 프로세스가 기다리는 시간이 길어질수록 우선순위가 높아지므로 곧 CPU 할당받을 수 있음

5) 라운드 로빈 (Round-Robin) 스케줄링

- FCFS 스케줄링을 기반으로 하여 CPU를 할당히되, 각 프로세스는 시간 할당량이 지나면 시간 종료 인터럽트에 의해 CPU 뺏기는 방식

- 선점 방식

- CPU를 반환한 프로세스는 다시 준비 큐의 끝에 들어가게 되고, 준비 큐의 맨 앞에 있는 프로세스가 CPU 선점

- ex)

- 위 프로세스들이 거의 동시에 도착했고, 시간 할당량이 10ms 일 때

- P1 (10) → P2 (8) → P3 (10) → P4 (10) → P1 (10) → P3 (5) → P1 (10) 순서로 CPU 할당 받음

- 평균 응답시간 = (63 + 18 + 53 + 38) / 4 = 43

- 평균 대기시간 = (33 + 10 + 38 + 28) / 4 = 27.25

- 한 프로세스가 CPU를 독점하는 단점을 방지할 수 있지만, CPU 선점에 따른 문맥교환의 오버헤드 감수해야 함

- 오버헤드: 문맥교환에 필요한 시간, 메모리 등

- 오버헤드에도 불구하고 이 기법은 대화식 시스템이나 시분할 시스템에 적합한 방식으로 알려져 있음

- 시간 할당량의 크기에 따라 시스템의 성능이 크게 달라질 수 있음

- 시간 할당량이 매우 크면 FCFS 방식과 같아지게 되며, 작을수록 문맥교환이 자주 발생하므로 문맥교환의 오버헤드가 커짐

- 일반적으로 시간 할당량은 10~100ms가 적당

- 연산 위주의 프로세스가 입출력 위주의 프로세스보다 우대받고 있음

- 입출력 위주 프로세스는 대부분 시간 할당량을 남긴 채 입출력을 발생시킨 다음 입출력이 완료되면 당시 남겨진 시간 할당량을 보상받지 못한 채 큐의 맨 뒤로 들어감 

→ 입출력을 마친 프로세스가 들어가는 준비 큐를 따로 하나 두고 우선순위는 더 높게 하되, 이 큐에서 CPU를 받을 때에는 이전 입출력을 발생시켰을 때 남긴 시간 할당량만큼만 주도록 하는 방식이 있음 : 가상 라운드 로빈 방식

- 프로세스가 생성될 때 부여된 우선순위가 완료 때까지 변하지 않는 값 → 정적 우선순위

- 시스템에 있는 동안 조정되도록 → 동적 우선순위

6) 다단계 큐 (Multi-level Queue) 스케줄링

- 정적 우선순위를 사용하는 선점 방식

- 우선순위의 개수만큼 큐 필요 → 같은 우선순위를 가지는 프로세스끼리 큐에 들어감

- 큐들 간에 프로세스 이동 불가능

- 우선순위가 낮은 하위 단계 큐의 작업은 실행 중이더라도 상위 단계 큐에 프로세스가 도착하면 CPU 뺏김

7) 다단계 피드백 큐 (MFQ, Multi-level, Feedback Queue)

- 프로세스들의 CPU 요구량을 몰라도 짧은 프로세스들에게 유리하면서 입출력 프로세스를 우대할 수 있는 기법

- 입출력 프로세스 우대 → 짧은 연산 후 입출력 발생하면 CPU는 다른 프로세스에게 주어지고 입출력 작업과 병행되어 시스템 성능 향상

- 동적 우선순위를 기반으로 하는 선점 방식

- 우선순위 개수만큼 큐가 있으며 각 단계마다 서로 다른 CPU 시간 할당량을 가지도록 함

- 우선순위가 높은 단계의 큐일수록 시간 할당량 작도록 함

- 새로운 프로세스는 최상위 단계의 준비 큐에 들어간 후 FCFS의 순서로 CPU를 할당받아 실행되다가 그 큐의 시간 할당량이 끝나면 한 단계 아래의 준비 큐에 들어감으로써 우선순위가 한 단계 낮아짐

- 각 단계에서도 그 단계 큐의 시간 할당량을 다 사용할 때까지 계속 실행된다면 다음 단계의 큐로 들어감

- 마지막 단계에서는 라운드 로빈 방식으로 실행 (시간 할당량이 지나면 다음 프로세스에게 CPU 할당, 준비 큐 맨 뒤로 들어감)

- 어떤 단계에서든 시간 할당량이 끝나기 전에 입출력 등으로 CPU를 내놓게 되면 다시 준비 상태가 되었을 때 한 단계 위의 큐에 들어가도록 함으로써 우선순위를 높여줌

- 중간 단계의 맨 앞에 있는 프로세스는 상위 단계의 큐들이 비어있는 경우에만 CPU를 받을 수 있고, 시간 종료 인터럽트에 의해 선점되거나 입출력이 발생하지 않는 한 그 큐의 시간 할당량까지 쓸 수 있음

- 일단 CPU를 받은 프로세스는 실행 중 상위 단계의 프로세스에 의해 선점되지 않고 부여받은 시간 할당량까지는 보장됨

- 상대적으로 짧은 프로세스들이 하위 큐까지 내려가지 않도록함으로써 비교적 높은 우선순위를 유지할 수 있도록 함

- 입출력은 우선순위의 상향조정으로 이어져 우대받음을 알 수 있음

- Behavior Adaptive 스케줄링

- 변형)

- 각 단계에서 시간 할당량을 다 쓸 경우 그 단계의 큐에서 몇 번의 순환 후 다음 단계로 떨어뜨림

- 입출력의 완료 시 단계의 상승 폭을 더 크게 줌 

- 현재 큐에서 대기한 시간이 일정 시간을 넘기면 상위 큐로 이동시켜 줌

8) Fair-share 스케줄링

- 프로세스들의 특성이나 중요도에 따라 몇 개의 그룹으로 나누고, 각 그룹에 할애된 일정량의 CPU 시간은 그 그룹에만 영향을 미치도록 함

- ex)

- 1(A B) 2(C D) 3(E F)

- 1그룹에는 CPU 시간의 50%, 2그룹과 3그룹에는 각 25% 할당

- ACBEADBF의 순서대로 스케줄을 하거나, A에게 많은 시간을 주어야 할 경우 B를 줄이고 A를 늘리는 등 타 그룹에는 영향이 가지 않도록

4. 실시간 Realtime 스케줄링

- 실시간 시스템: 실행될 모든 프로세스들이 정해진 시간 내에 완료되어야 하는 시스템

- 경성 실시간 시스템

    - 작업이 마감시한 내에 완료되지 않으면 치명적인 결과를 초래하는 시스템 (시스템이 중지되는 등) 

    - 마감시한을 넘긴 후 완료되는 일은 아무 가치가 없음

    - 일반적으로 실시간 시스템은 경성 실시간 시스템을 말함

- 연성 실시간 시스템

    - 작업이 마감시한 내에 종료되지 않으면 데이터의 손실 등 피해가 발생하지만 시스템은 계속 운영 가능한 시스템

    - 마감시한을 넘긴 후부터는 완료의 가치가 점점 떨어짐

- 정적인 방법:  프로세스들의 특징과 개수를 알 수 있는 경우에 유용

- 동적인 방법: 프로세스의 생성 시간이나 특성을 알 수 없는 경우에 사용

- 실시간으로 운영되는 환경은 대부분 특수한 상황으로, 실행되어야 할 일들의 성격이나 개수를 사전에 알 수 있는 경우가 많음

1) RM (Rate Monotonic) 알고리즘

- 대표적인 정적 스케줄링 방식

- 크기와 개수가 알려진 프로세스들이 각자 주기적으로 발생되는 환경에서 사용

- 프로세스는 서로 독립적이고 주기적으로 수행되는 환경에서 각 프로세스의 마감시한은 각자의 주기와 같다고 가정

- 주기가 짧을수록 높은 우선순위 받음

- 낮은 우선순위의 프로세스가 더 높은 우선순위의 프로세스가 도착할 경우 CPU를 뺏기는 선점 방식

- 정적 환경에서 최적의 기법으로 알려져 있음

- n개로 구성된 프로세스 집합이 있을 때, 이 프로세스들에 의한 CPU 사용률 U는 아래와 같음

- U = U1 + U2 + ... Un = C1/P1 + C2/P2 + ... + Cn/Pn ≤ n(2^(1/n) - 1)

- 이 식이 만족되면 RM 기법으로 모든 프로세스의 마감시한을 맞출 수 있는 스케줄링이 가능하다는 것이 알려져 있음

- 1보다 작거나 같을 경우 될 수도 있고 안될 수도 있으며, 1보다 큰 경우엔 불가능함

- P는 주기, D는 마감시한, C는 크기(수행시간)

- 스케줄링 비용이 적게 드는 대신, 새로운 프로세스가 추가되는 환경에 바로 적응하지 못하고 전체 스케줄링을 다시 해야하는 단점

- ex) 

- T1의 주기가 짧으므로 먼저 시작

- T1 (2) → T2 (1) // 3 → T1 (2) → T2 (1) // 6

- T1과 T2 모두 주기 내에서 일이 완료되었기 때문에 성공

- U = 2/3 + 2/6 = 1

2) EDF (Earliest Deadline First) 알고리즘

- 프로세스 마감시한이 가까울수록 우선순위 높게 부여하는 선점 방식의 동적 스케줄링

- 동적: 새로운 프로세스가 도착할 때 바로 대응할 수 있음

- 우선순위에 의해 실행 중 CPU 뺏길 수 있음

- 한 프로세스의 실행이 완료될 경우 마감시한이 가장 가까운 것을 찾아 스케줄

- 모든 프로세스가 주기적일 필요는 없으며, 주기가 있을 경우에는 마감시한을 주기로, 그렇지 않을 경우는 마감시한이 알려져야 함

- n개의 프로세스가 있을 때 아래와 같은 조건이 성립한다면 EDF 기법으로 가능한 스케줄이 존재

- C1/P1 + C2/P2 + ... + Cn/Pn ≤ 1

- 새로운 프로세스의 동적인 수용이 허용되나, 그럴 때마다 가능한 스케줄을 찾기 위한 계산을 해야하는 부담 존재

- ex)

- P1 (4) → P2 (3) → P3 (10) → P1 (4) //21

- P1이 수행되다가 4초 후에 마감 시간이 더 짧은 P2가 들어오면 P2가 CPU를 선점

- 1초 후에 P3가 들어오지만 여전히 P2의 마감 시간이 더 짧기 때문에 P2 수행 완료

- 그 다음 P3가 20초 내에 종료되어야 하기 때문에 P3 실행

- P3 종료 후 P1 마무리 → 성공

[수업출처] 숙명여자대학교 소프트웨어학부 유석종교수님 자료구조 수업 & [파이썬으로 배우는 자료구조 프로그래밍]

* 수강생이 혼자 푼 답을 기록한 것으로 정답이 아닐 수 있습니다 😁

1. 

l = [21, 7, 40, 29, 11, 5, 90, 78, 64, 15, 88]
max = 0
min = 1000

for i in range(len(l)):
    if l[i] > max:
        max = l[i]
    if l[i] < min:
        min = l[i]
    
print((min, max))

(5, 90)

2.

def mul(n, m):
    l = []
    for i in range(1, n):
        if i % m == 0:
            l.append(i)
    return l

print(mul(10, 3))

[3, 6, 9]

3.

def gcd(a, b):
    while a % b != 0:
        a, b = b, a % b
    return b

def fraction(num):
    down = 10**len(str(num))
    up = num * down
    common = gcd(up, down)
    new_up = int(up // common)
    new_down = int(down // common)
    print(new_up, '/', new_down)

fraction(3.14)
# 157/50

4. 

def palindrome(string):
    while len(string) > 1:
        if string[0] != string[-1]:
            return False
        else:
            string = string[1:-1]
    return True

palindrome('abnnba')
# True

palindrome('sdfg')
# False

5.

l = [1]
num = 1
for i in range(14):
    num += 3
    l.append(num)

[1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 35, 37, 40, 43]

6.

l = []
num = 1
for i in range(15):
    num += i
    l.append(num)

[1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79, 92, 106]

7.

scores = [[75, 90, 85], [60, 100, 75], [90, 70, 80]]

for score in scores:
    for i in score:
        print(i, end = ',')
    print()

75,90,85,
60,100,75,
90,70,80,

8.

p = [(9, 4), (5, 3), (4, 2)]
q = [(7, 3), (2, 2)]
add_list = []
mul_list = []

def add(p, q):
    while p and q:
        coef1, exp1 = p[0]
        coef2, exp2 = q[0]
        if exp1 > exp2:
            add_list.append(p.pop(0))
        elif exp1 < exp2:
            add_list.append(q.pop(0))
        else:
            add_list.append((coef1 + coef2, exp1))
            p.pop(0)
            q.pop(0)
    for coef, exp in p:
        add_list.append((coef, exp))
    for coef, exp in q:
        add_list.append((coef, exp))
    return add_list
        
def mul(p, q):
    while p and q:
        coef1, exp1 = p[0]
        for coef, exp in q:
            mul_list.append((coef1*coef, exp1+exp))
        p.pop(0)
    return mul_list

add(p, q)        
print('P + Q = ', add_list)
# P + Q =  [(9, 4), (12, 3), (6, 2)]

mul(p, q)
print('P * Q = ', mul_list)
# P * Q =  [(63, 7), (18, 6), (35, 6), (10, 5), (28, 5), (8, 4)]

- 곱셈 후 지수가 같은 항 합치는 방법 생각해야함!

[수업출처] 숙명여자대학교 소프트웨어학부 유석종 교수님 자료구조 수업

1. Python

- Interpreter

- 객체 지향 Object-oriented

- 자료형 미리 선언하지 않음 Dynamic typing

- Sequence, collection data type

- 값 저장X, 참조 방식 Literal reference

- 동적 할당 Dynamic allocation

- 파이썬의 모든 변수 → 포인터

- 값에 대한 참조 변수 (값이 저장되어 있는 곳의 주소 참조)

- a, b = b, a : swap

2. Data type

1) Immutable data type 불변자료형

- int, float, string

- 값 변경 불가능 → 값 변경이 아니고 새로운 literal 참조하는 것

- 매개변수 전달시 값 변경 불가능

2) Mutable data type 가변자료형

- list, dictionary

- 원소 값 변경, 추가 가능

- 리스트는 각 원소 값에 대한 참조들의 모음

- 매개변수 전달시 인수 값 변경될 수 있음

- 가변자료형: '참조변수'를 바꿀 수 있다는 것

3. Parameter Passing

- call by value

- call by reference

- python → call by object reference 객체 참조 전달

def f(a):
    a = 3
    print(a)
    return(a)
   
b = 2
f(b)         # 3
print(b)     # 2
b = f(b)     # 3
print(b)     # 3

return을 받으려면 변수에 입력해야함

4. Alias 별명

- 두 변수가 하나의 객체를 동시에 참조하여 공유하는 것

A = [[2, 3, 4], 5]
B = A
B[0][1] = 'f'
print(A, id(A))   # [[2, 'f', 4], 5] 1860139826944
print(B, id(B))   # [[2, 'f', 4], 5] 1860139826944

5. Shallow copy 얕은 복사

- 변수는 복사하여 새로 생성하지만 참조하는 리터럴은 공유하는 복사 방법

- copy 모듈의 copy() 함수로 실행

- 첫번째 level 객체만 복사

import copy

A = [[2, 3, 4], 5]
B = copy.copy(A)    # B = list(A)
B[0][1] = 'f'
B[1] = 7
print(A, id(A), id(A[0]), id(A[0][1]))  # [[2, 'f', 4], 5] 1860140611008 1860140611584 1860137884464
print(B, id(B), id(B[0]), id(B[0][1]))  # [[2, 'f', 4], 7] 1860140611904 1860140611584 1860137884464

- list A를 변수 B에 얕은 복사

- list B의 원소들은 새롭게 생성되지만, 원소들이 참조하는 객체는 원본과 동일하며 새로 생성되지 않음

- list A 와 B의 주소는 다르지만 리스트 원소가 참조하는 객체는 동일

6. Deep copy 깊은 복사

- 변수와 대상 객체(리터럴)를 모두 복제하여 생성

- 완전히 독립됨

import copy
A = [[2, 3, 4], 5]
B = copy.deepcopy(A)
B[0][1] = 'f'
B[1] = 7
print(A, id(A), id(A[0]), id(A[0][1]), id(A[1])
# [[2, 3, 4], 5] 1482518103488 1482518184832 1482509412720 1482509412784

print(B, id(B), id(B[0]), id(B[0][1]), id(B[1])
# [[2, 3, 4], 5] 14825181072000 1482518204544 1482509753136 1482509412848

- 변수 A와 B, 리스트 원소, 원소가 참조하는 객체의 주소가 모두 다름

- 리스트 원소가 참조하는 객체도 복제되기 때문에 B의 원소 값을 수정해도 리스트 A가 참조하는 객체에는 변화가 없음

7. List

- 원소의 자료형 같을 필요 없음

- 파이썬은 정적 배열 지원하지 않음

- 사이즈는 고정되어 있지 않음 dynamic

- referential array 리스트 원소는 값에 대한 참조 변수

A = [2, 3, 4]
A.append(7)
A[1] = 9

1) 리스트 생성

    - 리스트 복합 표현

    - range(), list() 함수 사용

    - 빈 리스트 선언 후 원소 추가

# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

num1 = [i for i in range(10)]
num2 = list(range(10))
num3 = []
for i in range(10):
    num3 = num3 + [i]  # num3.append(i)

2) 주사위 던지기 예제

import random

def throw_dice(count, n):
    for i in range(n):
        eye = random.randint(1, 6)
        count[eye-1] += 1
    
def calc_ratio(count):
    ratio = []
    total = sum(count)
    for i in range(6):
        ratio.append(count[i]/total)
    return ratio

def print_percent(num):
    print('[', end = '')
    for i in num:
        print('%4.2f %i, end = ' ')
    print(']')

dice = [0]*6
for n in [10, 100, 1000]:
    print('Times = ', n)
    throw_dice(dice, n)
    print(dice)
    ratio = calc_ratio(dice)
    print_percent(ratio)
    print()

Times = 10
[2, 1, 2, 1, 2, 2]
[0.20, 0.10, 0.20, 0.10, 0.20, 0.20]

Times = 100
[17, 14, 24, 28, 16, 21]
[0.15, 0.13, 0.22, 0.16, 0.15, 0.19]

Times = 1000
[197, 185, 176, 162, 188, 202]
[0.18, 0.17, 0.16, 0.15, 0.17, 0.18]

3) 2차원 배열 생성

scores = [[75, 90, 85], [60, 100, 75], [90, 70, 80]]
print('scores', scores)
for score in scores:
    for num in score:
        print(num, end = ' ')
    print()
print()

print('scores[0][1]', scores[0][1])
print('scores[2]', scores[2])
print('scores[2][2]', scores[2][2])

scores [[75, 90, 85], [60, 100, 75], [90, 70, 80]]
75 80 85
60 100 75
90 70 80

scores[0][1] 90
scores[2] [90, 70, 80]
scores[2][2] 80

4) 볼링 점수 계산 예제

score1 = [(8,0), ((4,3), (8,2), (4,6), (2,6), \
         (10,0), (9,0), (10,0), (8,2), (10,0), (10,10)]
score2 = [(10,0), (10,0), (10,0), (10,0), (10,0), \
          (10,0), (10,0), (10,0), (10,0), (10,0), (10, 10)]

score_list = [score1, score2]      # 첫번째, 두번째 게임
for score in score_list:
    i = total = 0
    frame = []                     # (프레임 점수, 결과)
    for first, second in score:    # 1회, 2회 쓰러뜨린 핀의 수
        f_total = first + second
        next_first, next_second = score[i+1]
        if first == 10:
            result = 'STRIKE'
            f_total += next_first + next_second
            # 1~9 프레임에서 더블을 친 경우
            if i != 9 and next_first == 10:
                next_next_first, next_next_second = score[i+2]
                f_total += next_next_first
        elif (first + second) == 10:
            result == 'SPARE'
            f_total += next_first
        else: result = 'NONE'
            
        total += f_total
        frame.append((f_total, result))
        i += 1
        if i == 10: break
    print(frame)
    print('Total = ', total)
    print()

[(8, 'NONE'), (7, 'NONE), (14, 'SPARE'), (12, 'SPARE'), (8, 'NONE'), (19, 'SPARE'), (9, 'NONE'), (20, 'STRIKE'), (20, 'SPARE'), (30, 'STRIKE')]
Total = 147

[(30, 'STRIKE'), (30, 'STRIKE'), (30, 'STRIKE'), (30, 'STRIKE'), (30, 'STRIKE'), (30, 'STRIKE'), (30, 'STRIKE'), (30, 'STRIKE'), (30, 'STRIKE'), (30, 'STRIKE')]
Total = 300

8. Set and Dictionary

1) Set

- 수학의 집합과 유사한 자료구조로 집합 연산자 지원

- 원소의 나열 순서가 없으며 중복 허용하지 않음

- s1 = set([1, 2, 3])

- s2 = {2, 3, 4}

- 연산자

    - membership( in ), 합집합 union( | ), 차집합 difference( - )

    - add()

    - update( {  } )

    - remove()

2) Dictionary

- key & value의 쌍으로 구성된 자료형

- 키를 통해 원소에 접근

- items() : 각 항목 튜플로 반환

- keys() : 키만을 추출하여 리스트로 반환

- values() : 값만을 추출하여 리스트로 반환

- 단어 출현 빈도 예제

sentence = sentence.lower()    # 소문자로 변환
words = sentence.split()       # 단어 단위로 분리
dic = {}
for word in words:
    if word not in dic:
        dic[word] = 0
    dic [word] += 1
print('# of different words =', len(dic))
n = 0
for word, count in dic.items():
    print(word, '(%d)' %count, end = ' ')
    n += 1
    if n % 3 == 0: print()

# sentence = 'Van Rossum was born and raised in the Netherlands, where he received a master's degree in mathematics and computer science from the University of Amsterdam in 1982. In December 1989, Van Rossum had been looking for a hobby programming project that would keep him occupied during the week around Christmas as his office was closed when he decided to write an interpreter for a new scripting language he had been thinking about lately, a descendant of ABC that would appeal to Unix / C hackers. '

# of different words = 66
van (2) rossum (2) was (2) born (1) and (2) raised (1) ...

9. Polynomial ADT 다항식 객체 (추상자료형)

- polynomial A(x) = 3x^20 + 2x^5 + 4

- x: variable, a: 계수 coefficient, e: 지수 exponent

- 튜플로 저장해야할 것: coefficient, exponent

# 다항식 덧셈

def padd(a, b, d):
    while a and b:
        coef1, exp1 = a[0]
        coef2, exp2 = b[0]
        if exp1 > exp2:
            d.append(a.pop(0))
        elif exp1 < exp2:
            d.append(b.pop(0))
        else:
            if coef1 + coef2 == 0:
                a.pop(0)
                b.pop(0)
            else:
                d.append((coef1 + coef2, exp1))
                a.pop(0)
                b.pop(0)
    for coef, exp in a:
        d.append((coef, exp))
    for coef, exp in b:
        d.append((coef, exp))

a = [(5, 12), (-6, 8), (13, 3)]
b = [(10, 15), (4, 8), (9, 0)]
d = []

padd(a, b, d)
print(d)

# [(10, 15), (5, 12), (-2, 8), (13, 3), (9, 0)]

10. Sparse Matrix 희소 행렬

- 2D array: matrix[m][n] → 공간복잡도 S(m, n) = m*n

- Sparse matrix A[m, n] : 유효한 값은 거의 없고 나머지는 0인 행렬

- 2D array에 저장하기에 메모리 공간이 아까운 경우 → 0이 아닌 값 저장 (행, 열, 값)

- a[0].row: 행렬의 행 수

- a[0].col: 행렬의 열 수

- a[0].value: 0이 아닌 값의 개수

- a[1]부터 0이 아닌 값의 행, 열, 값 저장 (left-right, top-bottom)

class SparseMatrix:
    def __init__(self):
        self.matrix = [[15, 0, 0, 22, 0, 15], \
                       [0, 11, 3, 0, 0, 0], \
                       [0, 0, 0, -6, 0, 0], \
                       [0, 0, 0, 0, 0, 0], \
                       [91, 0, 0, 0, 0, 0], \
                       [0, 0, 28, 0, 0, 0]]
        self.sparse_list = []

def toTuple(self):
    row = count = 0
    for rows in self.matrix:
        col = 0
        for value in rows:
            if value != 0:
                count += 1
                self.sparse_list.append((row, col, value))
            count += 1
        row += 1
    height = len(self.matrix)
    width = len(self.matrix[0])
    self.sparse_list.insert(0, (height, width, count))

s = SparseMatrix()
s.toTuple()
print(s.sparse_list)

# [(6, 6, 8), (0, 0, 15), (0, 3, 22), (0, 5, 15), 
# (1, 1, 11), (1, 2, 3), (2, 3, -6), (4, 0, 91), (5, 2, 28)]

[수업출처] 숙명여자대학교 소프트웨어학부 김주균 교수님 '운영체제' 수업 & [OS? Oh Yes!]

1. 프로세스

- 시분할 시스템에서 메모리의 한 부분을 차지하는 작업, 동시에 CPU라는 자원을 분배해 주어야 하는 대상이 되는 작업들

- CPU를 할당받는 단위이자 주어진 자원들의 소유자로서의 역할

- 수행 중인 프로그램 = 프로그램과 데이터를 기본으로 정상적인 실행을 위해 필요한 환경을 시스템으로부터 부여받은 능동적인 존재

2. 프로세스 제어 플록(PCB)

- 프로세스에 대한 모든 것을 표현하는 테이블 형태의 자료구조

- 프로세스 하나가 만들어진다는 것은 PCB 하나가 만들어진다는 말과 같음

- 운영체제가 프로세스를 관리한다는 것은 해당 PCB에 대한 행동(생성, 수정, 관련 리스트 연결, 삭제 등)

- 기본적으로 메모리에 저장

- 프로세스 번호, 프로세스 상태(준비, 실행, 대기, 보류 등), 프로세스 우선순위, 프로그램 카운터 값(PC), 메모리 포인터, 문맥 데이터, 할당받은 자원들에 대한 목록, 계정 정보, 입출력 정보 등

3. 프로세스 상태 변화

1) 생성

- 사용자가 요청한 작업이 커널에 등록되고 PCB가 만들어져 프로세스가 만들어진 다음, 준비나 보류 준비 상태로 되기 위해 잠시 거치는 상태

- 메모리 공간을 검사하여 충분한 공간이 있으면 메모리를 할당하며 준비 상태로 바꿔주고, 그렇지 못할 경우 보류 준비 상태로

2) 준비

- CPU를 할당받기 위해 기다리고 있는 상태

- CPU만 주어지면 바로 실행할 준비가 되어있는 상태

- 큐 또는 리스트가 사용됨

3) 실행

- CPU를 할당(Dispatch)받아 실행 중인 상태

- 단일 CPU 시스템에서는 한 개의 프로세스만 실행 상태에 있음

- CPU 스케줄링 정책에 의해 CPU를 뺏길 수 있으며 이 경우 준비 상태로 바뀜

- 시간 할당량이 소진되어 CPU를 뺏기는 경우를 시간 종료라고 함 → 인터럽트가 동원되어 처리

- 입출력이 필요하여 시스템 호출을 하면 대기 상태로 바뀌게 되고, 준비 상태의 프로세스 중 하나가 다음으로 실행됨

4) 대기

- 프로세스가 실행되다가 입출력 처리를 요청하거나, 바로 확보될 수 없는 자원을 요청할 때

- CPU를 양도하고 요청한 일이 완료되기를 기다리며 대기하는 상태

- 큐 또는 리스트가 사용됨

- 요청한 일이 완료되면 준비 상태로 바뀌면서 CPU를 기다림

5) 종료

- 프로세스가 종료될 때 아주 잠시 거치는 상태

- 할당되었던 모든 자원들이 회수되고 PCB만 커널에 남아있는 상태

- 운영체제가 시스템에 남아있는 프로세스의 흔적들을 최종 정리 후 PCB를 삭제하면 프로세스가 완전히 사라짐

- 준비, 실행, 대기 상태 → 활성 상태: 메모리 공간의 일정량 부여받음

- 활성 상태에 있는 프로세스 개수: Multi-programming degree

- 메모리가 부족하거나 다른 이유에 의해 메모리를 회수당한 경우 → 보류 상태

- 보류 상태) PCB는 메인 메모리에 저장, Multi-programming degree - 1

6) 보류

- 프로세스가 메모리 공간을 뺏기고 디스크로 나가는 경우

- 이 경우 스왑되어 나간다고 하고(Swapped Out), 다시 메모리로 들어오면 스왑되어 들어온다 함(Swapped In) → Swapping

- 보류 준비 상태

    - 생성된 프로세스가 바로 메모리를 받지 못할 때나,

    - 준비 또는 실행 상태에서 메모리를 잃게 될 때를 위해 필요

    - 실행 상태의 프로세스가 CPU를 반납하면서 준비 상태로 바뀔 때 메모리까지 잃어야 하는 경우(Suspended)

    → 충분한 메모리 공간의 확보를 위해 준비 상태의 프로세스를 보류시킬 수밖에 없는 경우   

    → 높은 우선순위의 보류 대기 상태 프로세스가 준비 상태가 되면서 실행 상태의 프로세스로부터 CPU를 뺏는 경우

    - 메모리의 여유가 생기거나 준비 상태의 프로세스가 전혀 없을 때 대기 상태의 프로세스를 보류 대기로 만들고, 메모리 공간이 확보되면 준비상태로 바뀌게 됨(Resume) → Swapping

- 보류 대기 상태

    - 대기 상태일 때 메모리 공간을 잃은 상태

    - 준비 상태의 프로세스가 아예 없어 대기를 보류 대기로 만드는 경우

    - 준비 상태의 프로세스가 있었다고 해도 메모리의 여유 공간을 더 확보하기 위해 

    - 특별한 경우가 아니면 입출력이나 기다리던 사건의 종료 시 보류 준비 상태가 됨

    - 메모리의 여유가 생겼을 때 대기시켰던 원인이 곧 해소될 것으로 판단되는 프로세스가 보류 대기 상태에 있는데, 보류 상태 중인 어떤 프로세스보다 우선순위가 높은 경우에는 그 프로세스에게 메모리를 주고 대기 상태로 만드는 것이 더 효과적일 것

- 보류 상태의 필요 이유

    - 일차적으로 메모리 공간의 확보를 위해

    - 실행되는 프로세스의 현재 결과가 바라던 것이 아닌 오류가 보일 때

    - 시스템에 위해를 가할 수 있는 수상한 행동을 보일 때

    - 주기적인 일이어서 다음 주기의 실행 때까지 메모리를 회수해도 문제되지 않을 때 등

4. 문맥교환

- 프로세스의 상태 변화는 인터럽트에 의해 처리됨

- 인터럽트 이전에 실행되던 프로세스가 인터럽트 처리 후에 계속 실행될 때도 있고, 다른 프로세스로 CPU가 할당될 때도 있음

- 인터럽트 처리 전후의 프로세스가 같은 경우 문맥교환을 위해 필요한 양이 적음 (PCB의 일부분만 보관)

- 다른 경우 문맥의 저장, PCB에서 관련 데이터들의 변경과 함께 PCB를 적절한 상태의 큐로 옮기기, 스케줄링, 그 프로세스의 PCB 변경과  문맥의 복원 등이 필요함

- 모드 스위칭: 인터럽트 처리 전후의 프로세스가 같은 경우 (사용자 모드 - 커널 모드의 변경만 생김)

- 프로세스 스위칭(문맥교환): 인터럽트 처리 전후 프로세스가 다른 경우

5. 스레드 Thread

- 하는 일은 서로 다르지만 관련 있는 작은 일들이 모여 프로세스를 구성한 경우, 세분된 작은 일들을 스레드라 함

- 프로세스는 부여된 자원의 소유자로서, 스레드는 스케줄링의 단위(CPU를 할당받는 단위)로서 존재

- 프로세스가 가지는 자원을 공유하면서, 각자는 자신의 실행환경(프로그램 카운터로 표현되는 현재 실행 위치, 스택, 레지스터 값)을 따로 가짐

- 다중 스레딩: 하나의 프로세스를 다수의 스레드로 만들어 실행하는 것

- 다수의 실행 단위들이 존재하여 작업의 수행에 필요한 자원들을 공유하기 때문에 자원의 생성과 관리가 중복되는 것을 줄일 수 있음

- 다중 스레딩에서 프로세스란 보호와 자원의 할당 단위

- 프로세스의 코드와 데이터를 수용하기 위한 가상주소 공간과 CPU, 다른 프로세스의 파일들, 입출력에 사용되는 자원에 대한 보호된 액세스를 보장하기 위한 단위

- 스레드 각각은 스레드의 수행 상태, 예를 들어 실행, 준비 등과 실행 상태가 아닐 경우를 위한 스레드 문맥, 각자의 실행 스택, 자신이 속한 프로세스가 가지는 메모리와 자원에 대한 접근 권한을 가짐

- 한 스레드에 의해 메모리의 데이터가 변경될 경우 다른 스레드들은 변경된 데이터를 사용하게 됨

- 열린 파일은 다른 스레드들에게도 열린 상태로 사용됨

- 단일 스레드 프로세스: PCB, 사용자 주소 공간, 사용자 스택과 커널 스택

- 다중 스레드 프로세스

    - 프로세스) PCB, 사용자 주소 공간 : 스레드들과 공유

    - 스레드) 스레드 제어 블록, 사용자 스택과 커널 스택

- 스레드의 생성, 삭제, 스위칭에 소요되는 시간과 비용이 프로세스 단위로 이루어질 때보다 빠르고 저렴

- 프로세스 간의 통신은 커널의 개입을 필요로 하지만, 한 프로세스 내 스레드 간 통신은 커널의 개입이 필요없음

- CPU 스위칭을 위한 스레드 단위의 자료는 유지되어야 하며, 프로세스 단위로 행해지는 보류, 종료 등은 전체 스레드에 동일한 영향 미침

6. 스레드 상태와 동기화 Synchronization

- 스레드 역시 실행, 준비, 대기의 상태를 가짐 (메모리 자원은 프로세스 단위로 할당되기 때문에 보류 상태는 없음)

- 대기는 레지스터 값, 프로그램 카운터(PC), 스택 포인터 등의 보관이 요구되며, 스레드의 종료는 해당 스레드의 레지스터 값들과 스택을 없앰

- 주소 공간과 자원 공유 → 특정 스레드가 변경시킨 내용이 다른 스레드에 바로 영향 미침

- 상호 간의 간섭이나 데이터 파괴 등을 방지하기 위한 스레드 실행의 동기화가 요구됨

→ 프로세스 간의 동기화에서 발생하는 문제와 해결책과 동일

7. 스레드의 종류

1) 사용자 레벨 스레드 

- 스레드 라이브러리에 의해 관리됨

- 스레드 라이브러리의 메모리에서의 위치는 사용자 공간

- 스레드와 관련된 모든 행위는 사용자 공간에서 이루어지므로 커널은 스레드의 존재를 알지 못함

- 커널은 스레드들의 행위를 프로세스의 행위로 인식함

- 스레드 라이브러리는 스레드의 생성, 소멸을 위한 코드와, 스레드 간의 메시지나 데이터의 전달, 스레드의 스케줄링, 스레드 문맥의 보관, 재 저장 등을 담당

- 스레드를 지원하지 않는 운영체제에서도 사용 가능

- 특정 스레드의 실행에서 대기는 소속된 프로세스의 대기 초래

- 당시 실행중이던 스레드는 지금 실제로 실행 중이 아니지만 스레드 라이브러리에 의해 실행으로 계속 간주되고 있다가 나중에 CPU가 다시 이 프로세스에 할당되었을 때 계속 실행해 나갈 수 있도록 해줌

- 스레드의 실행 중 프로세스의 시간 초과가 될 경우 커널은 프로세스의 스위칭 수행

- 당시 실행중이던 스레드 역시 실행 상태로 유지되다가 프로세스가 CPU 받으면 다시 실행됨

- 스레드의 스위칭 도중 프로세스 스위칭이 일어나도 CPU를 다시 받았을 때 스레드의 스위칭이 계속 진행되도록 함

- 스레드 스위칭에 커널의 개입 필요 없음 (모드 스위칭 필요 없음)

- 스레드 간의 스위칭 시 운영체제가 정한 스케줄링(프로세스 스케줄링)에 따를 필요 없고, 응용 별로 독자적인 스케줄링 사용할 수 있음

- 스위칭은 스레드 라이브러리에 있는 스위칭 프로그램에 의해 결정됨

- 특정 스레드의 대기가 프로세스 내의 모든 스레드들의 대기를 초래하며, 다중처리 환경이 주어진다해도 스레드 단위의 다중처리가 되지 못한다는 단점 (CPU는 프로세스 단위로 할당되기 때문)

2) 커널 레벨 스레드

- 모든 스레드의 관리를 커널이 하는 경우

- 스케줄링은 커널에 의해 스레드 단위로 이루어지므로 사용자 레벨 스레드의 단점을 극복할 수 있음

- 다중처리의 환경일 경우 한 프로세스 내의 다수 스레드는 각각 CPU를 할당받아 병렬 실행 가능

- 한 스레드의 대기 시 같은 프로세스에 속한 다른 스레드로 스위칭 가능

- 같은 프로세스에 속한 스레드 간의 스위칭에도 커널의 개입 필요 → 모드 스위칭 요구됨

- 커널 레벨 스레드라 해도 다중처리가 아닌 환경이라면 어차피 하나밖에 없는 CPU를 가동하기 때문에 시간적인 차이가 없을 것이라고 생각할 수 있음

- 단일 처리기 환경에서 다른 서버에 있는 프로시저 호출하고 그 다음 또 다른 서버에 있는 프로시저 호출하는, 즉 두 번의 순차적인 원격 프로시저 호출(RPC)을 수행하는 일을 할 때

- 스레드 없이 프로세스로 한 경우는 RPC 이후 서버로부터 결과를 받을 때까지 기다린 후 다음 RPC 호출을 실행함

- 스레드가 있는 경우 첫번째 호출을 한 스레드에게 맡기고 대기가 될 때 바로 다른 스레드를 실행시켜 두번째 호출을 실행함

- 두 개의 스레드가 대기 중인 시간대가 중복된 만큼 전체 일의 종료 시간이 앞당겨짐

[수업출처] 숙명여자대학교 소프트웨어학부 김주균 교수님 '운영체제' 수업 & [OS? Oh Yes!]

1. OS의 목적

- 사용자와 컴퓨터 사이의 가교 역할 → 사용자가 컴퓨터를 보다 편리하게 사용할 수 있도록 함

- 컴퓨터 시스템의 자원들을 효율적으로 사용될 수 있게 해야 함

- 사용자의 입장에서는 사용하기 쉽고 편리하며, 배우기 쉽고 신뢰할 수 있으며 빨라야 함

- 만드는 사람의 입장에서는 설계, 유지, 보수가 쉽고 적응성이 좋으며 오류없이 효율적이어야 함

- 경우에 따라 모두 가질 수 없는 경우가 많기 때문에 사용되는 환경에 맞춰 순위에 따라 합의해야 함

2. 부팅

- 전원이 꺼져있는 시스템에서 운영체제 전부는 디스크에 저장되어 있음

- 전원이 켜지면 운영체제의 일부인 '커널'이 메모리에 올라와 실행됨

→ 장치 준비, 각종 레지스터 값 초기화, 사용자의 입력 받을 준비 완료 → '부팅되었다'

- 이때 동원되는 것이 부트 프로그램(부츠트랩 로더), 대개 ROM에 저장되어 있음 → 전원이 켜지면 무조건 제일 먼저 실행됨

→ 커널을 찾아 메모리에 올린 후 실행시키는 역할

3. 레지스터

- CPU에 내장되어 있는 메모리보다 빠른 기억장치

- 시스템과 사용 목적에 따라 8비트, 16비트, 32비트 등의 크기 가짐

- 일반적으로 데이터, 주소, 조건 코드 레지스터 등이 있음

    - 데이터 레지스터: 연산 (메모리보다 빠름)

    - 주소 레지스터: 데이터나 명령어의 메모리 주소 저장하거나 계산

        - 인덱스 레지스터: 주소 지정

        - 세그먼트 포인터, 스택 포인터: 해당 포인터 값 저장

- CPU 연산 제어하기 위한 레지스터

    - MBR, MAR, IR, PC 등

- 모든 CPU는 현재 상태 정보를 저장하기 위해 프로그램 상태 워드(PSW)라는 레지스터 가짐

    - 여러가지 조건(condition)코드와 함께 인터럽트 가능, 불가능을 표시하는 비트, 현재 실행 모드를 나타내는 비트 등 포함

4. 명령어 처리

- 명령어 반입: 레지스터를 이용하여 메모리에 있는 명령어를 읽어 처리기에 있는 레지스터로 갖고 옴

- 연산 종류 파악, 실행 → 하나의 명령어 처리

- 반입에서 다음에 실행해야 할 메모리에 있는 명령어의 주소는 PC 레지스터가 갖고 있음

5. 인터럽트

1) 폴링(Polling)

- 컴퓨터 시스템의 각 자원들의 현 상황을 파악할 수 있는 방법 중 하나

- CPU가 일정한 시간 간격을 두고 각 자원들의 상태를 주기적으로 확인하는 방식

- 자원들은 폴링 신호를 받은 후 자신의 상태나 원하는 바를 CPU에게 알려줌

- 폴링의 간격을 정해야 하며, 각 자원들은 직전 폴링 이후 변화된 상태를 다음번 폴링 때까지는 알릴 수 없다는 단점

- 아무 일이 없을 때에도 CPU는 폴링에 일정량의 시간을 들여야 한다는 부담

2) 인터럽트

- 각 자원들이 능동적으로 자신의 상태변화를 CPU에게 알리는 방식

- CPU는 따로 시간을 들이지 않아도 되고, 자원들은 상황을 즉시 알려 처리받을 수 있음

- 오늘날 거의 대부분의 시스템에서 채택하고 있음

- 하드웨어 인터럽트: 장치 또는 주변장치들로부터의 인터럽트

- 소프트웨어 인터럽트: CPU 스스로 자신에게 인터럽트(=trap) (명령어 때문), 입출력할 때 시스템 콜

3) 인터럽트 처리 과정

- 장치가 CPU에 인터럽트 신호 전송 → 명령어 실행중이라면 명령어 실행을 우선 완료시키고 인터럽트 신호 확인 → 인터럽트 처리 루틴 실행 전, 실행중이던 프로그램의 현 상태 정보(PSW, PC 레지스터 값 등)를 시스템 스택에 저장 → 인터럽트 처리 루틴의 시작 주소를 PC에 넣어 실행 → 인터럽트 처리 루틴 실행

- 인터럽트 처리 루틴: CPU에 있는 레지스터들의 값 저장 → 필요한 인터럽트 처리

- 인터럽트 처리가 끝나면 이전에 저장했던 레지스터 값들 다시 재저장, PSW와 PC 값 원래 자리에 넣어주고 실행 → PC에 들어가있는 값이 인터럽트 이전에 실행 중이던 프로그램에서 다음에 실행할 명령어 위치 → 프로그램 실행 이어나감

4) 중첩된 인터럽트의 처리

- 순차적 처리: 인터럽트를 처리하는 동안 발생하는 인터럽트는 현재 처리가 끝난 뒤 차례대로 하나씩 처리해줌

- 중첩 처리: 현재 처리 중인 인터럽트를 잠시 접어두고 또 다른 인터럽트로 실행을 옮길 수 있음

- 인터럽트의 중요도에 따라 우선순위가 더 높은 경우에는 중첩을, 그렇지 않은 경우는 순차적으로 구현하는 방법

6. 기억 장치의 계층적 구조

[자기테이프 - 광디스크 - 자기디스크 - 전자디스크 - 주기억장치 - 캐시 - 레지스터]

- 보통 속도와 가격은 비례하기 때문에 용도에 맞게 적절히 저장장치를 계층적으로 구성하는 타협 필요

- 상위계층에 있을수록 속도와 가격이 올라감

- CPU에 의해 처리되어질 명령어나 데이터가 상위에 있을수록 시스템의 성능은 좋아짐

- 프로그램 또는 데이터는 평소에는 하위계층에 저장되다가 실행시에 적당량이 상위계층과 하위계층으로 번갈아 교체되어지면서, CPU는 최대한 상위계층으로 접근하도록 만들어 처리 속도를 높임

- 프로그램이 실행되기 위해서는 반드시 주기억장치(메모리)에 있어야 함

- 메모리에 있는 프로그램의 일부분이 다시 캐시로, 그 중 실행되어질 명령어는 처리기 레지스터에 적재되어 실행됨

- 메모리 관리를 어떻게 하느냐에 따라 시스템의 성능 좌우 → 운영체제의 역할 중요

7. I/O 방식 (입출력 방식)

- 하나의 입출력 장치에는 컨트롤러가 있고, 여기에는 CPU와 입출력 데이터를 저장하는 버퍼 존재

[CPU의 개입 정도에 따라]

1) 프로그램에 의한 입출력

- CPU는 입력을 지시한 후 워드가 컨트롤러의 버퍼에 입력되었는지 계속 확인

- 인터럽트가 필요없는 대신 CPU가 지속적으로 완료 여부 확인해야 함 

→ 전체 입출력 완료될 때까지 CPU 낭비됨

2) 인터럽트에 의한 입출력 

- 입력을 지시한 후 입력이 이루어지는 사이에 CPU는 다른 작업에 활용됨

- 입력 완료 시 인터럽트를 통해 CPU에 알림

- 프로그램에 의한 입출력 때의 CPU 낭비 없앨 수 있음

- 버퍼의 크기에 비해 입출력할 데이터가 클수록 잦은 인터럽트 처리가 요구됨

3) 메모리에 직접 접근하는 입출력(DMA)

- 인터럽트에 의한 입출력에서 인터럽트가 호출되는 횟수를 줄이고자 한 방식

- 입출력 작업을 CPU 대신 해줄 수 있는 '채널'이라는 위성 프로세서 필요

- CPU는 입출력할 데이터의 시작주소와 크기 등을 채널에게 알려주고 다른 작업에 동원됨

- 이때부터 입출력은 채널의 주도하에 이루어짐

- 일반적으로 한 번의 입출력 단위를 블록이라고 부르며, 채널은 블록 단위로 CPU에게 인터럽트를 보내 알림

- CPU와 채널이 동시에 메모리에 접근할 때, 메모리는 한 번에 하나의 접근만 허용하기 때문에 둘 중 하나를 결정해야 함

- Cycle Stealing: 일반적으로 속도가 빠른 CPU가 평소 메모리 접근 기회를 더 많이 가지기 때문에, 이때는 채널에게 기회를 주는 것이 공평하다고 보고 설계함

[하드웨어의 구성에 따라]

1) 독립적인 입출력

- 입출력 장치들이 입출력 버스(I/O Bus)를 통해 CPU와 연결되어 있는 경우

- 메모리는 따로 메모리 버스를 통해 연결되어 있음

- 입출력은 입출력을 담당하는 명령어를 통해 실행되는데, 입출력 버스를 통해 해당 장치의 지정, 데이터, 입출력을 구분해주는 제어값이 전달됨

- 입출력 명령어가 명령어 집합에 추가되므로 제어 로직이 복잡해지고, 입출력 버스를 장착하는데 추가 비용이 드는 단점

2) 메모리 주소지정 입출력

- 입출력 장치들이 메모리와 함께 메모리 버스에 연결되어 있음

- 입출력을 위한 명령어를 따로 두지 않고, 메모리에 대한 명령어(MOVE, LOAD 등)를 사용하여 실제 입출력 실행

- 입출력 장치들은 각각 메모리의 한 번지를 할당받아, 메모리에 대한 명령어로 그 번지에 해당하는 장치로의 입출력이 되도록 하는 것

- ex) 입출력 장치 2개, 주소의 크기가 3비트(0~7번지)라면 메모리는 0번지부터 5번지를 가는 크기이고, 6, 7번지는 입출력 장치를 나타내도록 하는 것인데 주소 공간만큼의 메모리를 활용할 수 없다는 단점이 있음

[수업출처] 숙명여자대학교 IT공학전공 박영호 교수님 수업 '데이터베이스'

1. 데이터 모델

- 모델: 실체를 가져올 수 없기 때문에, 핵심 특성을 담은 모형을 등장시켜 실체를 설명하기 위한 것

- 어떤 데이터에 대한 개념적, 형식적 표현

- original 대상을 다음 3가지로 구분하여 설명

1) 구조 structure (ex. DML 정의: CREATE SCHEMA ... )

2) 연산 operation (구조를 운용하기 위함. SELECT, DELETE, INSERT, UPDATE ...)

3) 제약조건 constraint (개념들의 집합)

종류

1) Conceptual Data Models (high-level, semantic-level) 개념적 데이터 모델

- 데이터를 높은 수준이나 의미적 수준으로 표현하는 데이터 모델

- ex) '학생' 테이블의 구성요소 - 나이, 주소 등

→ Database Schema

→ 데이터 베이스를 설계한다는 것 = Schema를 설계하는 것

2) Physical Data Models (low-level, internal-level) 물리적 데이터 모델

- 데이터를 낮은 수준이나 물리적 수준으로 표현하는 데이터 모델

- 데이터가 디스크에 어떻게 저장되는 것이 효과적인지 설명하기 위한 구현 수준의 실질적 데이터 모델

- ex) '나이'는 4byte 정수로, B-tree index 구축하자 등을 정하는 일

3) Implementation Data Models (record-oriented, representational)

- 상위 두 모델의 중간 레벨로, 상용 제품의 구현 시 적용되는 데이터 모델

4) Self-Describing Data Model

- data value를 가진 data들의 설명을 결합한 데이터 모델

- ex) XML, NoSQL systems

2. Schema vs Instance

1) Schema (구조, 뼈대)

- 데이터베이스에 대한 설명서

- 데이터베이스 구조 & 제약조건들에 대한 설명 포함

- 데이터베이스 카탈로그에 존재

- Schema Diagram 스키마 도면: 데이터베이스 스키마를 diagram 형식으로 표현한 것 (ex. E-R diagram)

- 테이블들을 구성하고 있는 속성들을 그림으로 표현한 데이터 설계 도면

- 스키마 구성: 스키마의 구성요소 또는 스키마에 포함된 객체 

2) Database State

- 특정 시점에 데이터베이스에 저장된 실제 데이터

- 데이터베이스의 모든 데이터 집합이 포함됨

= database instance (= occurrence, snapshot)

    - instance는 개별 데이터베이스 구성요소에도 적용됨

    - ex) record instance, table instance, entity instance

3) 비교

- 스키마는 자주 변하지 않음

- 인스턴스는 (state) 데이터베이스가 갱신될 때마다 변함

- 스키마 = intention

- 인스턴스 = extension

- ex) 학생 릴레이션의 나이는 '22', 주소는 '강남구 논현동', 학년은 '3' 일 때, 

나이, 주소, 학년은 schema,

'22', '강남구 논현동', '3'은 Instance