React에서 jquery, bootstrap 전역으로 사용하기
create-react-app으로 만들어진 react 앱에서 jquery와 bootstrap을 사용하려면 다음과 같이 설정해주면 된다.
import "jquery/src/jquery";
import "bootstrap";
Redis Flush가 안 될 경우 전체 캐시 비우기
FLUSH 명령어는 보안상 empty 값으로 대체되어있는 경우가 많은데, 이 경우 전체를 비우는 명령어가 없어서 편법을 써야한다.
해결
redis-cli -a '비밀번호' KEYS "*" | xargs redis-cli -a '비밀번호' DEL
이 명령은 모든 키 리스트를 가져와 하나씩 지워준다.
Vue multi page app에서 코드가 미리보이는 현상 제거
뷰에 데이터가 바인딩 되기전 {{태그}}
구문이 보일 때 다음과 같이 하면 된다.
해결
v-cloak api에 자세하게 나와있다.
<!-- vue가 바인딩 될 영역에 v-cloak attribute를 추가한다 -->
<div id="vue_area" v-cloak></div>
[v-cloak] {
display: none;
}
더 멋진 방법
로딩시에 content 영역에 loading...이라는 문구를 찍어주는 방법으로 여기에 자세히 설명되어있다.
[v-cloak] > * {
display: none;
}
[v-cloak]::before {
content: "loading...";
}
Laravel 5.5에 JWT (Json Web Token) Auth 추가하기
검색해 나온 포스트들은 5.4버전에 대해서만 나와있어서, 5.5에서는 아무짝에 쓸모가 없었다. 라라벨에서 좃인증을 시작해보자.
설치
jwt-auth
171103 기준으로 dev-develop 버전의 패키지를 설치해야한다.
composer require tymon/jwt-auth:1.0.0-rc.1
service provider 등록
<?php
'providers' => [
...
Tymon\JWTAuth\Providers\LaravelServiceProvider::class,
],
'alias' => [
...
'JWTAuth' => Tymon\JWTAuth\Facades\JWTAuth::class
],
설정파일 publish
php artisan vendor:publish --provider="Tymon\JWTAuth\Providers\LaravelServiceProvider" --force
secret key 생성
php artisan jwt:secret
연동
API Route 설정
API 가드와 유저 모델을 설정하다.
<?php
return [
'defaults' => [
'guard' => 'api', // 기본 가드를 api로 변경
'passwords' => 'users',
],
'guards' => [
...
'api' => [
'driver' => 'jwt', // api 가드를 jwt 인증을 사용
'provider' => 'users',
],
],
'providers' => [
'users' => [
'driver' => 'eloquent',
'model' => App\Models\Member::class, // 유저 모델을 해당 모델로 변경
],
],
...
];
Member Model 설정
<?php
...
// jwt를 모델에서 사용하기 위해 추가한다.
use Illuminate\Foundation\Auth\User as Authenticatable;
use Tymon\JWTAuth\Contracts\JWTSubject;
...
class Member extends Authenticatable implements JWTSubject
{
// 아래 두 메소드가 구현되어야 실행된다.
public function getJWTIdentifier() {
return $this->getKey();
}
public function getJWTCustomClaims() {
return [];
}
}
사용하기
login
<?php
public function login(Request $request) {
$credentials = $this->validate($request, [
'id' => 'required|string',
'password' => 'required|string'
]);
if ($token = $this->guard()->attempt($credentials)) {
return $this->respondWithToken($token);
}
return response()->json(['message' => 'Unauthorized'], 401);
}
protected function respondWithToken($token) {
return response()->json([
'access_token' => $token,
'token_type' => 'bearer',
'expires_in' => $this->guard()->factory()->getTTL() * 60
]);
}
public function guard() {
return Auth::guard();
}
Authorized Routes
Accept Header
application/json 로 설정해야 오류가 예쁘게 반환된다.
token 태우기
## header 이용한 방법
Authorization: Bearer yourtokens...
## Querystring으로도 인증 가능
https://gracefullight.github.io/me?token=yourtokens...
routes
Route::group(['middleware' => 'auth:api'], function() {
Route::get('member/logout', 'MemberController@logout');
Route::get('member/me', 'MemberController@me');
});
logout
<?php
public function logout(Request $request) {
$this->guard()->logout();
return response(null, 204);
}
refresh
refresh는 auth:api 미들웨어 없이 처리되어야한다.
<?php
public function refresh() {
return $this->respondWithToken($this->guard()->refresh());
}
여담
Expired거나 Unauthoriezed경우 status code로 체크하면 된다. 5.5버전 메뉴얼이 부족하다.
Docker jenkins 설치시 permission 오류
run시에 젠킨스가 올라가지 않고 /var/jenkins/home
에 파일 퍼미션 오류가 발생할 때 다음과 같이 해결하면 된다.
해결
마운트한 볼륨에 1000 유저 권한을 준다. (jenkins의 uid는 1000) docker hub에 나와있는 내용이긴 한다.
chown 1000 {볼륨 경로}
AWS Cli S3 파일 업로드
웹 상에서 파일을 업로드할 때 md5 checksum 오류가 발생해 파일이 전체가 다 안 올라가는 경우도 있고, 세션이 만료되 올라가는 도중에 끊기기도 하는 것 같다.
업로드 방법
업로드 할 bucket 의 이름을 조회한다.
aws s3 ls
앞이 복사할 폴더이고 뒤가 파일이 복사될 s3 bucket 경로이다.
aws s3 cp ./ s3://{bucket_name}/{path}/ --recursive --exclude "*.mp4" --acl public-read
mp4 를 제외한 폴더의 모든 하위 파일들을 public-read 권한으로 업로드했다.
옵션 확인
cli docs에서 디테일한 옵션은 확인 가능하다.
운영체제
운영체제
- 사용자와 하드웨어 간의 인터페이스 제공
목적
- 하드웨어를 효율적 사용하도록 성능 향상
- UI 제공
- 성능요소
- 처리율
- 응답시간
- 사용가능도
- 신뢰도
제어프로그램
- 감시 프로그램
- 데이터 관리 프로그램
- 작업 제어 프로그램
처리 프로그램
- 언어번역 프로그램
- 서비스 프로그램
- 문제 프로그램
구성 요소
- 프로세스 관리
- 주기억장치 관리
- 보조기억장치 관리
- 입출력 관리
- 파일 관리
프로세스 기능
- 생성 및 소멸
- 동기화
- 일시중지 및 재실행
- 프로세스 간 통신
- 보호 시스템
- 네트워크 관리
- 명령해석 시스템
종류
- 일괄처리 시스템
- 실시간 시스템
- 시분할 시스템
- 다중 프로그램 시스템: 여러 개의 프로갦이 동시에 실행되는 것처럼 처리하는 방식
- 다중 처리 시스템: 동시에 프로그램을 수행할 수 있는 CPU를 여러 개 두고 각각 분담하여 처리하는 방식
- 분산처리 시스템
- 결함허용 시스템: 시스템 일부가 고장나더라도 전체 시스템은 계속 가동할 수 있는 시스템
발달 과정
- 50년대: 일괄 처리 시스템
- 60년대: 다중 프로그래밍, 멀티 프로그래밍, 시분할, 실시간 처리 시스템
- 70년대: 멀티모드 시분할 시스템
- 80년대: 병렬 프로그램 실행, 펌웨어
- 90년대: GUI
- 00년대: 64bit
입출력장치 발전추세
프로그램에 의한 입출력
- CPU에서 실행되는 프로그램에 의해 입출력을 직접 제어
- CPU는 입출력장치에 명령을 보낸 후 동작이 완료될 때까지 대기
- CPU는 주기적으로 주변장치의 상태를 반복적으로 검사하는 폴링 방식
- 자원낭비가 발생
인터럽트 처리에 의한 입출력
- 입출력 인터페이스가 주변장치의 상태를 검사하여 준비상태가 되면 인터럽트 신호 발생
- 프로그램 상태를 스택에 저장한 후 문맥교환 과정을 통해 인터럽트 서비스 프로그램을 수행
- 주변장치에 명령을 보낸 후 결과가 올 때까지 CPU는 다른 작업을 수행할 수 있어 효율이 높다.
DMA
- 직접 메모리 접근 입출력
- CPU는 상태정보, 제어정보만을 교환하게 하고 데이터 전송은 주변장치와 기억장치 간에 직접 교환하게 하는 방식
- 시스템 버스상에 모듈이 하나 추가되어야 한다.
- CPU를 통하지 않고 한 번에 한 단어씩 직접 기억장치로부터 모든 데이터 블록을 전송한다.
- 전송이 완료되면 DMA모듈은 CPU에게 인터럽트 신호를 보내고 CPU는 전송의 시작과 끝 부분에만 관여한다.
- 사이클 스틸링: 버스를 사용하기 위해 CPU의 동작을 일시적으로 중단시키는 기법
채널
- DMA 개념을 확장하여 구현한 입출력만을 위한 전용 처리장치
- CPU처럼 독자적으로 주기억장치에 저장된 명령어를 처리할 수 있는 프로세스
종류
- 선택 채널: 채널 하나를 하나의 입출력장치가 독점해서 사용하는 방식
- 멀티플렉서 채널: 한 채널에 여러 개의 입출력장치를 연결하여 시분할 공유방식으로 입출력하는 저속 입출력 방식
- 블록 멀티플렉서 채널: 셀렉터 채널과 멀티플렉서 채널 방식을 결합한 방식
기억장치 인터리빙
- 인접한 메모리 위치를 서로 다른 뱅크에 둠으로 동시에 여러 곳에 접근할 수 있게 한다.
- 주기억장치의 구조적 개선으로 접근속도를 개선시키는 방법
- MAR과 MBR을 연결한 것을 기억모듈이라고 한다.
- 블록단위 전송이 가능하므로 DMA에서 많이 사용한다.
재배치 레지스터
- 수행 중인 프로그램을 다른 곳으로 옮길 수 있도록 하는 레지스터
- 주기억장치 내 프로그램의 기준 주소가 이 레지스터에 기억된다.
- 기준 레지스터 = 재배치 레지스터
폴링
- CPU가 특정 이벤트를 처리하기 위해 그 이벤트가 발생할 때까지 모든 연산을 모니터링하는데 쓴다.
- 단일 이벤트에 대해서는 유용하지만 프로그램이 길어지게 되면 그만큼 CPU 자원을 낭비하게 된다.
버퍼링
- 속도 차를 줄이기 위해 중간에서 데이터를 일시적으로 기억장소에 축적하는 방법
- CPU와 저속 입출력장치의 작동속도를 조정한다.
단일 버퍼링
- 주기억장치 일부를 버퍼로 사용한다.
- 버퍼가 채워지거나 비워지는 동안 CPU는 다른 작업을 할 수 없다.
이중 버퍼링
- 2개의 버퍼를 이용해 단일 버퍼링의 단점을 보완하고 입출력과 CPU의 처리성능을 높이는 방법
- 입출력작업과 처리작업을 동시에 처리할 수 있다.
환형 버퍼링
- 여러 개의 버퍼를 원형으로 구성하여 수행하는 방식
- CPU와 채널은 동시에 버퍼를 채우거나 비우는 일을 독립적으로 수행한다.
- 버퍼의 생산과 소비를 위해 버퍼의 수를 결정하는 게 성능에 매우 중요하다. (환형이기에)
보조기억장치
- SASD: 순차 기억장치 => 테이프
- DASD: 직접 접근 기억장치 => 나머지
광디스크
- CD-ROM: 650MB
- DVD: 4.7~17GB
- WORM Disk: write once read memory => CD-R
디스크 용어
- 트랙: 디스크의 회전축을 중심으로 만들어진 동심원
- 섹터: 트랙을 몇 개의 부채꼴 모양으로 나눈 구간
- 실린더: 디스크의 중심축으로부터 동일선상에 위치한 동일 트랙들의 모임
- 클러스터: 여러 개의 섹터를 하나로 묶은 단위, 하드디스크에서 데이터를 저장하기 위한 기본 단위
- 파일할당 테이블: 디스크에 저장되어 있는 각각의 파일들에 대한 정보를 저장한 테이블
- TPI: Track per Inch, 1인치 당 트랙의 수
보조기억장치 속도
- 레지스터 > 캐시 > 주기억장치 > 보조기억장치
- 자기드럼 > 하드디스크 > 광디스크 > 플로피디스크 > 자기테이프
입출력 채널
- IOP: Input Output Processor
- 입출력작업이 끝나면 CPU에게 인터럽트로 알려주며 입출력장치와 주기억장치 간의 속도 차이를 해결
채널의 기능
- 입출력 명령 해독
- 각각의 입출력장치에 명령 지시
- 지시된 입출력 명령의 실행을 제어
채널의 종류
셀렉터 채널
- 고속 입출력장치에 적합한 채널
- 입출력장치를 1:1로 전담
- 블록 단위 전송
멀티플렉서 채널
- 저속의 입출력장치 여러 개를 동시에 제어하는 채널
- 바이트 단위의 전송
블록 멀티플렉서 채널
- 여러 대의 고속 입출력장치를 블록단위로 처리
DMA
사이클 스틸링
- CPU가 메모리에서 명령어를 fetch하여 execute cycle 중에 있을 때 CPU가 메모리를 사용하지 않는 시간을 이용해 DMA를 행한다.
- 상태보존을 하지 않는다.
폴링은 주변장치의 상태보존을 하지 않음, 프로그램 제어하의 직접 입출력 방식
주소 지정방식
- 묵시적
- 즉시 주소 지정: 데이터가 명령어에 바로 있음
- 레지스터 주조 지정: 오퍼랜드가 메인 메모리의 주소가 아닌 레지스터를 참조
- 직접 주소 지정: 오퍼랜드에 실제 주소
- 레지스터 간접 주소 지정: 메모리 위치가 기억된 레지스터를 참조
- 인덱스 주소 지정: 오퍼랜드와 인덱스 레지스터의 내용이 더해져 유효번지가 결정
- 베이스 레지스터 주소 지정: 오퍼랜드와 베이스 레지스터 내용이 더해져 유효번지가 결정
- 상대 주소 지정: 오퍼랜드와 프로그램 카운터가 더해져 유효번지 결정
- 간접 주소 지정: 오퍼랜드가 메모리 내의 주소를 참조하여 유효번지를 계산해 메모리에 접근, 2번 메모리 참조
가상 기억장치
- 보조기억장치의 일부분을 주기억장치처럼 사용하는 것
- 매핑이 필요하다.
가상기억장치 구현방법
페이징
- 내부단편화 발생 가능
세그먼테이션
- 논리적 단위
- 기억장치 보호키 필요
- 외부단편화 발생 가능
스풀링
- 입출력할 데이터를 직접 I/O 장치로 보내지 않고 디스크에 모았다가 한꺼번에 입출력을 처리하는 방식
- CPU와 입출력장치의 처리속도 차이에서 오는 대기 시간을 줄이기 위해 고안
- 버퍼와 비슷한 개념
컴파일러
- 고급 언어 프로그램을 목적프로그램으로 번역한 후 링킹작업을 통해 컴퓨터에서 실행 가능한 실행프로그램을 생성
인터프리터
- 고급 언어 프로그램을 한 줄 단위로 받아들여 번역하고 번역과 동시에 프로그램을 한 줄 단위로 즉시 실행시키는 프로그램
- 컴파일러에 비해 느리다.
절대로더
- 번역된 목적프로그램을 입력으로 받아들인 간단한 로더
- 기억장소 할당이나 연결을 사용자가 직업 지정
- 프로그래머가 절대 주소를 기억해야 한다.
- 다중 프로그래밍 방식에서 사용할 수 없음
- 소규모
- 모듈, 라이브러리 사용 불가
재배치 로더
- 주기억장치의 상태에 따라 재배치 가능한 목적프로그램을 주기억장치의 임의 공간에 적재할 수 있도록 하는 로더
링킹 로더
- 프로그램 적재 시에 필요한 프로그램들을 결합하여 2진 프로그램 이미지를 주기억장치에 적재
객체지향 운영체재
- OOOS
- 운영체재 개발에 객체지향 프로그래밍 적용
- 객체: 모든 프로시저와 데이터를 묶어놓은 추상적 존재
펌웨어
- 마이크로 명령어로 작성된 프로그램
- 기계어 하부에 프로그래밍층을 형성
에뮬레이션
- 일종의 한 하드웨어 시스템에 부가장치를 부착하여 다른 하드웨어를 모방하는 것
- 하나의 컴퓨터가 다른 컴퓨터와 똑같이 행동하도록 만들어진 마이크로프로그래밍의 소프트웨어를 이용하는 기법
마이크로 다이어그노스틱스
- 시스템의 고장진단을 마이크로 프로그래밍에 의해 수행하는 것
마이크로 커널
- 운영체제의 커널 중에서 가장 기본적이고 핵심적인 기능만을 수행하는 부분만을 따로 구성한 모듈
- 높은 수준의 모듈화 제공
바인딩
- 프로그램 내에서 변수 등을 실제 값으로 배정하는 것
- 명령문과 데이터를 주기억장치에 특정 위치로 옮기는 것
기억장치 구성
단일 프로그래밍 시스템
- 주기억장치는 운영체제가 상주할 영역과 현재 수행될 사용자 프로그램이 적재될 영역으로 나뉜다.
다중 프로그래밍 시스템
- 여러 개의 프로세스를 처리
- 주기억장치 관리 기법이 필요하다.
연속 적재 방법
- 연속된 공간에 할당
분산 적재 방법
- 필요한 부분만 주기억장치에 적재하는 방법
- 페이지나 세그먼트로 구성
단일 사용자 연속기억장치 할당
- 주기억장치에 항상 한 프로그램만 적재된 가장 단순한 기법
상주모니터
- CPU의 유휴시간을 극복하기 위해 작업의 묶음들을 자동으로 처리할 수 있는 운영체제
- 한 프로그램에서 다른 프로그램으로 제어가 자동적으로 넘어가도록 하기 위해 기억장치에 상주
- 입출력 시간동안 CPU는 유휴상태
- 사용자 공간보다 큰 프로그램은 실행이 불가능
오버레이 기법
- 주기억 장치 용량보다 더 큰 프로그램을 분할해 그 분할 된 프로그램을 순차적으로 같은 영역에 적재해 실행하는 방법
- 디스크에 프로그램을 유지하고 운영체제에 의해 기억장치로 교체시키는 방법
- 프로그램을 여러 개의 분할된 조각으로 나누는 일은 프로그래머가 담당
교체 기법
- swipping
- 충분하지 못한 주기억장치를 가진 시스템에서 여러 개의 프로그램이 하나의 메모리에서 실행될 수 있도록 하기 위해 사용하는 기법
- swap out: 보조기억장치로 이동
- swap in: 주기억장치로 이동
- 오버레이 기능이 없으면 기억공간보다 작은 프로그램만 실행 가능
내부 단편화
- 하나의 분할에 작업을 할당하고 남은 공간
외부 단편화
- 대기 중인 작업보다 분할영역이 너무 적어 분할 전체가 빈 공간이 될 때
기억장치 통합
- 인접된 공간을 하나의 공간으로 만드는 것
기억장치 집약
- 여러 개의 기억공간들을 하나의 큰 기억공간으로 만드는 것
기억장치 배치 기법
- 최적 적합
- 최초 적합
- 최악 적합
블록 사상
- 가상기억장치 내의 작업을 블록단위로 사상하는 것
페이징 기법
직접사상
- 페이지 사상테이블의 시작점 레지스터에 페이지 번호를 더해 주기억장치에서 그 페이지 시작주소를 구한 다음 변위를 더함으로 실주소를 계산한다.
- 프로세스의 가상기억장치를 구성하는 모든 페이지에 대한 항목은 페이지 테이블에 존재
연관사상
- 빠른 주소변환을 위해 고속의 연관기억장치를 이용해 페이지 사상표 전체를 넣는 방법
연관/직접사상
- 연관기억장치에는 페이지 사상테이블 중 지역성 있는 페이지를 넣고, 나머지는 직접사상
세그먼테이션 기법
- 가상주소를 분할형태가 일정한 배열이나 함수와 같은 논리적인 다양한 크기의 가변 단위로 주기억장치의 연속적인 공간에 적재하는 방법
- 외부단편화 발생 가능
- 순수 세그먼테이션 기법에서 가상주소 양식: 세그먼테이션 번호, 변위, 가상 주소
- 세그먼 테이블 사상테이블 형식: R, W, E(xecute), A(append)
페이징/세그먼테이션 혼용
- 세그먼트를 페이지화 하는 것
- 가상주소형식이 3차원 요소로 구성: V = (s, p, d)
- 세그먼트 번호, 페이지 번호, 변위
- 세그먼트의 사상테이블의 항이 세그먼트 주소를 가지고 있지 않고 페이지 사상테이블의 기준주소를 가지고 있다.
페이지 사상테이블 항목
- 페이지 존재 비트
- 보조 기억장치 주소
- 페이지 프레임 번호
페이지 호출 기법
요구 페이지 호출기법
- 수행 중인 프로세스에 의해 호출된 페이지나 세그먼트를 주기억장치로 옮기는 전략
- 호출된 페이지는 실제로 참조되는 페이지
- 페이지를 할당받기 위해 대기시간이 길다.
예상 페이지 호출기법
- 프로세스에 의해 요청될 페이지나 세그먼트를 미리 예측하여 프로세스가 요구하기 전에 주기억장치로 적재시키는 전략
- 예측 결정이 올바라야 실행시간이 감소한다.
페이지 교체 기법
OPT
- 최적 교체
- 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법
- 실현 가능성이 없다.
무작위 페이지 교체
- 무작위로 교체
- 오버헤드가 적다.
FIFO
LRU
- Least Recently Used
- 최근에 가장 오랫동안 사용하지 않은 페이지를 교체
- 계수기나 스택을 두어 계산한다.
- 스택 알고리즘
LFU
- Least Frequently Used
- 사용빈도가 가장 적은 페이지를 교체하는 기법
- 프로그램 실행 초기에 많이 사용된 페이지가 나중에도 프레임을 계속 차지할 수 있다.
NUR
- Not Used Recently
- 최근에 사용하지 않은 페이지를 교체하는 기법
- 각 페이지마다 참조 비트와 변형 비트를 사용
클록 페이지 교체
- 원형 리스트를 사용해 페이지를 배열시켜 놓고 리스트의 포인터가 시계바늘이 돌아가는 것처럼 그 원형 리스트로 돌아가게 되는 것
SCR
- 2차 기회 페이지 교체
- 가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 것
- FIFO 기법의 단점을 보완한 기법
- Second Chance 기법
- 각 페이지마다 참조 비트를 두고 1일 경우 참조 비트를 0으로 바꿔 FIFO 리스트의 맨 마지막으로 이동시킨다.
시간 국부성
- 참조되는 기억장소가 가까운 미래에 계속 참조될 수 있다.
- 반복, 서부루틴, 스택, 계산, 집계
공간 국부성
- 하나의 기억장소가 참조되면 그 근처의 기억장소가 계속 참조될 수 있다.
- 배열 순회, 순차적 실행, 변수 집합
워킹 세트
- 지역성(국부성)을 이용해 페이지 부재율을 감소시키기 위한 개념
- 일정 시간 동안 자주 참조하는 페이지의 집합
스레싱
- 페이지 부재가 비정상적으로 많이 발생하여 프로그램이 처리보다 페이지 교체에 많은 시간을 소비함으로 시스템 처리량이 급격히 저하되는 현상
페이지 부재
- 프로세스 실행 시 참조할 페이지가 주기억장치에 없는 현상
페이지 크기
작을 경우
- 효과적인 워킹세트 확보
- 사상 테이블 크기 증가
- 기억공간 낭비
- 기억장치 효율을 좋다.
클 경우
- 페이지 부재 수 최소화
- 페이지 단편화 현상 초래
- 사상 테이블 크기 감소
- 입출력 효율 증가
요구 페이징 기법
- 페이지의 요구가 있을 때 주기억장치에 적재하는 기법
- 유효 또는 무효를 나타내는 비트가 페이지 사상테이블의 각 항목에 추가된다.
전역 교체
- 프로세스가 교체할 프레임을 그 프레임이 현재 다른 프로세스에 할당되어 있어도 그에 상관없이 전체 프레임 중에서 하나를 선택하여 그 프레임을 사용할 수 있도록 해준다.
- 한 프로세스에 할당된 프레임 수는 증가한다.
- 자신의 페이지 부재율을 조정할 수 없다.
지역 교체
- 각 프로세스가 그 프로세스에 할당된 프레임 중에서 하나를 선택해서 그 프레임을 사용할 수 있도록 해준다.
- 프로세스에 할당된 프레임 수는 변하지 않는다.
프로세스
- PCB를 가진 프로그램
- 실기억장치에 저장된 프로그램
- 프로시저가 활동 중인 실체
- 비동기적 행위를 일으키는 주체
- 운영체제가 관리하는 실행 단위
프로세스 스케줄러
- 둘 이상의 프로세스가 적절히 실행될 수 있도록 컨트롤 한다.
작업 스케줄러
- 작업의 운선순위, 리소스의 할당 등을 판단해 처리율을 높이는 작업을 한다.
프로세스 상태
- 제출상태: submit
- 보류상태: hold, 스풀러에 의해 디스크에 수록되어 있는 상태
- 준비상태: ready, CPU가 사용가능한 상태, 처리를 기다리고 있는 상태
- 실행상태: running, 프로세스를 수행 중
- 대기상태: blocked, 입출력 처리가 끝날 때 까지 대기 큐에서 대기하는 상태
- 완료상태: complete
프로세스 관리 모듈
- 스풀러: 제출된 작업을 디스크에 수록하여 보류상태로 변환
- 작업스케줄러: 보류 상태 작업들 중 실행될 작업을 선정
- 프로세스 스케줄러: 여러 프로세스 중에서 실행될 프로세스를 선정
- 트래픽 제어기: 모든 프로세스의 상태를 파악하고 프로세스 관리 및 상태변환을 수행하며 프로세스 간의 통신과 동기화를 조정
프로세스 제어 블록
- PCB
- 프로세스 생성시 만들어지며 모든 프로세스는 각기 고유의 PCB를 가진다.
- 프로세스 식별자
- 프로그램 카운터
- 우선순위
- 처리기 레지스터
- 기억장치 관리정보
- 입출력 정보
- CPU 사용 시간, 시간 범위, 계정번호, 작업 번호 등
스레드
- 프로세스는 스레드를 담는 공간
- 실행점이 여러개
- CPU가 하나인 시스템에서 병행실행 가능
스케줄러
장기 스케줄러
- 작업 스케줄러
- 디스크공간에 제출된 프로세스들을 선택하여 주기억장치로 적재하며 실행 빈도수가 적어 장기 스케줄링
- 프로세스가 종료되어 시스템을 떠날 때만 새로운 프로세스를 생성하기 위해 호출
단기 스케줄러
- CPU 스케줄러, 디스패쳐
- 실행되어 있는 프로세스 중에서 한 프로세스를 선택하여 CPU를 할당
중기 스케줄러
- CPU를 경쟁하는 프로세스들의 수를 줄여서 다중 프로그래밍의 정도를 완하하는 것
선점 스케줄링
- 우선순위가 높은 다른 프로세스가 현재 프로세스를 중단시키고 자신이 CPU를 차지할 수 있는 기법
- SRT, RR, 선점 우선순위, 다단계 큐, 다단계 피드백 큐
- 시분할 시스템에 유용
비선점 스케줄링
- 한 프로세스가 CPU를 할당 받으면 다른 프로세스는 CPU를 점유하지 못하는 기법
- 우선순위, FIFO, SJF, HRN, 기한부 알고리즘
- 모든 프로세스에 공정하고 응답시간이 예측 가능
스케줄링 알고리즘
기한부 스케줄링
- 처리기 할당시간을 제한하여 작업 할당시간안에 반드시 종료되도록 하는 기법
우선순위 스케줄링 알고리즘
- 우선순위가 높은 것에 먼저 CPU를 할당하는 방식
- FIFO 원리
- 기아현상 발생을 방지하기위해 우선순위를 높이는 에이징 기법이 있다.
FCFS
SJF
- Shortest Job First
- 작업 수행시간이 가장 짧다고 판단되는 것을 먼저 수행
SRT
- 비선점 스케줄링인 SJF를 선점형태로 변경한 기법
- Short Remaining Time
- 가장 짧은 시간이 소요된다고 판단되는 프로세스를 먼저 수행
- 더 짧다고 판단되는 프로세스가 큐에 들어오면 언제라도 선점된다.
- 시분할 시스템에 유용
RR
- 각 프로세스는 같은 크기의 CPU 시간을 할당받는다.
- 시분할 방식에 효과적이다.
- 할당시간이 크면 FCFS와 같고, 작은면 문맥교환 및 오버헤드가 자주 발생한다.
HRN
- Highest Response Ratio Next
- 실행시간이 긴 프로세스에 불리한 SJF 기법을 보완하기 위한 것
- 대기시간과 서비스 시간을 사용한다.
- 우선순위 = (대기시간 + 서비스시간) / 서비스 시간
FSS
- Fair Share Scheduling
- 프로세스들 집합 간에 프로세스의 스케줄링을 지원하며 UNIX 환경에서 서로 관계있는 사용자들에게 한정된 비용으로 시스템 자원을 사용할 수 있게 개발
- 사용자들은 그룹 짓는데 우선순위 RR 프로세스 스케줄러를 사용한다.
다단계 피드백 큐 스케줄링
- Multi-level Feedback Queue Scheduling
- 여러 개의 큐를 두고 시간이 지나면 우선순위가 떨어지는 큐로 밀려나게 하는 것과 같이 실행시간이 긴 작업에 벌칙을 주는 방식
- 각 큐의 CPU 할당시간을 정할 수 있어 적응력이 커진다.
병행 프로세스
- concurrent process
- 두 개 이상의 프로세스들이 동시에 존재하며 실행상태에 있는 것
우선순위 그래프
- precedence graph
- 각 노드가 개개의 문에 대응하는 방향성 비순환 그래프
- 어떤 연산의 일부분이 가지는 우선순위 제약조건을 정의하는데 유용하다.
- 프로그래밍 언어에서는 사용이 곤란하다.
Fork/join
- 최초로 병행 프로그램을 언어적으로 표현
- Fork: 단일 연산을 2개의 독립적인 연산으로 분할시키는 방법
- Join: 병행하는 2개의 연산을 하나로 재결합시키는 방법
병행문
- parbegin/parend 표현방법을 사용하는 기법
- 1개의 프로세스가 여러 가닥의 병렬 프로세스로 분할되었다가 다시 한 가닥의 프로세스로 결합하는 것
Master/Slave
- Master는 연산 + 입출력
- Slave 연산
약결합 시스템
- 각 프로세스마다 독립된 메로리를 가진 시스템
- 분산 처리 시스템
- 각 시스템마다 독립적인 운영체제
- 프로세스 간의 통신은 메세지 전달이나 원격 프로시저 호출을 통해 이뤄진다.
강결합 시스템
- 여러 개의 프로세스가 하나의 메모리를 공유하여 사용하는 시스템
- 다중처리 시스템
- 하나의 운영체제가 모든 프로세스와 시스템 하드웨어를 제어
- 프로세스 간의 통신은 공유메모리를 통해서 이뤄진다.
대칭 다중처리 구조
- 모든 프로세스가 동등한 입장의 대칭성을 가지고 있으며 구현 및 수해이 매우 복잡한 형태의 가장 강력한 시스템
- 한 운영체제를 동시에 수행할 수 있게 재진입 코드와 상호배제가 필요하다.
비동기 병행 프로세스
- 독립적 프로세스: 시스템에서 실행 중인 다른 프로세스에 영향을 받지 않고 주지도 않는 프로세스
- 유기적 프로세스: 프로세스가 가지는 동일한 입력에 대해 반드시 동일한 결과를 갖지는 않는다.
동기화 기법
- Synchronization
- 두 개 이상의 프로세스를 한 시점에 동시에 처리할 수 없으므로 각 프로세스에 대한 처리 순서를 결정하는 상호배제의 한 형태
- 세마포어와 모니터 기법이 있다.
상호 배제
- 공유자원을 어느 시점에서 단지 한 개의 프로세스만이 사용할 수 있도록 하며 다른 프로세스가 공유자원에 대해 접근하지 못하게 하는 기법
임계구역
- Critical Section
- 다중 프로그래밍 운영체제에서 여러 개의 프로세스가 공유하는 데이터 및 자원에 대하여 어느 한 시점에서 하나의 프로세스 자원 또는 데이터를 사용하도록 지정된 공유 자원을 의미하며 이를 보호구역이라 한다.
Test and set
- 동시성을 제어하기 위한 동기화 명령어 중 하나로 하드웨어의 도움을 받아 수행
- 함수 조건을 비교할 때엔 한 프로세스가 점령을 하면 다른 프로세스가 개입을 할 수 없도록 선점해서 사용하는 개념
- 상호배제를 하는 기법
세마포어
- semaphore
- 다익스트라가 제안
- P와 V라는 2개의 연산에 의해 동기화를 유지
- 상호배제 원리 보장
시간종속 오류
- 프로세스들이 임의적으로 변수들을 공유할 때 발생하며 어떤 특정 순서로 실행이 될 때만 발생
- 프로세스가 자원에 대한 접근허가를 얻지 않고 그 자원을 연산하는 경우
- 프로세스가 자원 접근을 허용받고 나서 그 자원을 결코 해제하니 않는 경우
- 프로세스가 요청하지 않은 자원을 해제하는 경우
- 프로세스가 동일한 자원을 반복해서 요청하는 경우
생산자 소비사 문제
- 여러 개의 프로세스를 어떻게 동기화할 것인가에 대한 고전적인 문제
- 한정 버퍼 문제, Bounded-Buffer Problem
- 생산자는 데이터를 인덱스를 통해 배열에 저장하는 식으로 데이터를 생성하며 소비자는 데이터를 증가시키며 배열에 있는 데이터를 인덱스로 접근하여 소비
판독기/기록기 문제
- 다수의 프로세스가 하나의 데이터 객체를 공유하는 경우 한쪽 프로세스는 판독을 하려하고 다른 한쪽 프로세스는 기록을 하려고 할 때 발생하는 문제
- 기록기가 공유객체에 배타적 접근을 하도록 하는 것
병행 프로그래밍 언어
- Ada: 구조화되고 통계학적 형태를 가지고 명령적, 객체지향적인 고급수준의 컴퓨터 프로그래밍 언어
- CSP: 처음으로 병행시스템에서 상호작용 패턴을 표현하는 언어
프로세스 간의 통신
- 직접통신
- 간접통신: 메일 박스를 통해 메세지를 보내거나 받는다, 단방향 양방향 모두 가능
교착상태
필수조건
- 상호배제 조건: 자원은 한 번에 한 프로세스만 사용해야 한다.
- 점유와 대기 조건: 각 프로세스가 이미 자신에게 할당된 자원을 갖고 있으면서 다른 자원을 더 요구하고 있다.
- 비중단 조건: 프로세스에 할당된 자원은 스스로 반납하기 전에는 빼앗지 못한다.
- 환형대기 조건: 프로세스 간 환형사슬이 존재하여 각 프로세스는 다음 프로세스가 요구하는 자원을 가지고 있다.
자원할당 그래프
- 프로세스와 자원 간의 관계를 나타내는 그래프를 의미한다.
교착상태 확인방법
- 자원할당 그래프의 사이클이 존재하는지 확인한다.
- 사이클이 지원 유형에 하나라도 있으면 교착상태다.
교착상태 회피
- 프로세스 시작 거부
- 자원할당 거부: 은행원 알고리즘
교착상태 탐지
교착상태 복구
디스크 접근 시간
- Access Time = Seek Time + Rotational Latency + Transfer time
- 탐색시간: 헤드를 적정 트랙으로 이동하는데 걸리는 시간
- 회전지연시간: 데이터가 현재 위치에서 디스크 헤드까지 회전하는 데 소요되는 시간
- 전송시간: 실제 바이트가 이동하는데 소요되는 시간
디스크 스케줄링
FCFS
SSTF
- Shortest Seek Time First
- 탐색거리가 가장 짧은 트랙에 대한 요청을 먼저 서비스하는 기법
- 일괄 처리 시스템에 유용
- 대화형 시스템에는 부적합
SCAN
- SSTF가 갖는 탐색시간의 편차를 해소하기 위한 방법
- 현재 진행 중인 방향으로 가장 짧은 탐색거리에 있는 요청을 먼저 서비스
- Denning이 개발
- 대부분의 디스크 스케줄링에서 기본 전략
- 진행하면서 들어온 요청도 처리
- 오버헤드가 작을 경우 가장 효율적
N-step SCAN
- 진행하면서 들어온 요청은 따로 모아 반대방향 진행 때 처리
C-SCAN
- 항상 바깥쪽에서 안쪽으로 움직이면서 가장 짧은 탐색거리를 갖는 요청을 서비스
- 안쪽 끝까지 이동하면 가장 바깥쪽 끝으로 이동하고 다시 안쪽으로 들어온다.
C-LOOK
- 안쪽 끝까지 이동 후에 가장 바깥쪽 요청 트랙으로 이동한다.
SLTF
- Shortest Latency Time First
- 섹터 큐잉
- 회전 시간의 최적화를 위해 디스크 대기 큐에 있는 여러 요청을 섹터 위치에 따라 재정렬하고 가장 가까운 섹터를 먼저 서비스
RAM 디스크
- 빠른 속도로 자료를 처리할 필요가 있을 때 주기억장치인 RAM의 일부를 보조기억장치인 디스크처럼 사용하는 것
블로킹
- 레코드의 입출력 효율을 높이기 위해 여러 개의 논리 레코드를 하나의 블록으로 묶는 것
버퍼링
- 주기억장치의 일부에 큐 방식으로 동작하는 버퍼
- 하나의 프로그램에서 CPU 연산과 I/O 연산을 중첩시켜 처리하는 방식
파일 구조
순차 파일
- 물리적 순서에 따라 저장
인덱스 순차파일
- 레코드를 키에 따라서 논리적 순서대로 저장하고 시스템은 각 레코드의 실제 주소가 저장된 색인을 관리
- 디스크에 적용되는 방식, 테이프 사용 불가
인덱스 순차파일 구성
- Prime
- Index
- 마스터
- 실린더
- 트랙
- Overflow
직접 파일
- 물리적 주소를 통해 직접 액세스되는 파일
- 해싱 함수를 이용해 물리적 상대주소를 계산한 후 해당주소에 레코드를 저장
- DASD의 물리적 주소를 통해 파일의 각 레코드에 직접접근이 가능하여 접근 및 기록의 순서에 제약이 없다.
파일 접근방식
- queued access method: 레코드 순서를 미리 예상 가능할 때 사용
- basic access method: 물리적 블록의 RW는 액세스 방식이 담당하고 블로킹 및 해체는 사용자가 담당한다.
디스크 공간할당
연속할당
- 집약 작업이 필요하다.
- 단편화가 발생할 수 있다.
불연속할당
섹터지향 할당
- 동일한 파일에 속하는 섹터들을 연결리스트로 구성하여 할당하는 방식
- 논리적 연결을 탐색하는데 오랜 시간이 필요하고 포인터를 저장할 공간이 필요하다.
블록할당
- 파일에 액세스할 때 해당 블록을 결정한 후 해당 섹터를 결정해야하는 기법
- 블록체인 기법
- 인덱스 블록체인 기법
- 블록지향 파일사상기법: 포인터 대신 FAT(할당 테이블)에 있는 블록번호를 사용하는 기법
파일 서술자
- file desriptor, FCB
- 파일이름
- 파일구조
- 보조기억장치에서 파일 위치
- 보조기억장치 유형
- 액세스 제어정보
- 파일 유형
- 생성 일시, 제거 일시
- 최종 수정 일시
- 액세스 횟수
접근제어
접근제어 행렬
- 시스템 보호기법으로 행은 사용자 영역, 열은 객체를 나타낸다.
접근제어 리스트
- ACL
- 각 객체에 댛나 리스트는 영역, 권한, 집합의 순서쌍으로 구성
자격 리스트
- capability list
- 각 사용자 영역에 대한 자격들로 구성되며 객체와 그 객체에 허용된 연산 리스트
분산파일시스템
- DFS, Distributed File System
- 여러 대의 서버에 걸쳐 분산되어 저장될 수 있는 계층형 파일시스템
데이터 압축
비손실 압축
- Run Length: 문자의 반복을 줄임
- 동적 사전법: 출현빈도에 따라 이진트리나 해시테이블 구성 후 포인터로 대체
손실압축
- 이미지 압축
- 오디오 압축
- 비디오 압축
프로세스 테이블 정보
- 프로세스 고유번호, 상위 프로세스 고유번호 (PID, PPID)
- 사용자 이름, 사용자 그룹 이름 (UID, GID)
- 프로세스 현재 상태
장치 드라이버
- 장치드라이버 디렉터리는 /dev
- 시스템의 각종 디바이스들에 접근하기 위한 디바이스 드라이버들이 저장되어 있는 디렉터리
- 하드디스크에 차지하는 공간이 없는 가상 디렉터리
UNIX의 장치 분류
- 블록 지향적: 입출력이 버퍼화되고 물리적인 입출력이 블록단위로 수행
- 문자 지향적: 입출력이 버퍼화되지 않고, 물리적 입출력이 문자 단위로 수행, Raw 인터페이스
UNIX의 파일
- 일반 파일
- 데이터 파일: 텍스트 데이터 파일, 이진 데이터 파일
- 실행가능 프로그램 파일
- 디렉터리 파일
- 특수 파일: 주변장치들을 파일이름을 통해 접근 가능
- 파일이름에 공백이 와서는 안 된다.
- 255자까지 가능하다.
파일접근 자료구조
- 부트 블록
- 슈퍼 블록
- i-node 블록: 각 파일에 대한 metadata가 기록된 고정된 크기의 구조체 블록
- 파일 소유자 사용번호, 그룹번호
- 파일의 종류
- 데이터 블록의 주소
- 파일의 크기
- 파일이 생성, 사용, 변경된 시간
- 파일의 링크 수
- 데이터 블록: 실제 파일블록을 저장하는 데 이용하는 블록
리디렉션
- 명령어 처리 시 입출력 방향을 지정할 때 사용
UNIX 시스템의 3가지 구성요소
- 쉘
- 커널
- 어플리케이션
VSCode 추천 패키지
필수 패키지
- Auto Close Tag: 자동으로 태그를 닫아준다.
- Auto Rename Tag: 자동으로 짝 태그의 이름을 바꿔준다.
Beautify: 선택 영역 및 파일을 beautify- Bookmarks: 라인을 북마크해 shift + alt + L 키로 넘어다닐 수 있다.
- Bracket Pair Colorizer: 괄호를 짝을 맞춰 색상을 입혀준다.
- Code Runner: 해당 영역을 간단히 실행시켜볼 수 있다.
- Color Highlight: 색상 코드가 색으로 표시된다.
- Code Spell Checker: 오타를 잡아준다. (영문만)
- Debugger for Chrome: 크롬 디버그 툴로 front 디버깅이 가능하다.
- DotEnv: .env syntax 를 잡아준다.
- EditorConfig for VS Code: .editorconfig 파일 설정을 불러와준다.
- ESLint: JS Linting
Git History: Git commit log 를 예쁘게 볼 수 있다. (Git Lens 에서 모두 확인 가능)- Git Lens: 라인별로 commit log 를 확인할 수 있다. 파일 비교도 가능하다.
- Guides: 가이드라인이 진해진다.
- Log File Highlighter: 이제 없으면 로그파일 못 보겠다.
- Path Intellisense: 경로를 자동으로 잡아준다.
- Prettier - Code formatter: Beautify 보다 더 좋다.
- Project Manager: ctrl + shift + p 로 프로젝트를 빠르게 바꿀 수 있다.
- REST Client: postman 과 같은 기능을 간단한 코드로 구현할 수 있다.
- Trailing Space: 비어있는 부분을 하이라이트하고 저장시 자동으로 삭제해준다.
- VS Live Share: Code 환경 간 세션 공유 가능
- XML tools: xml 하이라이터
개발환경별 취향
css
- Sass
java
- Debugger for Java
- Java Extension Pack
- Java Test Runner
- Maven for Java
- Sprint Initialzr Java Support
javascript
- EJS language support: EJS syntax highlighter 중 제일 낫다.
- JavaScript (ES6) code snippets
- Veltur: Vue 매니아라면
php
- Laravel 5 Snippets: 라라벨 backend
- laravel Blade Snippets: 라라벨 frontend
- PHP Debug
- PHP DocBlocker: 빠르게 주석을 만들 수 있다.
- PHP Intellisense - Crane: PHP intellisense 모듈 중에 가장 똑똑하다.
- PHP Namespace Resolver - 타입힌팅에 쓰이는 클래스를 바로 import 가능
python
- Python: Python 이 필요하다면
- Anaconda Extension Pack
server
- Apache Conf: 아파치 속성을 많이 열어봐야 한다면
- Docker: 도커를 쓴다면
ftp-kr: FTP 환경에서 작업할 일이 있다면- sftp: ftp-kr 보다 적응되면 나은 것 같다.
기타
- Markdown Shortcuts: markdown 의 폰트, 표 기능들을 쉽게 이용 가능하다.
- vscode-pdf: PDF 파일도 열어보고 싶다면
- Rainbow CSV: CSV 파일의 색깔을 입혀준다.
테마 및 아이콘
테마
- Dracula Official: 드라큘라 테마
- Shades of Purple: 보라색 테마
아이콘
- vscode-icons: 주관적으로 제일 예쁘다.
자료구조
자료
- 현실세계로부터 관찰이나 측정을 통해서 수집된 사실이나 값
- 자료형태는 숫자로 표현되는 수치값이나 문자들로 구성되는 스트링을 포함
정보
- 어떤 상황에 대한 적절한 의사결정을 할 수 있게 하는 데이터의 유효한 해석이 나 상호 관계
- 자료가 처리되어 발생하는 결과
- 한시성
- 비소모성
- 공공성
- 독점성
자료구조
- 데이터를 효율적으로 사용할 수 있도록 자료의 특성에 따라 분류하여 구조를 만들어서 저장해 둔 것
- 단순 자료구조: integer, float, char 등 단일자료
- 선형 자료구조: 리스트, 스택, 큐
- 비선형 자료구조: 트리, 그래프
- 파일구조: 보조기억장치에 저장되는 대용량의 자료구조
알고리즘
- 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법
- 입력, 출력, 명확성, 정확성, 유한성, 효율성, 일반성
순서도
- 사다리꼴 입출력
- 타원 터미널
- 마름모 비교, 판단
- 육각형 준비
추상
- 자세한 정보는 감추고 사용자가 자료를 사용하는 데 필요한 정보만 인터페이스를 통해 외부로 노출하는 것
프로시져
- 추상화 제공
- 재사용 가능
- 여러 프로그래머가 같은 문제를 해결할 수 있게 도와줌
- 구조 파악이 쉽다
프로시져 간 자료 전달 방법
- Call By Value: 값에 의한 호출, 프로시저를 호출하기 전에 실인수의 값을 계산하고 값을 호출시에 대응되는 국소적 변수인 가인수에 대입함으로써 전달하는 방식
- Call By Reference: 참조에 의한 호출, 주소와 포인터 등 실인수를 참조하기 위한 정보가 가인수에 전달되어 동일한 데이터를 참조하게 되어 호출된 프로시저에서 참조하는 값이 변경되면 실인수의 값도 동일하게 변경된다.
재귀
- 함수가 직접 자신을 호출하는 방식
공간 복잡도
- Space Complexity, 프로그램을 실행시켜 완료하는 데 필요로 하는 공간의 양
고정 공간
프로그램 입출력의 횟수나 크기와 관계없는 공간 요구
가변 공간
- 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들이 필요로 하는 공간
시간 복잡도
- 프로그램의 기능을 수행하기 위해 프로그램이 취한 단계수로 표현하는 것
빅오
- f(n) = O(g(n))은 모든 n, n >= n0에 대해
f(n) <= cg(n)
인 조건을 만족하는 두 양의 정수 c와 n0이 존재하기만 하면 f(n) = O(g(n))이다.
배열
- 같은 자료형과 같은 크기를 가진 원소가 순서를 가지고 만들어진 집합
- 인덱스에 의해 참조
순서 리스트
- 나열한 원소들 간에 순서를 가지고 있는 리스트
- 평균 이동 횟수 (n+1)/2, 삭제 시 (n-1)/2
- 삽입 삭제시 전체를 밀어야되지만, 기억장소 효율은 가장 좋다.
연결 리스트
- 공간 제약이 없다.
- 삽입 삭제가 효율적이다.
주소 저장
- 행 우선: 시작주소 + (행 전체 열 크기 + 열) 원소 크기
- 열 우선: 시작주소 + (열 전체 행 크기 + 행) 원소 크기
희소행렬
- 행렬의 대부분 원소가 0일 경우 기억공간의 낭비가 발생하므로 0이 아닌 원소만 추출하여 [행 번호, 열 번호, 원소] 쌍으로 2차원 배열에 저장하는 방식
- 연산 측면에선 반복적인 패턴을 찾을 수 없어 비효율적
전치행렬
- 행과 열을 바꾼 것, B = A^T로 표현
- A^T = A면 대칭행렬
스택
- 한 끝에서 삽입과 삭제가 일어나는 순서 리스트
- LIFO
시스템 스택
- 함수가 호출될 때마다 프로그램은 활성 레코드 또는 스택이라는 구조를 생성하고 시스템 스택의 top pointer에 적재한다.
스택의 적용
- 부프로그램 호출 시 복귀 주소 저장
- 함수 호출의 순서 제어
- 인터럽트 복귀 주소 저장
- 중위 표기식을 후위 표기식으로 변환
- 후위 표기법으로 표현된 산술식 연산
- 0-주소 지정방식의 명령어 자료 저장소
- 재귀 프로그램의 순서 제어
- 컴파일러를 이용한 언어 번역
큐
- 리스트의 한 쪽에선 원소를 삽입하고 다른 쪽에서는 삭제만 하는 구조
- FIFO
- front pointer: 가장 먼저 삽입된 자료의 포인터
- rear pointer: 가장 나중에 삽입된 자료의 포인터
- 초기 조건: front == rear = -1
- 공백: front == rear = 1 && front == rear
- 가득참: rear = n - 1
원형큐
- 큐가 가득 찬 후에 첫 번째 큐를 Q[0]에 위치하게 조정하는 배열 이동은 시간이 많이 걸려 원형으로 만듦
- 초기 조건: front == rear == 0
- 삽입 위치: rear = (rear + 1) % n
- 삭제 위치: front = (front + 1) % n
- 공백: front == rear
- 가득참: front == (rear + 1) % n
큐의 적용
- 작업 버퍼 큐
- 프로세스 스케줄링
- 큐잉 시뮬레이션
데크
- 원소의 삽입과 삭제가 리스트의 양쪽 끝에서 이뤄지는 자료구조
- 스택과 큐의 결합
- Double Ended Queue
스크롤
- 입력 제한 테크
- 한 쪽에선 삭제만 가능
셀프
- 출력 제한 데크
- 한 쪽에선 삽입만 가능
스택 수식 계산
- 우선순위: 승제 > 가감 > 시프트 > 비교 > 등가 > 비트 > 논리
연결 리스트
순서 리스트의 문제점
- 삽입 삭제시 많은 이동
- 할당 공간 부족시 재할당
- 표현방법과 기억 공간의 크기가 달라지면 컴파일부터 다시 실행
비사용 기억공간
- 기억 공간이 필요하여 요청하는 경우 할당해 줄 수 있는 공간
연결 리스트의 응용
- 다항식 표현
이중 연결 리스트
- 링크의 방향을 양방향으로 이동할 수 있어 검색 효율성이 좋다.
원형 연결 리스트에서 헤드 노드를 사용하는 이유 모든 원소가 환형으로 연결되어 있기 때문에 무한 루프에 빠질 수 있어 헤드 노드를 두어 리스트의 시작을 알린다.
트리
- 정보의 검색 및 자료 보관을 위해 널리 사용되고 있는 자료구조
- 사이클을 포함하지 않는 연결 그래프의 일종
- 계층적 자료구조
- 노드와 각 노드를 연결하는 간선으로 구성
- 임의의 노드에서 다른 노드로의 연결은 하나만 가능하다.
- 루트 노드는 하나만 존재
- 트리의 부분 집합은 하나의 트리, 이 것을 서브 트리라고 한다.
- 노드 연결에 순환이 존재하지 않는다.
균형트리
- B-tree, AVL tree, Red-black tree
용어
- 노드: 자료를 담는 영역
- 간선: 노드 간의 연결 선
- 차수: 하위 노드의 개수
- 레벨: 계층 구조의 노드의 위치 값
- 높이 또는 깊이: 루트에서 터미널 노드까지의 레벨의 개수
- 터미널 노드: 최하위 노드
- 포리스트: 루트 노드를 제거하고 생기는 서브 트리들
이진 트리
- 모든 노드의 차수가 2 이하인 특수한 형태의 트리
- 순서트리의 특성을 가지므로 노드의 위치 또는 순서가 중요한 의미를 가진다.
- 편향 이진 트리: 단말노드를 제외한 트리의 구성 노드들이 왼쪽 또는 오른쪽 자식 노드만을 가지는 형태의 트리
- 전 이진 트리: 단말노드를 제외한 노드들이 왼쪽 자식과 오른쪽 자식 노드를 모두 가지고 있는 형태의 트리
- 포화 이진 트리: 단말노드를 제외한 모든 노드의 차수가 2이면서 최하위 자식 노드들이 모두 차여 있는 형태의 트리
- 완전 이진 트리: 루트 노드에서부터 하위 레벨로 순차적으로 왼쪽 자식, 오른쪽 자식 노드 순으로 추가된 트리의 형태
- 균형 이진 트리: 단말 노드의 레벨 값의 차이가 1 이하인 형태 (완전 이진 트리와 포화 이진 트리를 포함)
- 일차원 배열(완전 이진트리로 가정)과 연결 리스트로 표현하는 방법
이진 트리 순회
- 중위 순회: 좌 루트 우
- 후위 순회: 좌 우 루트
- 전위 순회: 루트 좌 우
이진 트리 정렬
- 루트부터 비교하면서 작으면 왼쪽 자식, 크면 오른쪽 자식
- 완성되면 중위 순회
스레드 이진 트리
- 터미널 노드의 null 값의 링크를 조상 노드에 연결해 알고리즘 성능을 향상시키는 방식
히프
- 완전 이진 트리의 자료구조
- 가장 큰 값이나 가장 작은 값이 완전 이진 트리의 루트에 항상 존재하는 자료구조
- 데이터 목록에서 가장 작은 값이나 가장 큰 값을 빠르게 찾을 수 있도록 구성된 자료구조
우선순위 큐
- FIFO를 지키면서 우선순위가 부여된 원소는 큐에서 위치와 상관 없이 먼저 출력되는 구조
- 배열, 연결리스트, 히프로 표현이 가능하다.
- 히프 사용시 O(logn)의 복잡도
이진 탐색 트리
- 이진 트리의 구조로 자료 검색 삭제 및 삽입에 효율적인 자료구조
- 원소들은 유일한 키 값을 가지며 좌측 서브 트리는 루트 값보다 작은 값들로 구성된 이진 탐색트리고 우측 서브 트리는 루트의 값보다 큰 값들로 구성된 이진 탐색 트리로 구성
- 중간 노드 삭제시 왼쪽 서브트리의 최대 원소와 오른쪽 서브트리의 최소 원소를 비교하여 중간 노드 값으로 올린다.
- 최대 높이는 n, 최소 높이는 log₂(n)
선택 트리
- N개의 원소를 임의의 개수로 나눈 원소를 가진 K개의 목록을 합병 정렬할 목적으로 구성
승자 트리
- 2개의 자식 노드 중 값이 작은 노드가 승자가 되어 상위 부모 노드로 올라가는 트리
패자 트리
- 승자 대신 패자 원소를 나타내고 승자는 상위 부모 노드에 올린다.
포리스트
- 서로 연결되지 않은 여러 개의 서브 트리로 구성된 구조
- 자료 접근에 어려움이 있어 이진 트리로 변환해야 한다.
- 이진트리에서 루트 레벨이 1로 시작할 때 레벨 i에서 최대 노드의 수는 2^(i-1) 개 이다.
- 이진트리에서 깊이가 i라면 최대 노드 수는 2^i-1개다.
그래프
- 공집합이 아닌 정점들의 유한집합과 공집합도 허용하는 간선들의 유한집합으로 구성
- 완전 그래프: 최대 수의 간선을 가지는 그래프
- 가중 그래프: 간선에 가중치가 할당된 그래프
그래프의 표현
- 인접 행렬: 간선이 있으면 1 없으면 0
- 인접 리스트: vertex와 link로 표현
그래프 순회
- 깊이 우선 탐색: 스택
- 너비 우선 탐색: 큐
- 신장 트리: 그래프의 간선들로만 구성되고 그래프의 모든 정점을 포함하는 트리, 사이클이 포함되면 안된다.
최소 비용 신장 트리
- 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 트리
- 비용은 거리 및 시간을 의미한다.
- Prim, Kruskal, Sollin 알고리즘이 있다.
Prim
- 가중치가 적은 간선을 선택해 가는 방식
Kruskal
- 탐욕적 방법
- 매번 선택마다 전체에서 가장 좋다고 생각하는 간선을 선택
그래프의 응용
PERT/CPM
- Program Evaluation and Review Technique / Critical Path Method
- PERT: 프로젝트에 필요한 전체 작업의 상호관계를 표현하는 방법
- CPM: 프로젝트 완성에 필요한 작업을 나열하고 작업에 필요한 소요 기간을 예측하는 데 사용하는 기법
- 상세 계획을 수립하기 쉽고 변화나 변경에 대해 바로 대처할 수 있고 네트워크상 문제점을 파악할 수 있고 중점관리가 가능하나 작성에 많은 시간이 든다.
최단 경로
- Dijkstra 알고리즘: 첫 번째 정점 a에서 최단 경로의 길이인 두 번째 정점을 찾는 알고리즘
탐색
- 주어진 리스트에서 원하는 키를 찾는 것
- 비교 탐색방법: 탐색 대상의 키를 비교하여 탐색하는 방법, 순차 탐색, 이진 탐색, 이진 트리 탐색
- 계산 탐색방법: 계수적인 성질을 이용하여 계산으로 탐색을 하는 방법, 해싱
순차 탐색
- 주어진 리스트에서 탐색키와 같은 레코드를 검색하는 방법
- O(n)
이진 탐색
- 이미 정렬되어 있는 리스트에서 절반을 쪼개가며 값을 찾는 방식
- O(logn)
피보나치 탐색
- 피보나치 수열을 이용해 중간 값을 계산해 속도가 빠르다.
정렬
- 내부 정렬: 리스트가 작아 주기억장치에서 모두 정렬이 가능
- 외부 정렬: 외부 기억장치를 이용해 정렬
- 비교식 정렬: 비교하고자 하는 각 키 값들을 한 번에 2개씩 비교하여 교환하는 방식
- 분산식 정렬: 키 값을 기준으로 하여 자료를 여러 개의 부분 집합으로 분해하여 각 부분집합을 정렬함으로써 전체를 정렬하는 방식
삽입 정렬
- 정렬되어 있는 값들을 삽입하고자 하는 값과 비교하여 큰 값들은 뒤로 이동한 후 삽입하는 방법
- O(n^2)
- 두번 째 원소를 기준으로 이전의 레코드들과 비교하여 적절한 위치를 찾아 삽입하는 방식
쉘 정렬
- 매개변수 값을 정하여 매개변수의 값만큼 간격을 가지는 레코드들을 여러 개의 서브 파일로 구성하면서 각 서브 파일을 삽입 정렬방식으로 배열하는 과정을 반복하는 것
- interval은 전체 레코드의 개수의 절반인
interval = n/2
에서 시작해 매번interval = interval / 2
로 interval 값이 0보다 큰 경우에 반복 수행한다. - O(n^1.25)
퀵 정렬
- 기준값인 피벗을 중심으로 큰 원소들은 오른쪽 부분집합으로 분할하여 정렬하는 방법
- 분할 정복기법
- 정렬할 자료들을 기준값을 중심으로 2개의 부분집합으로 분할하는 작업과 기준값보다 작으면 왼쪽 부분집합으로 크면 오른쪽 부분집합으로 정렬하는 정복 작업을 부분 집합의 크기가 1 이하가 될 때까지 반복한다.
- O(nlog₂n), 최악 O(n^2)
버블 정렬
- 인접한 2개의 레코드를 비교하여 위치를 서로 교환하는 방식
- 한 회전을 거치면 리스트의 마지막의 가장 큰 레코드가 남게 된다.
- O(n^2)
2원 합병 정렬
- 이미 정렬된 2개 이상의 배열이 있을 때 이들을 합쳐서 하나의 정렬된 배열을 만드는 것
- O(nlogn)
히프 정렬
- O(nlogn)
- 히프 트리를 이용해 정렬하는 방식으로 항상 가장 큰 원소가 루트 노드가 되고 삭제 연산을 수행하면 항상 루트 노드의 원소를 삭제하여 반환하게 된다.
선택 정렬
- 단순한 정렬방법
- 이동하면서 가장 작은 값을 앞으로 보낸다.
- O(n^2)
- 데이터 양이 적을 때 아주 좋은 성능을 낼 수 있다.
기수 정렬
- 큐를 이용하여 자릿수 (digit) 별로 정렬하는 방식
- 부동소숫점 정렬 불가능
- O(dn)