• 시스템 전체를 작동시키는 프로그램
• 프로그램을 주기억 장치에 적재시키거나 인터럽트 관리, 장치 관리, 언어번역 등의 기능 담당
• 대표적으로 운영체제가 있음
• 번역프로그램, 매크로 프로세서, 링커, 라이브러리, 정렬/합병프로그램, 로더 등

구성​

• 제어프로그램
• 감시프로그램
• 작업 제어 프로그램 : Jbo Scheduler, Master Scheduler
• 자료 관리 프로그램
• 처리프로그램
• 언어 번역기 : 어셈블러, 컴파일러, 인터프리터
• 서비스 프로그램 : 연결 편집기, 정렬/합병 프로그램, 라이브러리안, 유틸리티
• 문제 프로그램

제어 프로그램​

• Control Program
• 시스템 전체의 작동 상태 감시, 작업의 순서 지정, 작업에 사용되는 데이터의 관리 등의 역할 수행
• 깜짝데이트(감시, 작업, 데이터)

감시 프로그램​

• Supervisor Program
• 제어 프로그램 중 가장 중요함
• 각종 프로그램 실행과 시스템 전체의 작동 상태를 감시 감독

작업 제어 프로그램​

• Job Control Program
• 다른 업무의 이행을 자동으로 수행하기 위해 준비
• 처리에 대한 완료를 담당하는 프로그램
• 작업의 연속 처리를 위한 스케쥴 및 시스템 자원 할당
• Job Scheduler : 다음 작업을 준비시키는 역할
• Master Scheduler : 시스템과 운영자 사이에서 정보를 주고 받을 수 있도록 중개자 역할 (CMD)

자료 관리 프로그램​

• Data Management Program
• 주기억장치와 보조기억장치 사이의 데이터 전송과 보조기억장치의 자료 갱신 및 유지보수 기능을 수행

처리 프로그램​

• Processing Program

언어 번역 프로그램​

• 원시 프로그램을 기계어 형태의 목적 프로그램으로 번역하는 프로그램
• 어셈블러, 컴파일러, 인터프리터

서비스 프로그램​

• 연결 편집기 : 프로그램을 연결하여 실행 가능한 프로그램을 만드는 프로그램 (링커)
• 정렬/합병 프로그램 : 데이터를 일정한 기준으로 정렬하거나 정렬된 파일을 합치는 프로그램
• 라이브러리안 : 프로그램의 라이브러리를 유지 관리
• 유틸리티 프로그램 : 사용자의 편의를 도모하기 위한 프로그램 (텍스트에디터, 디버거)
• 문제 프로그램 : 특정 업무 및 문제 해결을 위해 사용자가 작성

운영체제

• 컴퓨터 시스템의 자원들을 효율적으로 관리
• 사용자가 컴퓨터를 편리하고 효과적으로 사용할 수 있도록 환경을 제공하는 프로그램의 집합
• 유틸리티와 하드웨어 사이의 인터페이스 제공

목적​

• 처리능력 : Throughput 일정 시간 내에 시스템이 처리하는 양
• 반환시간 : Turn Around Time 시스템에 작업을 의뢰한 시간부터 처리가 완료될 때까지 걸린 시간
• 사용가능도 : Availability 시스템을 사용할 필요가 있을 때 즉시 사용 가능한 정도
• 신뢰도 : Reliability 시스템이 주어진 문제를 정확하게 해결하는 정도

기능​

• 프로세서, 기억장치, 입출력장치, 파일 및 자원 관리
• 자원 스케쥴링
• 사용자와 시스템 간의 인터페이스 제공
• 하드웨어와 네트워크 관리 제어
• 데이터 관리하고 데이터 및 자원 공유 기능 제공
• 시스템 오류 검사 및 복구
• 자원 보호 기능 제공
• 입 출력에 대한 보조 기능을 제공
• 가상 계산기 기능을 제공

자원관리​

• 프로세스 관리 : 프레세스 스케쥴링, 동기화, 생성 제거, 시작 정지, 메시지 전달
• 기억장치 관리 : 프로세스 메모리 할당 및 회수
• 주변장치 관리 : 입출력 장치 스케쥴링 및 관리
• 파일 관리

종류​

• 단일 작업 처리 시스템
• Single Tasking System
• 시스템을 한 개의 작업이 독점하여 사용하는 방식
• DOS
• 다중 작업 처리 시스템
• Multi Tasking System
• 여러 개의 프로그램을 열어 두고 다양한 작업을 동시에 진행하는 방식
• Windows

운영체제 운용 기법

일괄 처리 시스템​

• 초기의 컴퓨터 시스템
• 일정량 또는 일정 기간 동안 데이터를 모아서 한꺼번에 처리하는 방식
• 일괄 처리를 위해 작업제어언어(JCL)을 제공
• 시스템 효율적 사용 가능
• 반환 시간이 늦지만 하나의 작업이 모든 자원을 독점하므로 CPU Idle Time이 줄어듦
• 급여 계산, 지불 계산, 연말 결산 등

다중 프로그래밍 시스템​

• 하나의 CPU와 주기억장치를 이용하여 여러 개의 프로그램을 동시에 처리하는 방식
• CPU 사용률과 처리량이 증가

시분할 시스템​

• Time Sharing System = Round Robin
• 여러 명의 사용자가 사용하는 시스템에서 컴퓨터가 사용자들의 프로그램을 번갈아가며 처리
• 여러 사용자가 각자의 컴퓨터로 동시에 운영체제와 대화하면서 프로그램 실행
• 하나의 CPU는 같은 시점에서 여러 개의 작업을 동시 수행이 안되기 때문에 CPU를 같은 작업 시간량으로 나눠서 그 시간량 동안 번갈아가면서 CPU를 사용
• 작업시간량 : Time Slice = Quantum
• 다중 프로그래밍 방식과 결합하여 모든 작업이 동시에 진행되는 것처럼 대화식 처리 가능
• 시스템 전체 효율은 좋으나 사용자는 반응 속도가 느려질 수 있음

다중 처리 시스템​

• 여러 개의 CPU와 하나의 주기억장치를 이용하여 여러 개의 프로그램을 동시에 처리하는 방식
• 여러 CPU는 하나의 메모리를 공유하며 단일 운영체제에 의해 관리
• 프로그램의 처리 속도는 빠르지만 기억장치, 입출력장치 등의 자원 공유에 대한 문제점을 해결해야함

실시간 처리 시스템​

• 데이터 발생 즉시 처리하여 결과를 산출
• 처리시간이 단축되고 처리비용이 절감
• 우주선, 교통제어, 레이더, 핵실험, 데이터수집, 전화교환장치, 인터넷뱅킹 등 시간에 제한을 두고 수행되어야하는 작업

다중 모드 처리​

• 일괄처리, 시분할, 다중처리, 실시간처리를 한 시스템에서 모두 제공하는 방식

분산 처리 시스템​

• Distributed Processing System
• 여러 개의 컴퓨터를 통신 회선으로 연결하여 하나의 작업을 처리하는 방식
• 각 단말은 고유의 운영체제와 CPU, 메모리를 가진다.

발달과정​

• 1세데 : 일괄처리
• 2세대 : 다중프로그래밍, 다중처리, 시분할, 실시간
• 3세대 : 다중모드
• 4세대 : 분산처리

컴파일러와 인터프리터

고급언어로 작성된 원시프로그램을 목적프로그램으로 번역하는 번역프로그램

저급 언어​

기계어​

• 컴퓨터가 직접 이해할 수 있는 언어
• 기종마다 기계어가 다르므로 언어의 호환성이 없음

어셈블리어​

• 기계어와 1:1 대응되는 기호로 이루어진 언어
• 니모닉 언어 = Mnemonic = 상징어
• 하드웨어 제어에 주로 사용
• 언어의 호환성이 없음
• 어셈블러를 사용하여 기계어로 번역해야 됨

고급 언어​

• 컴파일러 언어
• 자연어와 비슷한 형태 및 구조
• 하드웨어 지식이 없어도 작성 가능
• 기계어로 번역하기 위해 컴파일러나 인터프리터가 사용
• C, BASIC, COBOL, ALGOL 등

컴파일러​

• 고급언어로 작성된 프로그램 전체를 목적 프로그램으로 번역한 후 링킹 작업을 통해 실행 프로그램을 생헝
• 번역과 실행과정을 거쳐야하기 때문에 번역 과정이 번거로움
• 번역 시간이 오래걸림
• 한번 번역 후에는 다시 번역하지 않아 실행속도는 빠름
• C, C++, FORTRAN, COBOL, PL/1
• 대부분의 언어는 컴파일러로 변환된다.

인터프리터​

• 고급 언어로 작성된 프로그램을 한 줄 단위로 받아들여 번역
• 번역과 동시에 프로그램을 한 줄 단위로 즉시 실행
• 프로그램이 직접 실행되므로 목적프로그램이 생성되지 않음
• 시분할 시스템에 유용
• 원시 프로그램에 변화에 대한 반응이 빠름
• 번역 속도는 빠르지만 실행속도는 느림
• BASIC, SNOBOL, LISP, APL
• CPU의 시간낭비가 크다.

어셈블리어

• 사용자가 이해하기 어려운 기계어 대신에 명령 기능을 쉽게 연상할 수 있는 기호를 기계어와 1:1 대응시켜 코드화한 기호 언어
• 어셈블리어로 작성한 원이프로그램은 어셈블러를 통해 목적 프로그램으로 어셈블하는 과정을 거쳐야한다.
• 사용자가 프로그램을 쉽게 읽고 이해할 수 있다.
• 프로그램에 기호화된 명령 및 주소를 사용한다.
• CPU마다 사용되는 어셈블리어가 다르다.
• 의사명령과 실행명령으로 구분

형식​

Label, OP, Operand

• Label : 데이터를 기억할 장소 또는 분기할 위치, 기호 상수에 대한 Symbol을 기술하는 부분으로 생략할 수 있다.
• OP : OPCode를 기술하는 부분
• Operand : OPCode가 연산을 수행하기 위한 대상인 상수, 데이터나 주소, 레지스터 번호를 기술하는 부분

어셈블러​

• 어셈블리어로 작성된 걸 기계어로 번역하는 프로그램
• 이중 패스 어셈블러르 사용하면 정의되지 않은 기호를 사용할 수 있다.
• 현재 대부분 이중 패스 어셈블러를 사용한다.
• 두 개의 패스를 사용하면 기호를 정의하기 전에 사용할 수 있는 프로그램 작업이 용이하다.
• 단일 패스 어셈블러 : 원시 프로그램을 하나의 명령문씩 읽는 즉시 기계어로 번역하여 목적 프로그램을 만듦
• 이중 패스 어셈블러 : 원시 프로그램을 끝까지 읽어서 1단계 작업을 수행한 후 다시 처음부터 읽어나가면서 1단계에서 수행한 결과를 이용해 완전한 목적프로그램을 만듦
• 크로스 어셈블러 : 현재 사용하는 컴퓨터와 다른 명령 형태로 동작하는 컴퓨터에서 사용할 프로그램을 어셈블 할 때 사용하므로 실행시킬 컴퓨터에 맞게 목적 프로그램을 생성

구성​

• 기계 명령어 테이블
  • Machin Operation Table = MOT
  • 어셈블리어의 실행 명령에 대응하는 기계어에 대한 정보를 가지고 있는 테이블
  • 어셈블러에 기본적으로 포함
• 의사 명령어 테이블
  • Pseudo Operation Table = POT
  • 의사 명령과 그 명령을 처리하는 실행 루틴의 주소를 가지고 있는 테이블
  • 어셈블러에 기본적으로 포함
• 기호 테이블
  • Symbol Table = ST
  • 원시 프로그램의 Label 부분에 있는 기호들을 모두 차례대로 저장하는 테이블
• 리터럴 테이블
  • Literal Table = LT
  • 원시 프로그램의 Operand 부분에 있는 리터럴을 차례로 저장하는 테이블

Pass-1 Pass-2​

• Pass-1
  • 기호와 리터럴을 정의
  • 기계 명령어의 길이 정의
  • 위치 계수기(PC, LC) 관리
  • 기호들의 값을 심볼 테이블에 기억
  • 사용된 리터럴을 리터럴 테이블에 기억
  • 해당하는 의사 명령어 처리
  • 사용 관련 DB : 원시 프로그램, Program Counter, MOT, POT, ST, LT
• Pass-2
  • 기호 번지에 대한 상대 번지를 생성
  • 목적 프로그램 생성
  • 기계 명령어 생성
  • 심볼 테이블에서 기호의 값을 찾음
  • 의사 명령어 처리
  • 리터럴 발생
  • 사용 관련 DB : 원시 프로그램의 사본, Program Counter, Pass-1에서 만든 ST, LT, MOT, POT, 베이스 레지스터 테이블, PRINT LINE, 목적 프로그램

매크로

• 일종의 부 프로그램 = 개방 서브루틴
• 프로그램 작성시 한 프로그램에서 동일한 코드가 반복될 경우 반복되는 코드를 한 번만 작성하여 이름을 정의하고 피료시에 정의된 이름을 호출하여 사용
• 호출된 횟수만큼 정의된 매크로 코드가 해당 위치에 삽입되어 실행
• 매크로 내에 매크로 사용 가능
• 사용자의 반복적인 코드 입력을 줄여준다.
• 프로그램 내에서 매크로 코드를 확인할 수 있음

부프로그램과 비교​

매크로 프로세서​

• 원시프로그램에 존재하는 매크로 호출 부분에 매크로를 삽입하여 확장된 원시 프로그램을 생성하는 시스템 소프트웨어
• 처리과정
  • 매크로 정의 인식
  • 매크로 정의 저장
  • 매크로 호출 인식
  • 매크로 확장과 매개변수 치환

링커

• 연결 편집기
• 언어 번역 프로그램이 생성한 목적 프로그램과 라이브러리, 또 다른 실행 프로그램 등을 연결하여 실행 가능한 로드 모듈을 만드는 시스템 소프트웨어
• 연결 기능만 수행하는 로더의 한 형태

로더

• 컴퓨터 내부로 정보를 들여오거나 로드 모듈을 보조기억장치로부터 주기억장치에 적재하는 시스템 소프트웨어

기능​

• 할당 : Allocation 실행 프로그램을 실행시키기 위해 기억장치 내에 옮길 공간을 확보하는 기능
• 연결 : Linking 부 프로그램 호출 시 그 부 프로그램이 할당된 기억장소의 시작주소를 호출한 부분에 등록하여 연결하는 기능
• 재배치 : Relocation 기억장소의 실제 주소로 배치시키는 기능
• 적재 : Loading 실행 프로그램을 할당된 기억공간에 실제로 옮기는 기능

종류​

Compile And Go 로더​

• 별도의 로더 없이 언어 번역 프로그램이 로더의 기능까지 수행
• 연결 기능은 수행하지 않는다.
• 할당, 재배치, 적재 작업을 모두 언어 번역 프로그램이 담당

절대 로더​

• Absolute Loader

• 절대적으로 로딩(적재)만 하는 로더

• 목적 프로그램을 기억장소에 적지시키는 기능만 수행하는 로더

• 로더 중 가장 간단한 프로그램으로 구성

• 기억장소 할당이나 연결을 프로그래머가 직접 지정

• 한번 지정한 주기억장소의 위치는 변경이 어려움

• 절대로더의 기능별 행위 주체

  • 할당 : 프로그래머
  • 연결 : 프로그래머
  • 재배치 : 언어 번역 프로그램
  • 적재 : 로더

직접 연결 로더​

• Direct Linking Loader = Relocation Loader = Relative Loader = 재배치로더 = 상대로더
• 일반적인 기능의 로더로 로더의 기본 네 가지 기능을 모두 수행

동적 적대 로더​

• Dynamic Loading Loader = 호출 시 적재 로더
• 프로그램을 실행시 필요한 부분만을 적재하고 나머지는 보조기억장치에 저장
• 프로그램 크기가 주기억장치의 크기보다 큰 경우에 사용

프로세스

• 프로세서에 의해 처리되는 실행중인 프로그램
• 작업 = 태스크
• PCB를 가진 프로그램
• 실기억장치에 저장된 프로그램
• 프로세서가 할다오디는 실체로 디스패치가 가능한 단위
• 프로시저가 활동중인 것
• 비동기적 행위를 일으키는 주체
• 지정된 결과를 얻기 위한 일련의 계통적 동작
• 목적 또는 결과에 따라 발생되는 사건들의 과정
• 운영체제가 관리하는 실행 단위

PCB​

• Process Control Block = 프로세스 제어 블록 = Task Control Block = Job Control Block
• 운영체제가 프로세스에 대한 중요한 정보를 저장해 놓는 곳
• 각 프로세스가 생성될 때마다 고유의 PCB가 생성
• 프로세스가 완료되면 PCB는 제거됨
• PCB에 저장된 정보
  • 프로세스의 현재 상태
  • 포인터
    • 부모 프로세스에 대한 포인터
    • 자식 프로세스에 대한 포인터
    • 프로세스가 위치한 메모리에 대한 포인터
    • 할당된 자원에 대한 포인터
  • 프로세스 고유 식별자
  • 스케쥴링 및 프로세스의 우선순위
  • CPU 레지스터 정보 : AC, IR, PC, 범용 레지스터
  • 주기억 장치 관리 정보 : Base Register, Page Table
  • 입출력 상태 정보
  • 계정 정보 : CPU 사용시간, 실제 사용시간, 한정된 시간

프로세스 상태​

• 제출 : Submit 사용자가 작업을 시스템에 제출한 상태
• 접수 : Hold 작업이 스풀공간인 디스크의 할당 위치에 저장된 상태
• 준비 : Ready
  • 프로세스가 프로세서를 할당 받기 위해 기다리고 있는 상태
  • 프로세스는 준비상태 큐(스케쥴링 큐)에서 실행을 준비
  • 접수 상태에서 준비상태로의 전이는 Job Scheduler에 의해 수행
• 실행 : Run
  • 준비상태 큐에 있는 프로세스가 프로세서를 할당받아 실행되는 상태
  • 할당 시간이 종료되면 프로세스는 준비상태로 전이
  • 실행중인 프로세스에 I/O처리가 필요하면 실행중인 프로세스는 대기상태로 전이
  • 준비 상태에서 실행상태로의 전이는 CPU Scheduler에 의해 수행
• 대기, 보류, 블록: 프로세스에 I/O처리가 필요하면 현재 실행 중인 프로세스가 중단되고 I/O처리가 완료될 때까지 대기하는 상태
• 종료 : Terminated, Exit 프로세스 실행이 끝나고 프로세스 할당이 해제된 상태
• 실행중지 : Suspend
• 하나의 프로세스가 입출력 이외의 다른 이유에 의해 실행되지 못하는 상태
• 실행중지된 프로세스는 다른 프로세스로 다시 시작하기 전에는 실행될 수 없다.
• 시스템에 이상이 있거나 부하가 많을 경우 운영체제 필요에 의해 중지
• 프로세스의 이상유무를 확인하기 위해 해당 프로세스를 완전히 종료하지 않고 중지

상태 용어​

• Dispatch : 준비상태에서 대기하고 있는 프로세스 중 하나가 프로세서를 할당받아 실행 상태로 전이되는 과정
• Wake Up : 입출력 작업이 완료되어 프로세스가 대기 상태에서 준비상태로 전이되는 과정
• Traffic Controller : 프로세스의 상태에 대한 조사와 통보 담당

스레드​

• 프로세스의 작업 단위로서 시스템의 여러 자원을 할당받아 실행하는 프로그램 단위
• 프로세스의 일부 특성을 가지고 있지 때문에 경량 프로세스라고 한다.
• 독립적인 스케쥴링의 최소 단위
• 동일 프로세스 환경에서 서로 독립적인 다중 수행 가능
• 병행성 증진
• 처리율 향상
• 응답시간 단축
• 기억장소 낭비 줄어듦
• 프로세스 간 통신 향상
• 공통적으로 접근 가능한 기억장치를 통해 효율적으로 통신

사용자 수준의 스레드​

• 사용자가 만든 라이브러리를 사용하여 스레드 운용
• 속도는 빠르지만 구현이 어려움

커널 수준의 스레드​

• 운영체제 커널에 의해 스레드 운용
• 구현 쉽지만 속도가 느림

스케쥴링

• 프로세스가 생성되어 실행될 때 필요한 시스템의 여러 자원을 해당 프로세스에게 할당하는 작업
• 장기 스케쥴링 : 어떤 프로세스가 시스템의 자원을 차지할 수 있도록 할 것인가를 결정하여 준비상태 큐로 보내는 작업
• 중기 스케쥴링 : 어떤 프로세스들이 CPU를 할당받을 것인지 결정하는 작업
• 단기 스케쥴링 : 프로세스가 실행되기 위해 CPU를 할당받는 시기와 특정 프로세스를 지정하는 작업
• 문맥교환 : 하나의 프로세스에서 다른 프로세스로 CPU가 할당되는 과정에서 발생되는 것으로 새로운 프로세스에 CPU를 할당하기 위해 현재 할당된 프로세스의 상태를 저장하고 새로운 프로세스의 상태정보를 설정한 후 CPU를 할당하여 실행되도록 하는 작업

목적​

스케쥴링은 PCU나 자원을 효율적으로 사용하기 위한 정책

• 공정성
• 처리율 증가
• CPU 이용률 증가
• 우선순위 제도 : 우선순위가 높은 프로세스 먼저 실행
• 오버헤드 최소화
• 응답시간 최소화
• 반환시간 최소화
• 대시시간 최소화
• 균형 있는 자원의 사용
• 무한 연기 회피

성능 평가 기준​

• CPU 이용률
• 처리율
• 반환시간
• 대기시간
• 응답시간

비선점 스케쥴링​

• Non-preemptive
• 이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케쥴링 기법
• 프로세스가 CPU를 할당받으면 해당 프로세스가 완료될 때까지 CPU를 사용
• 모든 프로세스에 대한 요구를 공정하게 처리 가능
• 응답 시간 예측이 용이
• 일괄 처리 방식에 적합
• 짧은 작업이 긴 작업을 기다리는 경우가 발생
• FCFS, SJF, 우선순위, HRN, 기한부 알고리즘

선점 스케쥴링​

• Preemptive
• 하나의 프로세스가 CPU를 할당받아 실행하고 있을 때 우선순위가 높은 다른 프로세스가 CPU를 빼앗아 사용할 수 있는 스케쥴링 기법
• 우선순위가 높은 프로세스를 빠르게 처리 가능
• 시분할 시스템에 사용
• 많은 오버헤드 초래
• 인터럽트용 타이머 클록이 필요
• RR, SRT, 선점우선순위, 다단계 큐, 다단계 피드백 큐 알고리즘

비선점 스케쥴링

FCFS​

• FIFO
• 짧은 작업이 긴 작업을 기다리는 경우가 생김
• 가장 간단한 알고리즘

SJF​

• Shortest Job First = 단기 작업 우선
• 프로세스들 중에서 실행시간이 가장 짧은 프로세스에게 먼저 CPU를 할당
• 가장 적은 평균 대기시간을 제공하는 최적 알고리즘
• 실행시간이 긴 프로세스는 실행시간이 짧은 프로세스에게 할당 순위가 밀려 무한 연기 상태가 발생할 수 있음

HRN​

• 긴 프로세스에 불리한 SJF를 보완하기 위한 것
• 대기 시간과 서비스 실행 시간을 이용하는 기법
• 서비스 실행 시간이 짧거나 대기 시간이 긴 프로세스일 경우 우선순위가 높아진다.
• 우선순위 = (대기시간 + 서비스시간) / 서비스 시간

기한부​

• Deadline
• 일정한 시간을 주고 그 시간안에 프로세스를 완료하도록 하는 기법
• 프로세스가 제한시간 안에 완료되지 않을 경우 제거되거나 처음부터 다시 실행해야함
• 프로세스 실행 시 집중적으로 요구되는 자원관리에 오버헤드가 발생

우선순위​

• Priority
• 준비상태 큐에서 기다리는 각 프로세스마다 우선순위를 부여하여 그 중 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법
• 우선순위가 동일할 경우 FCFS 기법으로 CPU 할당
• 가장 낮은 순위를 부여받은 프로세스는 무한연기 또는 기아상태가 발생

에이징​

• Aging
• 특정 프로세스의 우선순위가 낮아 무한정 기다리게 되는 경우 기다린 시간에 비례하여 일정 시간이 지나면 우선순위를 한 단계씩 높여 가까운 시간에 자원을 할당받도록하는 기법
• SJF나 우선순위 기법에서 발생하는 무한연기, 기아상태를 예방

