공통적으로 선형 자로구조이다 Stack LIFO top을 통해서만 접근이 가능하다. 비어있는 스택에서 원소를 추출하려고 할 때 stack underflow라고 하고 스택이 넘치는 경우 stack overflow라고 한다. 괄호 문제 해결 역순 문자열 DFS Queue FIFO 삽입은 rear에서 이루어진다. Enqueue 삭제는 front에서 일어난다. Dequeue 가장 첫 원소와 끝 원소를 통해 접근이 가능하다. BFS Cache

Array 논리적 저장 순서와 물리적 저장 순서가 일치한다. 따라서 인덱스로 해당 원소에 접근이 가능하다. 그러므로 검색에는 원하는 원소의 인덱스를 알고있다면 O(1) 이다. 삽입과 삭제에는 삭제 또는 삽입을 한 후에 Shift 비용이 발생하므로 O(n) 이다. 정의와 동시에 길이를 지정하고, 바꿀 수 없다.(정적인 표현) 컴파일 시 Stack 영역에 할당된다. 장점 검색 연속적이므로 메모리 관리가 편함 단점 크기가 고정되어있기 때문에 삭제를 한 후에 shift를 하지않는다면 메모리 낭비가 생긴다. 배열의 크기를 바꿀 수 없다 List 불연속적인 메모리 공간 할당 동적인 표현 인덱스를 사용하지 않고 포인터를 통해 접근한다. 새로운 노드가 추가될 때 Heap 영역에 할당된다. 장점 삽입 삭제가 자유로움 단..

Critical Section 동일한 자원을 동시에 접근하는 작업을 실행하는 코드영역 해결법 Mutual Exclusion(상호 배제) P1이 CS에서 실행중이라면 다른 프로세스들은 해당 CS에서 실행될 수 없다. Progress(진행) CS에서 실행중인 프로세스가 존재하지 않고, 별도의 동작인 없는 프로세스만 CS진입 후보로서 참여될 수 있다. Bounded Waiting(한정된 대기) P1이 CS에 진입 신청 후 부터 받아들여질 때까지, 다른 프로세스들이 CS에 진입하는 횟수에 제한이 있어야한다. 해결책 Lock 하드웨어 기반 해결책 임계영역에 진입하는 프로세스는 Lock을 획득하고 빠져나올때 Lock을 방출하여 동시진입을 막는다. 다중처리기 환경에서는 시간적인 효율성 측면에서 적용할 수 없다. Se..

스케줄러 프로세스를 스케줄링하기 위한 Queue에 프로세스를 넣고 빼주는 역할 Queue Job Queue : 현재 시스템 내에 있는 모든 프로세스의 집합 Ready Queue : 현재 메모리 내에 있으면서 CPU를 잡아서 실행되기를 기다리는 프로세스의 집합 Device Queue : Device I/O 작업을 대기하고 있는 프로세스의 집합 장기 스케줄러 (Job Scheduler) 메모리는 한정되어 있는데 많은 프로세스들이 한꺼번에 메모리에 올라올 경우, 대용량 메모리(일반적으로는 Disk)에 임시지로 저장된다. 이 pool에 저장되어 있는 프로세스 중 어떤 프로세스에 메모리를 할당하여 ready Queue로 보낼지 결정하는 역할을 한다. Memory Disk 스케줄링 담당 프로세스에 메모리를 할당 d..

정의 프로세스가 자원을 얻지 못해 다음 처리를 하지 못하는 상태 교착 상태라고도 하며 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생한다. 멀티 프로그래밍 환경에서 한정된 자원을 사용하려고 할 때 상황이 발생한다. 발생조건 발생조건 4가지 모두 성립할 때 발생한다. 상호 배제(Mutual Exclusion) 자원은 한 번에 한 프로세스만이 사용할 수 있어야 한다. 점유 대기(Hold and Wait) 최소한 하나의 자원을 점유하고 있으면서, 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다. 비선점(No Preemption) 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 한다. 순환 대기(Circular Wait..

정의 데이터베이스의 상태를 변환시키는 하나의 논리적 기능을 수행하기 위한 작업의 단위 또는 한번에 모두 수행되어야하는 일련의 연산 특징 하나의 Transaction은 Commit 되거나 Rollback된다. 사용자가 시스템에 대한 서비스 요구 시 시스템이 응답하기 위한 상태 변환 과정의 작업단위이다. 성질 Atomicity All or Noting Consistency Transaction이 그 작업을 성공적으로 완료하면 언제나 일관성 있는 데이터베이스 상태로 변환한다. 시스템이 가지고 있는 고정요소는 수행 전과 후의 상태가 같아야 한다. Isolation 둘 이상의 Transaction이 병행 실행되는 경우 Transaction간의 연산은 독립적이다. Durability 성공적으로 완료된 Transac..