21.10.13
5. 교착상태(deadlock)

• 2개 이상의 프로세스가 서로 차지하고 있는 자원을 요구하면서 무한정 대기
• 충분조건으로 mutual exclusive, hold & wait, preemptive, circular wait 조건을 충족시 교착상태 발생
• 상호배제는 프로세스가 자원을 사용하므로 다른 프로세스는 대기하며, 점유&대기는 프로세스가 현재 사용중인 자원을 내놓지 않기 때문에 발생하고, 선점은 현재 수행중인 프로세스가 자원을 독점하기 때문이며, 환형 대기는 각 프로세스가 요구하는 자원을 계속적으로 요구하면서 자원을 사용할 수 없는 상태를 의미한다.
  1) Deadlock preventive
  교착상태 발생조건 4개 중에서 각 발생조건들이 발생되지 않도록 배제(제거)->자원할당 그래프 ->circle

=> unsafe상태 => deadlock 발생가능성 존재
2) Deadlock avoidance

• 교착상태 회피 방법으로 Banker’s algorithm 사용
• 은행가 알고리즘은 시스템에서 각 프로세스가 가질 수 있는 최대 자원을 자원의 종류마다 미리 신고하여 교착상태가 발생되지 않도록 하는 방법
• Available: 각 자원이 이용가능한 자원의 수
• Max: 시스템의 최대 자원의 수
• Allocation: 현재 프로세스에게 할당된 자원의 수
• Need: 프로세스가 앞으로 요구하는 자원의 수
  =>safe상태가 되도록 유지 -> 교착상태 발생하지않은 상태
  ->시스템이 계속 safe상태인가를 점검하는 과정을 반복 수행
  3) Deadlock detection
• 교착상태가 발생하였는가를 일정한 시간마다 점검
  4) Deadlock Recovery
• 교착 상태 발생시 교착상태가 발생한 특정 프로세스를 강제중지시키고, 해양 자원을 회수하여 다른 프로세스가 사용가능하도록 할당
• 교착상태가 발생한 프로세스의 복구 문제: starvation이 발생하지 않도록 조정하고, 프로세스에게 자원할당을 위해 Aging 기법적용
  starvation: 무한정 프로세스 기다리기
  aging 기법: 자원을 기다린 순서에 비례하여 할당하는 것 오랜기간동안 wait 기다린 프로세스에게 적용
  중간고사
  10/21 수 : 11시
  시험범위: 1장~5장(중간)
  1장~배운데까지(기말)’

21.10.14
교착상태 회피: 은행가 알고리즘
-available,max,allocate,lead
교착상태 탐지: 일정 시간마다 시스템을 감지하여서
프로세스가 무한 연기 되었는지 탐지해내는 것도 os의 한 기능이다
교착상태가 발생됐을 때 강제중지시키고 이 자원을 다른 프로세스에게 할당하므로써 기존의 강제중지 했던 걸 어떻게 복구 할 것인가
기아상태 해결할 수 있다

143p
환형대기: 전용 자원을 다른 프로세스가 요구해서 교착 상태 발생

\

• 프로세스 Deadlock

SPOOL : 출력 내용을 프린터로 직접보내지 않고
보조기억장치에 보낸후, 보조기억 장치에서 프린터 전송
속도 차이를 해결하여 대기시간을 감소하는방법
Simultaneous
phenipheral
Operation
On
Line
동시에 주변장치로 동시에 온라인으로 보내는 방법
보조기억 장치에 할당하는데 공간이 꽉 차면 overflow -> 교착상태에 빠질 수가 있다
<OS기능>
교착상태
-prpeventive예방
avoidance회피
detection감지
recovery복구

무한연기 -> aging
가장 오랜시간 기다린 프로세스에세 자원을 할당하는 방법

복구: 강제 중지시키고 강제중지시킨 프로세스의 자원을 다른 프로세스에게 할당

회피: banker's algorithm
교착상태 회피: 교착 발생 가능성을 미리 제거
자원 효율적 이용 목적
예방보다는 덜 엄격
1) 3가지 시스템 상태
안전:시스템이 순서대로 자원 할당할 수 있고 교착 상태 방지
불안전: 교착상태 발생 할 수 있는 상태
Banker's algorithm
-Available: 이용 가능 이용가능량
max: 최대 최대요구량
allocation: 할당 할당량
need: 추후 요구 요구량

max-all=need
need<=work
work=work+allocation
p2,work=2+5=7 안전상태
detection
일정시간마다 교착상태인지 판단
다음주 수업x 자율학습

21.10.27
6. 주기억장치 관리
1) 주기억장치관리 전략
Fetch strategy