선점 스케쥴링

선점 우선순위​

• 준비상태 큐의 프로세스 중에서 우선순위가 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법
• 준비상태 큐에 새로 들어온 프로세스의 우선순위가 높을 경우 현재 프로세스를 보류하고 새로운 프로세스를 실행

SRT​

• Shortest Remaining Time = 선점 SJF 기법
• 비선점 스케쥴링인 SJF기법을 선점으로 변경
• 시분할 시스템에 유용
• 오버헤드 증가

RR​

• Round Robin
• 시분할 시스템을 위해 고안
• FCFS를 선점형태로 변경
• 시간할당량 동안만 실행 후 실행이 완료되지 않으면 다음 프로세스에게 CPU를 넘겨주고 준비상태 큐의 가장 뒤로 배치
• 할당시간이 큰 경우 FCFS와 같음
• 할당시간이 작을 경우 문맥교환 및 오버헤드가 자주 발생되 요청 작업을 신속히 처리 불가
• 할당되는 시간의 크기가 작으면 작은 프로세스에 유리
• 대기시간 : 구하고자하는 프로세스의 가장 마지막 실행이 시작되기 전까지의 진행시간을 구하고 해당 프로세스가 앞에서 실행되었을 경우 그 시간을 뺀다.

다단계 큐​

• MQ = Multi-level Queue
• 프로세스를 특정 그룹으로 분류할 수 있을경우 그룹에 따라 각기 다른 준비상태 큐를 사용하는 기법
• 우선순위에 따라 시스템 프로세스, 대화형 프로세스, 편집 프로세스, 일괄 처리 프로세스 등으로 나누어 큐를 배치
• 각 큐는 독자적인 스케쥴링을 가지고 있어 그룹의 특성에 따라 다른 스케쥴링 기법 사용 가능
• 각 큐가 준비상태로 들어간 경우 달느 준비상태 큐로 이동할 수 없음
• 하위 단계 큐를 실행 중이라도 상위 단계 큐에 프로세스가 들어오면 상위단계에게 CPU를 할당

다단계 피드백 큐​

• MFQ = Multi-level Feedback Queue
• 다단계 큐 기법에서 준비상태 큐 사이를 이동할 수 있게 개선
• 적응 기법(Adaptive Mechanism)의 개념을 적용
• 각 준비상태 큐마다 시간할당량을 부여해서 완료하지 못한 프로세스는 다음 단계의 준비상태 큐로 이동
• 상위 단계 큐일수록 우선순위가 높고 시간할당량이 적다.
• 요구 시간이 적은 프로세스, I/O 프로세스, 오래 기다린 프로세스를 기준으로 높은 우선순위를 할당
• 하위 단계 큐를 실행 중이라도 상위 단계 큐에 프로세스가 들어오면 상위단계에게 CPU를 할당, 마지막 단계 큐에선 작업이 완료될 때까지 RR 사용

병행 프로세스

두 개 이상의 프로세스들이 동시에 존재하며 실행상태에 있는 것

임계구역​

• 다중 프로그래밍 운영체제에서 여러 개의 프로세스가 공유한 데이터 및 자원에 대해 어느 한 시점에는 하나의 프로세스만 데이터 또는 자원을 사용하도록 지정된 공유 자원영역
• 하나의 프로세스만 접근할 수 있고 해당 프로세스가 자원을 반납한 후 에만 다른 프로세스가 자원이나 데이터를 사용할 수 있다.
• 특정 프로세스가 독점할 수 없다.
• 수행 중인 프로세스는 인터럽트가 불가능하다.
• 임계 구역 내의 작업은 신속하게 이루어져야 한다.
• 프로세스가 임계 구역에 대한 진입을 요청하면 일정 시간 내에 진입을 허락해야한다.
• Critical Section
• 임계구역은 화장실에 비유해 기억하자

상호 배제 기법​

• 특정 프로세스가 공유 자원을 사용하고 있을 경우 다른 프로세스가 해당 공유 자원을 사용하지 못하게 제어하는 기법

• 임계 구역을 유지하는 기법

• 소프트웨어적 구현

  • 두 개 프로세스 기준 : Dekker, Peterson 알고리즘
  • 여러 개의 프로세스 기준 : Lamport의 빵집 알고리즘

• 하드웨어적 구현 : Test & Set 기법, Swap 명령어 기법

동기화 기법​

두 개 이상의 프로세스를 한 시점에서는 동시에 처리할 수 없으므로 각 프로세스에 대한 처리 순서를 결정하는 것으로 상호 배제의 한 형태

세마포어​

• Semaphore = 신호기 = 깃발
• 각 프로세스에 제어 신호를 전달하여 순서대로 작업을 수행하도록 하는 기법
• E.J.Dijkstra가 제안
• P와 V라는 두 개의 연산에 의해서 동기화를 유지시키고 상호 배제의 원리를 보장
• S는 P와 V 연산으로만 접근 가능한 세마포어 변수로 공유 자원의 개수를 나타내며 0과 1혹은 0과 양의 값을 가질 수 있다.
• 다른 프로세스가 이미 자원을 점유한 상태라면 자원을 사용할 수 있을 때까지 기다린다.
• 순서
  • P : While S <= 0 Do skip;
  • S = S - 1;
  • V : S = S + 1;

모니터​

• Monitor
• 동기화를 구현하기 위한 특수 프로그램 기법
• 특정 공유 자원을 프로세스에게 할당하는데 필요한 데이터와 이 데이터를 처리하는 프로시저로 구성
• 자료 추상화와 정보 은폐 개념을 기초
• 공유 자원을 할당하기 위한 병행성 구조
• 모니터 내의 공유자원을 사용하려면 프로세스는 반드시 모니터 진입부를 호출해야함
• 외부 프로시저는 직접 액세스할 수 없음
• 모니터 경계에서 상호배제가 시행
• 한 순간에 하나의 프로세스만 진입하여 자원을 사용
• Wait와 Signal 연산 사용

교착상태

• Dead Lock
• 상호 배제에 의해 나타나는 문제점
• 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상

필요 충분 조건​

교착상태가 되려면 이 조건들이 모두 충족되어야함

• 상호 배제 : Mutual Exclusion 한 번에 한 개의 프로세스만이 공유 자원을 사용할 수 있어야 한다.
• 점유와 대기 : Hold & Wait 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다.
• 비선점 : Non-preemption 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 한다.
• 환형 대기 : Circular Wait 공유 자원과 공유 자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어 자신에게 할당된 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구해야 한다.

예방기법​

• 교착상태가 발생하지 않도록 사전에 시스템을 제어하는 방법
• 교착상태 발생의 네 가지 조건 중에서 어느 하나를 제거함으로 수행
• 자원의 낭비가 가장 심한 기법
• 상호 배제 부정 : 한 번에 여러 개의 프로세스가 공유 자원을 사용할 수 있도록 한다, 실제로는 구현하지 않음
• 점유 대기 부정 : 프로세스가 실행되기 전 필요한 모든 자원을 할당하여 프로세스 대기를 없애거나 자원이 점유되지 않은 상태에서만 자원을 요구하도록 한다.
• 비선점 부정 : 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고 요구한 자원을 사용하기 위해 기다리게 한다.
• 환형 대기 부정 : 자원을 선형 순서로 분류하여 고유 번호를 할당하고 각 프로세스는 현재 점유한 자원의 고유 번호보다 앞이나 뒤 어느 한 방향으로만 자원을 요구하도록 한다.

회피기법​

교착상태가 발생할 가능성을 배제하지 않고 교착상태가 발생하면 적절히 피해나가는 방법

은행원 알고리즘​

• E.J.Dijkstra가 제안한 것
• 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는 데서 유래
• 각 프로세스에게 자원을 할당하여 교착상태가 발생하지 않음
• 모든 프로세스가 완료될 수 있는 상태를 안전 상태
• 교착상태가 발생할 수 있는 상태를 불안전 상태 (불안전 상태라고해서 모두 교착상태는 아님)
• 적용하기 위해선 자원의 양과 프로세스 수가 일정해야 한다.
• 프로세스의 모든 요구를 유한한 시간 안에 할당하는 것을 보장

발견기법​

• 시스템에 교착상태가 발생했는지 점검하여 교착상태에 있는 프로세스와 자원을 발견하는 것
• 교착상태 발견 알고리즘과 자원할당 그래프 등을 사용

회복기법​

• 교착상태를 일으킨 프로세스를 종료하거나 교착상태의 프로세스에 할당된 자원을 선점하여 프로세스나 자원을 회복하는 것
• 프로세스 종료 : 교착상태에 있는 프로세스 종료
• 자원 선점 : 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하며 해당 프로세스를 일시 정지시키는 방법

기억장치 관리

상위 계층구조일 수록 접근 속도와 접근 시간이 빠르지만 기억용량이 적고 비싸다.

반입 전략​

• Fetch
• 보조기억장치에 보관중인 프로그램이나 데이터를 언제 주기억장치로 적재할 것인지를 결정하는 전략
• 요구 반입 : Demand Fetch 실행 중인 프로그램이 특정 프로그램이나 데이터 등의 참조를 요구할 때 적재
• 예상 반입 : Anticipatory Fetch 실행 중인 프로그램에 의해 참조될 프로그램이나 데이터를 미리 예상하여 적재

배치 전략​

• Placement
• 새로 반입되는 프로그램이나 데이터를 주기억장치의 어디에 위치시킬 것인지를 결정하는 전략
• 최초 적합 : First Fit 프로그램에 데이터가 들어갈 수 있는 크기의 빈 영역 중에 첫 번째 분할 영역에 배치
• 최적 적합 : Best Fit 프로그램이나 데이터가 들어갈 수 있는 크기의 빈 영역 중에서 단편화를 가장 작게 남기는 분할 영역에 배치
• 최악 적합 : Worst Fit 프로그램이나 데이터가 들어갈 수 있는 크기의 빈 영역 중에서 단편화를 가장 많이 남기는 분할 영역에 배치

교체 전략​

• 주기억장치의 모든 영역이 이미 사용중인 상태에서 새로운 프로그램이나 데이터를 주기억장치에 배치하려고 할 때, 이미 사용되고 있는 영역 중에서 어느 영역을 교체하여 사용할 것인지를 결정하는 전략
• FIFO, OPT, LRU, LFU, NUR, SCR

주기억장치 할당 기법

• 연속 할당 기법 : 프로그램을 주기억장치에 연속으로 할당하는 기법 (로딩)
  • 단일 분할 할당 기법 : 오버레이, 스와핑
  • 다중 분할 할당 기법 : 고정 분할 할당 기법, 동적 분할 할당 기법
• 분산 할당 기법 : 프로그램을 특정 단위의 조각으로 나누어 주기억장치 내에 분산하여 할당하는 기법
  • 페이징 기법
  • 세그먼테이션 기법

단일 분할 할당 기법​

• 주기억장치를 운영체제 영역과 사용자 영역으로 나누어 오직 한 명의 사용자만 주기억장치의 사용자 영역을 사용하는 기법
• 경계 레지스터가 사용된다.
• 오버레이 기법을 사용하면서 주기억장치보다 큰 사용자 프로그램을 실행할 수 있게 되었다.

오버레이 기법​

• 주기억장치보다 큰 사용자 프로그램을 실행하기 위한 기법
• 보조기억장치에 저장된 하나의 프로그램을 여러 개의 조각으로 분할한 후 필요한 조각을 차례로 주기억장치에 적재하여 프로그램을 실행한다.
• 불필요한 조각이 위치한 장소에 새로운 프로그램 조각을 중첩하여 적재
• 프로그램을 여러 개의 조각으로 분할하는 작업은 프로그래머가 수행하므로 시스템 구조나 프로그램 구조를 알아야함

스와핑 기법​

• 하나의 프로그램 전체를 주기억장치에 할당하여 사용하다 필요에 따라 다른 프로그램과 교체하는 기법
• 하나의 사용자 프로그램이 완료될 때까지 교체 과정을 여러 번 수행할 수 있다.
• 주기억장치 => 보조기억장치 이동을 Swap Out
• 보조기억장치 => 주기억장치 이동을 Swap In

다중 분할 할당 기법​

고정 분할 할당​

• Multiple contiguous Fixed partTition allocation = MFT = 정적 할당 = Static Allocation
• 프로그램을 할당하기 전에 운영체제가 주기억장치 사용자 영역을 여러 개의 고정된 크기로 분할하고 준비상태 큐에서 준비중인 프로그램을 각 영역에 할당하여 수행하는 기법
• 프로그램을 실행하려면 프로그램 전체가 주기억장치에 위치해야 한다.
• 프로그램이 분할된 영역보다 커서 영역 안에 못 들어가는 경우가 있다.
• 내부 단편화 및 외부 단편화 발생
• 다중 프로그래밍을 위해 사용되었으나 현재는 사용되지 않음

가변 분할 할당​

• Multiple contiguous Variable parTition allocation = MVT = 동적 할당 = Dynamic Allocation
• 고정 분할 할당 기법의 단편화를 줄이기 위한 것으로 프로그램을 주기억 장치에 적재하면서 필요한 만큼의 크기로 영역을 분할하는 기법
• 주기억장치를 효율적으로 사용 가능
• 다중 프로그래밍의 정도를 높일 수 있음
• 실행될 프로세스 크기에 대한 제약이 적음
• 단편화를 해결할 수 있으나 영역과 영역사이에 단편화가 발생할 수 있음

단편화

• 분할된 주기억 장치에 프로그램을 할당하고 반납하는 과정을 반복하면서 사용되지 않고 남는 기억장치의 빈 공간 조각
• 내부 단편화 : Internal Fragmentation 분할된 영역이 할당될 프로그램 크기보다 크기 때문에 남는 공간
• 외부 단편화 : External Fragmentation 분할된 영역이 할당될 프로그램 크기보다 작아 들어갈 수 없어 남는 공간

해결방법​

통합 기법​

• Coalescing
• 빈 공간이 다른 빈 공간과 인접되어 있는지 점검한 후 결합하여 사용

압축 기법​

• Compaction
• 분산되어 있는 단편화된 빈 공간을 결합하여 하나의 큰 공간을 만드는 작업
• 집약 = 가비지 컬렉션
• 분산된 단편화된 공간을 주기억 장치의 한 쪽 끝으로 옮긴 후 합침
• 압축이 실행되는 동안 시스템은 모든 일을 일시 중지
• 기억장소의 재배치
  • 압축기법을 수행시에 각 프로그램에 주어진 분할영역의 주소를 새롭게 지정해줘야한다.
  • Base Register와 Boundary Register를 사용한다.

가상기억장치

• 보조기억장치의 일부를 주기억장치처럼 사용하는 것
• 프로그램을 여러 개의 작은 블록으로 나눠서 가상기억장치에 보관하고 프로그램 실행시 요구되는 블록만 주기억장치에 불연속적으로 할당
• 주기억장치의 용량보다 큰 프로그램을 실행하기 위해 사용
• 주기억장치의 이용률과 다중 프로그래밍 효율 증대
• 단편화 해결
• 가상기억장치에 저장된 프로그램 실행시 주소변환 작업 필요
• 주소변환
  • 가상기억장이체 있는 프로그램이 주기억장치에 적재되어 실행될 때 논리적인 가상주소를 실기억주소로 변환하는 것
  • 주소 사상 = 주소 매핑
  • 인위적 연속성 : Artificial Contiguity 연속적인 가상주소가 반드시 연속적인 실기억주소로 변환되지 않아도 된다.
  • 가상주소는 보조기억장치에 있는 프로그램 상의 주소 = 논리 주소
  • 실기억주소는 주기억장치에 있는 기억공간의 주소 = 실주소

페이징 기법​

• 가상 기억장치에 보관되어 있는 프로그램과 주기억장치의 영역을 동일한 크기로 나눈 후 나눠진 프로그램(페이지)을 동일하게 나눠진 주기억장치의 영역(페이지 프레임)에 적재시켜 실행하는 기법
• 페이지 : 프로그램을 일정한 크기로 나눈 단위
• 페이지 프레임 : 페이지 크기로 일정하게 나눠진 주기억장치의 단위
• 외부 단편화는 발생하지 않으나 내부 단편화는 발생
• 주소 변환을 위해 페이지 위치정보를 가지고 있는 페이지 맵 테이블 필요
• 페이지 맵 테이블 사용으로 비용 증가, 처리속도 감소
• 일반적인 페이지 크기는 1~4KB
• 가상 주소는 페이지 번호와 실제 내용이 위치하고 있는 곳까지의 거리를 나타내는 변위값으로 구성
• 실기억주소는 페이지 프레임 번호와 프레임 내에서 실제 참조하는 위치까지의 거리를 나타내는 변위값으로 구성
• 페이지 맵 테이블은 주기억장치에 존재하는지의 여부를 나타내는 상태 비트와 보조기억장치 주소를 나타내는 디스크주소, 페이지가 주기억장치에 있을 때의 페이지 프레임 번호로 구성

Page Fault​

• 프로그램 실행시 참조한 페이지가 주기억장치에 없는 현상
• 처리 순서
  • 운영체제에서 트랩요청
  • 사용자 레지스트리와 프로그램 상태 저장
  • 현재 교체 가능한 페이지를 페이지 맵 테이블에서 검색
  • 가상기억장치에 있는 페이지를 주기억장치로 전달
  • 페이지 맵 테이블 갱신
  • 프로그램 상태를 불러와 이전 작업 진행

세그먼테이션 기법

• Segmentation
• 가상기억장치에 보관되어 있는 프로그램을 다양한 크기의 논리적인 단위로 나눈 후 주기억장치에 적재시켜 실행시키는 기법
• 각 세그먼트는 고유한 이름과 크기를 갖는다.
• 기억장치의 사용자 관점을 보존하는 기억장치 관리 기법이다.
• 기억공간을 절약하기 위해 사용한다.
• 주소변환을 위해서 세그먼트 맵 테이블이 필요
• 세그먼트가 주기억장치에 적재될 때 다른 세그먼트에게 할당된 영역을 침범할 수 없으며 이를 위해 기억장치 보호키가 필요
• 내부 단편화는 발생하지 않으나 외부 단편화는 발생
• 가상 주소는 세그먼트 번호와 세그먼트 내에 실제 내용이 위치하고 있는 곳까지의 거리를 나타내는 변위값으로 구성
• 실기억주소는 완전주소 형태이면 세그먼트 기분번지와 변위값을 더해서 구함
• 세그먼트 맵 테이블은 세그먼트 번호와 세그먼트 크기, 주기억장치 상의 기준번지로 구성

페이지 교체 알고리즘

• 페이지 부재가 발생했을 때 가상기억장치의 필요한 페이지를 주기억장치에 적재해야 하는데 주기억장치의 모든 페이지 프레임이 사용중이면 어떤 페이지 프레임을 선택하여 교체할 것인지를 결정하는 기법
• OPT ,FIFO, LRU, LFU, NUR, SCR

OPT​

• OPTimal replacement = 최적 교체
• 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법
• Belady가 제안
• 페이지 부재가 가장 적게 발생하는 효율적인 알고리즘
• 각 페이지의 호출 순서와 참조 상황을 예측해야하므로 실현 가능성이 없음

FIFO​

• 가장 오래 있었던 페이지를 교체하는 기법
• 이해하기 쉽고 프로그램이 및 설계가 간단
• 벨레이디의 모순 현상 발생 : 페이지 프레임 수를 증가시켰는데도 페이지 부재가 더 많이 일어나는 현상

LRU​

• Least Recently Used
• 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법
• 각 페이지마다 Counter나 Stack을 두어 체크한다.
• 별도의 하드웨어가 필요하며 시간적인 오버헤드가 발생한다.
• 실제로 구현하기가 매우 어렵다.

LFU​

• Least Frequently Used
• 사용 빈도가 가장 적은 페이지를 교체하는 기법
• 프로그램 실행 초기에 많이 사용된 페이지가 후에 사용되지 않을 경우에도 프레임을 계속 차지할 수 있다.

NUR​

• Not Used Recently
• LRU와 비슷한 알고리즘으로 최근에 사용하지 않은 페이지를 교체하는 기법
• 최근에 사용하지 않은 페이지는 나중에도 사용되지 않을 가능성이 높다는 것을 전제로, LRU에서 나타나는 시간적인 오버헤드를 줄일 수 있다.
• 각 페이지마다 참조 비트와 변형비트가 사용된다.
  • 참조비트 : 페이지가 호출되지 않았을 때는 0, 호출되었을 때는 1
  • 변형비트 : 페이지 내용이 변경되지 않았을 때는 0, 변경되었을 때는 1
• 참조비트와 변형비트 값에 따라 교체될 페이지의 순서가 결정된다.

SCR​

• Second Chance Replacement = 2차 기회 교체
• 가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 것
• FIFO의 단점을 보완한다.
• 각 페이지마다 참조 비트를 두고 0일경우 교체하고 1일 경우 참조 비트를 0으로 변경 후 FIFO 큐의 맨 마지막으로 이동시킨다.
• LRU처럼 참조 비트를 둔다.

가상기억장치 관리

페이지 크기​

페이지 크기가 작을 경우

• 페이지 단편화 감소
• 효율적인 워킹 셋 유지
• Locality에 더 일치하기 때문에 기억장치 효율이 높아짐
• 맵 테이블의 크기가 커지고 매핑 속도가 늦어짐
• 디스크 접근 횟수가 많아져서 전체적인 I/O 효율성 감소

페이지 크기가 클 경우

• 맵 테이블 크기가 작아지고 매핑 속도가 빨라짐
• 디스크 접근 횟수가 줄어들어 I/O 효율성이 증가
• 페이지 단편화가 증가
• 불필요한 내용까지 주기억장치에 적재될 수 있음

Locality​

• 국부성 = 지역성 = 구역성 = 국소성
• 프로세스가 실행되는 동안 주기억장치를 참조할 때 일부 페이지만 집중적으로 참조하는 성질이 있다는 이론
• 스레싱 방지를 위한 워킹 셋 이론의 기반
• 가상기억장치 관리의 이론적인 근거
• Denning 교수에 의해 구역성의 개념이 증명
• 캐시 메모리 시스템의 이론적 근거

시간 구역성​

• Temporal Locality
• 프로세스가 실행되면서 하나의 페이지를 일정 시간동안 집중적으로 액세스
• 한 번 참조한 페이지는 가까운 시간 내에 계속 참조할 가능성이 높음
• Loop, Stack, Sub Routine, Counting, 집계(Totaling)

공간 구역성​

• Spatial Locality
• 프로세스 실행 시 일정 위치의 페이지를 집중적으로 액세스하는 현상
• 어느 하나의 페이지를 참조하면 그 근처의 페이지를 계속 참조할 가능성이 높음을 의미
• 배열 순회, 순차적 코드 실행, 프로그래머가 변수를 서로 근처에 선언하여 할당되는 기억장소, 같은 영역에 있는 변수 참조할 때 사용

워킹 셋​

• 프로세스가 일정 시간 동안 자주 참조하는 페이지들의 집합
• Denning이 제안한 프로그램의 움직임에 대한 모델로 프로그램의 Locality 특징을 이용
• 워킹 셋을 주기억장치에 상주시킴으로 페이지 부재 및 페이지 교체 현상이 줄어들어 프로세스의 기억장치 사용이 안정
• 시간이 지남에 따라 자주 참조하는 페이지들의 집합이 변화하기 때문에 워킹셋은 시간에 따라 변경

페이지 부재 빈도 방식​

• 페이지 부재율에 따라 주기억장치에 있는 페이지 프레임의 수를 늘리거나 줄여 페이지 부재율을 적정 수준으로 유지하는 방식

프리페이징​

• 필요할 것 같은 모든 페이지를 한꺼번에 페이지 프레임에 적재하는 방식

스래싱​

• Thrashing
• 프로세스의 처리 시간보다 페이지 교체에 소요되는 시간이 더 많아지는 현상
• 다중 프로그래밍 시스템이나 가상기억장치를 사용하는 시스템에서 하나의 프로세스 수행 과정 중 자주 페이지 부재가 발생함으로써 나타나는 현상
• 다중 프로그래밍의 정도가 높아짐에 따라 CPU의 이용률은 어느 시점까지는 높아지지만, 더 높아질 경우 스래싱이 나타나고 CPU 이용률은 급격히 감소한다.

스래싱 방지​

• 다중 프로그래밍의 정도를 적정 수준으로 유지
• 페이지 부재 빈도를 조절하여 사용
• 워킹 셋을 유지
• 부족한 자원을 증설하고 일부 프로세스를 중단
• CPU 성능에 대한 자료의 지속적 관리 및 분석해 임계치를 예상하고 운영

