cs 공부/운영체제
sy9723
2023. 7. 5. 13:18
2023. 7. 5. 13:18
- Deadlock
- 몇몇 스레드는 자원 경쟁을 함
- 대기중인 스레드가 다른 대기중인 스레드가 점유한 자원을 요청하여 계속 waiting state에 머무르는 상황을 deadlock이라 함
- Livelock
- Deadlock과의 유사점
- Deadlock과의 차이점
- fail되는 action을 지속적으로 시도 -> CS에 진입할 때까지 계속 반복
- block X, progress X
- 예시) 두 사람이 복도를 지나가는 상황 발생 -> 두 사람이 멈춰있지 않고(block X), 좌우로 피해가려 하지만 진행은 안됨(progress X)
- Livelock 회피방법
- 각 스레드가 random 시간에 retry 하도록 함
- 이더넷 네트워크에서 네트워크 충돌 시 취하는 해결법
- 충돌 후 바로 재전송하지 않고, 재전송 전에 random 기간동안 물러남
- deadlock보다 덜 일반적으로 발생하고 특정 스케줄링 상황에서만 발생 가능
- Deadlock 특징
- Necessary Conditions(교착 상태 발생의 필요 조건)
- 아래 4가지 조건을 동시에 만족하면 deadlock 임 (아래 조건들은 독립적인 조건은 아님)
- Mutual exclusion (공유자원은 deadlock 아님, 해당 자원을 어떤 스레드가 요청했을 때 해당 자원이 release될 때까지 요청 스레드가 delay되어야 함)
- Hold and wait (스레드가 어떤 자원을 hold하면서 또 다른 자원을 요청하면서 wait하는 상황)
- No preemption (선점 X)
- Circular wait (wait이 circle을 이룸)
- Resource-Allocation Graph (교착 상태의 기술 방법)
- deadlock은 방향 그래프로 더 정확히 기술 가능함
deadlock 아님
deadlock 발생
- deadlock 처리 방법
- 무시하고 deadlock이 일어나지 않은 척 하기 (성능이 저하되면 재부팅되거나 deadlock이 발생한 스레드들만 중지) -> 대부분의 OS(윈도우, 리눅스 등)에서 사용중인 방법
- deadlock 예방/회피 프로토콜 사용 -> deadlock 상태가 되지 않도록 보장
- 예방: 4가지 필요조건 중 최소 하나가 성립하지 않도록 보장 (단점: 장치 이용률 저하, 시스템 처리율 감소)
- Mutual exclusion: 자원이 share할 수 있도록 하면 됨 -> 어떤 자원은 근본적으로 공유 불가 -> 해결 x
- Hold and wait: hold와 wait을 동시에 하지 않도록 함
- 각 스레드가 실행 전에 모든 자원을 요청하고 할당하도록 함 -> 자원 요청의 동적인 특성으로 비현실적
- 자원을 갖고 있지않을 때만 요청하도록 함 -> 스레드는 자원을 추가로 요청하기 전에 현재 할당된 자원을 해제해야 함
- 단점: 자원 이용률 저하, 기아(여러 자원을 요청한 경우 필요 자원 중 최소 하나가 항상 다른 스레드에 할당 -> 무한 대기) 발생 가능
- No preemtion: 자원 선점을 허용
- 즉시 할당 불가능한 추가 자원을 요청시 hold한 모든 자원을 뺏김
- 상태가 쉽게 save되고 나중에 restore되는 자원들에 적용됨
- deadlock이 흔히 일어나느 자원에는 적용이 쉽지 않음
- Circular wait: chain을 끊음
- 모든 자원 유형에 전체 순서를 매기고, 각 스레드가 열거된 오름차순으로 자원을 요청함
- 자원을 비교하여 순서상 빠른 것을 결정하고 순서대로 요청하도록 함
- 회피: 현재 요청에 대해 현재 가용자원, 현재 할당된 자원, 향후 요청/해제 등을 고려하여 요청 처리 결정
- 시스템이 어떤 순서로든 각 스레드에 자원을 할당하고 deadlock을 피할 수 있다면 safe
- safe sequence가 있으면 시스템은 safe state
- 스레드 Ti가 현재 가용자원 외에 Tj (j<i) 점유한 자원에 의해 만족된다면(Tj가 해제되어 Ti가 사용가능하다면) safe
- safe sequence가 없다면 시스템은 unsafe state
- unsafe state에서 deadlock state로 갈 수 있음 =>
- 각 자원 유형의 인스턴스가 하나인 경우
- 기존 자원-할당 그래프의 변형
- 예약 간선(claim edge) 추가 => 점선으로 표현
- 자원 요청은 claim edge가 assignment edge로 변환 시 cycle을 형성하지 않을 때만 허용됨
- cycle이 발견된다면 unsafe state이므로 스레드는 요청이 충족될 때까지 wait해야 함
- 각 자원 유형의 인스턴스가 여러 개인 경우
- Banker's Algorithm (생략,,,, 나중에)
- 감지 및 처리기법
- deadlock 발생 여부를 결정하기 위해 시스템 상태를 검사하는 알고리즘
- deadlock으로부터 회복하는 알고리즘
- Single instance: 각 자원 유형의 인스턴스가 한 개인 경우
- wait-for graph: 자원-할당 그래프의 변형을 사용
- wait-for 그래프에 cycleㅇ이 있으면, 시스템에 deadlock 존재
- Several instances: 각 자원 유형의 인스턴스가 여러 개인 경우
- Available: m개의 각 data type에 대한 가용 자원의 수
- Allocation: 각 스레드에 현재 할당된 자원의 수
- Request: 각 스레드가 현재 요청한 자원의 수
- 완료되어야하는(=처리해야하는) 스레드들에 대해 모든 가능한 할당 순서를 조사함
- 알고리즘 호출시기
- 할당 요청이 즉시 승인되지 않을 때마다 => deadlock을 야기시킨 특정 스레드 식별 가능 => overhead 문제
- 일정한 시점마다 => overhead는 덜함 => 어느 스레드가 deadlock을 야기시켰는지 판단 불가
sy9723
2023. 6. 26. 19:29
2023. 6. 26. 19:29
- 시스템은 일반적으로 동시에 또는 병렬로 실행되는 여러 스레드(수백 또는 수천)로 구성됨
- 스레드는 종종 사용자 데이터를 공유함
- 공유 데이터에 대한 접근이 제어되지 않을 때 race condition이 존재하여 데이터 값이 손생될 수 있음
- 프로세스 동기화에는 race condition을 피하기 위해 공유 데이터에 대한 접근을 제어하는 도구를 사용함
- Mutex Lock
- 공유자원에 접근하기 위해 lock 필요
- critical section(프로세스가 여러 개 있을 때 그 여러 프로세스들이 공유하게 되는 자원에 해당하는 코드 부분)에 들어갈 땐 lock을 얻어야 하고, 나오면 해제해야함
- Mutex Lock의 단점
- 한 프로세스가 CS에 있는 동안, 다른 프로세스가 계속 조건을 확인하며 loop를 실행해야 함
- Semaphore
- Mutex Lock의 확장된 개념
- 여러 자원에 대한 동기화 가능
- 공유변수 S를 사용
- 공유자원이 여러 개인 경우 가용 자원의 수로 초기화됨
- 공유자원이 하나인 경우 => Mutex Lock
- 예) 공유자원이 3개인데 count 값이 -2인 경우: 3개는 사용중이고 2개의 프로세스가 대기중이라는 뜻
- Monitors
- 가장 high level
- 프로그래머가 세마포나 뮤텍스 락을 잘못 사용하면 error가 쉽게 발생함
- 간단한 동기화 도구들을 고급 언어 구조물로 통합하면 해결할 수 있음
- ADT(abstract data type): 특정 구현과는 무관한 데이터와 데이터에 대한 연산을 캡슐화한 것
- Monitor type(=ADT): instance의 state를 정의한 변수와 그 변수에 동작하는 함수 본체를 선언
- Monitor type은 프로세스가 직접 사용 금지(class 개념)
- 모니터 내부의 함수는 내부에 정의된 변수와 파라미터에 의해서만 접근 가능
- 모니터 내부의 local 변수는 local 함수에 의해서만 접근(read/write) 가능
- 모니터 내에서 한 번에 한 프로세스만 active함을 보장함
- 동기화 메커니즘 필요
- 프로그래머가 type condition 변수들을 정의 가능
sy9723
2023. 6. 12. 00:12
2023. 6. 12. 00:12
- CPU 스케줄링 비교 기준
- CPU utilization (CPU 이용률)
- 가능한 CPU를 바쁘게 만들어야 함
- 실제 시스템에서 40% ~ 90% 까지 가능함
- Throughput (처리량)
- 작업량 측정 방법
- 시간 단위 당 완료된 프로세스의 수
- Turnaround time (처리 시간)
- 프로세스 실행에 소요되는 시간
- 대기 시간 + 실행 시간 + I/O 시간
- Waiting time (대기 시간)
- Response time (응답 시간)
- 첫 응답이 시작되는 데까지 걸리는 시간
- 요구 제출 ~ 첫 응답 까지의 시간
- First-Come, First-Served Scheduling (FCFS)
- 가장 간단한 CPU 스케줄링 알고리즘
- CPU를 처음 요청한 프로세스가 CPU를 처음으로 할당 받음
- 프로세스가 ready queue에 들어가면, 큐의 끝에 PCB가 연결됨
- CPU가 가용해지면, 큐의 앞에 있는 프로세스에 할당됨
- 단점
- 프로세스의 대기 시간이 종종 꽤 김
- Convoy effect (호위 효과): 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하길 기다림
- Shortest-Job-First Scheduling (SJF)
- 각 프로세스를 다음 CPU burst와 연관시켜서 스케줄링함
- smallest next CPU burst를 가진 프로세스에 할당함
- 두 프로세스의 값이 동일하면, FCFS가 적용됨
- 프로세스의 전체 길이가 아닌, next CPU burst의 길이에 좌우됨
- 주어진 프로세스 집합에 대해 평균 대기시간이 최소임
- short 프로세스를 long 프로세스보다 앞으로 이동 => short 프로세스의 대기시간을 줄이고 long 프로세스의 대기시간이 증가
- next CPU burst 길이를 알 수 없으므로, CPU 스케줄링 수준에서 구현 불가함
- 하지만 값을 예측하여 구현 가능 (next CPU burst는 이전의 값과 비슷하다고 기대함, 측정한 이전 CPU burst의 길이를 지수평균하여 예측할 수 있음)
- 선점 / 비선점 방식이 있음
- Round-Robin Scheduling (RR)
- FCFS 스케줄링과 유사함
- 시스템이 프로세스 간 전환이 가능하도록 선점이 추가됨 (FCFS + Preemption)
- 원형 큐를 돌며 하나의 시간 할당량 동안 CPU를 할당함
- 새로운 프로세스는 준비 큐의 tail에 추가됨
- 준비 큐의 첫 프로세스 선택 -> 시간 할당량 후 interrupt 되도록 timer 설정 -> 프로세스를 dispatch
- RR 알고리즘의 성능은 시간할당량 크기에 크게 좌우됨
- context swiitch time < time quantum(시간 할당량)
- 시간할당량은 너무 커도 안됨, 너무 크면 FCFS로 퇴보함 => 프로세스의 80%가 시간 할당량 내에 끝나도록 설정해야 함
- Priority Schedule
- 우선순위는 각 프로세스와 연관, 우선순위가 높은 프로세스에 CPU 할당됨
- 우선순위는 기준(내부적 요인: 시간 제한, 메모리 요구, 사용한 파일의 수, IO 대 CPU 비율, 외부적 요인: 프로세스 중요도, 비용, 작업 후원 부서, 정치적 요인)에 의해 정해짐
- 우선순위가 낮은 일부 프로세스는 무한 대기할 수 있음
- 해결방법 1) aging: 장시간 대기중인 프로세스의 우선순위를 점차 높여줌
- 해결방법 2) Priority Scheduling + RR
sy9723
2023. 6. 11. 23:15
2023. 6. 11. 23:15
- 프로세스(process)
- 실행중인 프로그램
- 작업의 단위(unit of work)
- 시스템은 프로세스의 모음
- 동시에 실행 가능
- 프로세스의 메모리 레이아웃
- Text section: 실행코드
- Data section: 전역변수
- Heap section: 프로그램 실행시 동적으로 할당되는 메모리
- Stack section: 함수호출시 임시 데이터 스토리
- 프로그램과 프로세스
- 프로그램 자체는 프로세스가 아님
- 실행파일이 메모리에 load될 때 프로그램이 프로세스가 됨
- ex) 두 프로세스가 동일 프로그램과 관련
- 두 개의 독립된 실행 순서로 간주됨
- 창을 여러 개 열어놓는 경우, 같은 프로그램이더라도 여러 개의 독립적인 프로세스를 가짐
- Text section은 동일, 나머지는 다름
- 프로세스가 실행 중에 다른 프로세스를 생성할 수 있음
- 프로세스의 상태
- new: 새로 만들어진 상태
- ready: cpu를 사용하기 위해 기다리고 있는 상태, 프로세서에게 할당되기 위해 기다리고 있는 상태
- running: 실행중인 상태
- waiting: 입출력이 필요하거나 어떤 이벤트가 발생한 경우(파일 접근 등) 기다리는 상태
- terminated: 실행이 끝난 상태
- 오직 한 프로세스만이 어떤 프로세스 코어에서 running 상태일 수 있음
- 많은 프로세스들은 ready 와 waiting 상태에 있음
- Process Control Block(PCB)
- 프로세스가 가지는 상태정보를 저장하는 자료구조/공간
- 특정 프로세스 관련 정보들을 포함
- Process state: new, ready, running, waiting, halted 등
- Program conter: 다음에 실행해야되는 명령어가 있는 위치(주소값)
- CPU registers
- CPU-scheduling information: process priority, pointers to scheduling queues, and any other scheduling parameters
- Memory-management information
- Accounting information
- I/O status information
- 프로세스 스케줄링(Process Scheduling)
- 항상 프로세스들이 실행되도록 하여 CPU 이용률을 최대화함
- 프로세스 사이에서 CPU core를 자주 switch => user와 program이 interact함
- core에서 프로그램을 실행하기 위해 실행 가능한 프로세스를 하나 고름
- 각각의 cpu core에서 한 번에 하나의 프로세스 실행
- core 수 보다 프로세스 수가 더 많은 경우, 프로세스들이 wait해야 함
생략......(나중에)
- 프로세스간 통신(Interprocess Communication)
- 여러 프로세스는 OS에서 동시에 실행됨
- independent
- 프로세스는 시스템에서 실행중인 다른 프로세스와 데이터를 동유하고 있지 않을 때 independent임
- cooperating
- 프로세스는 시스템에서 실행중인 다른 프로세스와 영향을 주고 받을 때 cooperating임
- 프로세스 협력(cooperating)의 이유: 정보공유 및 데이터 공유, 처리속도 높임, modularity
- cooperating process는 interprocess communication(IPC) mechacism을 필요로 함
- IPC 모델
- shared-memory 모델
- 메모리 영역 공유
- 빠름
- 충돌이 일어날 수 있으므로 프로세스들은 동시에 동일 위치에 쓰지 않도록 책임져야 함 (순서 제어 필요)
- message-passing 모델
- 메세지를 교환
- 더 작은 양의 데이터를 교환할 때 유용함
- 느림
생략......(나중에)
- 스레드(Thread)
- CPU를 사용하는 기본적인 단위 (즉, CPU 1개에 thread 1개가 올라감)
- 프로세스 안의 제어 흐름
- 동일 프로세스에 속하는 다른 thread들과 code, data, resource, file signal를 공유함
- 한 번에 하나 이상의 task 실행 가능
- ex) 웹 브라우저에서 하나의 스레드는 이미지나 텍스트를 표현하고, 또 다른 스레드는 네트워크에서 데이터를 검색할 수 있