• 보조기억 장치에서 주기억장치로 언제 프로그램과 데이터를 가져올것인지 결정
• Demand Fetch: 실제 프로세스가 실제로 사용할 블록을 가져오는 방법
• Anticipatory Fetch: 프로세스가 추후 호출 가능성이 높은 블록을 적재
  Placement strategy
• 주기억 장치의 어디에 프로그램과 데이터를 적재할 것인가를 결정
• Best fit, worst fit, first fit
  Replacement strategy
• 주기억장치에서 보조기억장치로 블록을 제거하기위한 정책
  2) 주기억장치 관리 기법
  Single programming 초창기
• 주기억 장치에 사용자프로그램을 1개 적재하여 수행하는 방법으로 컴퓨터 초창기시스템에 적용하였으며, bound register를 사용
  Overlay
• 주기억 장치의 용량보다 큰 프로그램을 수행하기 위해 주기억장치에서 수행가능한 여러 조작으로 분할하여 나누고, 이를 차례대로 적재하여 수행하는 방법으로, 프로그래머는 프로그램의 모드,구조,데이터 구조에 대한 이해필요
  Swapping
• 보조기억장치에서 주기억장치로 새블록(page)을 가져와서 기존의 블록과 교체하며 실행중인 프로세스의 입출력이 발생, cpu의 할당시간 초과, 프로세스의 수행 종료시 발생
  Fixfed programming=multiprogramming
• 주기억 장치를 고정된 크기로 분할하여 사용
• 사용자 프로그에 대한 성격이 파악되어있는 경우 주기억장치의 효율적 사용
• 사용자 프로그램이 대체하고 남는 영역을 fragmentation이라고 하며, 이는 프로그램이 차지하고 남는 영역으로 다른 프로그램에 의해 사용될 수 없으므로 낭비 초래
• 작업의 크기가 주기억장치보다 작은 경우 fragmentation 발생
  Variable partitioning=multi programming
• 주기억장치에 사용되는 프로그램의 크기에 맞추어 기억장소를 할당
• 내부 단면화는 발생되지 않지만, 외부 단편화가 발생하며, 이를 해결하기 위한 garbage collection 필요
• Coalescing(인접한 기억장소 통합하여 사용 가능하게 만듦)과 compaction(압축)기법을 사용하여 필요한 공간 확보

5. 주기억장치관리
   1) 전략
   Fetch,placement,replacement
   2) 기법: single programming
   Overlay
   swapping

기억장치를 관리하는 운영체제 일부를 기억장치 관리자
할당,
174p overlay 필요한 데이터만 기억장치에 적재하고 필요하지 않으면 보조기억장치에 적재하여 실행하는 방법
분할1,2,3로 나누어 차례대로 적재한다
Swap in swap out
177p 2-2 출력, 인터럽트: swapping 발생한다
단일사용자 기억장치 할당
Throughput 단위시간 내에 처리하는 작업량
고정분할할당
각 큐에 있는 내용 -> 각 분할 내용에 사용될 수 있음
각 큐에 있는 내용이 차례대로 사용될 수도 있음
단편화가 발생할 수 있다
단편화: 사용될 수 있는 기억공간
090k,100k,30k 이렇게 사용하다가 빈 공간이 생김
가변분할에서도 단편화 발생 가능
192p 통합
193p 페이지기법
219p
연습문제
페이지 크기가 작으면
페이지/segment

• 가상기억장치에서 사용자 프로그램에 대한 분할 단위
• 분할단위에서 크기 고정 -> page
  가변 -> segment
   Page 크기가 작으면 page table 증가
   단편화 줄어듦

Trap: 내부 인터럽트
 가상기억장치 virtual memory(=storage)

• 주기억장치의 용량 한계로 인해 보조기억장치를 사용하여 주기억장치의 용량을 확대하여 사용하는 방법
• Virtual address를 real address로 변환하기 위한 과정: DAT=VAT(Virtual address transformation)
• 가상주소: 현재 진행중인 프로세스가 참조하는 주소
• 실제 주소: 실제 주기억 장소에 프로세스가 참조하는 주소
  (Dynamic Address Transformation) 과정을 수행
• Virtual storage상의 user program에 대한 분할단위는 block 단위
  주기억장치에 적재되며, page와 segment로 구분
  Base, displacement변위
• page방식에서 실제주소 r=(b,d)로 구분되며, PMT(page map table)의 시작점 레지스터와 블록 사상표에 의해 r을 b’와 d’에 의해 계산
• PMT 시작레지스터 -> 블록사상표 * r: resident bit – 1 :if exists in real memory
  0: if not exists in real memory
  S: secondary address
  b’: 실제 블록의 주기억장치 주소
  R S B’ => r=b’+d’에 의해 실제 주소 계산
• segment방식
• r a l R w e a
  (protection key) s