디스크 스케쥴링

• 사용할 데이터가 디스크 상에 여러 곳에 저장되어 있을 경우 데이터를 액세스하기 위해 디스크 헤드가 움직이는 경로를 결정하는 기법
• 탐색시간을 최적화하기 위해 수행된다.
• 처리량 최대화
• 응답 시간 최소화
• 응답 시간 편차의 최소화

FCFS​

• FIFO
• 가장 간단한 스케쥴링으로 디스크 대기 큐에 먼저 들어온 순서로 실행
• 디스크 오버헤드가 적을 때 효율적
• 프로그래밍이 쉬움
• 헤드 이동거리가 상당히 길어질 수 있다.
• 디스크 오버헤드가 커지면 응답시간이 길어진다.
• 탐색 시간을 최적화하려는 시도가 없는 기법

SSTF​

• Short Seek Time First
• 탐색거리가 가장 짧은 트랙에 대한 요청을 먼저 서비스
• 현재 헤드 위치에서 가장 가까운 거리에 있는 트랙으로 헤드를 이동
• FCFS보다 처리량이 많고 평균 탐색 시간이 짧다.
• 일괄 처리 시스템에 유용
• 먼 거리의 트랙은 무한정 기다릴 수도 있음
• 응답 시간 편차가 크기 때문에 대화형 시스템에 부적합

SCAN​

• SSTF가 갖는 탐색 시간의 편차를 해소하기 위한 기법
• Denning이 개발, 대부분의 디스크 스케쥴링에서 기본 전략으로 이용
• 현재 헤드의 위치에서 진행방향이 결정되면 탐색 거리가 짧은 순서에 따라 그 방향의 모든 요청을 서비스하고, 끝까지 이동하면 역방향으로 요청 사항을 서비스
• 헤드가 이동하면서 새로운 요청이 서비스됨
• 현재 진행방향에 더 이상의 요청이 없을 때만 방향을 바꿈
• SSTF에서 발생하는 응답 시간의 편차 감소
• 오버헤드가 적을 경우 가장 효율적인 기법

C-SCAN​

• Cicular SCAN
• 항상 바깥쪽에서 안쪽으로 움직이면서 가장 짧은 탐색 거리를 갖는 요청을 서비스
• 헤드는 트랙 바깥쪽에서 안쪽으로 한 방향만 움직이며 서비스하여 끝까지 이동한 후 안쪽에 더 이상의 요청이 없으면 헤드는 가장 바깥쪽의 끝으로 이동한 후 다시 안쪽으로 이동하면서 요청을 서비스
• 처음과 마지막 트랙을 인접시킨 것과 같은 원형 형태로 디스크를 처리
• 새로운 요청이 도착하면 다음 헤드가 진행할 때 서비스
• 트랙 안쪽과 바깥쪽 요청에 대한 서비스가 공평

LOCK​

• SCAN 기법을 기초로 사용하되 마지막 요청을 서비스한 후 그 방향의 끝으로 이동하는 것이 아니라 바로 역방향으로 진행하는 기법

C-LOCK​

• C-SCAN 기법을 기초로 사용하되 바깥쪽에서 안쪽 방향의 모든 요청을 처리한 후 가장 바깥쪽 요청 트랙으로 이동한 후 안쪽 방향으로 요청을 서비스

N-SCAN​

• N-step SCAN
• SCAN 기법의 무한 대기 발생 가능성을 제거한 것
• 어떤 방향의 진행이 시작될 시에 대기 중이던 요청들만 서비스하고 진행 도중 들어온 요청은 한데 모아서 다음 반대 방향 진행 때 서비스하는 기법
• SSTF나 SCAN보다 응답시간의 편차가 적다.
• 특정 방향에 많은 수의 요청이 도착할 경우 반대 방향에서의 무한 지연 발생을 방지
• 진행도중 도착한 요청은 반대 방향 진행시 서비스하기 위해 디스크 대기 큐에 저장

Eschenbach​

• 에션바흐는 부하가 매우 큰 항공 예약 시스템을 위해 개발
• 탐색 시간과 회전 지연 시간을 최적화하기 위한 최초의 기법
• 헤드는 C-SCAN처럼 움직이며 모든 실린더는 그 실린더에 요청이 있던 없던 전체 트랙이 한 바퀴를 회전할 동안에 서비스를 받음

SLTF​

• Shortest Latency Time First = Sector Queuing
• 회전 지연 시간의 최적화를 위해 구현된 기법
• 드럼에서 사용

파일

• 사용자가 작성한 서로 관련 잇는 레코드의 집합체
• 프로그램 구성의 기본 단위며 보조기억장치에 저장
• 소멸성 : 파일을 추가하거나 제거하는 작업의 빈도수
• 활성률 : 프로그램이 한번 수행되는 동안 처리되는 레코드 수의 백분율
• 크기 : 파일에 저장되어 있는 정보량

파일 시스템​

• 파일의 저장, 액세스, 공유, 보호 등 보조기억장치에서의 파일을 총괄하는 파일 관리 기술
• 사용자와 보조기억장치 사이에서 인터페이스를 제공
• 사용자가 파일을 생성, 수정, 제거할 수 있도록 한다.
• 파일을 공동으로 사용할 수 있게 한다.
• 여러 종류의 액세스 제어방법 제공
• 사용자가 적합한 구조로 파일을 구성
• 파일의 예비와 복구 등의 기능 제공
• 사용자가 물리적 장치 이름 대신에 기호화된 이름을 사용할 수 있게 함
• 사용자가 파일을 편리하게 사용할 수 있도록 파일의 논리적 상태를 보여줘야함
• 파일을 안전하게 사용할 수 있도록하고 파일이 보호되어야함
• 파일 정보가 손실되지 않도록 데이터 무결성을 유지
• 파일 단위 작업 : Open Close Create Copy Destory Rename List
• 파일 내 레코드 단위 작업 : Read Write Update Insert Delete Search

파일 디스크립터​

• File Descriptor = 파일 서술자 = FCB = File Control Block = 파일 제어 블록
• 시스템이 필요로하는 파일에 대한 정보를 갖고 있는 제어블록
• 파일마다 독립적으로 존재
• 시스템에 따라 다른 구조를 가짐
• 보조기억장치 내에 저장되어 있다가 해당 파일이 열릴 때 주기억장치로 옮겨짐
• 파일 시스템이 관리하므로 사용자가 참조 불가
• 파일 디스크립터의 정보
  • 파일 이름 및 파일 크기
  • 보조기억장치에서의 파일 위치
  • 파일 구조 : 순차, 색인 순차, 색인 파일..
  • 보조기억장치의 유형
  • 액세스 제어 정보
  • 파일 유형 : 텍스트, 목적 프로그램...
  • 생성 날짜와 시간
  • 제거 날짜와 시간
  • 최종 수정 날짜와 시간
  • 액세스한 횟수

파일 구조

파일 접근 방법이라고도 한다.

순차 파일​

• Sequential File = 순서 파일 = 순차 접근 방식 = SAM = Sequential Access Method
• 레코드를 논리적인 처리 순서에 따라 연속된 물리적 저장공간에 기록하는 것
• 레코드들이 순차적으로 기록되어 판독할 때도 순차적으로 접근
• 자기 테이프를 모형화한 구조
• 일괄 처리에 적합한 구조
• 레코드를 삽입하거나 삭제하는 경우 파일 전체를 복사한 후 수행하므로 시간이 오래 걸림
  • 파일 전체를 복사
  • 복사된 파일을 대상으로 레코드를 특정 위치에 삽입하거나 삭제
  • 모든 레코드의 위치를 순차적으로 재배치
  • 재비치된 복사파일을 원래 파일로 저장

직접 파일​

• Direct File = 직접 접근 방식 = DAM = Direct Access Method
• 파일을 구성하는 레코드를 임의의 물리적 저장공간에 기록하는 것
• 레코드에 특정 기준으로 키가 할당
• 해싱 함수(사상함수)를 이용하여 이 키에 대한 보조기억장치의 물리적 상대 레코드 주소를 계산한 후 해당하는 주소에 레코드를 저장
• 레코드는 해싱 함수에 의해 계산된 물리적 주소를 통해 접근
• 임의 접근이 가능한 자기 디스크나 드럼을 사용
• 접근 시간이 빠르고 레코드의 삽입, 삭제, 갱신이 용이
• 레코드의 주소 변환 과정이 필요해 시간 소요
• 기억공간의 효율 저하
• 기억장치의 물리적 구조에 대한 지식 필요
• 프로그래밍이 복잡

색인 순차 파일​

• Indexed Sequential File = 색인 순차 접근 방식 = ISAM = Index Sequential Access Method
• 순차 파일과 직접 파일에서 지원하는 편성 방법이 결합된 형태
• 각 레코드를 키 값 순으로 논리적으로 저장하고 시스템은 각 레코드의 실제 주소가 저장된 색인을 관리
• 레코드 참조시 색인을 탐색한 후 색인이 가리키는 포인터를 사용하여 참조
• 자기디스크에서 많이 사용
• 자기테이프에서 사용 불가
• 순차처리나 임의처리가 모두 가능
• 효율적인 검색 가능하고 삽입 삭제 갱신이 용이
• 색인영역이나 오버플로 영역을 설정해야하므로 기억공간이 필요
• 색인을 이용하여 참조하기 때문에 접근 시간이 직접파일보다 느리다.

구성​

• 기본 영역 : Prime Area 실제 레코드가 기록되는 데이터 영역
• 색인 영역 : Index Area 레코드들의 위치를 찾아가는 색인이 기록되는 영역
• 오버플로 영역 : Overflow Area 예비로 확보해 둔 영역

분할파일​

• 하나의 파일을 여러 개로 분할하여 저장하는 형태
• 여러 개의 순차 서브파일로 구성된 파일
• 백업과 같이 하드디스크에 있는 내용을 테이프와 같은 보조기억장치에 저장할 때 사용
• 파일의 크기가 클 경우 사용

디렉터리 구조

1단계 디렉터리 구조​

• 단일 디렉터리 구조
• 모든 파일이 하나의 디렉터리 내에 위치하여 관리되는 구조
• 모든 파일들이 유일한 이름을 갖고 있어야함
• 모든 파일이 같은 디렉터리 내에 유지되므로 이해가 쉬움
• 파일이나 사용자의 수가 증가하면 파일 관리가 복잡
• 파일명은 일반적으로 내용과 관련된 이름을 사용
• 파일명의 길이는 시스템에 따라 제한을 받음

2단계 디렉터리 구조​

• 중앙에 마스터 파일 디렉터리(MFD)가 있고, 그 아래 사용자별 파일 디렉터리(UFD)가 있는 2계층 구조
• 마스터 파일 디렉터리는 각 사용자의 정보와 사용자 파일 디렉터리를 가리키는 포인터를 갖고 있으며 사용자 파일 디렉터리를 관리
• 사용자 파일 디렉터리는 오직 한 사용자가 갖고 있는 파일들에 대한 정보를 가짐
• 각 사용자는 다른 사용자의 파일 디렉터리를 검색할 수 없음
• 한 사용자 파일 디렉터리에서는 유일한 파일이름을 사용해야되나 서로 다른 사용자라면 동일한 파일이름을 사용할 수 있다.

트리 디렉터리 구조​

• 하나의 루트 디렉터리와 여러 개의 서브 디렉터리로 구성된 구조
• DOS, UNIX, Windows의 운영체제에서 사용되는 디렉터리 구조
• 디렉터리 탐색은 포인터를 사용

비순환 그래프 디렉터리 구조​

• 비주기 그래프 디렉터리 = Acyclic Graph Directory
• 하위 파일이나 하위 디렉터리를 공동으로 사용할 수 있는 것
• 사이클이 허용되지 않는 구조 = 하위 디렉터리가 상위 디렉터리나 상위 파일을 공유할 수 없다.
• 하나의 파일이나 디렉터리가 여러 개의 경로로 접근이 가능
• 디렉터리 구조가 복잡하고 시스템 성능이 저하됨
• 공유된 파일을 삭제할 경우 고아포인터(Dangling Pointer)가 발생

일반적인 그래프 디렉터리 구조​

• 트리 구조에 링크를 첨가시켜 사이클을 허용하는 그래프 구조
• 디렉터리와 파일 공유에 완전한 융통성
• 탐색 알고리즘이 간단하여 파일과 디렉터리를 액세스하기 쉬움
• 사용되지 않은 디스크 공간을 되찾기 위해 가비지 컬렉션이 필요
• 가비지 컬렉팅을 해야되기에 참조 계수기가 필요

디스크 공간 할당 방법

연속 할당​

• Contiguous Allocation
• 연속된 공간에 할당하는 방법으로 생성되는 파일의 크기만큼 공간이 있어야함
• 논리적으로 연속된 레코드가 물리적인 저장공간에도 연속적으로 저장됨
• 파일의 생성과 삭제가 반복되면 단편화 발생
• 단편화를 줄이기 위해 재배치에 의한 주기적인 압축이 필요
• 파일의 크기가 시간에 따라 변경될 경우 구현하기 어려움

불연속 할당​

• Non-Contiguous Allocation
• 디스크 공간을 일정 단위로 나누어 할당하는 기법

섹터 단위 할당​

• 하나의 파일이 디스크 섹터 단위로 분산되어 할당되는 방법
• 하나의 파일에 속하는 섹터들이 연결 리스트로 구성
• 디렉터리는 파일의 시작과 마지막 주소에 대한 정보만 가지고 있음
• 섹터 단위로 저장되므로 디스크 단편화가 발생되지 않음
• 파일의 크기만큼 연속된 공간이 없어도 저장 가능
• 레코드 검색시 파일이 속한 레코드를 순차적으로 검색해야 하므로 탐색시간이 오래 걸린다.
• 직접 접근이 불가능

블록 단위 할당​

• 하나의 파일이 연속된 여러 개의 섹터를 묶은 블록 단위로 할당되는 방법

블록 체인 기법​

• 할당 단위를 블록으로 구성하는 방법
• 하나의 블록은 러 개의 섹터로 구성
• 디렉터리는 파일의 첫 번째 블록을 가리키는 포인터를 가지고 있음
• 하나의 블록은 데이터와 다음 블록을 가리키는 포인터로 구성
• 삽입 삭제시 포인터만 수정하면 되므로 간단
• 순차적으로 탐색해야 되므로 속도가 느림

색인 블록 체인 기법​

• 인덱스 블록 체인 기법
• 파일이 할당된 블록의 모든 포인터를 색인 블록에 모아 직접 접근이 가능
• 디렉터리는 파일의 색인 블록에 대한 포인터를 갖고 있음
• 색인 블록의 포인터를 사용하여 직접 접근이 가능해 탐색 시간이 빠름
• 삽입시 색인 블록을 재구성

블록 지향 파일 사상 기법​

• 포인터 대신 파일 할당 테이블(File Allocation Table)에 있는 블록번호를 사용하는 기법
• 파일 할당 테이블에는 각 블록에 해당하는 항목이 있고 각 항목은 블록번호에 의해 색인된다.
• 블록 번호에 의해 색인된 테이블의 각 항목은 다음 블록의 블록번호를 가짐
• 디스크 구조의 특성상 블록번호는 실제 기억공간의 주소로 쉽게 변환 가능
• 데이터의 삽입 삭제가 용이
• 디렉터리는 파일 할당 테이블의 시작위치를 가지고 있음

자원 보호

• 불법적으로 접근하는 것을 제어
• 자원의 물리적인 손상을 예방하는 기법
• 접근 제어 행렬, 전역 테이블, 접근 제어 리스트, 권한(자격) 리스트

접근 제어 행렬 기법​

• Access Control Matrix
• 자원보호의 일반적인 모델
• 객체에 대한 접근 권한을 행렬로써 표시한 기법

전역 테이블 기법​

• Global Table
• 가장 단순한 구현 방법
• 세 개의 순서쌍인 영역, 개체, 접근 권한의 집합을 목록 형태로 구성
• 테이블이 매우 커서 주기억장치에 저장할 수 없으므로 가상기억장치 기법을 사용해야한다.
• 주기억장치에 저장될 경우 공간 낭비

접근 제어 리스트​

• Access Control List
• 접근 제어 행렬에 있는 각 열, 즉 객체를 중심으로 접근 리스트를 구성
• 각 객체에 대한 리스트는 영역, 접근권한의 순서쌍으로 구성되며 객체에 대한 접근 권한을 갖는 모든 영역을 정의

권한 리스트 기법​

• Capability List = 자격 리스트
• 접근 제어 행렬에 있는 각 행, 즉 영역을 중심으로 권한 리스트를 구성
• 권한 리스트는 영역과 결합되어 있지만 그 영역에서 수행중인 프로세스가 직접 접근할 수는 없다.
• 권한 리스트는 운영체제에 의해 유지되며 사용자에 의해 간접적으로만 접근이 되는 보호된 객체이기 때문

Lock-Key 기법​

• 접근 제어 리스트와 권한 리스트를 절충한 기법
• 객체는 Lock 영역은 Key라 불리는 유일 값을 가지고 있어 영역과 객체가 일치하는 경우만 해당 객체를 접근 가능

파일 보호 기법​

• 자원 보호 기법과 마찬가지로 파일에 대한 일방적인 접근과 손상 및 파괴를 방지하기 위함
• Naming, Password, Access Control
• 파일의 명명 : 접근하고자 하는 파일 이름을 모르는 사용자를 접근 대상에서 제외
• 비밀번호
• 접근 제어 : 공유 데이터에 접근할 수 있는 권한을 제어, 각 파일마다 접근 목록을 둔다.

보안

• 컴퓨터 시스템 내에 있는 프로그램과 데이터에 대해 통제된 접근 방식을 어떻게 제공할 것인가를 다루는 것
• 컴퓨터 시스템 내의 자원을 보호하고 대응하기 위한 일련의 정책과 행위
• 프로그램, 프로세스 또는 사용자의 허용된 권한 외의 접근을 제한

보안 요건​

• 기밀성 : Confidentiality 자원은 인가된 사용자에게만 접근이 허용, 노출되어도 데이터를 읽을 수 없음
• 무결성 : Integrity 오직 인가된 사용자만 수정 가능
• 가용성 : Availability 인가받은 사용자는 언제든 사용 가능
• 인증 : Authentication
• 부인 방지 : NonRepudiation 데이터를 송수신한 자가 송수신 사실을 부인할 수 없도록 송수신 증거 제공

보안 유지 기법​

• 외부 보안
  • 시설보안
  • 운용보안 : 사용자마다 인가된 등급 부여
• 사용자 인터페이스 보안 : 사용자의 신원 확인
• 내부 보안
  • 하드웨어나 운영체제에 내장된 보안 기능 사용
  • 하드웨어나 운영체제 내에 접근 제어 코드를 내장

보안 위험 감소 방법​

• 사용자 감시 : User Surveillance
• 위험 탐지 : Threat Monitoring
• 확충 : Amplification
• 패스워드 보호

정보 보안 기법

비밀키 시스템​

• Private Key System
• 동일한 키로 데이터를 암호화하고 복호화하는 대칭 암호화 기법
• 암/복호화의 속도가 빠르며 알고리즘이 단순
• 파일 크기가 작음
• 사용자가 많아지면 관리할 키의 수가 상대적으로 많아지고 키의 분배가 어려워짐
• DES (Data Encryption Standard)

공용키 시스템​

• Public Key System
• 서로 다른 키로 데이터를 암호화하고, 복호화하는 비대칭 암호화 기법
• 키의 분배가 용이하고 관리해야할 키의 개수가 적음
• 암/복호화 속도가 느리며 알고리즘이 복잡
• 파일의 크기가 큼
• RSA (Rivest Shamir Adleman)

디지털 서명 기법​

• Digital Signature Mechanism
• 고유의 전자 서명으로 송신자가 전자 문서 송신 사실을 부인할 수 없도록 함
• 작성 내용이 송수신 과정에서 변조된 사실이 없다는 것을 증명
• 공개키 암호화 기법을 사용

여분 정보 삽입 기법​

• Traffic Padding Mechanism
• 정상 데이터에 여분의 거짓 데이터를 삽입하여 불법적으로 데이터를 분석하는 공격을 방어하는 기법
• 삽입한 거짓 데이터가 정상 데이터와 구별이 되지 않아야함

인증 교환 기법​

• Authentication Exchange Mechanism
• 수신자가 메세지 전송 도중 변경되지 않았음을 확인할 수 있다.
• 메세지가 정당한 상대방으로부터 전달된 것을 확인할 수 있다.

접근 제어 기법​

• Access Control Mechanism
• 데이터에 접근이 허가된 사용자에게만 데이터 사용을 허용하는 정책을 강화하기 위해 사용

Fault Tolerant System​

• 고장 방지 시스템 = 결함 허용 시스템
• 시스템 부품 고장이나 프로그램에 버그가 있더라도 시스템 전체에 장애가 발생하지 않도록 시스템을 구성하는 방법
• Dual System : 같은 장치를 두 개로 구성하여 하나가 고장나면 다른 하나를 작동시켜 작업을 처리하는 시스템

다중 처리기

• Multi Processor
• 하나의 시스템에 여러 개의 처리기를 두어 하나의 작업을 각 처리기에게 할당하여 수행하도록 하는 것을 의미
• 강결합 시스템
• 실행시간이 감소되고 전체 효율을 향상
• 하나의 운영체제에 의해 전체 시스템이 제어
• 하나의 공통된 기억장소를 가짐
• 프로세서 중 하나가 고장 나도 다른 프로세서들에 의해 작업이 처리되므로 장애극복 가능
• 각 프로세서는 자체 계산능력을 가짐
• 프로세서나 주변장치 등을 공동으로 사용
• 주변장치가 기억장치에 연결되는 방식에 따라 시분할 및 공유버스, 크로스바 교환행렬, 하이퍼 큐브 방식으로 나뉨

시분할 및 공유 버스 연결 방식​

• 각종 장치들을 버스 하나로 연결한 방식
• 장치 연결이 단순하고 경제적이며 융통성이 있음
• 장치 추가 용이
• 한 시점에 하나의 전송만 가능
• 버스가 고장나면 시스템이 먹통
• 시스템 전체 전송량이 버스의 전송률에 의해 제한
• 장치들의 경쟁 상태가 발생하면 시스템 효율이 저하

크로스바 교환 행렬 연결 방식​

• 시분할 및 공유 버스 방식에서 버스의 수를 기억장치의 수만큼 증가시켜 연결한 방식
• 각 기억장치마다 다른 경로를 사용 가능
• 두 개의 서로 다른 기억장치를 동시에 참조
• 장치의 연결이 복잡

하이퍼 큐브 연결 방식​

• 다수의 프로세서들을 연결하는 방식으로 비교적 경제적
• 네 개의 프로세서를 두 개 씩 서로 이웃하게 연결한 사각형 모양의 2차원 하이퍼 큐브를 만들고, 여기에 대응점을 각각 연결하여 3차원 하이퍼 큐브를 형성하고.. 계속 늘린다.
• 다수의 프로세서를 연결할 수 있으며 확장성이 좋음
• 많은 프로세서를 연결시에 비용이 급속도로 증가
• 하나의 프로세서에 연결되는 다른 프로세서의 수가 (연결점) n개일 경우 프로세서는 총 2^n개가 필요

다중 포트 기억장치 연결 방식​

• 시분할 및 공유 버스방식과 크로스바 교환 행렬 방식을 혼합한 형태의 방식
• 많은 수의 프로세서를 쉽게 연결 가능
• 다양한 연결이 가능하다.
• 전송 시간이 비교적 느림

다중 처리기의 운영체제 구조

주종 처리기​

• Master / Slave 처리기
• 하나의 프로세서를 Master로 지정하고 나머지는 Slave로 지정하는 구조
• 주 프로세서가 고장나면 전체 시스템 먹통
• 주 프로세서만 입출력을 수행하므로 비대칭 구조
• 주 프로세서
  • 입출력과 연산 담당
  • 운영체제 수행
• 종 프로세서
  • 연산만 담당
  • 입출력발생시 주프로세서에 요청
  • 사용자 프로그램만 담당

분리 실행 처리기​

• 주/종처리기의 비대칭성을 보완하여 각 프로세서가 독자적인 운영체제를 가지고 있도록 구성
• 각 프로세서에서 발생하는 인터럽트는 해당 프로세서에서 해결
• 한 프로세서에 일이 밀려있어도 다른 프로세서는 유휴상태가 될 수 있다.

대칭적 처리기​

