소프트웨어 기반 기술

1. 자료구조
1. 정의
1. 컴퓨터에서 다양한 자료를 더욱 효율적으로 표현, 활용할 수 있도록 자료의 특성과 사용 용도를 고려하여 조직적, 체계적으로 구분하여 표현한 것
2. 분류
1. 선형구조
1. 배열
2. 리스트
1. 선형 리스트
2. 연결 리스트
3. 스택
4. 큐
2. 비선형구조
1. 트리
2. 그래프
3. 자료구조의 선택 기준
1. 자료의 처리 시간
2. 자료의 크기
3. 자료의 활용 빈도
4. 자료의 갱신 정도
5. 프로그램의 용이성
4. 자료구조의 활용
1. 배열
1. 리스트의 표현, 다항식의 덧셈 문제 해결, 희소행렬 등
2. 리스트
1. 배열의 구현, DBMS 인덱스, 탐색, 정렬 등
3. 스택
1. 인터럽트 처리, 재귀 프로그램의 순서 제어, 서브루틴의 복귀 번지 저장, 후위 표기법 수식 연산, 텍스트 에디터 Undo 기능 등
4. 큐
1. 운영체제의 작업 스케줄링, 대기 행렬의 처리, 비동기 데이터 교환, 키보드 버퍼 이용, 스풀 운용 등
5. 트리
1. 탐색, 정렬 문제 , 문법의 파싱, 하프만 코드, 결정 틀, 게임 등
6. 그래프
1. 컴퓨터 네트워크, 전기 회로 분석, 이항 관계, 연립 방정식 등
2. 알고리즘
1. 정의
1. 주어진 문제를 해결하기 위한 처리 절차를 단계적으로 기술한 것
2. 효과적인 알고리즘의 조건
1. 입력과 출력
1. 0개 이상의 자료가 입력되고, 수행 후 하나 이상의 결과를 출력
2. 명확성
1. 수행할 작업의 내용과 순서를 나타내는 처리 단계는 명확해야 한다.
3. 유한성
1. 작업의 수행 후에는 반드시 종료한다.
4. 유효성
1. 모든 단계의 처리가 명백하게 수행 가능해야 한다.
2. 알고리즘 분석 기준
1. 정확성
1. 알고리즘이 올바른 입력에 대해서 유하 시간 내에 올바른 결과를 산출하는가를 판단
2. 작업량
1. 알고리즘을 수행하는데 걸리는 수행 횟수, 핵심이 되는 중요한 연산 들로만 작업량을 측정
3. 기억 장소 사용량
1. 알고리즘이 수행되는 동안 데이터를 저장하기 위해 필요한 컴퓨터 메모리의 사용량
4. 최적성
1. 알고리즘을 적용할 시스템의 사용 환경을 고려 할 때 그 알고리즘보다 더 적합한 알고리즘이 없는 것
5. 단순성
1. 알고리즘의 표현이 얼마나 이해하기 쉽게 작성되었는지를 의미
3. 알고리즘 성능 분석
1. 평가 방법
1. 공간 복잡도, 시간 복잡도를 추정하여 평가
2. 공간 복잡도
1. 알고리즘을 프로그램으로 실행하여 완료하기 까지 필요한 총 저장공간
2. 계산 방법
1. 고정 공간량 + 가변 공간량
1. 고정 공간량 : 프로그램의 크기, 입출력 횟수에 상관 없이 고정적으로 필요한 저장 공간
2. 가변 공간량 : 프로그램의 수행 과정에서 사용하는 자료, 함수 실행에 관련된 정보를 저장하는 공간
3. 시간 복잡도
1. 알고리즘을 프로그램으로 실행하여 완료하는데 걸리는 시간
2. 계산 방법
1. 컴파일 시간 + 실행 시간
1. 컴파일 시간 : 프로그램의 특성과 관련이 적은 고정적인 시간,
2. 실행 시간 : 프로그램의 실행시간, 명령문의 실행 빈도를 구하여 계산
3. 표기법
1. 빅-오 표기법을 사용하여 O(n)으로 표기
2. 
1. 정렬, 탐색 알고리즘
1. 정렬의 분류
1. 내부 정렬
1. 소량의 데이터에 대해 주 기억 장치에 올려서 정렬하는 방식
2. 속도 빠름, 정렬 데이터의 양이 제한됨
2. 외부 정렬
1. 대량의 데이터에 대해 보조 기억 장치에서 정렬하는 방식
2. 속도 느림
2. 내부 정렬 알고리즘의 분류
1. 삽입법
1. 삽입 정렬
1. 데이터기 정렬되어 있다고 가정하고 값을 해당 위치에 삽입하여 정렬
2. 쉘 정렬
1. 주어진 자료 리스트를 서브파일로 쪼갠 후, 각 서브파일에서 삽입 정렬을 수행
2. 교환법
1. 선택 정렬
1. 최소값을 찾아 왼쪽으로 이동, 데이터의 크기만큼 반복하여 정렬
2. 퀵 정렬
1. 임의의 기준을 선택하여 그 기준보다 작은 값을 왼쪽, 큰 값을 오른쪽에 위치시키는 작업을 반복하여 정렬
2. 재귀호출을 사용
3. 버블 정렬
1. 인접한 데이터 간에 교환이 계속해서 일어나면서 정렬이 이루어지는 방법
3. 선택법
1. 힙 정렬
1. 최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방법
4. 병합법
1. 머지 정렬
1. 데이터의 크기를 반으로 계속 나누고 이를 정렬하면서 다시 합치는 방법
5. 분배법
1. 계수 정렬
2. 기수 정렬
1. 데이터의 낮은 자리 수부터 비교하여 정렬해 가는 방법
3. 버킷 정렬
3. 탐색
1. 정의
1. 데이터 집합에서 원하는 항목을 효율적으로 찾는 기법
2. 선형 탐색
1. 선형 탐색
1. 처음부터 마지막까지 순서대로 레코드를 비교하면서 찾아가는 방법
2. 파일의 크기가 커질수록 탐색 시간이 증가
3. 제어 탐색
1. 이진 탐색
1. 상한 값과 하한 값을 설정하고 그 중간 값을 구한 후 그 중간 값을 계속 비교하면서 검색하는 방법
2. 레코드 수가 많을수록 효과적
2. 피보나치 탐색
1. 피보나치 순열을 이용하여 서브 파일을 형성해 가면서 검색하는 방법
3. 보간 탐색
1. 탐색 대상이 있을 것으로 예상되어지는 위치를 선택한 후 선형 탐색
4. 블록 탐색
1. 전체 데이터를 일정한 개수의 블록으로 구분하고 찾기를 원하는 데이터가 속한 블록을 결정한 후 해당 블록 내의 키 값을 순차적으로 검색
5. 이진 트리 탐색
1. 이진 트리를 이용하여 검색하는 방법
4. 특정 함수를 이용하여 접근하는 방식
1. 해싱
1. 해싱 함수를 이용하여 데이터가 저장되어 있는 주소를 직접 계산하여 찾아간다.
1. 운영체제
1. 정의
1. 컴퓨터 하드웨어와 응용 프로그램 간의 중재자 역할을 하는 시스템 소프트웨어
2. 구성요소
1. 프로세스 스케줄러
2. 메모리 관리자
3. 입출력 관리자
4. 프로세스간 통신 관리자
5. 파일 시스템 관리자
3. 프로세스 개념
1. 프로세스의 상태
1. 프로세스는 생명 주기 동안 구분된 프로세스 상태를 갖는다.
2. 프로세스 생명주기
1. 
1. 생성 : 프로세스가 생성되었으나 아직 운영체제에 의해 실행 가능하게 되지 못한 상태
2. 준비 : 프로세스가 실행을 위해 CPU를 할당 받기를 기다리는 상태
3. 실행 : 프로세스가 CPU를 차지하고 있는 상태
4. 종료 : 프로세스의 실행이 끝나고 CPU 할당이 해제된 상태
5. 대기 : 프로세스가 CPU를 할당 받아 실행 되다가 입출력 완료 등의 사건을 기다리고 있는 상태
1. 프로세스 제어 블록
1. 정의
1. 운영체제가 프로세스 관리를 위해 필요한 정보를 저장하는 것
2. 프로세스가 생성될 때마다 고유의 PCB가 생성되고 프로세스가 완료되면 PCB는 제거된다.
2. PCB의 구성 요소
1. 프로세스 식별 번호 (PID)
2. 프로세스 상태
3. 프로그램 카운터 (PC)
4. 스케줄링 우선 순위
5. 레지스터 정보
6. 주기억장치 관리 정보
2. 쓰레드
1. 정의
1. 프로세스 내에서의 작업 단위
2. 부모 프로세스와 공유할 자원을 초기화 할 필요가 없으므로 오버헤드가 적다.
2. 쓰레드와 프로세스의 관계
1. 
1. 장점
1. 하나의 프로세스를 여러 개의 쓰레드로 생성하여 병행성을 증진시킨다.
2. 하드웨어, 운영체제의 성능, 응용 프로그램의 처리율을 향상시킴으로써 응답시간을 단축한다.
3. 실행 환경의 공유로 기억 장소의 낭비를 감소시키고 공통적으로 접근 가능한 기억 장치를 통한 효율적인 통신을 지원한다.
1. 병행 프로세스
1. 정의
1. 두 개 이상의 프로세스를 동시에 처리하는 것
2. 공유 자원에 대한 배타적인 접근이 보장되지 않을 경우 교착상태에 빠질 수 있다.
2. 해결책
1. 임계 영역
1. 특정 시점에서는 하나의 프로세스만 데이터를 사용할 수 있도록 지정된 공유 자원
2. 상호 배제
1. 한 프로세스가 공유 자원을 사용하고 있을 경우 다른 프로세스는 해당 자원을 사용하지 못하게 제어하는 기법
3. 세마포어