• l: segment의 크기
• r:read w:write e:erase a:append 가변
• l:실제 블록의 주기억장치주소
  a: 보조기억장치의 해당 segment 주소
  r=s’+d: 실제주소 계산
  v=(S,d)

21.11.03
*CPU

• control unit(제어장치)+ALU(연산장치:arithmetic&logic unit)로 구성
• IR,PC,명령어해독기,번지해독기로 구성
• 제어장치는 제어신호
  신호를 규칙적으로 발생하여 명령어 처리
  -가산기,누산기,보수기,레지스터,상태 레지스터
• cpu의 4대기능
  ① 기억기능: register가지고 수행(AC,PC,IR,MAR,MBR,PSWR)
  레지스터간의 전송
• Serial transfer 직렬전송 한 레지스터에서 다른 레지스터로 데이터를 한 clock pulse 동안 1 bit씩 전송하는 방법
  A->B : clock pulse: 직렬전송을 수행하는 시간
• Parallel transfer 병렬 전송 한 clock pulse 동안에 레지스터의 내용을 모ㅗ두 한번에 전송하는 방법
• Bus transfer 버스 전송 공통배선의 모임인 버스에 레지스터들이 연결되고, 전송을 원하는 레지스터의 제어선을 1로 하여 전송을 수행하는 방법
• Memory transfer메모리 기억 전송 : 메모리와 외부회로사이의 전송

② 연산기능: ALU(Arithmatic & Logic unit)
-구성: 가산기,누산기,보수기,레지스터,논리 레지스터 등으로 구성
-연산의 종류:
unary operation 단항 연산: not,move,complement,shift,rotate
Binary operation 이항 연산: +.-.*,/,and,or,xor
③ 전달기능: Bus수행: 공통배선의 모임
-내부bus: ALU에 직접 연결
-외부bus:cpu와 주기억장치, cpu와 보조기억 장치 사이를 연결
④ 제어기능

21.11.04
보조기억장치관리
1) 보조기억장치에서 저장공간할당

• 사용되지 않는 공간이나 삭제된 공간을 os가 사용할 수 있도록 지원
  (1) Bit-vector
  연속적으로 이용가능한 n개의 블록을 탐색하는 방법으로, 브록이 사용중이면 1, 그렇지 않으면 0으로 지정하여 이용가능한 저장공간을 확인
  (2) Linked-list
  보조기억매체에서 사용가능한 블록을 포인터를 사용하여 관리
  (3) Grouping
  하나의 블록에 비어있는 n개의 블록을 가지며, 마지막 1개는 비어있는 n개의 블록에 대한 번지를 지정하여 가용블록 관리
  (4) Counting
  Contiguous allocation 이용시 연속된 블록을 연속되어 할당되며, 첫 가용블록의 주소와 그 블록에서 이용가능한 연속된 블록을 관리

1) 기본공간관리
2) 공간할당: 저장하고, 할당되며, 그 파일을 접근할 것인가에 대한 내용(문제처리방법)
(1) Contiguous allocation 연속할당

• 프로그램과 데이터가 저장장치에 저장될 때, 그 전체가 물리적 기억장치에 연속되어 저장
• 파일의 크기에 맞는 연속공간이 없으면 공간할당이 불가
• 논리적으로 연속된 레코드들은 저장장치에 물리적으로 인접하여 저장되는 방법
• 저장된 파일이 삭제시, 해당공간에 다른 파일이 저장되는 경우 크기가 작으면
  (2) Linked allocation 링크드 할당
• Sector-oriented allocation
• 파일에 속하는 sector 단위로 포인터를이용하여 사용
  *sector: 보조기억매체에 저장되는 최초 단위 512byte
• Block-oriented allocation
• Vlock chaining,index lock chaining,block oriented
• File mapping방법

3) 보조기억매체(디스크,USB,SSD) 스케줄링
(1) FIFO
요청 대기큐에 들어온 작업순서대로 처리하며, 실행순서가 고정되는 방법으로보조기억매체에 대한 탐색패턴이 최적화되지 않으며, 대화식 시스템에는 부적합한방법
(2) SSTF
Shortest seek time first
현재 요청된 작업의 탐색시간이 가장 적은 작업을 우선 처리하며, 작업중에 요청된 작업도 진행하면서 함께 처리
(3) SCAN
탐색 패턴이 보조기억매체의 마지막에서 처음, 처음에서 마지막영역으로 이동, 반복하면서 수행하며, 작업중간에 요청된 작업도 함께 처리
(4) C-SCAN
작업 중 요청된 작업은 현재 요청된 작업 종료후 수행
작업 방향은 항ㅇ상 마지막 트랙에서 첫번째 트랙으로 진행
(5) N-SCAN
SCAN과 동일하나 중간에 요청된 작업은 현재요청된 작업종료후 수행