• 분리 실행 처리기를 보완하여 여러 프로세서들이 완전한 기능을 갖춘 하나의 운영체제를 공유하여 수행하는 구조
• 가장 복잡하지만 가장 강력함
• 여러 개의 프로세서가 동시에 수행 가능
• 모든 프로세서가 동등한 권한을 가짐
• 메모리와 입출력장치를 공유
• 프로세서간의 통신은 공유 메모리를 통해 이루어짐
• 공유된 장치를 사용할 때 대립문제가 발생하므로 대비책 필요
• 프로세서의 수를 늘려도 시스템 효율은 향상되지 않음

약결합 시스템​

• Loosely Coupled System = 분산 처리 시스템
• 각 프로세서마다 독립된 메모리를 가진 시스템
• 둘 이상의 독립된 컴퓨터 시스템을 통신망을 통해 연결한 시스템
• 각 시스템마다 독자적인 운영체제를 가짐
• 각 시스템마다 독자적인 운영이 가능하므로 프로세서간 결합력이 약함
• 프로세서 간 통신은 메세지 전달이나 원격 프로시져 호출을 통해 이뤄짐

강결합 시스템​

• Tightly Coupled System = 다중 처리 시스템 = 병렬 처리 시스템
• 동일 운영체제 하에서 여러 개의 프로세서가 하나의 메모리를 공유하여 사용하는 시스템
• 하나의 운영체제가 모든 프로세서와 시스템 하드웨어를 제어
• 프로세서 간의 통신은 공유 메모리를 통해 이뤄짐
• 하나의 메모리를 사용하므로 프로세서 간의 결합력이 강함
• 공유 메모리를 차지하는 프로세서 간의 경쟁을 최소화 해야함

분산 처리 시스템

• Distributed Processing System
• 약결합 시스템으로 독립적인 처리능력을 가진 컴퓨터 시스템을 통신망으로 연결한 시스템
• 사용자는 각 컴퓨터 위치를 몰라도 자원을 사용 가능
• 중앙 집중형 시스템에 비해 개발이 어려움
• 보안 문제 발생
• 시스템 유지상 통일성을 잃기 쉬움
• 시스템 설계가 복잡하고 데이터 처리 서비스의 질이 떨어짐

설계 목적​

• 자원 공유
• 연산 속도 향상
• 신뢰도 향상 : 여러 시스템 중 하나의 시스템에 오류가 발생해도 다른 시스템에서 처리 가능
• 컴퓨터 통신 : 지리적으로 멀어도 정보 교환 가능

투명성​

• Transparence
• 분산 처리 운영체제에서 구체적인 시스템 환경을 사용자가 알 수 없도록 함
• 환경을 알지 못해도 원하는 작업을 수행할 수 있도록 지원
• 자원의 위치나 정보가 변경되더라도 사용자가 이를 인식하지 못하게 함

종류​

• 위치 투명성 : 물리적 위치를 몰라도 자원에 접근 가능
• 이주 투명성 : 사용자나 응용 프로그램의 동작에 영향을 받지 않고 시스템 내에 있는 자원을 이동 가능
• 복제 투명성 : 자원의 복제를 사용자에게 통지할 필요 없이 자유로이 복제
• 병행 투명성 : 자원을 병행 처리하고 공유 가능
• 접근 투명성
• 성능 투명성 : 성능을 증가시키기 위해 시스템 재구성 가능
• 규모 투명성 : 시스템 구조나 알고리즘의 변경 없이 확장 가능
• 고장 투명성 : 고장이 나도 작업 가능

계층구조​

• 하드웨어 계층
• 기억장치 계층
• 프로세스 계층
• 파일시스템 계층
• 사용자 프로그램 계층

분산 파일 시스템​

• 여러 사이트에 분산되어 있는 서버, 장치, 사용자들에 대한 파일 서비스를 제공하는 시스템
• 분산 시스템이 통신망으로 연결되어 있으므로 파일 서비스는 여러 개의 기억장치에서 네트워크를 통해 이뤄짐
• 서로 다른 컴퓨터 사용자 간에 정보를 쉽게 공유 가능
• NFS : 선 마이크로 시스템에서 개발
• LoCUS : 캘리포니아 대에서 개발
• Andrew : 카네기 멜론 대학에서 개발

분산 처리 시스템 분류

위상에 따른 분류​

망형 - 완전 연결​

• Full Connection
• 각 사이트들이 시스템 내의 다른 모든 사이트와 직접 연결된 구조
• 사이트 수가 n개이면 링크 수는 n(n - 1) / 2
• 모든 사이트를 연결해야 하므로 기본비용은 많이 들지만 통신비용은 적다.
• 하나의 링크가 고장나도 다른 링크를 이요하므로 신뢰성이 높다.

망형 - 부분 연결​

• Partially Connection
• 시스템 내의 일부 사이트들 간에만 직접 연결하는 구조
• ㅈ기접 연결되지 않은 사이트는 연결된 타 사이트를 통해 통신

트리 또는 계층형​

• Tree, Hierarchy
• 분산 처리 시스템의 가장 대표적인 형태
• 각 사이트들이 트리 형태로 연결된 구조
• 부모 사이트의 자식 사이트는 그 부모 사이트를 통해 통신이 이뤄짐
• 부모 사이트가 고장나면 자식 사이트는 통신이 불가능

성형​

• 스타형
• 모든 사이트가 하나의 중앙 사이트에 직접 연결되어 있고 다른 사이트와는 연결되어 있지 않은 구조
• 기본 비용은 사이트 수에 비례하며 통신비용이 적다.
• 구조가 간단하고 보수 및 관리가 용이하다.
• 중앙 사이트가 고장나면 다 먹통
• 데이터 전송이 없는 사이트가 접속된 통신회선은 휴지 상태가 된다.

환형​

• 링형
• 시스템 내의 각 사이트가 인접하는 달느 두 사이트와만 직접 연결된 구조
• 정보는 단방향 또는 양방향으로 전달 가능
• 특정 사이트가 고장나면 통신이 불가능해짐

다중 접근 버스 연결​

• Multi Access Bus Connection
• 시스템 내의 모든 사이트들이 공유 버스에 연결된 구조
• 기본 비용은 사이트 수에 비례하고 통신 비용은 일반적으로 저렴

범위에 따른 분류​

LAN​

• 근거리 통신망
• 버스형이나 링형 사용

WAN​

• 광대역 통신망
• 국가-국가간 대륙-대륙간
• 일정 지역 사이트를 근거리 통신망으로 연결 후 각 근거리 통신망을 연결하는 방식

프로세서 모델에 따른 분류​

클라이언트/서버 모델​

• 클라이언트와 서버가 하나의 작업을 분산 협동 처리 하는 방식
• 프로그램의 모듈성과 융통성을 증대

프로세서 풀 모델​

• 하나 이상의 프로세서 풀과 여러 서버가 연결된 형태

혼합 모델​

• Hybrid Model
• 클라이언트/서버 모델과 프로세서 풀 모델을 혼합한 형태의 방식
• 사용자는 워크스테이션이나 단말기를 통해 시스템에 접근

운영체제에 따른 분류​

네트워크 운영체제​

• 독자적인 운영체제를 가지고 있는 시스템을 네트워크로 구성한 것
• 사용자가 원격 시스템으로 로그인하거나 원격 시스템으로부터 필요한 자원을 전달 받는 방식
• 사용자는 시스템의 각 장치에 대해 알고 있어야 함
• 지역적으로 멀리 떨어진 대규모 시스템에 사용
• 설계와 구현이 쉽다.
• 자원 공유가 번거로움

분산 운영체제​

• 하나의 운영체제가 모든 시스템 내의 자원을 관리하는 것
• 원격에 있는 자원을 마치 지역 자원인 것과 같이 쉽게 접근하여 사용하는 방식
• 사용이 편리하고 시스템 간 자원 공유가 용이
• 하나의 운영체제가 시스템 전체를 관리해야 하므로 설계와 구현이 어려움
• 요청한 컴퓨터에 요청된 컴퓨터의 자원이 이주됨으로 자원 사용 가능
• 데이터 이주
  • 데이터를 요청한 사용자의 컴퓨터로 해당 데이터의 복사본을 전송 시키는 방식
  • 사용자가 데이터가 필요하지 않을 경우 데이터의 복사본을 원래 컴퓨터로 돌려보냄
• 연산 이주
  • 요청한 데이터가 있는 컴퓨터에서 데이터를 처리하여 해당 결과를 요청한 컴퓨터에게 보내는 방식
  • 결과를 전송시키는 것
• 프로세스 이주 : 프로세스의 전체 또는 일부를 다른 컴퓨터에서 실행되도록 하는 방식

UNIX

• 서버 컴퓨터에서 사용되는 운영체제
• 시분할 시스템을 위해 설계된 대화식 운영체제
• 소스가 공개된 개방형 시스템
• 크기가 작고 이해하기 쉬움
• 이식성이 높고 프로세스 간 호환성이 높음
• Multi User, Multi Tasking
• 트리 구조의 파일 시스템
• 하나 이상의 작업을 백그라운드에서 수행하므로 여러 작업을 동시 처리 가능

구성​

• 하드웨어
• 커널
• 쉘
• 유틸리티
• 사용자

커널​

• UNIX의 핵심 부분
• 컴퓨터가 부팅될 때 주기억장치에 적재된 후 상주하면서 실행
• 하드웨어를 보호하고 프로그램과 하드웨어 간의 인터페이스 역할
• 프로세스 관리, 기억장치 관리, 파일 관리, 입출력 관리, 프로세스간 통신, 데이터 전송 및 변환

쉘​

• 사용자의 명령어를 인식하여 프로그램을 호출하고 명령을 수행하는 명령어 해석기
• 시스템과 사용자 간의 인터페이스 역할
• DOS의 COMMAND.COM과 같은 기능
• 보조기억장치에 명령어가 포함된 파일로 존재하며 교체처리가 가능
• 주기억장치에 상주하지 않는다.

유틸리티​

• 일반 사용자가 작성한 응용 프로그램을 처리하는데 사용
• 에디터, 컴파일러, 인터프리터, 디버거
• DOS의 외부명령어

프로세스간 통신​

• 각 프로세스는 시스템 호출을 통해 커널의 기능을 사용
• 프로세스 간 통신은 시그널, 파이프, 소켓 등을 사용
• 시그널 : 간단한 메세지를 이용하여 통신, 초기 UNIX
• 파이프 : 한 프로세스의 출력이 다른 프로세스의 입력으로 사용되는 단방향 통신
• 소켓 : 프로세스 간의 대화를 가능하게 하는 쌍방향 통신

UNIX 파일 시스템

파일 시스템​

• 트리 구조
• 디렉터리나 주변장치를 파일과 동일하게 취급
• 파일 생성 및 삭제, 보호 기능을 가짐
• 일반파일, 디렉터리파일, 특수파일 형식 제공

파일 시스템 구조​

• 디스크를 블록으로 분류하여 배치한 구조
• 부트 블록, 슈퍼블록, 아이노드 블록, 데이터 블록으로 구성
• 부트 블록 : 부팅 시 필요한 코드를 저장
• 슈퍼 블록 : 전체 파일 시스템에 대한 정보를 저장
• Index-Node 블록 : 각 파일이나 디렉터리에 대한 모든 정보를 저장하고 있는 블록
  • 파일 소유자의 사용자 번호 및 그룹 번호
  • 파일 크기
  • 파일 타입
  • 생성 시기
  • 최종 변경 시기
  • 최근 사용 시기
  • 파일 보호 권한
  • 파일 링크 수
  • 데이터가 저장된 블록의 시작 주소
• 데이터 블록 : 디렉터립려로 디렉터리 엔트리와 실제 파일에 대한 데이터가 저장된 블록

프로세스 관련 명령어​

• fork : 프로세스 생성, 하위 프로세서 호출, 프로세스 복제
• exec : 프로세스 수행
• exit : 프로세스 종료
• wait : fort 후 exec에 의해 실행되는 프로세스의 상위 프로세스가 하위 프로세스 종료 등의 event를 기다림
• kill : 프로세스 제거
• getpid : 자신의 프로세스 아이디
• getppid : 부모 프로세스 아이디
• & : 백그라운드 처리를 위해 명령의 끝에 입력
• signal : 신호를 받았을 때 프로세스가 취할 동작 지정
• pipe : 프로세스 간 통신을 위한 경로 설정

파일 및 디렉터리 명령어​

• creat : 파일 생성
• open : 파일을 사용할 수 있는 상태로 준비
• close : 파일 닫기
• cp : 복사
• mv : 파일 이동 또는 이름 변경
• rm : 파일 삭제
• cat : 파일 내용 표시
• chmod : 파일 사용 허가 지정
• chown : 소유자 변경
• find : 파일 찾기
• mknod : 특수 파일 생성
• mount : 파일 시스템 마운팅
• mkfs : 파일 시스템 생성
• fsck : 파일 시스템 검사
• mkdir : 디렉터리 생성
• chdir : 디렉터리 위치 변경
• rmdir : 디렉터리 삭제
• ls : 디렉터리 파일 목록 확인
• finger : 사용자 정보 표시

Windows

• GUI
• 선점형 멀티태스킹 : 동시에 여러 개의 프로그램을 실행하는 멀티 프로그래밍을 하면서 운영체제가 각 작업의 CPU 이용시간을 제어하여 응용 프로그램 실행중 문제가 발생하면 해당 프로그램을 강제 종료시키고 모든 시스템 자원을 반환하는 방식
• FAT 32 파일 시스템 사용
• Plug and Play
• OLE 사용 : 다른 여러 프로그램에서 작성된 문자가 르미 등의 개체를 현재 작성 중인 문서에 자유롭게 연결하거나 삽입하여 편집할 수 있는 기능
• 255자의 긴 파일명
• Single User 시스템

MS-DOS

• CUI
• Single User
• Single Tasking
• 시스템 파일 : 도스의 핵심파일로 주변장치의 입출력과 시스템 전체를 통제, MSDOS.SYS와 IO.SYS가 있다.
• 명령어 처리기 : COMMAND.COM
• 자동 일괄 처리 파일 : AUTOEXEC.BAT
• 환경 설정 파일 : CONFIG.SYS

명령어​

내부 명령어​

• COMMAND.COM에 포함되어 있고 메모리에 항상 상주되어 있다.
• DIR : 파일 목록 표시
• COPY : 복사
• TYPE : 파일 내용 표시 (like cat)
• REN : 파일 이름 변경
• DEL : 파일 삭제
• MD : 디렉터리 생성
• CD : 디렉터리 위치 변경
• RD : 디렉터리 삭제
• CLS : 화면 내용을 지움
• VER : 버전 표시 (like uname)
• PATH : 파일 탐색 경로 지정

외부 명령어​

• 실행과정이 복잡하거나 자주 사요하지 않는 것
• 디스크에 파일로 저장
• 처리속도가 느림
• UNDELETE : 삭제한 파일 복원
• SYS : 시스템 파일 복사
• ATTRIB : 파일 속성 변경 (like chmod)
• MOVE : 파일 이동
• FIND : 파일 찾기
• FORMAT : 포맷
• UNFORMAT : 포맷한 디스크를 복원
• CHKDSK : 디스크 상태 점검 (like df)
• DISKCOPY : 디스크 단위 복사
• DISKCOMP : 디스크 비교

• 영국 수학자 불에 의해 개발
• AND : 입력 값이 모두 1일 때 1 출력
• OR : 입력 값이 하나라도 1일 때 1 출력
• NOT : 부정

기본 공식​

• 합의 곱을 곱의 합으로 변환
• 분배법칙 예외 : A ＋(B×C) = (A ＋ B)(B ＋ C)
• 드모르강
  • (A ＋ B)` = A`×B`
  • (A×B)` = A`＋ B`
• 멱등
  • A ＋ A = A
  • A×A = A
• 보수
  • A ＋ A` = 1
  • A×A` = 0
• 항등
  • A ＋ 0 = A
  • A ＋ 1 = 1
  • A×0 = 0
  • A×1 = A
• 콘센서스
  • AB ＋ BC ＋ CA` = AB ＋ CA`
  • (A ＋ B)(B ＋ C)(C ＋ A`) = (A ＋ B)(C ＋ A`)
• 복원 : A`` = A
• 기타
  • A ＋ A`B = A ＋ B
  • A ＋ AB = A

카르노 맵​

• 설계된 논리식을 도표로 표현하여 최소화 하는 방법
• Karnaugh map = K-map = 카노맵

AB와 CD의 위치를 바꾸어 계산하는게 쉽다.

논리 게이트

• BUFFER : 입력된 정보를 그대로 출력
• NAND : NOT + AND
• NOR : NOT + OR
• XOR : 입력이 같으면 0, 다르면 1
  • X = A⊕B
  • X = A`B + AB`
  • X = (A + B)(A` + B`)
• XNOR : NOT + XOR
  • X = A⊙B
  • X = (A⊕B)`
  • X = AB + A`B`

조합논리회로

반가산기, 전가산기, 병렬가산기, 반감산기, 전감산기, 디코더, 인코더, 멀티플렉서, 디멀티플렉서, 다수결회로, 비교기 등

반가산기​

2진수 두 개를 더한 합과 자리올림수를 구하는 조합논리회로

• 합은 S, 자리올림(캐리)는 C
• C = AB
• S = A`B + AB` = A⊕B

전가산기​

1bit 2진수 3자리를 더하여 합과 자리올림수를 구하는 조합논리회로

• 두 개의 반가산기와 한 개의 OR GATE로 구성
• 합은 S, 자리올림(캐리)는 C
• C = (A⊕B)C + AB
• S = (A⊕B)⊕C
• 3 × 8 디코더 1개 + 4 입력 OR 게이트 2개로 구성가능

병렬가산기​

n bit로 된 2진수 A, B에 대한 덧셈을 n개의 전가산기를 이용하여 구현한 실질적인 가산기

• 전파지연을 줄이기 위해 Carry Look Ahead 사용
• 전파지연 : ALU Path에서 가장 긴 Delay

반감산기​

1bit 2진수 2자리에 대한 감산을 하는 조합논리회로