임계 영역에서 공유 자원에 대한 접근을 제어하는 방법

4. 모니터
1. 쉽고 효율적인 프로세스 동기화 수단을 제공하는 고급 언어 수준의 동기화 구조물
5. 교착상태
1. 정의
1. 서로 다른 프로세스가 점유하고 있는 자원을 사용하기 위해 무한정 대기하는 상태
2. 
1. 교착상태의 발생 조건
1. 상호 배제 : 한 번에 하나의 프로세스만이 공유 자원을 사용할 수 있는 상태
2. 점유 대기 : 프로세스들이 현재의 자원을 점유하면서 다른 자원을 요구하는 상태
3. 비선점 : 각 프로세스에 할당된 자원은 사용이 완료될 때까지 강제로 해제할 수 없는 상태
4. 순환 대기 : 서로 다른 프로세스 간의 자원 요구가 연속적으로 반복 되는 상태
2. 교착상태의 해결 방안
1. 예방 : 교착상태의 발생 조건을 제거하여 사전에 미리 예방하는 방법
2. 회피 : 교착상태의 발생 조건을 제거하지 않고 적절하게 피해 나가는 방법 
3. 발견 : 교착상태의 발생을 허용하고 발생시 원인을 찾아 해결 하는 방법
4. 회복 : 교착상태에 빠진 프로세스를 재시작 하거나 원래 상태로 되돌림으로써 교착상태를 해결하는 방법
1. 스케줄링
1. 정의
1. 다중프로그래밍을 지원하는 운영체제에서 CPU활용의 극대화를 위해 프로세스를 효율적으로 CPU에게 할당하는 것
2. 스케줄링의 목적
1. 프로세스의 공정성
2. 단위 시간당 처리량의 최대화
3. 반응시간의 최소화
4. 예측 가능한 수행 시간
5. 시스템의 과부화 방지
6. 균형 있는 자원 활용
7. 프로세스 수행의 무한정 연기 방지
8. 우선 순위 제도 실시
3. 스케줄링 알고리즘의 종류
1. 선점형 스케줄링
1. 정의
1. 한 프로세스가 CPU를 점유하고 있을 때 다른 프로세스가 CPU를 빼앗을 수 있는 방식
2. SRT
1. 수행 도중에 남은 작업 시간 추정치가 가장 적은 프로세스에 CPU를 할당하는 방식
3. RR
1. 각 프로세스들은 정해진 시간 동안만 CPU를 사용할 수 있음
2. 시분할 처리에 가장 적합한 방식
4. MLQ
1. 여러 단계의 큐를 만들어 상위단계에서 하위단계로 우선순위를 지정하여 실행
5. MFQ
1. 모든 작업이 최상위 큐에서 실행되어 각 큐에는 할당 시간이 존재한다.
2. 하위 큐로 내려가면 우선순위는 감소하지만 할당시간이 증가한다.
2. 비선점형 스케줄링
1. 정의
1. 일단 한 프로세스에게  CPU가 할당되면 작업이 완료되기 전까지는 CPU를 다른 프로세스에게 할당 할 수 없는 방식
2.  FIFO
1. CPU를 요구하는 순서에 따라 CPU를 할당하는 방식
3. 우선순위
1. 각 프로세스에 우선순위를 부여하여 우선순위가 높은 프로세스에 CPU를 할당하는 방식
4. SJF
1. 예상 작업 시간이 가장 짧은 프로세스에 먼저 CPU를 할당하는 방식
5. 마감시간
1. 제한된 시간 내에 프로세스가 반드시 완료되도록 하는 방식
6. HRN
1. 우선순위 = (대기시간 + 서비스를 받을 시간) / 서비스를 받은 시간
2. 가상기억장치
1. 정의
1. 운영체제의 제한된 메모리 공간 문제를 해결하기 위한 기법
2. 주기억장치를 대용량처럼 사용할 수 있도록 한다.
3. 가상 기억 장치에 저장된 프로그램을 실행하려면 매핑 작업이 필요하다.
2. 가상기억장치의 구현기법
1. 가상 기억 장치에는 프로세스에서 참조하는 가상주소와 주기억장치의 실제 사용 가능한 영역을 가리키는 실제 주소가 있다.
2. 시스템은 프로세스가 가상 주소에 접근할 때마다 메모리관리장치를 통해 실제주소로 변환한다.
3. 페이징 기법
1. 가상기억장치에 보관되어 있는 작업을 동일한 크기의 페이지로 분할하여 주기억장치에 적재해서 실행하는 기법
4. 세그먼테이션 기법
1. 가상기억장치에 보관되어 있는 작업을 다양한 크기의 세그먼트로 분할 한 후 주기억 장치에 적재해서 실행하는 기법
5. 페이징과 세그먼트 물리 메모리 할당 비교
1. 
1. 가상기억장치의 페이지 교체 기법
1. 최적화 기법
1. 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 기법
2. 프로세스의 행동을 예측하기 어려우므로 현실적으로 불가능
2. 선입 선출 (FIFO)
1. 제일 처음 적재되었던 페이지를 교체하는 기법
3. 최소 최근 사용 (LRU)
1. 가장 오랫동안 사용되지 않은 페이지를 교체하는 기법
4. 최소 사용 빈도 (LFU)
1. 가장 적게 사용되거나 집중적인 사용이 아닌 페이지가 대체됨
5. 최근 미사용 (NUR)
1. 최근에 사용되지 않은 페이지를 교체하는 기법
4. 가상기억장치의 성능에 영향을 미치는 요인
1. 워킹셋
1. 프로세스가 일정 시간 동안 자주 참조하는 페이지들의 집합
2. 워킹셋을 주기억장치에 상주시킴으로써 페이지 부재 및 페이지 교체 현상을 줄임
2. 스레싱
1. 프로세스의 처리 시간보다 페이지 교체 시간이 더 많아져 CPU 이용률을 저하시키는 현상
2. 스레싱을 방지하기 위해 다중프로그래밍의 정도를 줄이거나 워킹셋을 활용한다.
3. 지역성
1. 프로세스가 실행되는 동안 일부 페이지만 집중적으로 참조하는 성질
1. 파일시스템
1. 정의
1. 파일시스템은 파일 자원을 관리하고 데이터에 대한 제어 및 접근을 관리한다.
2. 제공 기능
1. 파일 관리
2. 보조기억장치 관리
3. 파일 무결성 메커니즘
4. 접근 방법
5. 파일의 백업과 복구
2. 입출력 시스템
1. 정의
1. 입출력시스템은 시스템의 입출력장치, 입출력 모듈을 포함한다.
2. 입출력 장치
1. 프로세서와 사용자 간의 자료와 정보에 대한 입출력을 수행
3. 입출력 모듈
1. 프로세서가 여러 입출력 장치를 쉽게 제어할 수 있는 기능 제공
2. 제공 기능
1. 입출력 장치의 제어
2. 타이밍 조정
3. 프로세서와의 통신
4. 입출력 장치 들과의 통신
5. 데이터 버퍼링
6. 오류 검출
3. 최신 OS 기술
1. 모바일 OS
1. 모바일 장치나 정보 기기를 제어하는 운영체제
2. 웹 OS
1. 웹 브라우저에서 구동되는 가상의 OS 또는 일련의 애플리케이션들
3. 임베디드 OS
1. 하드웨어에 내장되어 있는 운영체제
4. 분산 OS
1. 분산 처리 시스템을 관리하는 운영체계
4. 컴퓨터 구조
1. 컴퓨터의 구성 요소
1. 하드웨어
1. 중앙처리장치
1. 기억장치로부터 명령어를 읽고 해독하여 수행할 동작을 결정하고 필요시 데이터의 관리를 수행한다.
2. 주기억장치
3. 제어장치
1. 중앙처리장치 내부에서 일어나는 모든 작업을 통제하고 관리한다.
4. 연산장치
1. 산술연산과 논리연산을 수행한다.
5. 레지스터
1. 중앙처리장치 내부에서 처리할 명령어, 연산의 중간 결과값을 일시적으로 기억하는 장치
6. 버스
1. 중앙처리장치, 메모리, IO장치 등과 필요한 정보를 교환하기 위해 연결된 전송선
2. 주변장치
1. 입력장치
2. 출력장치
3. 보조기억장치
2. 소프트웨어
1. 시스템 소프트웨어
2. 응용 소프트웨어
2. 저장장치의 계층구조와 동작 원리
1. 저장장치의 계층구조
1. 
1. 저장장치의 성능 평가 요소
1. 저장 용량
2. 접근 시간
3. 사이클 시간
4. 저장장치의 대역폭
5. 데이터 전송률
6. 가격
2. 저장장치의 분류 및 특징
1. 용도
1. 주기억장치
1. 특징 : 컴퓨터가 처리할 프로그램이나 데이터를 일시적으로 저장하는 기억장치
2. 구분 : RAM, ROM
2. 보조기억장치
1. 특징 : 비 휘발성 특징을 이용해 데이터를 반영구적으로 저장하는 기억장치
2. 구분 : 자기디스크, 광학디스크 등
2. 물리적 저장방식
1. 자기
1. 특징 : 자기성을 유지하여 자속의 방향에 따라서 이진 정보를 기억하는 장치
2. 구분 : 자기 테이프, 하드 디스크, 집 드라이브 등
2. 광학
1. 특징 : 금속성 원판의 표면에 레이저 광선을 이용하여 정보를 기록하는 장치
2. 구분 : CD, DVD, BD
3. 반도체
1. 특징 : 집적회로기술을 사용하여 아날로그 정보를 저장하는 장치
2. 구분 : RAM, ROM, 플래시 메모리
3. 전원 단절시 데이터 유지 여부
1. 휘발성
1. 특징 : 전원이 단절되면 모든 정보가 삭제되는 메모리
2. 구분 : RAM 기반의 SSD
2. 비 휘발성
1. 특징 : 전원이 단절 되어도 기억된 정보가 보존되는 메모리
2. 구분 : ROM, 자기코어, 보조기억장치
4. 접근 방식
1. 순차 접근
1. 특징 : 기억공간의 필요한 위치에 처음부터 순서대로 접근
2. 구분 : 자기테이프
2. 직접 접근
1. 특징 : 기억공간의 필요한 위치를 직접 접근
2. 구분 : 디스크, 플래시 메모리 등
5. 내용의 보존 여부
1. 파괴성
1. 특징 : 판독 후 저장된 내용이 파괴되는 메모리
2. 구분 : 자기코어
2. 비파괴성
1. 특징 : 판독 후에도 저장된 내용이 그대로 유지되는 메모리
2. 구분 : 자기코어를 제외한 기억장치
3. 주소지정방식
1. 즉시 주소지정 방식
1. 
1. 직접 주소지정 방식
1. 
1. 간접 주소지정 방식
1. 
1. 묵시적 주소지정 방식
2. 변위 주소지정 방식
1. 상대 주소지정 방식
1. 
1. 인덱스 주소지정 방식
1. 
1. 베이스 레지스터 주소지정 방식
1. 
1. 최신 기술 및 동향
1. 멀티코어 프로세서
1. 두 개 이상의 코어를 탑재하여 만든 프로세서
2. 싱글 코어 프로세서에 비해 고성능의 작업을 수행하는데 유용하다.
3. 고가이며 전력소비가 크다
2. 병렬 시스템
1. 다수의 프로세서들이 동시에 여러 작업을 처리하는 것
2. 짧은 시간에 정확하고 많은 데이터를 처리하는 시스템에 적용된다.
3. 장점
1. 처리 속도가 빠르다.
2. 기억 장치를 공유할 수 있다.
3. 일부 하드웨어의 오류가 발생하더라도 전체 시스템 동작에는 영향이 없다.
4. 단점
1. 프로그램 작성이 어렵다.
2. 분할 문제, 스케줄링, 동기화 등의 추가적인 작업이 필요하다.
5. 병렬 컴퓨터 프로세서의 구조
1. 
1. 병렬 컴퓨터 프로세스 구조 분류
1. SISD
1. 한 번에 하나의 데이터를 하나의 명령어로 처리하는 기법
2. 성능 향상을 위해 파이프라이닝, 슈퍼 스칼라 기법이 이용된다.
2. SIMD
1. 한 번에 다수의 데이터를 하나의 명령어로 처리하는 기법
2. 배열 프로세서라고 불리며, 배열 처리기에 의한 동기적 병행 처리가 가능하다.
3. MISD
1. 한 번에 하나의 데이터를 다수의 명령어로 처리하는 기법
2. 각 프로세스는 서로 다른 명령어를 실행하지만 처리되는 데이터들은 하나의 스트림
4. MIMD
1. 한 번에 다수의 데이터를 다수의 명령어로 처리하는 기법
2. 대부분의 병렬 컴퓨터들이 이 분류에 해당된다.
3. 기억장치 결합도에 따른 분류
1. 강결합 시스템
1. CPU들이 서로 연결되어 메모리, 입출력 장치를 공유한다.
2. 하나의 OS가 시스템을 제어한다.
2. 약결합 시스템
1. CPU마다 독립된 메모리를 사용한다.
2. 병렬처리 기능을 가진 프로세서 분류
1. 파이프라인 프로세서
1. 하나의 프로세서를 서로 다른 기능의 서브 프로세서로 나누어 동시에 서로 다른 데이터를 처리
2. 서브 프로세서간 중첩되면서 단계별 수행을 하는 수직 형태의 종속적 구조의 병렬성을 가짐
2. 배열 프로세서
1. 데이터를 고속으로 처리하기 위해 연산장치를 병렬로 배열한 처리 구조
2. 벡터, 행렬 계산에 사용됨
3. 서로 다른 처리 요소들이 하나의 제어장치에 의해 동기화됨
3. 다중 프로세서
1. 병렬처리의 가장 일반적인 모델
2. 시스템상의 여러 프로세서에 여러 개의 독립적인 작업을 배정해 동시에 작업을 수행 할 수 있도록 한다.
3. 스케줄링, 동기화, 기억장치 관리, 성능관리 등의 추가적인 기능이 필요하다.