• 차는 D, 빌려온 수는 B
• B = A`B
• D = A`B + A`B = A⊕B
• 2 × 4 디코더 1개 + 3 입력 OR 게이트 1개로 구성가능

디코더​

n bit의 코드화된 정보를 그 코드의 각 bit 조합에 따라 2^n개의 출력으로 번역하는 조합논리회로

• n개의 입력을 2^n개의 출력으로
• 명령어의 명령부나 번지를 해독할 때 사용
• 주로 AND 게이트로 구성
• 부호화된 데이터에서 정보를 찾아냄
• n × 2^n 디코더의 AND 게이트 수 : 2^n 개
  • 5 × 8 디코더 : 8개

인코더​

2^n개의 입력선으로 입력된 값을 n개의 출력선으로 코드화해서 출력하는 조합논리회로

• 2^n개의 입력을 n개의 출력으로
  • 16개의 입력선일 경우 4개의 출력선 필요 (2^4)

멀티플렉서​

2^n개의 입력선 중 1개를 선택하여 그 선에서 입력되는 값을 1개의 출력선으로 출력하는 조합논리회로

• 2^n개의 입력선 중 1개의 선을 선택하기 위해 n개의 선택선 이용
  • 16개의 입력선일 경우 4개의 선택선 필요 (2^4)
  • 출력선은 하나

디멀티플렉서​

1개의 입력선으로 들어오는 데이터를 2^n개의 출력선 중 1개를 선택하여 출력하는 회로

• 2^n개의 출력선 중 1개의 선을 선택하기 위해 n개의 선택선 이용
• 16개의 출력선일 경우 4개의 선택선 필요 (2^4)
• 입력선은 하나

순서논리회로

• 외부의 입력과 현재 상태에 따라 출력이 결정
• 논리 게이트 외에 메모리 요소와 피드백 기능을 포함
• 기억기능 존재
• 출력이 일정한 값을 갖지 않음
• 플리플롭과 논리 게이트로 구성
• 동기식과 비동기식으로 나뉨
• 플리플롭, 카운터, 레지스터, RAM, CPU 등

플리플롭​

• 전원이 공급되는한 상태의 변화를 위한 외부신호가 발생할 때까지 현재의 상태를 그대로 유지하는 논리회로
• 레지스터, 카운터, 반도체메모리(RAM)의 기본 구성요소
• 2진수 1bit를 저장 가능
• 두 개의 NAND 또는 두 개의 NOR 게이트를 이용하여 구성

특성표​

순서논리회로의 기능을 나타내는 표로 입력선의 값에 따라 현재 상태가 다음 상태로 어떻게 변하여 저장되는지를 나타낸다.

여기표​

특성표 대신 순서논리회로의 기능을 표로 나타낸 것, 현재 상태 값을 새로운 값으로 변경시키려면 입력선으로 어떤 값을 입력해야 하는가를 나타낸다. 출력을 이용하여 입력을 알아내는 것.

RS 플립플롭​

• Reset-Set FF
• 특성표

• 여기표는 특성표를 떠올리면 구할 수 있다.

D 플립플롭​

• RS 플리플롭의 R선에 인버터(NOT 연산자)를 추가하여 S선과 하나로 묶어서 입력선을 하나만 구성한 플립플롭
• 입력값을 그대로 저장하는 기능을 수행
• 특성표

JK 플립플롭​

• RS에서 S=1, R=1일 때 동작하지 않는 점을 보완한 플립플롭
• RS 플립플롭의 입력선 S와 R에 AND 게이트 2개를 추가하여 JK 플립플롭의 입력선 J와 K로 사용한다.
• 모든 플립플롭의 기능을 포함한다.
• 플립플롭의 네가지 기능을 모두 갖춘 것을 찾으라는 문제가 나오면 RS가 있으면 RS, JK가 있으면 JK
• 특성표

• 여기표는 특성표를 떠올리면 구할 수 있다.

T 플립플롭​

• JK 플립플롭의 두 입력선을 묶어서 한 개의 입력선으로 구성한 플립플롭
• T=1인 경우 현재 상태를 토글한다. 보수가 출력된다.
• 카운터에 이용

M/S 플립플롭​

• 마스터-슬레이브 플립플롭
• 출력 측의 일부가 입력 측에 피드백되어 유발되는 레이스 현상을 없애기 위해 고안된 플립플롭
• 두 개의 플립플롭으로 구성
• 레이스 현상 : 입력이 되는 조합회로의 출력을 플리플롭이 받는 동안 플리플롭의 내부 상태가 변하고 있으면 그 상태값이 피드백통로를 통해 조합회로로 전달되므로 회로가 불안정해지는 현상

자료 구성 단위

비트​

• 자료, 정보 표현의 최소 단위
• 0과 1을 표시하는 2진수 1자리

니블​

• 4bit가 모여 구성
• 16진수 1자리를 표현하기에 적합

바이트​

• 문자를 표현하는 최소 단위
• 8bit가 모여 1Byte
• 1Byte는 256가지의 정보를 표현(2^8bit)
• Alphanumeric은 1Byte, 한글한자는 2Byte
• KB = 2의 10승, MB = 2의 20승...

워드​

• 컴퓨터가 한 번에 처리할 수 있는 명령 단위
• 전워드 : 4Byte (full word)
• 하프워드 : 2Byte (반워드)
• 더블워드 : 8Byte

필드​

• 파일 구성의 최소 단위
• 의미 있는 정보를 표현하는 최소 단위

레코드​

• 하나 이상의 관련된 필드가 모여서 구성
• 컴퓨터 내부 자료 처리 단위
• 논리 레코드를 의미

블록​

• 물리 레코드
• 하나 이상의 논리 레코드가 모여서 구성
• 각종 저장 매체와의 입출력 단위를 의미

파일​

• 프로그램 구성의 기본 단위
• 같은 종류의 여러 레코드가 모여서 구성

데이터베이스​

• 여러 개의 관련된 파일의 집합
• 관계형, 계층형, 망형 DB

진법

2진수​

정수는 나누고 소숫점은 곱하고

8진수​

2진수를 구하고 3자리씩 묶고

16진수​

2진수를 구하고 4자리씩 묶고

보수

• 덧셈회로를 이용하여 뺄셈을 수행하기 위해 사용
• 1의 보수 : 그냥 반전
• 2의 보수
  • 1의 보수를 구한 뒤 1을 더함
  • 뒤에서부터 1이 나올때까지는 그냥쓰고 나머지는 반전

뺄셈​

• 1의 보수 이용 : 자리올림이 발생하면 결과에 자리올림수를 더한다.
• 2의 보수 이용 : 자리올림이 발생하면 버린다.

고정 소수점

정수 데이터 표현 및 연산에 사용하는 방법

2진연산​

• 정수값을 2진수로 변환하여 표현하는 방식
• 표현할 수 있는 범위가 작음
• 연산속도 빠름
• 맨처음 1bit는 부호비트로 사용

음수연산​

• 부호화 절대치법 : 양수 표현에 대해 부호비트만 바꾼다.
• 부호화 1의 보수법 : 양수 표현에 대해 1의 보수를 구한다.
• 부호화 2의 보수법 : 양수 표현에 대해 2의 보수를 구한다.
  • 1의 보수 표현법에 비해 음수 1개를 더 표현할 수 있다.
  • 자리올림을 무시하므로 1의 보수 표현에 비해 연산이 간단하다.
  • 0이 하나만 존재한다.

부호화 2진 표현을 10진수로 변경시

1. 부호 비트를 빼고 2의 보수 연산
2. 부호를 대입

10진연산​

언팩연산​

• 존형 10진연산 = Zone Decimal
• 연산이 불가능하다.
• 데이터 입출력에 사용
• 1Byte로 10진수 1자리를 표현
• 4개의 존 비트와 4개의 숫자 비트를 사용
• 최하위 바이트의 존 부분을 부호로 사용
• Zone = F, Digit = 4Bit 2진수
• Sign = 양수 C, 음수 D, 부호 없는 양수 F

팩연산​

• 연산이 가능
• 데이터 입출력 불가능
• 1Byte로 10진수 2자리를 표현
• 최하위 바이트의 마지막 4Bit를 부호로 사용
• Digit = 4Bit 2진수
• Sign = 양수 C, 음수 D, 부호 없는 양수 F

부동소수점

• 매우 크거나 작은 수, 매우 정밀한 수를 적은 비트로 표현 가능
• 연산시간이 느림
• 부동 소수점의 연산 수행횟수를 FLOPS로 표시
  • FLOPS : FLoating point Operations Per Second, 컴퓨터 연산속도의 단위
• 지수부와 가수부를 분리하는 정규화 과정 필요 정규화 : 0.1 <= 가수부분 < 1 을 만족시키게 변경
• 4Byte를 사용하는 단정도와 8Byte를 사용하는 배정도 표현법
• 지수부에는 정규화해서 분리한 지수값을 64Bias법으로 표현
  • 64Bias : 지수 7Bit에 100 0000이 입력되어 있고 2^n의 n만큼을 더하고 뺴서 지수를 표현하는 방식

IEEE 표준​

• IEEE 754 표준
• 정규화시 가수부가 1이되게 정규화
• 127Bais를 사용해 지수 8Bit에 0111 1111이 들어있음

연산​

덧셈 및 뺄셈​

1. 0인지 확인
2. 지수가 큰쪽에 수를 맞추어 정규화
3. 연산
4. 결과 정규화

곱셈​

1. 0인지 확인
2. 지수 덧셈
3. 가수 곱셈
4. 결과 정규화

나눗셈​

1. 0인지 확인
2. 레지스터 초기화
3. 부호 결정
4. 나눠지는 수가 나누는 수보다 작게 나눠지는 수를 정규화
5. 지수 뺄셈
6. 가수 나눗셈

자료 표현

BCD​

• 2진화 10진코드 = Binary Coded Decimal
• 6Bit 코드로 IBM에서 개발
• 1개의 문자를 2개의 Zone Bit와 4개의 Digit Bit로 표현
• 6Bit이므로 64개 문자 표현 가능
• 1Bit의 Parity Bit를 추가해 7Bit로 사용
• 영소문자 표현 불가

ASCII​

• American Standard Code for Information Interchange
• 7Bit 코드로 미국 표준협회에서 개발
• 7Bit이므로 128개의 문자 표현 가능
• 1Bit의 Parity Bit를 추가해 8Bit로 사용
• 영대소문자, 숫자, 제어문자, 특수문자 등 표현 가능
• 통신 제어용 및 마이크로 컴퓨터의 기본코드로 사용

EBCDIC​

• 8Bit 코드로 IBM에서 개발
• 1개의 문자를 4개의 Zone Bit와 4개의 Digit Bit로 표현
• 8Bit이므로 256개의 문자 표현 가능
• 1Bit의 Parity Bit를 추가해 9Bit로 사용
• 특수문자, 영대소문자, 숫자 등 표현 가능

BCD 코드​

• 10진수 1자리를 2진수 4Bit로 표현
• 8421 코드
• 가중치 코드
  • 2진수 각 자리가 고유한 값을 가지는 코드
• BCD에서 Zone을 생략한 형태
• 10진수 입출력이 간편

Excess3 코드​

• BCD 코드에 3을 더하여 만든 코드
• 모든 비트가 동시에 0이 되는 경우가 없다.
• 3 초과 코드
• 자기보수 코드
• 비가중치 코드
• 10진수를 표현하기 위함이다.
• 보수를 구하기 편해 산술연산에 좋다.

Gray 코드​

• BCD 코드의 인접하는 Bit를 XOR 연산하여 만든 코드
• 코드 변환이 용이
• 입출력장치, A/D변환기, 주변장치 등에서 숫자를 표현할 때 사용
• 1Bit만 변화시켜 다음 수치로 증가시키기 때문에 하드웨어 오류가 적다.
• 2진수를 Gray로 변경시 : n자 모양으로 연산
  • 첫번째 그레이 비트는 2진수 첫번째 비트 그대로
  • 2진수 비트를 앞뒤로 XOR 연산
• Gray를 2진수로 변경시 : h자 모양으로 연산
  • 첫번째 2진수는 그레이 비트 그대로
  • 두번째부턴 왼쪽 변경된 2진수와 변경할 우측 그레이 비트를 XOR 연산

패리티 코드​

• 전송된 코드의 오류를 검사하기 위해 데이터 비트 외에 1Bit의 패리티 체크 비트를 추가하는 것
• 1Bit의 오류만 검출 가능

홀수 패리티​

• Odd Parity = 기수 패리티
• 1의 갯수가 홀수가 되도록 0이나 1을 마지막에 추가

짝수 패리티​

• Even Parity = 우수 패리티
• 1의 갯수가 짝수가 되도록 0이나 1을 마지막에 추가

해밍 코드​

• 오류를 검출하고 교정이 가능한 코드
• 2Bit의 오류를 검출할 수 있고 1Bit를 교정 가능
• 잉여비트가 많이 필요
• 1, 2, 4, 8, ... 2^n번째 Bit는 오류 검출을 위한 패리티 비트
• 패리티 비트 결정시
  • 1번 Bit는 1, 3, 5, 7...
  • 2번 Bit는 2, 3, 6, 7, 10, 11... 2Bit씩 건너 뛰면서
  • 4번 Bit는 4, 5, 6, 7, 12, 13, 14, 15... 4Bit씩 건너 뛰면서

코드 분류​

가중치코드는 일반적으로 숫자로 이루어져 있다.

중앙처리장치

제어장치, 연산장치, 레지스터, 버스로 구성

제어장치​

• 컴퓨터의 모든 장치에 대한 동작을 지시하고 제어
• 명령 레지스터에서 읽어들인 명령어를 해독해 장치에 제어신호를 보내 명령을 수행하도록 지시
• 제어장치에 입력되는 항목
  • 명령어 레지스터
  • 플래그
  • 클록

구성요소​

• 명령 레지스터 : 현재 실행중인 명령어 내용 기억
• 명령 해독기(디코더) : 명령 레지스터에 있는 명령어를 해독
• 제어 발생기(인코더) : 해독된 명령에 따라 각 장치로 본래 제어 신호 생성
• 제어 주소 레지스터(CAR) : 다음에 실행할 마이크로 명령어의 주소를 저장하는 레지스터
  • 매핑의 결과값, 주소필드, 서브루틴 레지스터의 내용이 기록
• 제어 버퍼 레지스터(CBR) : 제어 기억장치로부터 읽혀진 마이크로명령어를 일시적으로 저장하는 레지스터
• 제어 기억장치 : 마이크로 프로그램을 저장하는 내부 기억장치
• 순서 제어모듈 : 마이크로 명령어의 실행 순서를 결정하는 회로집합
• 순차 카운터 : 디코더에 의해 선택된 번호에 해당하는 타이밍 신호를 생성

연산장치​

• 제어장치에 명령에 따라 실제로 연산을 수행하는 장치
• 산술연산, 논리연산, 관계연산, Shift 등
• 가산기, 누산기(AC), 보수기(Complementor), 데이터레지스터, 오버플로 검출기, 시프트 레지스터 등

레지스터​

• CPU 내부에서 처리할 명령어나 연산의 중간 결과값 등을 일시적으로 기억하는 임시 기억장소
• 플리플롭이나 래치들을 병렬로 연결하여 구성
• 메모리 중에서 속도가 가장 빠르다.
• 레지스터의 크기는 워드를 구성하는 비트 개수만큼의 플립플롭으로 구성
  • 워드의 크기가 16Bit => 레지스터는 16개의 플립플롭이나 래치로 구성
• 저장값을 0으로 하는 것을 설정해제(CLR)

자료전송​

• 직렬 전송 : 직렬 시프트 마이크로 오퍼레이션, 느림
• 병렬 전송 : 하나의 클록펄스 동안 워드가 동시에 전송
• 버스 전송 : 모든 레지스터가 공통으로 이용하는 경로, 병렬에 비해 결선의 수를 줄일 수 있다.

주요 레지스터​

• PC : 프로그램 카운터, 다음번 실행할 명령어의 번지를 기억하는 레지스터로 분기 명령이 실행되는 경우 그 목적지 주소로 갱신
• IR : 명령레지스터, 현재 실행중인 명령의 내용을 기억하는 레지스터
• AC : 누산기, 연산된 결과를 일시적으로 저장하는 레지스터
• PSWR : Status Register, Program Status Word Register, Flag Regiester
  • 시스템 내부의 순간 상태가 기록된 정보를 PSW라 한다.
  • 오버플로, 언더플로, 자리올림, 계산상태, 인터럽트 등의 PSW를 저장하는 레지스터
  • 프로그램 제어와 밀접한 관계
• MAR : 메모리 주소 레지스터, 데이터의 번지를 기억하는 레지스터
• MBR : 메모리 버퍼 레지스터, 데이터가 잠시 기억되는 레지스터, CPU가 데이터를 처리하기 위해서 반드시 거처야한다.
• Base Register : 명령이 시작되는 시작 번지를 기억하는 레지스터
• Index Register : 주소의 변경, 서브루틴 연결 및 프로그램에서의 반복연산의 횟수를 세는 레지스터로 프로그래머가 내용을 변경할 수 있다.
• Data Register : 연산에 사용될 데이터를 기억하는 레지스터
• Shift Register : 저장된 값을 미는 연산을 하는 레지스터, 2배 길이 레지스터
• Major Status Register : CPU의 현재상태(인출, 간접, 실행, 인터럽트)를 저장하고 있는 레지스터

버스​

• CPU, 메모리, I/O장치와 상호 필요한 정보를 교환하기 위해 연결하는 전송선
• 내부회로에서 버스를 사용하는 목적은 결선의 수를 줄이기 위해서다.

종류​

• 제어 버스 : Control Bus, 양방향 전송선, 제어신호 전송
• 주소 버스 : Address Bus, 번지 버스, 단방향 전송선, 번지 지정
• 데이터 버스 : Data Bus, 자료 버스, 양방향 전송선, 데이터 전송
• 내부버스 : CPU 및 메모리에 구성된 버스
• 외부버스 : 주변 I/O장치에 구성된 버스

명령어

OP code부, Mode부, Operand부로 구성

연산자부​

• Operation Code부 = OP Code
• 연산자부의 크기는 표현할 수 있는 명령의 종류를 나타내는 것
• nBit일 때 최대 2^n의 명령어 표현 가능

모드부​

• Mode부
• 주소부의 유효 주소가 결정되는 방법을 지정
• 0이면 직접, 1이면 간접

자료부​

• Operand부 = 오퍼랜드부 = 주소필드
• 실제 데이터에 대한 정보를 표시하는 부분
• 주소, 레지스터 번호, 사용할 데이터 등을 표시
• 자료부의 크기는 메모리 용량과 관계가 있다.

설계시 고려사항​

• 연산자의 종류
• 명령어 형식
• 주소지정방식
• 데이터 구조
• 효율성 제고방안 : 기억공간, 사용빈도, 주소지정방식, 주기억장치의 대역폭 이용

기능​

함수 연산, 자료전달, 제어, 입출력 기능

함수 연산 기능​

• 산술연산 : ADD, SUB, MUL, DIV, 산술 Shift
• 논리연산 : NOT, AND, OR, XOR, 논리 Shift, Rotate, Complement, Clear
• 단항연산 : NOT, Complement, Shift, Rotate, Move
• 이항연산 : 사칙, AND, OR, XOR, XNOR
• 연산자 우선순위
  1. 산술연산자 : 거듭제곱 > 곱=나눔 > 덧,뺄
  2. 관계연산자
  3. 논리 연산자 : NOT > AND > OR

자료 전달 기능​

• Load : 기억장치 => CPU
• Store : CPU => 기억장치 저장
• Move : 레지스터간 자료 전송
• Push : 스택에 자료 저장
• Pop : 스택에서 자료 꺼냄

제어 기능​

• 무조건 분기 : GOTO, JMP (PC <- X)
• 조건 분기 : IF, SPA, SNA, SZA
  • SPA : Skip if AC is Positive
  • SNA : Skip if AC is Negative
  • SZA : Skip if AC is Zero
• Call : 부 프로그램 호출
• Return : 부 프로그램에서 복귀

입출력 기능​

• Input
• Output

연산

AND​

• 특정 비트를 삭제(Clear)하는 연산
• Masking 연산

OR​

• 특정 비트를 1로 만드는 연산
• Selective Set 연산

XOR​

• 두 개의 데이터를 비교하거나 특정 비트를 반전시킬 때 사용
• 결과에 1Bit라도 1이 있으면 서로 다른 데이터
• 반전시킬 Bit를 1과 XOR

NOT​

• 그냥 반전

논리 Shift​

• 0을 삽입해 비트를 좌우로 한칸씩 민다.

Rotate​

• Shift에서 밀려나간 비트를 반대편으로 가져와 입력하는 연산
• 문자 위치를 변환할 때 사용

산술 Shift​

• 부호를 고려하여 자리를 이동시키는 연산
• 2^n으로 곱하거나 나눌 때 사용
• 왼쪽으로 Shift시 2^n을 곱한 값과 같음
• 오른쪽으로 Shift시 2^n을 나눈 값과 같음
• 홀수를 오른쪽으로 Shift시에 0.5의 오차 발생
• 정수 표현 방식에서만 사용 가능
• 정수 수치 표현 방법에 따라 Padding Bit 및 결과가 다름

Shift Left​

• 부호화 절대치, 2의 보수법은 무조건 0
• 1의 보수법은 부호 비트와 같은 0, 1

Shift Right​

• 부호화 절대치는 0
• 1의 보수법, 2의 보수법은 부호 비트와 같은 0, 1

명령어 형식

3주소 명령어​

• Operand부가 세 개로 구성되는 명령어 형식
• GPR(범용 레지스터)를 가진 컴퓨터에서 사용
• 연산의 결과는 Operand 1에 주로 기록 (컴퓨터에 따라 Operand 3에도 기록)

장점​

• 연산시 원래 자료를 파괴하지 않음
• 다른 형식의 명령어를 이용하는 것보다 프로그램 전체의 길이가 짧음
• 전체 프로그램 실행시 명령인출을 위해 주기억장치를 접근하는 횟수 감소

단점​

• 명령어 한 개의 길이가 너무 길어짐
• 하나의 명령을 수행하기 위해 최소한 4번 기억장소에 접근해야함
• 수행시간이 길다.

2주소 명령어​

• Operand가 두 개로 구성되는 일반적인 명령어 형식
• 여러 개의 GPR(범용 레지스터)를 가진 컴퓨터에서 사용

장점​

• 실행 속도가 빠르고 기억장소를 많이 차지하지 않음
• 3주소 명령에 비해 명령어의 길이가 짧음
• 계산결과가 기억장치에 기억되고 CPU에도 남아 있어 계산 결과를 시험할 때 시간이 절약된다.

단점​

• 연산 결과가 주로 Operand1에 저장되므로 원래 Operand1에 있던 자료는 파괴된다.
• 전체 프로그램의 길이가 길어진다.

1주소 명령어​

• Operand가 한 개로 구성된 명령어 형식
• AC를 이용하여 명령어를 처리하므로 결과도 누산기에 저장된다.

0주소 명령어​

• Operand부 없이 OPCode만으로 구성
• 모든 연산은 Stack 메모리의 Stack Pointer가 가리키는 Operand를 이용하여 수행
• 스택 머신
• 인스트럭션 수행시간이 짧다.
• 기억공간 이용이 효율적
• 수식을 계산하기 위해선 Postfix 형태로 변경해야한다.
• 연산 결과를 다시 스택에 넣기 때문에 원래의 자료가 남지 않는다.

주소지정방식

고려사항​

• 표현의 효율성 : 빠르게 접근가능하고, 주소지정에 적은 비트를 사용해야하며 다양항 Address 모드를 사용할 수 있어야한다.
• 사용의 편리성 : 프로그램 작업을 위해 포인터, 프로그램 리로케이션 등의 편의를 제공해야한다.
• 주소공간과 기억공간의 독립성 : 프로그램에서 사용한 주소를 변경 없이 실제 기억공간 내의 주소로 재배치할 수 있도록 서로 독립적이여야한다.
  • 주소공간 : 보조기억장치 내의 기억공간
  • 기억공간 : 주기억장치 내의 기억공간

암시적 주소지정방식​

• 명령 실행에 필요한 데이터의 위치를 지정하지 않고 누산기나 스택의 데이터를 묵시적으로 지정하여 사용
• 오퍼랜드가 없는 명령이나 오퍼랜드가 1개인 명령어 형식에 사용

즉시적 주소지정방식​

• 명령어 자체에 오퍼랜드를 가지고 있는 방식
• 별도의 기억장소를 액세스하지 않기 때문에 실행 속도가 빠르다.
• 데이터 값 범위가 제한적이다.

직접 주소지정방식​

• 오퍼렌드부에 표현된 주소를 이용해 실제 데이터가 기억된 기억장소에 직접 매핑
• 실제 사용할 데이터의 유효주소를 적기 때문에 주소 길이에 제약을 받음
• nBit 오퍼랜드부 => 2^n 개의 주소 표현 가능
• 오퍼렌드부에 데이터를 가지고 있는 레지스터의 번호를 지정하면 레지스터 모드

간접 주소지정방식​

• 주기억장치를 두 번 이상 접근하여 데이터가 있는 기억장소에 도달
• 오퍼랜드부에 할당된 비트 수로 주소를 나타낼 수 없을 때 사용하는 방식
• 명령어의 길이가 짧고 제한되어도 긴 주소에 접근이 가능한 방식
• 레지스터 간접모드

계산에 의한 주소지정방식​

• 오퍼랜드부와 CPU의 특정 레지스터 값이 더해져서 유효주소를 계산하는 방식
• 약식 주소
• 상대주소 : 명령어 주소 + PC
• 베이스 레지스터 : 명령어 주소 + Base Register
  • 명령어의 시작주소를 가지고 있는 레지스터
  • 베이스 레지스터의 값과 명령어에 포함된 변위값을 더해 유효주소를 얻는 것을 재배치라고 한다.
• 인덱스 레지스터 : 명령어 주소 + Index Register

마이크로 오퍼레이션

• 인스트럭션을 수행하기 위해 CPU 내의 레지스터와 플래그가 의미있는 상태변환을 하도록하는 동작
• 레지스터에 저장된 데이터에 의해 이루어진다.
• 한 개의 클록펄스 동안 실행되는 기본 동작
• 모든 마이크로 오퍼레이션은 CPU의 클록펄스에 맞춰 실행된다.
• 순서를 결정하기 위해 제어장치가 발생하는 신호를 제어신호
• 제어워드 : 레지스어틔 선택과 산술논리연산장치의 역할을 결정하고 어떤 마이크로 연산을 할 지 결정하는 비트의 모임 = 마이크로 명령어
• 마이크로 프로그램 : 제어워드가 저장되 있을 때 마이크로 프로그램

마이크로 사이클 타임​

• 한 개의 마이크로 오퍼레이션을 수행하는데 걸리는 시간
• CPU는 클록펄스에 의해 동기화되어 동작하는데 펄스를 CPU 클록이라하며 한 개의 마이크로 오퍼레이션은 CPU 클록 발생 주기의 간격 내에 실행된다.
• CPU Cycle Time = CPU Clock Time
• CPU 속도를 나타내는 척도
• 1us = 10^-6s, 1ns = 10^-9s

동기 고정식​

• 모든 마이크로 오퍼레이션 동작시간이 같다고 가정해 클록 주기를 마이크로 사이클 타임과 같도록 정의하는 방식
• 동작 시간이 가장 긴 마이크로 오퍼레이션의 동작시간을 마이크로 사이클 타임으로 정한다.
• 모든 마이크로 오퍼레이션 동작시간이 비슷할 때 유리하다.
• CPU 낭비가 심하다.
• 구현이 쉽다.

동기 가변식​

• 수행시간이 유사한 마이크로 오퍼레이션끼리 그룹을 만들어 그룹별로 서로 다른 마이크로 사이클 타임을 정의하는 방식
• 수행시간이 현저한 차이를 나타낼 때 사용
• CPU 시간 낭비를 줄일 수 있다.
• 구현이 복잡하다.
• 각 그룹(집합) 간 서로 다른 사이클 타임의 동기를 맞추기 위해 그룹간 마이크로 사이클 타임을 정수배가 되게 한다.

비동기식​

• 모든 마이크로 오퍼레이션이 서로 다른 마이크로 사이클 타임을 가진다.
• 시간 낭비는 없다.
• 구현이 매우 복잡하다.
• 실제로 거의 사용되지 않는다.

메이저 스테이트

• 현재 CPU가 무엇을 하고 있는가를 나타내는 상태
• Fetch, Indirect, Execute, Interrupt
• Major Cycle = Machine Cycle
• 메이저 스테이트 레지스터를 통해 알 수 있다.
• F와 R 플립플롭의 상태에 따라 메이저 스테이트 상태가 결정된다.

Fetch Cycle​

• 인출단계
• 중앙처리장치의 명령 레지스터로 명령어를 가져와 해독하는 단계
• 가장 먼저 수행되는 동작
• 1Cycle 명령어면 수행 후 다시 Fetch Cycle로 변경됨
• 1Cycle 명령어가 아니면 모드 비트에 따라 직 간접 주소를 판단
• 모드가 0이면 직접주소 => Execute 단계로
• 모드가 1이면 간접주소 => Indirect 단계로

• PC : 다음 실행할 명령의 주소가 들어있음
• MAR : 저장하거나 읽어올 주기억장치의 주소가 들어있음
• MBR : 주기억장치에서 읽어오거나 저장할 데이터가 들어있음
• M[MAR] : 메모리에서 MAR에 해당하는 실제 데이터
• IR : 현재 실행하는 명령어가 들어있음
• OP : 명령 코드 부분
• I : 모드 비트
• AD : 명령 주소 부분
• F, R : 다음 상태를 지정하는 플립플롭

Indirect Cycle​

• Fetch 단계에서 해석한 주소를 읽어온 후 간접주소이면 유효주소를 계산하기 위해 다시 Indirect 단계를 수행
• 직접주소인 경우 Execute 단계 또는 Fetch 단계로 이동
  • 분기같은 1Cycle 명령이면 Fetch로
  • 실행이면 Execute로

Execute Cycle​

• 해석된 명령을 실행하는 단계
• 플래그 레지스터의 상태를 검사하여 Interrupt 단계로 갈지 결정

Interrupt Cycle​

• 인터럽트 발생시 복귀주소를 저장시키고 인터럽트 처리 프로그램의 첫 번째 명령으로 제어순서를 옮긴다.
• 인터럽트 단계는 항상 Fetch 단계로 이동된다.
• 메모리의 인터럽트 주소는 0번지에 저장되고, 인터럽트 벡터는 인터럽트 처리 프로그램의 주소 번지를 말한다.
• 현재 상태를 저장하고 인터럽트가 처리된다.
• 인터럽트 처리시 다음 실행주소를 PC에 넣고 인터럽트 벡터로 이동한다.

주요 마이크로 오퍼레이션

AND​

• AC와 메모리의 내용을 AND 연산해서 AC에 저장
• 논리곱 연산
• AC ← AC ∧ MBR

ADD​

• AC와 메모리의 내용을 더해서 AC에 저장
• AC ← AC +MBR

LDA​

• 메모리의 내용을 AC로 Load하는 명령
• AC에 0을 전송하여 AC를 초기화하는 부분이 있어야함
• AC ← 0
• AC ← AC + MBR

STA​

• AC의 내용을 메모리에 저장
• M[MAR] ← MBR

BUN​

• 실행 명령의 위치를 변경하는 무조건 분기
• Branch UNconditionally
• PC ← MBR[AD]

BSA​

• 복귀주소를 저장하고 부 프로그램을 호출하는 명령
• Branch and Save Return Address

ISZ​

• 메모리의 값을 읽고 값을 1 증가 시킨 후 그 값이 0이면 현재 명령을 건너 뛰고 다음으로 이동
• IF(MBR=0) THEN ← PC + 1

제어기

제어데이터​

• 제어장치가 제어신호를 발생하기 위한 자료
• CPU가 특정한 메이저 상태와 타이밍 상태에 있을 때 제어 자료에 따른 제어 규칙에 의해 발생한다.

종류​

• 메이저 스테이트 사이의 변천을 제어하는 데이터
• 중앙처리장치의 제어점을 제어하는 데이터
• 인스트럭션의 수행 순서를 결정하는데 필요한 제어데이터

단계​

구현​

• 하드웨어적 고정배선제어장치
• 소프트웨어적 마이크로 프로그래밍 기법

고정배선 제어장치​

• 독립 제어점에 제어신호를 가해야 할 조건들을 제어 데이터와 제어기의 상태로 표현한 후 이를 만족하는 조합논리회로를 설계하여 해당 제어점에 연결하는 방식
• 하드웨어적 구성방법
• 속도 빠름
• 비싸다.
• RISC구조를 기본으로 하는 컴퓨터에서 주로 사용
• 한 번 만들어진 명령어 세트를 변경할 수 없음
• 회로 구성이 복잡

마이크로 프로그래밍​

• 내부 제어 신호를 지정하는 여러가지 마이크로 인스트럭션으로 작성하는 것
• 소프트웨어적 구성방법
• 펌웨어를 이용하는 방식
• 마이크로 프로그램된 제어장치를 사용하는 컴퓨터는 주 메모리 외에 마이크로 프로그램이 저장되는 제어메모리(ROM)이 필요하다.
• 명령어 세트를 쉽게 변경할 수 있다.
• 다양한 어드레스 모드를 갖음
• 속도 느림
• 유지보수 및 수정 용이
• 복잡한 명령 세트를 가진 시스템에 적합

제어 메모리 번지 결정​

• 제어 주소 레지스터(CAR) : 값을 1 증가
  • 매핑의 결과값
  • 주소 필드
  • 서브루틴 레지스터 데이터
• 명령 레지스터(IR) : 지정하는 번지로 무조건 분기, 주소 필드로부터 제어 메모리의 주소로 매핑
• 상태 레지스터(SR) : 조건에 따른 분기
• 서브루틴의 호출(call)과 복귀(return)

형식​

수평 마이크로 명령​

• Horizontal Micro Instruction
• 한 비트가 한 개의 마이크로 동작을 관할하는 명령
• 마이크로 오퍼레이션 부가 nBit일 때 n개의 마이크로 동작 표현 가능
• 제어 비트를 디코딩 할 필요가 없다.
• 마이크로 명령 한 개로 여러 개의 하드웨어를 동시에 동작시킬 수 있다.
• 제어 워드의 길이가 길어진다.
• 비트가 충분히 활용되지 못함.
• 비용이 많이 든다.

수직 마이크로 명령​

• Vertical Micro Instruction
• 제어 메모리 외부에서 디코딩 회로를 필요로 하는 마이크로 명령
• 디코더의 출력을 제어신호로 사용
• 한 개의 마이크로 동작만 제어 가능

나노 명령​

• Nano Instruction
• 나노메모리(낮은 레벨의 메모리)에 저장된 마이크로 명령
• 수직 마이크로 명령을 수행하는 제어기에서 디코더를 ROM(나노메모리)로 바꿔 두 메모리 레벨로 구성
• 제어 메모리의 각 워드는 나노 메모리의 번지를 저장

제어장치 구현방식​

• 상태 플리플롭 제어
• PLA (Programmable Logic Array)
• 마이크로 프로그램 제어

입출력장치

입출력 제어장치​

• 입출력장치와 컴퓨터 사이의 자료 전송을 제어하는 장치
• 데이터 버퍼 레지스터를 이용하여 두 장치간의 속도 차를 조절 = 데이터 버퍼링
• 제어 신호의 논리적, 물리적 변환 및 오류를 제어
• DMA, 채널, 입출력 프로세서, 입출력 컴퓨터가 포함된다.

입출력 인터페이스​

• 동작방식이나 데이터 형식이 다른 컴퓨터 내부의 장치끼리 2진 데이터를 원활하게 전송하기 위함
• CPU와 주변장치의 전송속도, 동작방식, 워드형식의 차이 제어
• 동작방식이 다른 주변장치끼리의 차이 제어

입출력 버스​

• 주기억장치와 입출력장치 사이의 데이터 전송을 위해 모든 주변장치의 인터페이스에 공통으로 연결된 버스
• 구성
  • 데이터 버스
  • 주소 버스
  • 제어 버스

기억장치와 입출력장치의 차이​

• 기억장치 : 전자적, 빠르다, 타율, 오류 적음, Word단위
• 입출력장치 : 기계적, 느리다, 자타율, 오류 많음, Byte(문자)단위

비동기 데이터 전송​

• 비동기 데이터 전송을 하기 위해선 데이터 전송시각을 알기 위한 제어신호를 서로 교환하여 송수신 상태를 서로 맞춰야한다.

스트로브 펄스​

• Strobe Pulse
• 데이터 버스와 한 개의 제어선
• 스트로브 신호 : 두 개의 독립적인 장치 사이의 비동기적인 데이터 전송을 하기 위해 전송 시각을 알리는 제어 신호
• 메모리와 CPU 사이의 정보를 교환할 때 사용
• 수신장치가 데이터를 받았는지는 모름

핸드쉐이킹​

• 데이터 전송시 송신측과 수신측에서 입출력의 준비나 완료를 나타내는 신호를 사용하여 서로의 동작을 확인하면서 데이터를 전송
• 전송을 시작한 장치에 응답하는 제 2의 제어신호를 전송
• 높은 융통성과 신뢰성
• 병렬 입출력 데이터 전송방식의 기본으로 많이 사용
• 2~3개의 제어선 사용
• RDY, STB 신호 사용

스풀링​

• 다중 프로그래밍 환경 아래에서 용량이 크고 신속한 액세스가 가능한 디스크를 이용해 각 사용자 프로그램이 입출력할 데이터를 직접 입출력장치로 보내지 않고 디스크에 모았다가 한꺼번에 입출력 시키는 방법
• 입출력장치의 공유 및 느린 처리속도를 보완
• 디스크의 일부를 매우 큰 버퍼로 사용한다.
• 큐 방식의 입출력을 수행
• Simultaneous Peripheral Operation OnLine
• 보조기억장치에 저장
• 다중 작업
• 소프트웨어 구현

버퍼링​

• 입출력 장치와 CPU의 속도차를 해결하기 위해 사용
• 주기억 장치에 저장
• 단일 작업
• 하드웨어 구현

입출력 제어방식

• 입출력 처리 능력 순서 : 프로그램 < 인터럽트 < DMA < 채널

Programmed I/O​

• 폴링
• 원하는 I/O가 완료되었는지 여부를 검사하기 위해 CPU의 Status Flag를 계속 조사해 I/O가 완료되었으면 MDR(MBR)과 AC사이의 자료 전송도 CPU가 직접 처리하는 방식
• 입출력의 대부분을 CPU가 해준다.
• MDR(MBR), Flag(PSW), 장치번호 디코더로 구성
• CPU가 계속 I/O에 관여해야되기 때문에 비효율적

Interrupt I/O​

• 데이터 전송 준비가 되면 입출력 인터페이스가 컴퓨터에게 알려 I/O가 이루어지는 방식
• 입출력 인터페이스가 CPU에게 인터럽트 신호를 전송
• 수행중인 프로그램의 인스트럭션을 끝내고 I/O 처리후 다시 복귀
• 대량 자료 전송시 CPU에 부담

DMA I/O​

• Direct Memory Access
• 입출력장치가 직접 주기억장치를 접근하여 데이터 블록을 입출력하는 방식
• I/O가 CPU를 경유하지 않음
• CPU는 I/O에 필요한 정보를 DMA 제어기에 전달해 I/O동작만을 개시하고 끝
  • I/O 장치의 주소
  • 데이터 있는 주기억장치의 시작 주소
  • DMA 시작 명령
  • I/O 데이터 양
  • 입력 또는 출력을 결정하는 명령
• 빠른 데이터 전송 가능
• DMA는 인터럽트 신호를 발생해 CPU에게 I/O 종료를 알림
• 블록으로 대용량 데이터 전송 가능
• CPU의 Cycle Steal 해 메모리를 접근하여 I/O 데이터를 전송
  • 데이터 채널과 CPU가 주기억장치를 동시에 접근할 때 우선순위를 전자에게 줌
  • CPU는 그동안 메모리 참조가 필요없는 오퍼레이션을 계속 진행
  • CPU의 상태 보존이 필요 없음
• CPU와 DMA 제어기는 메모리와 버스를 공유
• 명령 받고 => 버스 사용 요구 => 버스 사용 허가 => 데이터 전송 => 인터럽트 전송
• 한 개의 인스트럭션에 의해 한 개의 블록을 입출력

구성​

• 인터페이스 회로
• 주소 레지스터 및 주소 라인
• 워드 카운트 레지스터 = 단어 계수기
• 제어 레지스터
• 데이터 레지스터

Channel I/O​

• I/O 프로세서
• I/O를 위한 특별한 명령어를 I/O 프로세서에게 수행토록 하여 CPU 관여 없이 주기억장치와 입출력장치 사이에서 I/O를 하는 전용 프로세서
• DMA의 한계를 극복하기 위해 고안
• DMA의 방법으로 입출력을 수행하지만 확장된 개념
• 채널 제어기는 채널 명령어로 작성된 채널 프로그램을 해독하고 실행하여 I/O 처리
• CPU로 I/O 명령어를 받으면 CPU와는 독립적으로 동작
• 주기억장치에 저장된 채널 프로그램의 수행과 데이터 전송을 위해 주기억장치에 직접 접근
• I/O 장치는 제어장치를 통해 채널과 연결
• I/O 채널은 CPU의 I/O 명령을 수행하지 않고 I/O 채널 내의 특별한 명령어를 수행
• CPU와는 인터럽트로 통신
• 한 개의 인스트럭션에 의해 여러 개의 블록을 입출력
• 입출력장치와 주기억장치를 연결하는 중개자
• 입출력 전담장치
• 입출력 장치와 CPU사이의 존재하는 현저한 속도차를 극복하기 위한 장치
• CPU의 명령을 받고 입출력을 시작하면 CPU와는 독립적으로 조작하는 장치

채널 명령어​

• 명령코드
• 데이터 주소
• 플래그
• 워드 카운터

종류​

• Selector Channel
  • 선택 채널
  • 고속 입출력장치(자기로 시작하는 친구들)와 입출력하기 위해 사용
  • 특정 한 개의 장치를 독점해서 입출력
• MultiPlexer Channel
  • 다중채널
  • 저속 입출력장치(카드리터, 프린터)를 제어하는 채널
  • 동시에 여러 개의 입출력장치 제어
• Block Multiplexer Channel
  • 고속 입출력장치를 제어
  • 동시에 여러 개의 입출력장치 제어

인터럽트

• 프로그램 실행 도중 예기치 않은 상황이 발생하는 경우 현재 작업을 즉시 중단하고 발생된 상황을 우선 처리 후 실행 중인 작업으로 복귀
• 내부 인터럽트는 CPU의 하드웨어 신호에 의해 발생
• 소프트웨어 인터럽트는 명령어의 수행에 의해 발생

외부 인터럽트​

• 입출력장치, 타이밍장치, 전원 등 외부 요인에 의해 발생
• 전원 이상 인터럽트 : 정전이거나 정원이상
• 기게 착오 인터럽트 : CPU의 기능적인 오류 동작 발생
• 외부 신호 인터럽트
  • Time Slice 를 알림
  • 인터럽트 키를 누른 경우 (Ctrl + Alt + Del)
  • 외부 장치로부터 인터럽트 요청이 있는 경우
• 입출력 인터럽트
  • 입출력 데이터의 오류나 이상현상 발생
  • 입출력장치가 데이터 전송을 요구하거나 전송이 끝났을 때

내부 인터럽트​

• 잘못된 명령이나 데이터를 사용할 때 발생
• 트랩
• 프로그램 검사 인터럽트
  • 0으로 나누기
  • 오버플로 또는 언더플로
  • 프로그램에서 명령어 잘못 사용
  • 부당한 기억장소의 참조
  • 프로그램상 오류

소프트웨어 인터럽트​

• 프로그램 처리중 명령의 요청에 의해 발생
• SVC 인터럽트
  • 제어 프로그램 호출 인터럽트 = SuperVisor Call
  • 사용자가 SVC 명령을 써서 의도적으로 호출한 경우
  • 복잡한 입출력 처리를 해야하는 경우
  • 기억장치 할당 및 오퍼레이터와 대화를 해야하는 경우

인터럽트시 CPU확인 요소​

• 프로그램 카운터 내용
• 사용한 모든 레지스터의 내용
• 상태 조건의 내용 = PSW = Status Register

동작 원리​

1. 인터럽트 요청 신호 발생
2. 현재 인스트럭션까지 실행 후 프로그램 실행 중단
3. 현재 프로그램 상태 보존
4. 인터럽트 처리 루틴 실행
5. 인터럽트 서비스(취급) 루틴 실행

• 처리기 상태 복구
• 인터럽트 원인 결정
• 처리기 레지스터의 상태 보존
• 상대적으로 낮은 레벨의 마스크 레지스터 클리어

6. 상태 복구
7. 중단된 프로그램 실행 재개

인터럽트 우선순위

1. 전원 이상 = Power Fail
2. 기계 착오 = Machine Check
3. 외부 신호 = External
4. 입출력 = I/O
5. 명령어 잘못
6. 프로그램 = Program Check
7. SVC = Supervisor Call

• Non Maskable Interrupt : 마스크 불가능 인터럽트로 0순위

폴링​

• 소프트웨어적 인터럽트 우선순위 판별 방식
• 우선순위가 높은 인터럽트 자원의 인터럽트 요청 플래그를 검사해 해당하는 인터럽트 서비스 루틴을 수행
• 우선순위 변경이 쉽다.
• 자기디스크와 같이 속도가 빠른 장치에 높은 등급 부여
• 회로가 간단하고 융통성이 있음
• 별도의 하드웨어가 필요 없어 경제적
• 많은 인터럽트가 있을 때 모두 조사해야하므로 반응시간이 느림

벡터 인터럽트​

• 하드웨어적인 인터럽트 판별 방식
• CPU와 인터럽트를 요청할 수 있는 장치 사이에 장치 번호에 해당하는 버스를 연결하여 요청 장치의 번호를 CPU에게 알리는 방식
• 인터럽트를 발생한 장치가 프로세서에게 분기할 곳에 대한 정보를 제공
• 인터럽트 벡터 : 인터럽트 처리 루틴으로 분기하는 명령어만을 기억하는 기억장치의 특정 영역으로 분기번지가 저장됨
• 별도의 프로그램 루틴이 없어 응답속도가 빠름
• 회로가 복잡하고 융통성이 없음
• 추가 하드웨어가 필요하므로 비경제적

직렬 우선순위​

• 데이지 체인 방식
• 모든 장치를 한 개의 회선에 직렬로 연결

병렬 우선순위​

• 인터럽트가 발생하는 각 장치를 개별적인 회선으로 연결
• 각 비트를 개별적으로 세트할 수 있는 Mask Register 사용
• 마스크 레지스터는 인터럽트 요청의 허락이 가능하다.
• 우선순위는 마스크 레지스터의 비트 위치에 의해서 결정
• 우선순위가 높은 것이 서비스 받고 있을 때 우선순위가 낮은 것을 비활성화시킬 수 있다.
• 높은 우선순위의 인터럽트는 낮은 인터럽트가 처리되는 중에도 우선 처리된다.

기억장치

• 주기억장치 : 시스템 프로그램영역과 사용자 프로그램영역으로 구성
  • 반도체 : RAM, ROM
  • 자기 : 자기 코어
• 보조기억장치
  • DASD : 자기 디스크, 자기 드럼, 하드 디스크, 광디스크
  • SASD : 자기테이프
• 특수기억장치 : 복수 모듈 기억장치, 연관기억장치, 캐시기억장치, 가상기억장치
• 광디스크의 종류 : 블루레이, DVD, Compact

계층구조​

• 특수기억장치 : 레지스터, 캐시, 연관
• 주기억장치 : RAM, ROM, 자기코어
• 보조기억장치 : 자기디스크, 자기테이프

특성 결정 요소​

기억 용량​

Access Time​

• 기억장치에 읽기 요청이 발생한 시간부터 요구한 정보를 꺼내서 사용 가능할 때까지의 시간
• 한 Word의 단위 정보를 읽거나 기록하는데 걸리는 시간
• Access Time = Seek Time + Latency Time(Search Time) + Transmission Time

Cycle Time​

• 기억장치에 읽기 신호를 보낸 후 다시 읽기 신호를 보낼 수 있을 때까지의 시간 간격
• Cycle Time ≥ Access Time
• DRAM : Cycle Time = Access Time + Refresh Time
• 자기코어 : Cycle Time = Access Time + Restoration Time
• 기타 모든 장치 : Cycle Time = Access Time

Bandwitdh​

• 대역폭 = 전송률 = 밴드폭
• 메모리에서 또는 메모리까지 1초동안 전송되는 최대한의 정보량
• 기억장치의 자료 처리 속도를 나타내는 단위
• 하드웨어 특성상 주기억장치가 제공할 수 있는 정보 전달능력의 한계를 의미
• 메모리 워드의 길이가 작을수록 대역폭이 좋음
• 전송단위 : bps = Baud = 보

구분​

주기억장치

ROM​

• Read Only Memory
• 읽기전용
• 비휘발성 메모리
• BIOS, 자가진단프로그램 등 변경 가능성이 거의 없는 시스템 소프트웨어 탑재

종류​

• Mask ROM : 제조 공장에서 프로그램되어 나옴, 내용 변경 불가
• PROM : Programmable ROM, 한 번만 쓰기 가능
• EPROM : Erasable PROM, 자외선을 사용해 내용을 지울 수 있음
• EAROM : Erasable Alterable ROM, 전기적 특성을 이용하여 기록된 정보 일부를 바꿀 수 있는 ROM
• EEPROM : Electonic EPROM, 전기를 이용해 내용 수정 가능

RAM​

• Random Access Memory, Read Write Memory
• 현재 사용중인 프로그램이나 데이터가 저장
• 휘발성 메모리 = Volatile Memory
• 정보가 저장된 위치는 주소로 구분

자기 코어​

• 전류 일치 기술에 의하여 기억장소를 선별
• 데이터를 읽으면 내용이 지워지는 파괴 메모리
• Dectructive Read Out Memory
• 내용을 읽은 후 지워진 내용을 기록하기 위한 재저장 시간 필요
• 현재 거의 사용되지 않음

구성​

• 구동선 : X,Y축 번지 선택선 2개
• 센스선 : 자기 코어의 상태를 검출하는 선 1개
• 금지선 : 불필요하게 자화되었을 때 금지 전류를 흘려 자화를 소진시키는 선 1개

반도체 기억소자 구성​

RAM​

• CS1, CS2 : 칩 선택선
• RD : 입력 신호선
• WR : 출력 신호선
• AD : 주소선
  • MAR과 PC의 수와 같음
  • 주소선이 n개이면 2^n개의 워드 지정 가능
• Data Bus : 워드의 크기
  • MBR = IR = 단어의 크기
  • 버스가 10Bit이면 워드의 크기가 10Bit

ROM​

• CS1, CS2 : 칩 선택선
• AD : 주소선
• Data Bus : 워드의 크기

보조기억장치

• 주기억 장치의 단점 보완
• 속도는 느리지만 전원이 차단되도 내용 유지
• 저장용량이 큼
• CPU와 직접 자료교환이 불가능
• 주기억장치에 데이터를 저장할 때 DMA를 사용

자기 테이프​

• 순차처리 = SASD
• 블록단위로 데이터를 전송
• 블록 사이에는 데이터를 기록할 수 없는 공간인 갭이 있다.
• BOT : Beginning Of Tape
• EOT : End Of Tape
• BPI : Byte Per Inch, 1인치에 기억할 수 있는 바이트 수
• IRG : Inter Record Gap, 레코드와 레코드 사이의 갭
• IBG : Inter Block Gap, 블록과 블록 사이의 갭
• Block : 한 개 이상의 논리 레코드의 집합 = 물리 레코드
• 블로킹 : 한 개 이상의 논리적 레코드를 묶어서 테이프에 기록하는 방식
  • IRG가 줄어든다.
  • 기억공간 낭비 감소
  • Access Time 감소
  • 입출력 횟수 감소
• Blocking Factor : 하나의 블록을 구성하는 논리 레코드의 갯수

자기 디스크​

• DASD
• 회전축에 여러장의 디스크를 연결하고, 디스크 상하면마다 R/W Head를 액세스암에 연결하여 구성
• 가장 윗면과 가장 아랫면은 사용하지 않는다.
• 트랙 : 디스크 표면에서 회전푹을 중심으로 데이터가 기록되는 동심원
• 섹터 : 트랙들을 일정한 크기로 구분한 부분이며 정보 기록의 기본 단위
• 실린더 : 서로 다른 면들에 있는 동일 위치의 트랙들의 모임
• Random Access와 Sequential Access 방식을 모두 사용

디스크의 3요소​

• 디스크
• 액세스암
• 헤드

Access Time​

• Access Time = Seek Time + Latency Time + Transmission Time
• Seek Time : 탐색시간으로 R/W Head가 특정 트랙까지 이동하는데 걸리는 시간
• Latency Time : R/W Head가 특정 트랙까지 이동한 후 디스크가 회전하여 트랙에 포함되어 있는 특정 섹터가 R/W Head까지 도달하는데 걸리는 시간
  • Search Time = Rotational Delay Time
• Transmission Time : 전송시간으로 R/W Head가 액세스한 섹터와 주기억장치 간의 자료전송에 걸리는 시간

자기 드럼​

• 각 트랙마다 고정된 R/W Head를 두고 있다.
• DASD
• Access Time = Latency Time + Transmission Time

연관기억장치

• 기억장치에서 기억된 내용의 일부를 이용하여 액세스하는 자료를 찾는 기억장치
• CAM = Content Addressable Memory = 연상기억장치
• 정보 검색 빠름
• 캐시 메모리나 가상 메모리 관리기법에서 사용하는 매핑 테이블에 사용
• 외부 인자와 내용을 비교하기 위한 병렬 판독 논리회로를 가지고 있음
• 하드웨어 비용 증가

구조​

• 데이터 레지스터 : 인수 레지스터, 찾고자 하는 내용의 일부를 기억하는 레지스터
• 키 레지스터 : 마스크 레지스터, 검색에 사용할 비트를 결정하는 레지스터
• 매치 레지스터 : 일치 지시기, 데이터를 찾은 경우 찾았다고 표시하기 위해 사용

복수모듈기억장치

• 독자적으로 데이터를 저장할 수 있는 기억장치 모듈을 여러 개 가진 기억장치
• 주기억장치와 CPU의 속도 차이 문제점을 개선
• 기억장치의 버스를 시분할하여 사용
• 각각의 기억장치는 자체 어드레스 레지스터와 버퍼 레지스터를 가지고 독자적으로 데이터를 저장
• 인터리빙 기법에 의해 기억장치를 구성하는 모듈 수만큼 단어(워드)들에 동시 접근 가능
• 버스가 많으면 모든 모듈 동시 병렬 접근 가능

메모리 인터리빙​

• Memory Interleaving = 디스크 인터리빙
• 여러 개의 독립 모듈로 이루어진 복수 모듈 메모리와 CPU 간의 주소 버스가 한 개로만 구성되어 있으면 같은 시각에 CPU로부터 여러 모듈로 동시에 주소를 전달할 수 없다.
• CPU가 각 모듈로 전송할 주소를 교대로 배치한 후 차례대로 전송하여 여러 모듈을 병행 접근하는 기법
• 중앙처리장치와 기억장치 사이의 실질적인 대역폭 효율을 높일 수 있다.
• 캐시 기억장치, 고속 DMA에서 사용
• CPU 유휴시간 감소

캐시 메모리

• CPU와 주기억장치의 속도차를 줄이기 위해 사용
• 고속 Buffer Memory
• 자주 사용하는 프로그램과 데이터를 기억
• 메모리 계층에서 가장 빠른 소자
• 캐시 주소표는 검색 시간을 단축시키기 위해 연관기억장치(CAM)을 사용

설계 고려사항​

• 캐시 크기
• 전송 블록 크기
• 교체 알고리즘

매핑 프로세스​

주기억장치로부터 캐시 메모리로 데이터를 전송하는 방법

직접 매핑​

• Direct Mapping
• 주기억장치의 블록들이 지정된 한 개의 캐시 라인으로만 매핑되는 방법
• 간단하고 구현 비용이 적다
• 적중률이 낮다

어소시에이티브 매핑​

• Assciative Mapping = 연관 매핑
• 직접 매핑의 단점 보완
• 모든 태그를 병렬로 검사하기 때문에 복잡하고 비용이 높음
• 거의 사용안함

세트-어소시에이티브 매핑​

• 직접 매핑과 연관 매핑의 장점만 취함

쓰기 정책​

저장되어 있는 데이터 수정이 발생할 때 수정된 내용을 주기억장치에 갱신하기 위해 시기와 방법을 결정하는 것

• Wirte-Through : 캐시에 쓰기 동작이 이루어질 때마다 캐시 메모리와 주기억장치의 내용을 동시 갱신
• Write-Back : 캐시에 쓰기 동작이 이루어지는 동안은 캐시의 내용만이 갱신, 캐시의 내용이 캐시로부터 제거될 때 주기억장치에 복사
• Write-Once : 캐시에 쓰기 동작이 이루어질 때 한 번만 기록하고 이후의 기록은 모두 무시

적중률​

• 캐시메모리에 접근하는 경우 원하는 정보가 캐시 메모리에 기억되어 있을 때 적중되었다고 함
• 캐시 기억장치가 있는 컴퓨터의 성능을 나타네내는 척도
• 적중률 = 적중횟수 / 총 접근 횟수
• 미스율 = 1 - 적중률

가상기억장치

• 기억 용량이 작은 주기억장치를 큰 용량을 가진 것처럼 사용할 수 있는 기법
• 보조기억장치를 이용한 주기억장치의 용량 확보
• 소프트웨어적 방법으로 구현
• 프로그램을 여러 블록으로 나눠서 보조기억장치에 보관하고 프로그램 실행시 필요 부분만 주기억장치에 적재
• 오버레이 문제가 자동적으로 해결
• 보조기억장치 접근이 빈번하면 시스템 처리 효율이 저하
• DASD에만 가능

주소​

• 가상주소 : 논리주소로 보조기억장치 상의 주소
• 실기억주소 : 물리적주소로 주기억장치 상의 주소

관리​

• 페이징 기법 : OS가 보조기억장치에 있는 프로그램을 동일한 크기의 블록으로 나눠서 관리
• 세그먼트 기법 : 사용자가 보조기억장치에 있는 프로그램을 가변적인 크기의 블록으로 나눠서 관리

관리전략​

반입 전략​

• Fetch
• 보조기억장치에 보관중인 프로그램이나 데이터를 언제 주기억장치로 적재할 것인가?

배치 전략​

• Placement
• 새로 반입되는 포르개림이나 데이터를 주기억장치 어디에 위치시킬 것인가를 결정
• 최초, 최적, 최악접합이 있음

교체 전략​

• Replacement
• 주기억장치의 영역이 이미 사용중인 상태에서 새로운 프로그램을 주기억장치에 배치할 때 어떤 방식을 사용할지 결정하는 전략
• FIFO, OPT, LRU, NUR, LFU, MFU 등
• Page Fault 발생시 교체할 페이지를 결정해서 보조기억장치의 이전 위치에 기억시키고 새 페이지를 교체한 페이지의 위치에 놓는 것을 스테이징이라 한다
• 스테이징 : 느린 장치에서 바른 장치로 옮겨가는 것

주소 매핑​

• 가상주소를 실 기억주소로 변환하는 작업
• 가상주소 형식 : 페이지 번호와 변위값
• 실기억주소 형식 : 페이지 프레임과 변위값
• 페이지 맵 테이블 : 디스크 페이지 번호와 페이지 프레임 번호, 상태 비트

변환 순서​

• 페이지 번호에 해당하는 페이지 프레임 번호와 가상주소의 변위 주소값을 이용해 실 기억주소를 만듦
• 실기억주소를 이용하여 주기억장치를 액세스

병렬 컴퓨터

• I/O 채널 또는 프로세서와 같은 다수의 프로세서에서 동시에 여러 프로세스를 처리하는 것
• 일부 하드웨어 오류가 발생해도 전체 시스템은 동작
• 처리 속도가 빠름
• 프로그램 작성이 어려움
• 기억장치 공유
• 특수한 업무에 적용 : 예보, 인공지능, 역학계산, 모의실험, 유도탄 등

Flynn의 분류​

플린의 분류, 명령 흐름과 자료 흐름을 고려하여 분류

SISD​

• Single Instruction stream Single Data stream
• 현재 보통 컴퓨터 구조
• 명령 하나가 자료 하나를 처리
• 파이프라인에 의한 시간적 병렬 처리 가능

SIMD​

• Single Instruction stream Multi Data Stream
• 한 개의 명령으로 여러 데이터를 동시에 처리하는 구조
• 배열 처리기에 의한 동기적 병렬처리가 가능
• 다수의 처리기가 한 개의 제어장치에 의해 제어

MISD​

• Multi Instruction stream Single Data stream
• 다수의 처리기에 의해 각각의 명령들이 하나의 데이터를 처리하는 구조
• 실제로 사용되지 않음
• 파이프라인에 의한 비동기적 병렬처리 가능

MIMD​

• Multi Instruction stream Multi Data stream
• 다수의 처리기가 각각 다른 명령 흐름과 자료 흐름을 가지고 여러 개의 자료를 처리하는 구조
• 각 처리기 사이에에서 상호작용(Interaction)이 일어남
• 멀티 프로세서에 의한 비동기적 병렬처리 가능
• Tightly Coupled System = 다중 처리기
• Loosely Coupled System = 분산 처리 시스템

Feng의 분류​

팽은 병렬 수행 정도에 따라 분류

WSBS​

• Word-Serial, Bit-Serial
• 한 번에 한 비트씩 처리하는 방식 (초기 컴퓨터)

WPBS​

• Word-Parallel, Bit-Serial
• 단어를 묶어서 그 중 한 개의 비트 슬라이스 단위를 순차적으로 처리

WSBP​

• Word-Sreial, Bit-Parallel
• 한 번에 한 단어씩 병렬로 처리
• 현재의 컴퓨터

WPBP​

• Word-Parallel, Bit-Parellel
• 단어별 병렬, 비트별 병렬 처리

병렬 처리 기법

파이프라인 프로세서​

• CPU 처리속도를 높이기 위해 여러개의 인스트럭션을 동시에 병렬처리하는 장치
• 시간적 병렬처리
• 명령인출 => 명령 해독 => 오퍼랜드 인출 => 명령 실행
• 스칼라 프로세서를 이용하는 기법
• 파이프라인이 차고 나면 연산속도가 빠르다.
• 같은 연산이 반복되면 효율적이지만 아니면 구조가 복잡하고 시간이 오래 걸린다.

벡터 프로세서​

산술 및 논리연산, 비교, 내적연산, 최대, 최소값 구하기 등 벡터 연산 명령을 효율적으로 수행하도록 구성된 처리기

시스톨릭 프로세서​

• 데이터 흐름과 제어 흐름이 규칙적인 특징을 갖는 시스톨릭 알고리즘을 이용하여 수행하는 처리기
• 파이프라인화 된 벡터 프로세서와 배열 프로세서의 특징을 결합한 것
• 초고밀도 직접회로(VLSI) 기법을 이용하여 구현
• 응용의 한계성과 프로그래밍의 어려움이 있음

배열 프로세서​

• 배열처리기는 PE(Processing Element)라 불리는 다수의 연산기를 갖는 동기적 병렬 처리기
• 명령 해독 및 제어는 제어장치가 하고, PE들는 명령 해독 능력이 결여된 수동적 장치로 명령처리만 한다.
• PE를 중복 이용해서 공간적 병렬성을 얻는다.
• 벡터 계산이나 행렬 계산에 적합

데이터 플로우 컴퓨터​

• 데이터 흐름 컴퓨터는 PC(Program Counter)가 필요 없다.
• 제어 흐름 컴퓨터와는 반대되는 개념
• 인스트럭션의 필요한 피연산자가 모두 준비되었을 때 인스트럭션을 수행하고 결과를 필요로하는 인스트럭션에 보내주는 방식

필요한 데이터를 수집, 필요시에 처리하는 수단

• 자료 : 관찰이나 측정을 통해 수집, 가공되지 않은 상태
• 정보 : 자료를 가공

자료처리시스템​

정보시스템의 서브시스템

• 일괄처리시스템 : 급여, 회계, 세무 등 모아서 처리

• 온라인실시간처리시스템 : 예약, 은행처리

• 분산처리시스템

• 데이터웨어하우스 : 업무 시스템에서 추출 된 데이터 집합체

DB 시스템

개념​

• 통합된데이터 : 중복을 배제한 데이터의 모임 (Integrated)
• 저장된데이터 : 저장매체에 저장된 자료 (Stored)
• 운영데이터 : 업무를 수행하는데 반드시 필요한 자료 (Operational), 임시불가
• 공용데이터 : 공동으로 소유, 유지 하는 자료 (Shared)

특징​

• 실시간접근성 : (Real-Time Accessibility)
• 계속적인변화 : (Continuous Evolution)
• 동시공용 : (Concurrent Sharing)
• 내용에 의한 참조 : 주소나 위치에 의해서가 아니라 사용자가 요구하는 데이터로 검색(Content Reference)

구성요소​

• 데이터베이스
• 스키마
• DBMS
• DB언어
• DB컴퓨터
• DB사용자

DBMS

• DB 관리 소프트웨어
• 모든 응용 프로그램이 DB 공용하도록 관리
• DB 구성, 접근방법, 유지관리에 책임

DBMS의 기능​

• 정의(조직)기능 : 데이터 타입과 구조 정의, 이용방식, 제약조건 명시 (Definition)
• 조작기능 : CRUD를 위해 사용자와 DB사이의 인터페이스 수단을 제공 (Manipulation)
• 제어기능 : 데이터 무결성, 보안, 권한, 병행제어 처리 (Control)

DBMS의 장단점​

• 단점 : 전문가부족, 비용증가, Overhead, Backup과 Recovery의 어려움, 복잡

파일시스템의 문제점

• 종속성 : 데이터의 접근방법을 변경하면 응용프로그램도 변경
• 중복성 : 일관성, 보안성, 경제성, 무결성 위반

데이터독립성

• 논리적 독립성 : 응용프로그램과 DB를 독립, 논리적 구조를 변경해도 응용프로그램 변경하지 않음
• 물리적 독립성 : 응용프로그램과 물리적장치 독립, DB에 디스크를 추가해도 응용프로그램 변경하지 않음

DB의 구성요소

• 개체
• 속성 : 개체의 성질
• 관계

데이터사전

• 모든 데이터 개체들에 대한 정보를 유지 관리
• alias 시스템 카탈로그
• 데이터에 관한 데이터

스키마

• 외부스키마
• 개념스키마
• 내부스키마

특징​

• 데이터 사전에 저장
• alias 메타데이터
• 데이터의 구조적 특성을 의미
• 인스턴스에 의해 규정

외부스키마​

• 개인이 필요로하는 DB의 논리적 구조
• VIEW
• alias 서브스키마
• 여러 개 존재 가능
• 사용자는 SQL을 사용해 접근
• 응용 프로그래머는 COBOL, C를 사용해 접근

개념스키마​

• DB의 전체적인 논리적 구조
• 하나만 존재
• DB 파일에 저장되는 데이터의 형태를 나타냄
• alias 스키마
• DBA에 의해 구성

내부스키마​

• 물리적 저장장치에서 본 DB 구조
• DB에 저장될 레코드의 물리적인 구조 정의
• 내부 레코드의 물리적 순서를 기술
• alias 저장스키마
• 시스템 프로그래머나 시스템 설계자가 봄

DB언어

DDL​

• DB를 구축하거나 수정

DML​

• 비절차적 데이터 언어
• SQL, IMS, DBTG, TOTAL

DCL​

• 무경설, 보안, 권한, 회복

DB 사용자

DBA​

• DDL, DML, DCL 사용

응용 프로그래머​

• DML을 사용해 일반 사용자에게 응용프로그램 제공

일반사용자​

• SQL 사용

데이터 모델

정보를 단순화, 추상화하여 체계적으로 표현한 개념적 모형

개념적 데이터 모델​

• 추상적인 개념으로 표현
• 개체와 관계를 통해 현실을 표현
• ER모델
• 현실 세계의 개체를 인간이 이해하는 구조로 기술

논리적 데이터 모델​

• 데이터 타입과 데이터 타입간의 관계를 통해 현실을 표현
• DBMS는 논리적 데이터 모델을 하나만 사용
• 관계모델, 계층모델, 네트워크모델
• 현실 세계의 개체를 컴퓨터의 데이터구조로 기술

표시요소​

표현요소, 구성요소

• 구조 : 논리적으로 표현된 개체 타입들 간의 관계로 데이터 구조 및 정적 성질을 표현 (Structure)
• 연산 : DB에 저장된 실제 데이터를 처리하는 작업에 대한 명세로 DB를 조작하는 기본 도구 (Operation)
• 제약조건 : 실제 데이터의 논리적인 제약조건 (Constraint)

구성요소​

• 개체 : DB에 표현하려는 것, 유무형의 정보, 서로 연관된 속성, fs의 레코드 (Entity)
• 속성 : 데이터의 가장 작은 논리적 단위, fs의 데이터항목 또는 데이터 필드, 개체를 구성하는 항목 (Attribute)
• 관계 : 개체 간 또는 속성 간의 관계 (Relationship)

ER모델

Perter Chen, 개념적 표현

ERD​

• 개체 : □
• 관계 : ◇
• 속성 : ○
• 기본키속성 : 밑줄원 또는 ●
• 연결 : 선, 링크로 개체와 속성을 연결
• DB의 논리적 구조 표현

관계형 데이터모델

테이블 (Relation)으로 표현

계층형 데이터모델

트리, 노드 = 개체, 부모 자식 관계

특징​

• 연쇄삭제
• 개체 간 사이클 허용 안됨
• 개체 = 세그먼트
• DBMS = IMS

장점​

• 구조 간단, 판독 용이
• 구현, 수정, 검색 용이
• 독립성 보장

단점​

• 데이터 상호 유연성 붖고
• 검색경로 한정
• 삽입 삭제 연산 매우 복잡
• 다 대 다 관계 처리 어려움

망형 데이터모델

CODASTYL DBTG 모델, 그래프, Owner-Member, N:M 관계

DB설계

고려사항​

• 무결성
• 일관성
• 회복
• 보안
• 효율성
• DB 확장가능

개념적 설계​

• 개념 스키마 모델링과 트랜젝션 모델링
• ERD 작성
• alias 정보 모델링
• 독립적 개념스키마

논리적 설계​

현실세계를 물리적저장장치에 저장할 수 있도록 논리적 자료구조로 변환

• 트랜잭션 인터페이스 설계
• 테이블 설계
• alias 데이터 모델링
• 종속적 논리스키마

물리적 설계​

• DB file의 저장구조 및 액세스 경로 결정
• 데이터가 컴퓨터에 저장되는 방법 묘사
• 저장 레코드 양식 설계
• 데이터타입
• 데이터 값의 분포
• 접근 빈도
• 레코드 집중의 분석 설계
• 접근 경로 설계
• 기본 단위는 저장레코드

고려사항​

• 인덱스 구조
• 반응시간 : (Response Time)
• 공간활용도 : (Space Utilization)
• 트랜잭션 처리량 : (Transaction Throughput)

DB 구현​

• DDL 이용해 스키마 기술
• 응용 프로그램을 위한 트랜잭션 작성
• DB 접근을 위한 응용 프로그램 작성

설계 순서​

요구 분석 > 개념적 설계 > 논리적 설계 > 물리적 설계 > 구현

관계형 DB 구조

테이블로 표현

• 릴레이션 스키마 : 속성명
• 릴레이션 인스턴스 : 데이터

튜플​

• row
• 튜플은 릴레이션을 구성하는 각각의 행 ㅡ
• 속성의 모임
• fs의 레코드
• 튜플의 수 = 카디널리티 (Cardinality) = 기수 = 대응수

속성​

• column
• DB를 구성하는 가장 작은 논리적 단위, 열 ㅣ
• fs의 데이터 또는 데이터 필드
• 개체의 특성
• 속성의 수 = 디그리 (Degree) = 차수

도메인​

• 하나의 속성 값들의 집합

관계형 DB 제약조건

후보키​

모든 튜플에 대해 유일성과 최소성 만족

• 유일성 : 하나의 키값으로 하나의 튜플만 식별 가능
• 최소성 : 모든 레코드를 유일하게 식별하는데 필요한 속성

기본키​

특정 튜플을 유일하게 구별할 수 있는 속성으로 후보키 중 선택한 Main key

• Null 값 불가

대체키​

• 후보키가 둘 이상일 때 기본키를 제외한 나머지 후보키
• alias 보조키

슈퍼키​

• 속성들의 집합으로 구성된 키
• 유일성은 만족, 최소성은 불만족

외래키​

• 기본키를 포함하면 참조 릴레이션
• 외래키를 포함하면 참조하는 릴레이션

무결성

• 개체무결성 : 기본키를 구성하는 속성은 NULL이나 중복 불가
• 참조무결성 : 외래키 값은 NULL이거나 참조 릴레이션의 기본키와 동일, 도메인과 속성 갯수가 같아야함

관계대수

관계형 DB에서 원하는 정보를 얻기 위해 사용하는 절차적인 언어로 연산자와 연산규칙을 제공한다.

• 순수 관계 연산자 : Select, Project, Join, Division
• 일반 집합 연산자 : Union, Intersection, Difference, Cartesian Product

순수 관계 연산자​

Select​

• 수평연산
• 시그마(σ)

Project​

• 속성만 추출하는 연산
• 수직연산
• 파이(π)

Join​

• 두 개의 릴레이션을 합쳐서 새로운 릴레이션으로 반환
• 나비넥타이 (▷◁)
• 자연조인 : 중복된 속성을 제거하여 같은 속성을 한 번만 표기하는 방법

Division​

• 속성을 제외한 속성만을 구하는 연산
• 나누기 (÷)

일반 집합 연산자​

• 합집합, 교집합, 차집합은 합병 조건이 가능해야함.
• 합병조건 : 합병하려는 두 릴레이션 간에 속성 수가 같고 도메인의 범위가 같음

합집합​

• Union
• A ∪ B ≤ A ＋ B
• 합집합의 카디널리티는 두 릴레이션의 카디널리티의 합보다 크지 않다.

교집합​

• Intersection
• A ∩ B ≤ MIN(A, B)
• 교집합의 카디널리티는 두 릴레이션 중 작은 릴레이션보다 크지 않다.

차집합​

• Difference
• A－B ≤ A
• 차집합의 카디널리티는 A의 카디널리티보다 크지 않다.

교차곱​

• Cartesian Product
• (A×B) = (A)×(B)
• 교차곱은 두 릴레이션의 카디널리티를 곱한 것과 같다.
• 디그리(차수)는 더하고, 카디널리티(튜플 수)는 곱하면 된다.

관계해석

• E.F.Codd가 Predicate Calculus에 기반
• 연산을 표현하는 방법, 원하는 정보를 정의시 계산 수식 사용
• 비절차적 특성
• 튜플 관게해석과 도메인 관계해석
• 질의어로 표현

정규화

잘못 설계된 관계형 스키마를 작은 스키마로 쪼개서 바람직하게 만드는 과정으로 DB의 논리적 설계 단계에서 수행

목적​

• 안정성 최대화
• 어떠한 릴레이션이라도 DB에서 표현이 가능
• 효과적인 검색 알고리즘
• 중복 배제하여 CRUD 이상의 발생 방지
• 데이터 삽입시 릴레이션 재구성 필요성 제거

Anomaly​

속성 간 종속 또는 튜플의 중복으로 발생

• 삽입이상 : 원하지 않는 값도 같이 삽입
• 삭제이상 : 연쇄 삭제
• 갱신이상 : 일부만 갱신

과정​

1NF​

원자값으로만 되어있는 릴레이션

2NF​

키가 아닌 모든 속성이 기본키에 대해 완전 함수적 종속

• 함수적 종속관계 : A에 따라 B가 항상 같은 값이 나올 때 (키->값)
• 완전 함수적 종속관계 : A,B에 따라 C가 항상 같은 값이 나오지만 A-C, B-C에서는 종속이 사라질 때 (여러 키->값)

3NF​

키가아닌 모든 속성이 기본키에 대해 이행적 종속관계를 제거

• 이행적 종속관계 : A->B, B->C일 때 A->C 인 관계

BCNF​

릴레이션에서 결정자가 모두 후보키인 관계 (Boyce-Codd Normal Form)

• 결정자 : A->B 일 때 A를 결정자, B를 종속자
• 모든 BCNF가 종속성을 보존하는 것은 아니다.

4NF​

릴레이션에서 A->->B가 성립할 때 모든 속성이 A에 함수적 종속인 관계

• 다치종속 : A,C에 대응하는 B값들이 A에만 종속되고 C에는 무관할 때 A->->B

5NF​

조인 종속성이 후보키를 통해서만 만족될 때

• 조인종속 : 어떤 릴레이션이 자신의 pROJECTION에 대한 조인의 결과가 자신과 같을 때

SQL

• IBM에서 개발한 SEQUEL에서 진화

• 관계대수와 관계해석을 기초로한 혼합 데이터 언어

• 정의, 조작, 제어 기능

• DDL : Create, Alter, Drop

• DML : Select, Insert, Delete, Update

• DCL : Commit, Rollback, Grank, Revoke

DDL​

• CREATE SCHEMA|DOMAIN
• CREATE TABLE 테이블명 PRIMARY UNIQUE FOREIGN KEY REFERENCES CONSTRAINT CHECK
• CREATE INDEX ON [CLUSTER]
• ALTER TABLE ADD|ALTER|DROP [CASCADE]
• DROP SCHEMA|DOMAIN|TABLE|VIEW|INDEX [CASCADE|RESTRICTED]

DML​

• SELECT FROM [WHERE][group by] [HAVING][order by]

DML​

• INSERT INTO VALUES
• DELETE FROM WHERE
• UPDATE SET

내장 SQL

컴퓨터 프로그램에 SQL 명령을 삽입한 것

• 일반 SQL은 여러 개의 튜플을 반환하지만, 내장 SQL은 단 하나의 튜플을 반환
• 반환되는 튜플은 일반 변수를 사용하여 저장 가능
• 호스트 변수와 DB 필드명은 같아도 된다.
• 내장 SQL 앞에 EXEC SQL 사용
• 호스트 변수는 변수앞에 콜론(:)을 붙임

커서​

• 내장 SQL문의 수행 결과로 복수의 튜플이 반환될 시 액세스 할 수 있게 해준다.
• 질의 수행 결과로 반환되는 첫 튜플에 대한 포인터

커서 명령어​

• DECLARE : 선언
• OPEN : 첫번째 튜플 포인트
• FETCH : 다음 튜플로 포인터 이동
• CLOSE : 종료

뷰

• 본 테이블로 유도된 가상 테이블
• 조인 사용 최소화로 사용상의 편의성을 최대화
• 외부 스키마
• 물리적으로 구현되어 있지 않음
• 뷰가 정의된 테이블이나 뷰를 삭제하면 그걸 참조한 다른 뷰도 삭제됨.

장점​

• 논리적 데이터 독립성 제공
• 보안

단점​

• 독립적인 인덱스 사용 불가
• 정의 변경 불가
• CRUD 제한

시스템 카탈로그

• 시스템에 관련된 다양한 객체가 담긴 시스템 DB
• alias 자료사전 = data dictionary = 카탈로그 = 데이터사전
• 메타데이터 : 카탈로그에 저장된 정보
• SQL을 이용해 내용 검색 가능
• 수정 및 삽입 불가
• DB에 따라 다른 구조
• DBMS가 스스로 생성하고 유지
• 시스템, 사용자 접근가능

Data Directory​

• 데이터 사전에 있는 데이터를 실제로 접근하는데 필요한 정보를 관리하는 시스템
• 시스템만 접근가능

트랜잭션

• DB 상태를 변환시키는 하나의 논리적 기능의 단위
• 한꺼번에 모두 수행되어야할 연산들
• 병행 제어 및 회복 작업시 처리되는 작업의 논리적 단위
• 시스템이 응답하기 위한 상태 변환 과정의 작업 단위

특성​

무결성을 보장

원자성​

• Atomicity
• 트랜잭션 내의 명령은 반드시 완벽히 수행
• 모두가 수행되거나 오류시 전부가 취소되어야함

일관성​

• Consistency
• DB의 전체 요소는 트랜잭션 수행 전과 트랜잭션 수행 완료 후의 상태가 같아야함 (질량 보존 법칙처럼)

독립성​

• Isolation = 격리성 = 순차성
• 둘 이상의 트랜잭션이 병행 실행되는 경우 다른 트랜잭션 연산이 끼어들 수 없음
• 수행 중인 트랜잭션은 완료될 때 까지 다른 트랜잭션에서 참조 불가.

영속성​

• Durability = 지속성
• 시스템이 고장나도 영구적으로 반영

Commit​

Rollback​

• Active : 트랜잭션 실행 중
• Failed : 트랜잭션 오류 발생으로 중단
• Aborted : 트랜잭션 비정상적 종료로 Rollback 연산 실행한 상태
• Partially Committed : 트랜잭션 마지막 연산까지 실행됬으나 Commit은 안 한 상태
• Committed : 트랜잭션이 성공적으로 종료되어 Commit 연산 실행한 상태

회복

장애 발생으로 DB가 손상되었을 때 복구하는 작업, Recovery

• 트랜잭션 장애 : 실행 또는 로직 오류
• 시스템 장애 : 하드웨어 오동작, 소프트웨어 손상, 교착상태
• 미디어 장애 : 물리적 데미지

회복기법​

연기 갱신 기법​

• Deferred Update
• 트랜잭션동안 갱신된 내용이 Log에 보관됨
• Partially Committed 상태에서 Log에 보관한 내용을 실제 DB에 기록
• Redo 작업만 가능

즉시 갱신 기법​

• Immediate Update
• 트랜잭션 중이라도 DB에 반영
• 장애 대비로 갱신 내용을 Log에 보관
• Redo, Undo 모두 사용 가능

그림자 페이지 대체 기법​

• Shadow Paging
• 트랜잭션을 Rollback할 때, 갱신된 이후의 실제 페이지 부분에 그림자 페이지를 대체하여 회복
• 로그, Undo, Redo 필요 없음

검사점 기법​

• Check Point
• 복구 시점을 로그에 보관하고 그 시점부터 회복작업을 수행

병행제어

다중 실행되는 트랜잭션들이 DB의 일관성을 파괴하지 않도록 트랜잭션 상호작용을 제어하는 것

목적​

• DB 공유 최대화
• 시스템 활용도 최대화
• DB 일관성 유지
• 응답시간 최소화

직렬화 가능성​

병행수행된 각각의 트랜잭션 결과는 각 트랜잭션을 독자적으로 실행했을 때의 결과와 같아야한다.

문제점​

• 갱신 분실 : 갱신 결과의 일부가 없어짐 (Lost Update)
• 비완료 의존성 : 하나의 트랜잭션이 실패 후 회복되기 전에 다른 트랜잭션이 실패한 갱신결과를 참조하는 현상 (Uncommitted Dependency)
• 모순성 : 두 개의 트랜잭션이 병행될 때 원치 않는 자료를 이용 (Inconsistency)
• 연쇄 복귀 : 하나를 Rollback시 다른 것도 Rollback 되는 경우 (Cascading Rollback)

병행제어 기법

로킹​

• Lock이 허락되어야만 액세스할 수 있도록 하는 기법

2단계 로킹 규약​

• Tow-Phase Locking
• 직렬성을 보장하지만 교착상태 예방 불가

타임 스탬프 순서​

• 트랜잭션을 실행 하기 전에 Time Stamp를 부여하여 부여된 시간에 따라 처리
• 교착상태 발생 안함

최적 병행수행​

• 검증 = 확인 = 낙관적 기법
• Read Only 트랝개션일 경우 충돌률이 낮으므로 병행제어를 안하고 실행

다중 버전 기법​

• 갱신될 때마다 버전을 부여하여 관리

무결성

• DB 데이터의 정확성, 일관성을 보장하기 위해 부정확한 자료가 DB내에 저장되는 것을 방지하기 위한 제약조건
• 사용자로부터 DB를 보호
• 사용자가 정확하게 DB를 사용할 수 있도록 보장
• 대표적인 방법은 중앙 통제에 의한 데이터 갱신
• Null 무결성 : 특정 속성이 Null이 될 수 없음
• 고유 무결성 : 각 튜플의 값이 서로 달라야함
• 참조 무결성 : 외래키 값은 Null이거나 참조 릴레이션의 기본키 값과 같아야함.
• 도메인 무결성 : 특정 속성이 그 도메인에 속해야함.
• 키 무결성 : 하나의 테이블에는 적어도 하나의 키가 존재해야함.
• 관계 무결성 : 릴레이션에 한 튜플의 삽입 가능 여부 또는 다른 릴레이션 튜플 사이의 관계에 대한 적절성 여부를 지정.
• 개체 무결성 : 기본 키를 구성하는 어떤 속성도 Null이나 중복값을 가질 수 없음

DB 보안

• 권한이 없는 사용자로부터 DB를 보호
• 사용자들이 DB를 사용하고자 할 때 언제든지 사용할 수 있도록 보장

암호화​

개인키 암호방식​

• alias 비밀키 암호방식 = 대칭 암호방식 = 단일키 암호화 기법
• 동일한 키로 데이터를 암복호화
• 전위, 대체, 대수, 합성기법
• 암복호화 속도가 빠름
• 알고리즘 단순
• 파일 크기가 작음
• 사용자가 증가하면 키 파일이 많아짐
• DES : 64Bit의 평문 블록을 56Bit의 16개의 키를 이용해 암호 계산

공개키 암호방식​

• 서로 다른키로 데이터를 암복호화
• 암호화키는 공개키로 복호화키는 관리자가 관리
• alias 비대칭 암호 방식
• 키 분배가 용이
• 관리할 키 개수가 적음
• 암복호화 속도가 느림
• 알고리즘 복잡
• 파일 크기가 큼
• RSA

권한 부여​

• GRANT 사용자 등급 TO
• REVOKE 사용자 등급 FROM
• CASCADE 사용시 권한을 부여받았던 사용자가 다른 사용자에게 부여한 권한도 연쇄적으로 삭제됨

사용자 등급​

• DBA : DB 관리 책임자
• RESOURCE : DB 및 테이블 생성 가능자
• CONNECT : 단순 사용자

분산 DB

보안, 보호가 어렵다.

구성​

• 분산처리기
• 분산db
• 통신네트워크

목표​

• 위치 투명성 : DB의 논리적인 명칭으로 액세스 가능 (Location Transparency)
• 중복 투명성 : 사용자는 하나의 데이터만 존재하는 것처럼 사용 (Replication Transparency)
• 병행 투명성 : 다수의 트랜잭션이 실행 가능 (Concurrency Transparency)
• 장애 투명성 : 장애가 나도 트랜잭션 처리 가능 (Failure Transparency)

미들웨어​

• 분산 환경에서 구성원을 연결하고 구성원 간의 차이를 극복하도록 범용으로 개발된 소프트웨어
• 클라이언트와 서버 사이에 존재하면서 다중통신, 데이터 액세스 프로토콜과 인터페이스를 지원
• 통신 미들웨어 : NOS
• DB 미들웨어 : ODBC
• 분산 객체 미들웨어 : CORBA, DCOM

자료구조

어떠한 자료구조에서도 필요한 모든 연산을 처리하는 것이 가능하다.

분류​

{
   "선형":{
        "리스트":["선형", "연결"],
        "스택",
        "큐",
        "덱"
    },
   "비선형":["트리","그래프"]
}

리스트

선형 리스트​

• 연접 리스트 = Dense List = 축차 구조 = Sequential Structure
• 배 열
• 간단한 자료 구조
• 접근 속도 빠름
• 중간 자료 삽입시 연속된 빈공간이 있어야함
• 기억장소 효율 가장 좋음
• 이동횟수 : 삽입시 $\frac{n+1}{2}$ 삭제시 $\frac{n-1}{2}$
• 삽입 삭제 시 자료의 이동이 필요하기 때문에 번거로움

연결 리스트​

• 노드의 삽입 삭제 작업 용이
• 기억공간이 연속적이지 않아도 저장 가능
• 연결을 위한 포인터가 필요하기 때문에 기억공간 효율이 좋지 않음
• 트리를 표현할 때 가장 적합
• 희소행렬을 표현하면 기억장소가 절약됨
• 희소행렬 : 행렬의 요소 중 많은 항이 0으로 되어 있는 형태

종류​

• 단순 연결 리스트
• 단순 환상 연결 리스트
• 이중 연결 리스트
• 이중 환상 연결 리스트

스택

• 한 쪽에서만 삽입 삭제 가능

• 후입선출 (LIFO)

• Top : 마지막으로 삽입된 자료의 위치 = 스택 포인터

• Bottom : 스택 바닥

• Overflow

• Underflow

• 부 프로그램 호출시 복귀주소 저장

• 함수 호출의 순서 제어

• 인터럽트 복귀주소 저장

• 후위 표기법 연산

• 0 주소 지정방식 명령어의 자료 저장소

• 재귀 프로그램

• 컴파일러를 사용한 언어 번역

큐

• 선형 리스트의 한쪽에서는 삽입, 다른쪽에서는 삭제만 이루어짐

• 선입선출 (FIFO)

• 시작과 끝을 표시하는 두개의 포인터 존재

• 프런트 포인터

  • 가장 먼저 삽입된 자료의 포인터
  • 삭제 작업시 사용

• 리어 포인터

  • 가장 마지막에 삽입된 자료의 포인터
  • 삽입 작업시 사용

• 운영체제 작업 스케줄링

• spool

덱

• 삽입과 삭제가 리스트 양쪽에서 일어남
• Double Ended Queue
• Stack과 Queue를 합쳐서 만듦
• Scroll : 입력 제한 데크
• Shelf : 출력 제한 데크

트리

• 족보, 연산수식, 구조도, 힙(heap)에 사용
• 근노드 : Root node
• 단말노드 : Terminal Node = Leaf Node
• 차수 : Degree = 가지 수
• 레벨 : 노드의 레벨
• 깊이 : 최대 레벨
• 숲 : Forest 여러 트리의 집합
• tree의 degree : MAX(degree)

이진트리​

• 차수가 2이하인 노드로 구성된 트리
• 레벨 i에서의 최대 노드의 수는 $2^{n-1}$
• 전체의 최대 노드의 수는 $2^n-1$
• 단말 노드 수가 $N_0$, 차수(가지 수)가 2인 노드의 수가 $N_2$라고 할 때 $N_0=N_2+1$ 성립

정이진 트리​

꽉찬 트리

전이진 트리​

왼쪽부터 오른쪽으로 하나씩 빠짐없이 채워진 트리

사향트리​

한 쪽 자식 노드가 없는 치우친 트리

• 왼쪽 사향 이진 트리
• 오른쪽 사향 이진 트리

이진트리 운행법

• Preorder : Root > Left > Right
• Inorder : Left > Root > Right
• Postorder : Left > Right > Root

수식의 표기​

• Prefix : 연산자 > Left > Right

• Infix : Left > 연산자 > Right

• Postfix : Left > Right > 연산자

• Infix to Prefix or Postfix : 연산에 따라 괄호로 묶고 연산자를 괄호 앞뒤로 옮김

• Prefix or Postfix to Infix : 운행 순서에 따라 괄호로 묶어 연산자를 피연산자 사이로 이동

스레드 이진트리​

• 이진트리에서 발생하는 Null 링크를 트리 운행에 필요한 다른 노드의 포인터로 사용하도록 된 트리
• Nil로 Null pointer 기록
• 왼쪽이 Nil이면 운행상 전 노드를 가리킴
• 오른쪽이 Nil이면 운행상 후 노드를 가리킴
• Nil이 아닐경우 다음 노드를 가리킴

그래프

• 정점 (Vertex)와 간선 (Edge)로 이루어짐
• 차수
  • 무방향 그래프 : 한 정점에 연결된 간선 수
  • 방향 그래프 : 진입(Indegree), 진출(Outdegree)
• 완전 그래프의 간선 수
  • 무방향 그래프 : $\frac{n(n-1)}{2}$
  • 방향 그래프 : $n(n-1)$
• 사이클 : 같은 정점으로 시작과 끝이 이루어짐
• 최대 사이클 : 사이클을 이루는 경로 중 최대 경로의 길이

인접행렬​

• Adjacency Matrix
• 선이 있으면 1, 없으면 0으로 표기

최소 비용 신장 트리​

• MST = Minimum-Cost Spanning Tree
• 가중치가 작은 간선들을 사이클을 이루지 않게 연결한 그래프

정렬

{
  "내부정렬": {
    "선택": ["힙"],
    "삽입": ["삽입", "쉘"],
    "교환": ["버블", "선택", "퀵"],
    "병합": ["2-Way Merge Sort"],
    "분배": ["기수"]
  },
  "외부정렬": [
    "밸런스 병합",
    "케스케이드 병합",
    "폴리파즈 병합",
    "오실레이팅 병합"
  ]
}

고려사항​

• 데이터의 양
• 초기 데이터의 배열 상태
• 키 값들의 분포 상태
• 소요공간 및 작업시간
• 시스템의 특성

내부정렬

삽입정렬​

• 이미 순서화된 파일에 $N$번째 키를 앞의 $N-1$개의 키와 비교
• 뒤에서 앞으로 비교

쉘정렬​

• 매개변수
• 입력파일이 부분적으로 정렬되어 있는 경우

선택정렬​

• $N$개의 레코드에서 최소값을 찾아 첫 번째 레코드에 놓고 나머지 $N-1$개 중에서 다시 최소값을 찾아 두번째... 를 반복
• 앞에서 뒤로 비교

버블정렬​

• 주어진 파일에서 인접한 두 개의 레코드를 비교하여 그 크기에 따라 레코드 위치를 서로 교환
• 계속 정렬 여부를 플래그 비트로 결정

퀵정렬​

• 작은 값은 왼쪽에 큰 값은 오른 쪽에 모이도록해서 분할해서 정렬
• 가장 바름
• 스택 필요

힙 정렬​

• 전이진 트리를 이용한 정렬 방식

2-Way 합병 정렬​

• Merge Sort
• 두 개의 키를 한 쌍으로 하여 각 쌍에 대해 순서를 정함
• 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 병합

기수 정렬​

• 큐를 이용하여 자릿수 별로 정렬
• 레코드의 키를 분석하여 같은 수 또는 문자끼리 그 순사에 맞는 버킷에 분배했다가 버킷 순으로 레코드를 꺼내어 정렬
• 키워드를 나타내는 레이블 내의 주소로 키워드를 변경

검색

선형 검색​

• 첫 번쨰 레코드 키 값부터 차례로 비교하여 검색
• 순차 검색

제어 검색​

• 반드시 순서화된 파일이여야 검색 가능
• 한 번의 비교가 끝난 후 비교 대상이 된 레코드를 다음에 비교할 대상을 선택하는 기준으로 사용
• 이분 검색 : M = $\frac{F+L}{2}$
• 피보나치 검색
• 보간 검색 : 있음직한 부분의 키를 택하여 검색, 프로그래밍 불가
• 블록 검색 : 블록으로 분할해 인덱싱 후 어느 인덱스에 있는지 검색 후 블록 내를 다시 선형 검색

이진 트리 검색​

• 파일을 이진 검색 트리로 구성하여 검색
• 이진 검색 트리 : 왼쪽 자식노드는 부모보다 작고, 오른쪽 자식노드는 부모보다 크게 구성

해싱

• 해싱은 DAM 파일을 구성할 때 사용, 접근 속도는 빠르나 기억공간 요구
• 다른 방식에 비해 검색속도가 가장 빠름
• 삽입 삭제 작업이 많을 때 유리
• 키-주소 변환방법

해시테이블​

• 버킷 : 하나의 주소를 갖는 파일의 한 구역
• 슬롯 : 한 개의 레코드를 저장할 수 있는 공간, N개의 슬롯이 모여 하나의 버킷
• Collision : 서로 다른 두 개 이상의 레코드가 같은 주소를 갖는 현상
• Synonym : 충돌로 인해 같은 주소를 같는 레코드들의 집합
• Overflow : 버킷에 저장할 공간이 없는 상태, Collision은 발생해도 Overflow는 발생하지 않을 수 있음

해싱함수​

• 제산법 : 소수를 사용함 (Division)
• 제곱법 : 키를 제곱해 중간부분을 추출 (Mid-Square)
• 폴딩법 : 키를 여러부분으로 나눠 각 부분을 더하거나 XOR한 값을 추출 (Folding)
• 기수 변환법 : 키 숫자의 진수를 다른 진수로 변환시켜 초과한 자릿수를 절삭
• 대수적 코딩법 : 키 값의 비트 수를 다항식의 계수로 간주
• 계수 분석법 : 숫자 분포를 분석하여 비교적 고른자리
• 무작위법 : 랜덤

Overflow 해결​

개방 주소법​

• 선형 방법
• 순차적으로 그 다음 빈 버킷을 찾아 저장
• Open Addressing

폐쇄 주소법​

• Overflow된 레코드를 별도의 Overflow영역에 저장하고 체인(Pointer)로 홈버킷과 연결
• Direct Chaining : Cylinder Overflow Area에 보관 (해시테이블 내)
• Indirect Chaining : Independent Overflow Area에 보관 (해시테이블 밖)

재해싱​

새로운 해싱함수로 새로운 홈 주소

인덱스

• 데이터 레코드를 빠르게 접근하기 위해 구성하는 것
• 데이터가 저장된 물리적 구조와 밀접한 관계
• 레코드가 저장된 물리적 구조에 접근하는 방법을 제공
• 삽입과 삭제가 빈번하면 인덱스의 갯수를 최소화

m-원 검색 트리​

• m-Way Search Tree
• 키 값의 일부분이 동일한 문자열이나 숫자로 구성된 자료를 표현하는데 효과적
• 삽입, 삭제시 트리 균형을 유지하기 위해 복잡한 연산이 필요

B트리​

• 균형된 m원 검색트리
• 모든 Leaf는 같은 레벨이 있다.
• 한 노드 안에 있는 키 값들은 오름차순을 유지

B+트리​

• B트리의 변형, 인덱스 세트와 리프 노드로만 구성된 순차 데이터 세트로 구성
• B트리의 연산과정을 줄일 수 있는 트리구조

트라이 색인​

• Trie
• 탐색을 위한 키 값을 직접 표현하지 않고 키를 구성하는 문자나 숫자 자체의 순서로 키 값을 구성하는 구조
• 키 값이 문자 또는 숫자일 경우, 키 값들에 대해 일부분이 같은 문자나 숫자로 구성되어있을 때 적합
• 삽입, 삭제시 노드의 분열과 병합이 없음
• 키 값의 분포를 예측할 수 있다면 기억장소를 절약 가능

파일 편성

순차 파일​

• Sequential File = 순서파일
• 물리적 연속 공간에 순차적으로 기록
• 급여관리 등 기간별로 일괄처리를 주로 하는 경우에 적합
• 자기테이프

장점​

• 기록 밀도가 높아 기억공간 효율적 사용
• 어떠한 매체에도 적용
• 키 순서대로 편성되어 취급 용이
• 키 순서대로 레코드 처리시 빠름

단점​

• 새로운 레코드 삽입, 삭제시 재구성을 위해 전체를 복사해야함
• 검색시 처음부터 순차적으로 하기에 효율이 낮고 응답시간이 느림

색인 순차 파일​

• Indexed Sequential File
• 순차 처리와 랜덤처리가 모두 가능하도록 레코드를 키 값순으로 정렬시켜 기록
• 레코드의 키 항목만을 모은 색인 파일을 구성하여 편성
• 색인을 이용한 순차적인 접근방법을 제공하여 ISAM
• 레코드를 참조시 색인 탐색 후 색인이 가리키는 포인터를 사용해 직접 참조
• 자기디스크
• 자기테이프 불가능

구성​

• 기본 구역 : 실제 레코드를 기록하는 부분, 키 값 순으로 저장
• 색인 구역
  • 마스터 색인 구역 : 실린더 색인 구역의 정보가 많을 경우, 해당 레코드가 어느 실린더 색인 구역에 기록되어 있는지를 기록
  • 실린더 색인 구역 : 트랙 색인의 최대키 값과 해당 레코드가 기록된 실린더의 정보가 기록, 한 파일당 하나씩 만들어짐
  • 트랙 색인 구역 : 트랙상 기록되어 있는 데이터 레코드 중의 최대 키 값과 주소가 기록, 한 실린더당 하나씩, 처리할 레코드가 실제로 어느 트랙에 기록되어있는지를 판별
• 오버플로 구역 : 기본구역에 빈공간이 없어서 예비적으로 확보해둔 구역
  • 실린더 오버플로 구역 : 해당 실린더의 기본구역에서 오버플로된 데이터 기록
  • 독립 오버플로 구역 : 실린더 오버플로에 더 이상 기록할 수 없을 때 사용할 수 있는 예비 공간

장점​

• 삽입, 삭제, 갱신 용이
• 파일 전체를 복사할 필요 없음

단점​

• 색인 및 오버플로 구역을 구성하기 위한 추가 기억공간 필요
• 오버플로 레코드가 많아지면 파일을 재편성
• 파일이 정렬되어 있어야함
• 삽입, 삭제가 많으면 효율이 떨어짐
• 액세스 시간이 랜덤 편성파일보다 느림

정적 인덱스​

• 인덱스의 구조가 변경되지 않고 내용만 변하는 구조
• ISAM

동적 인덱스​

• 추가로 삽입될 레코드를 감안하여 빈 공간을 미리 예비해 두는 인덱스
• VSAM
• 블록에 레코드가 가득차면 동적으로 분열
• 일정 수의 레코드가 유지되지 않는 블록은 병합

VSAM​

동적 인덱스 방법을 이용한 색인 순차 파일

• 기본 구역과 오버플로 구역을 구분하지 않음
• 레코드를 삭제하면 그 공간을 재사용
• 제어 구간에 가변 길이 레코드를 쉽게 수용

직접 파일​

• Direct File = Random File = DAM (Direct Access Method)
• 레코드에 특정 기준으로 키가 할당, 해시 함수를 이용해 이 키에 대한 물리적 상대 레코드 주소를 계산 후 레코드 저장
• 자기 디스크, 자기 드럼

장점​

• 물리적 주소를 통해 각 레코드에 직접 접근
• 접근시간이 빠름
• 삽입, 삭제, 갱신 용이
• 어떤 레코드라도 평균 접근 시간에 검색 가능

단점​

• 레코드 주소 변환 과정 필요
• 기억 공간 효율 저하
• 물리적 구조에 대한 지식 필요
• 프로그래밍 복잡
• 충돌 발생 염려로 기억공간 확보

역파일​

• Inverted File
• 여러 개의 색인을 만들어 항목별 특성에 맞게 분배한 파일로 다중 키 파일에 속함
• 다중 키 파일 : 하나의 데이터에 여러개의 접근 방법을 지원하는 구조
  • 순차 처리와 임의 처리가 모두 가능하도록 편성
  • 검색 속도가 빨라 빠른 시간 내에 정보를 얻고자하는 시스템에 적합
• 색인 값을 결합하여 레코드 주소를 결정
• 레코드를 파일 중간에 삽입하기 쉬움
• 검색 속도 빠름
• 데이터 파일에 접근하지 않아 응답시간이 줄어듦
• 처리가 쉬움
• 색인 항목이 가변적

다중 리스트 파일​

• Multi-List File
• 다중 키파일의 한 종류
• 각 키에 대해 색인을 만든 후 각 데이터 레코들 간에 다중 리스트를 구축하여 구성
• 색인의 각 항목들의 길이가 고정적으로 관리가 용이
• 수정, 삭제 검색이 효율적

다중 링 파일​

• Multi-Ring File
• 같은 특성을 가진 레코드들을 포인터로 연결하여 구성
• 같은 항목값을 가진 레코드를 한꺼번에 처리하는 효과적
• 기억장소 절약
• 자료 중복성 배제
• 레코드 형식이 달라도 처리 가능