Translation Lookaside Buffer

Relocation 을 위해서 Page Table 을 이용한다. Page Table 에는 두가지 종류가 있다.

• hierarchical page table
• inverted page table

hierarchical page table 을 사용할 때는 Page Table 자체가 크기 때문에 이게 2, 3, 4, ... 단계 page table 이 될 수 있다.

2단계 페이지 테이블의 경우
데이터 읽기 → Root Page Table → 2nd Page Table → 정확한 Physical Address 주소 획득 → memory
⇒ 데이터를 읽을 때, memory 에 3번 access

ex) 보통 프로그램을 실행할 때 
코드 → 데이터 → 코드 → 데이터 → ... 을 반복하는데 
각각 3번씩 접근하므로 프로그램의 속도가 3배가 느려진다.

3단계 페이지 테이블까지 존재하는 경우에는 4번 메모리에 접근해야 한다.

⇒ TLB (Translation Lookaside Buffer) : Cache 이용

페이지 크기 2^10, 2^12 → 너무 큰 숫자
⇒ 만약, 명령 1000개라고 치면, 한 페이지 안에 명령 1000개가 들어있다는 뜻인데 이건 매우 많은 양이다.

처음에 코드를 읽어올 때 이 코드가 몇번 프레임에 있는지 페이지 테이블을 통해 찾고, Locality 덕분에 그 뒤 같은 테이블을 계속 읽는다.
어떤 페이지를 한 번 읽었을 때 몇 번 프레임에 있었다는 정보를 TLB에다 최근에 내가 읽은 페이지에 대한 정보를 적어 놓게 되면 다시 페이지 테이블을 찾으러 갈 필요가 없다.
⇒ Cache 역할을 한다.

TLB 에서 access 하면 된다. 최근에 내가 access 한 페이지의 정보 O
⇒ 속도 저하 방지 가능

Each virtual memory reference can cause two physical memory accesses

• one to fetch the page table
• one to fetch the data

To overcome this problem a high-speed cache is set up for page table entries

• called the TLB - Translation Lookaside Buffer
• Contains page table entries that have been most recently
  used
• Functions same way as a memory cache

주소를 변환하는 과정

1. 페이지 번호를 TLB 에 주고 프레임 번호를 얻어온다.
2. 만약 데이터가 있다면, 이걸 TLB hit 라고 한다.
   = TLB 에 내가 원하는 페이지에 대한 정보가 있는 경우
3. 만약 데이터가 없다면, TLB miss 라고 한다.
   = TLB 에 내가 원하는 페이지에 대한 정보가 없는 경우
   → 페이지 테이블로 접근
   ↳ 페이지 테이블을 2단계, 3단계 거쳐서 내가 원하는 프레임 정보를 얻어내면 이걸 다시 TLB 에 쓴다 .
   → 그 후 , 주소 변환
4. 페이지가 메모리에 없는 경우 (= 페이지 테이블에 페이지가 없는 경우) 는 Page fault 라고 한다.
   → 하드디스크에 가서 페이지를 메모리에 올려 놓는다.
   당연히 올려 놓는 과정에서 페이지 테이블을 업데이트 하고, TLB 도 업데이트 한다.

이렇게 한 번 작업하고 나면, 나중에 TLB에서 내가 원하는 정보를 얻을 수 있기 때문에 주소 변환이 즉시 즉시 이루어지게 된다.

왼편은 일반적인 메모리에 TLB 가 저장되어 있는 것
어떤 프로세스의 연속된 정보가 들어 있는 것이 아니라 최근 정보가 들어 있는 것이기 때문에 sequential 하게 5번 페이지가 37 번 프레임에 있다 하면, 5번 페이지를 꼭 찾아야 한다.

른편은 페이지 번호가 원소의 일부로 사용되는 association 타입을 이용한다. 하나의 엔트리 안에 페이지 번호와 프레임 번호가 들어 있어있다.
⇒ 한번에 내가 원하는 프레임 번호를 찾아낼 수 있다.

associative 메모리를 사용하기 때문에 TLB 는 한번에 access 하면 프레임 번호가 딱 튀어 나온다.

거의 모든 시스템이 Virtual Memory 와 TLB 를 사용한다.

하지만, Page size 에는 의견이 다양하다.

Page Size (페이지 크기는 작아서는 안된다!)

• Smaller page size, more pages required per process
• More pages per process means larger page tables
• Larger page tables means large portion of page tables in virtual memory

페이지의 크기가 작다면, 같은 크기의 프로그램 내에 더 많은 페이지 수가 많아지게 되므로 페이지 테이블의 Entry 개수가 많아지게 된다.
⇒ Page Table 수가 증가한다.
↳ 메모리에 페이지 테이블이 없을 확률이 높아진다.
⇒ 시간 소요가 증가한다. ⇒ 페이지 크기는 작아서는 안된다!

Page Size2 (페이지 크기는 커서는 안된다!)

• Small page size, large number of pages will be found in main memory
• As time goes on during execution, the pages in memory will all contain portions of the process near recent references. Page faults low.
• Increased page size causes pages to contain locations further from any recent reference. Page faults rise.

Virtual Memory System 에서는 여러 프로그램들이 메모리에 들어와 있어야 한다. 대부분의 경우 프로세스 하나하나 마다 일정한 크기의 공간을 나누어 준다.

만약 내가 할당받은 공간이 이만할 때, 우연히 내 페이지 크기가 딱 그만큼이라서 이 공간에 딱 한페이지만 들어갈 수 있다고 하자.
↳ 즉, 페이지 크기가 상당히 큰 것이다.

프로그램을 실행하려고 하면, 코드와 데이터가 있어야 한다. 코드 한줄, 데이터 한줄 계속 실행하는데, 각각의 코드와 데이터가 들어 있는 페이지는 하드디스크로 계속 Swap-In, Swap-Out 하게 된다.

그럼 계속 코드가 들어 있는 페이지와 코드가 들어 있는 페이지가 왔다갔다 실행되며 Thrasing 이 발생할 것이다.

만약 페이지의 크기가 작아서 내 프로그램이 더 작은 단위로 나뉘어져 있다면, 코드 한쪽 데이터 한쪽 스택 한쪽, ... 필요한 애들을 한쪽씩 갖다 놓고 작업을 할 수 있기 때문에 Page fault 가 일어나지 않는다.

Thrasing이 발생할 것이다

data ↔ code 왔다갔다 많이할 것

페이지를 작게하면 필요한 애들을 적게 적게 갖다 놔서 Page Fault 가 적어질 것이다.
↔ 페이지 크기를 크게 하면 Page Fault 가 많아질 것이다.

⇒ 결론적으로는 페이지는 너무 커도 안되고, 너무 작아도 안된다.

Segmentation

Segmentation을 이용한 Virtual momory system 은 굉장히 비효율적이기 때문에 사용하지 않는다.

• May be unequal, dynamic size
• Lends itself to sharing data among processes
• Lends itself to protection

sharing 하는 단위가 분명하다.

의미 있는 단위로 나뉠 것이다. → 한 segment 안에 data 또는 code 만 존재할 것이다.

Protect 하는 단위가 분명하다.

• PCB → OS 가 사용
• Code → User 가 사용

Segment Table Entries

Segment 을 이용한 시스템에서는 Dynamic Partitioning 을 사용하기 때문에 Segment 의 정확한 시작 주소를 알아야 한다.

길이가 제각각이기 때문에 Offset > Length 인지 계속 확인해 주어야 한다.

Segment Tables

• Each entry contains the length of the segment
• A bit is needed to determine if segment is already in
  main memory
• Another bit is needed to determine if the segment has been modified since it was loaded in main memory

Address Translation in Segmentation

주소변환과정

Combined Paging and Segmentation

두 시스템의 장점을 결합하여 사용

• Paging System → External Fragmentation X
• Segmenation System → Protection, Sharing 👍

1. 페이지 크기로 나누기 전에 Segmentation 4가지 영역으로 먼저 나눔
2. 동일한 크기의 page frame 크기로 나눔 ⇒ page 크기로 나눔
   ⇒ 한 페이지 안에 code 와 data, pcb 등등 서로 섞인 페이지가 존재하지 않게 된다.
3. 각 Segment 로 나눈 단위마다 Internal Fragmentation 존재 가능 (공간 낭비 조금 존재, but Protection 과 Sharing 이 더 중요)

Types of Memory

Real Memory

Main Memory

Physical 한 메모리 자체를 말한다.

Virtual Memory

Main Memory + Memory on disk

전체 프로그램을 모두 메모리에 넣지 않고, 프로그램의 일부만 메모리에 넣고 실행을 시키는 방식.

전체 프로그램 중 일부는 진짜 Physical 한 메모리에 들어 있고 나머지는 hard disk에 들어있는채로 시작한다.

Execution of a Program

Resident set

전체 프로그램 중 메모리에 올라와 있는 부분(page, segment)

Interrupt

프로세스가 주소에 접근하려는데, 메모리에 올라와 있지 않은 주소가 필요한 경우
OS 가 Interrupt 를 건다.
→ 현재 프로세스 Blocked Queue 로 이동
→ 프로세스의 I/O 작업 (I/O Request)
→ 끝
→ I/O Interrupt
→ 프로세스가 Ready Queue 로 이동

Thrashing & Locality

메모리는 무제한이 아니기 때문에 하나의 프로세스당 몇 페이지만 메모리에 올라올 수 있다. 따라서 다른 페이지를 메모리로 가지고 오기 위해서는 메모리에 원래 있던 페이지를 하드디스크로 버려야 한다.

Thrashing

페이지를 잘못 버려서 프로세스를 실행하지 못하고 페이지를 버리고 가져오는데 시간을 다 쓰는 것

Reference Locality

별 일 없으면, 프로그램은 순차적으로 실행되는데, Reference Locality 덕분에 Page는 한 번 실행되면 웬만하면 Page 변경을 하지 않는다.

Paging

프로그램을 실행하기 위해서는 다음 두가지가 잘 되어야한다.

• Relocation
• Protection

Relocation 에 필요한 요소들

Relocation 은 Physical Address 를 얻는 과정이다.

1. Page Table 이 필요 → Frame# 필요 → offset 과 연결 ⇒ physical address
2. Presence bit : 메모리에 있나 없나 확인하는 비트
   • 0 → 해당 페이지가 메모리에 없음
     ↳ Interrupt → Block → harddisk에서 page 가져옴 → page table update → Ready → Running
   • 1 → 해당 페이지가 메모리에 있음
     ⇒ page frame# 를 찾아서 offset과 연결하여 physical Adress 를 완성해 relocation 가능
3. Modify bit : 해당 페이지가 메모리에 올라온 이후, update 된적이 있는지 확인하는 비트
   • 0 → code 변경 X
   • 1 → code 변경 O

code는 변경되지 않고, data는 변경되는 경우가 많다.

P1 프로세스의 페이지 두개를 메모리에 올려 놓고 실행을 하고 있는 상황이다.

두 페이지 중 한 페이지는 프로그램 코드이고, 한 페이지는 데이터가 포함되어 있는 페이지이다.

코드가 포함되어 있는 페이지는 수정된 것이 없지만, 데이터가 포함된 페이지는 수정된 상태이다.

P1 의 페이지는 메모리에 최대 2개까지만 올라갈 수 있기 때문에 새로운 페이지를 가져오기 위해서는 기존의 페이지를 버려야 한다.

• 이때, modify bit = 1인 경우인, data가 포함된 페이지를 그냥 버리면, 데이터가 날라가므로 hard disk에 적어주어야 한다.
• 그러나 modify bit = 0인 경우에는 새로운 페이지를 읽어올 때, hard disk 를 쓸 필요 없이 읽기만 하면 된다.

Each process has its own page table

• Each page table entry contains the frame number of
  the corresponding page in main memory
• A bit is needed to indicate whether the page is in main memory or not
• Another modify bit is needed to indicate if the page has been altered since it was last loaded into main memory

각각의 프로세스마다 Page Table 을 가지고 있다.

• 각각의 Page Table entry 는 main memory안의 해당하는 페이지의 frame# 가 있다.

Page Table Entries

Virutal Address

Logical Address 인데, Virutal Memory 에서 사용하는 Logical Address 이다.

Paging System 이므로, Page#와 Offset 으로 구성이 되어 있다.

Page Table Entry

한 페이지마다 해당하는 페이지의 Presence bit, Modify bit, Other Control Bit, Frame# 가 구성요소로 존재한다.

구조체 변수라고 생각하면, 4개의 멤버를 가지는 구조체 변수이다.

페이지마다 하나씩 존재하므로 구조체 배열로 관리 된다.

Address Translation in a Paging System

Register

• Register 는 실행하고 있는 프로세스의 페이지 테이블의 시작 주소값이 들어 있다.
• Register 는 1개만 있으면 된다.
  → CPU 는 한번에 하나의 프로세스만 실행하기 때문이다.

Q. Page # 와 Page Table 의 시작 주소를 더하는 이유?

X[i] ⇒ 여기서 X 는 구조체 배열의 이름이며, X[i] 의 주소는 X + i 이다.

즉, Page Table 의 시작 주소는 배열의 시작 주소이고 Page# 는 인덱스이므로 더하는 것이다.

하지만, 이러한 경우는 굉장히 운이 좋은 것이다.
페이지 테이블은 프로그램 크기가 커지면, 크기가 어마무시하게 커져, 한 페이지 안에 안 들어갈 수도 있다. 위와 같은 상황은 페이지 테이블이 한 페이지보다 작은 경우이기에 가능한 경우이다.

만약 페이지 테이블이 한 페이지가 넘어가게 되면, 페이지 테이블 중, 누구는 메모리에 있고 누구는 메모리에 있지 못하게 되는데, 페이지 테이블의 각 페이지가 메모리에 있나 없나, 메모리에 있다면, 어떤 프레임에 있나 알 수 있는 또다른 페이지 테이블이 필요하게 된다.

Two-Level Hierarchical Page Table

Second Level Page Table

• 엔트리 하나하나마다 페이지가 어디에 있는지를 나타낸다.
• Page Table 의 크기가 4Mbyte 인데, 이는 한 페이지를 넘어가게 된다.
  즉, 이 Page Table 의 Page 가 메모리 프레임 어느 곳에 위치하는지를 나타내는 root page table이 필요하게 된다.

Root Page Table

• Second Level Page Table이 메모리 어디 프레임에 들어가 있는지를 나타낸다.

프로그램의 최대 크기
(= 전체주소가 사용하는 bit, 기본 가정)

주어지는 값이다.

이 프로그램의 최대 크기는 4Gbyte(2^32 bytes) 이다.

• Giga = 2^30 Bytes

페이지의 크기
(= Offset bit, 기본 가정)

주어지는 값이다.

페이지의 크기는 2^12 byte 이다.

한 프로그램이 포함하는 페이지의 최대 개수

프로그램의 최대 크기 / 페이지의 크기 = 페이지의 최대 개수

한 프로그램이 포함하는 페이지의 최대 개수는 2^20 개 있을 수 있다.

페이지 테이블의 한 entry 의 크기

주어지는 값이다.

entry 는 원소의 개수를 말한다.

페이지가 2^20개 존재하므로, entry는 최대 2^20개 존재할 수 있다.

전체 페이지 테이블의 최대 크기 (2단계 페이지 테이블)

entry의 크기 X 최대 Page 수 = Page Table 의 최대 크기

• Mega = 2^20

전체 페이지 테이블(2단계 페이지 테이블)이 포함하는 페이지의 최대 개수

페이지의 테이블중 일부는 메모리, 일부는 하드디스크에 위치할 수 있다.

Page Table 의 최대 크기 / Page의 크기 = 전체 페이지 테이블이 포함하는 페이지의 최대 개수

• K = 2^10

즉, 1024개의 페이지가 페이지 테이블에 존재한다.
→ 어디에?
→ 하나하나 Entry 가 필요하다.

Root page table(페이지 테이블의 각 페이지가 어디에 있는지를 알려주는 페이지 테이블)의 크기

Entry 의 크기 X 전체 페이지 테이블이 포함하는 페이지의 최대 개수 = Root Page Table 의 크기

2^12 는 딱 한페이지 안에 들어가는 크기이다.

프로그램 처음 시작
→ root page table 만 메모리에 존재
↳ 2nd level page table 의 page 는 root page table 을 보고 실제 올릴 page 가져오기
→ 내가 원하는 데이터가 실제로 어디에 있는지 찾으러 간다.

Q. 각 단계의 Page Table 크기를 계산할 줄 알아야 한다.

이 예제에선 전체 프로그램의 크기 = 2^32 & 페이지의 크기 = 2^12
→ 만약, 페이지의 크기를 2^10 으로 바꾸면 어떻게 될까?

• 페이지 크기 ↓
• 페이지 개수 ↑
• 페이지 테이블 크기 ↑
• root 테이블 크기 ↑

지금은 root table 이 딱 1 페이지에 들어가서 root 페이지 테이블 먼저 메모리에 올려놓고 프로세스를 실행할 수 있지만,
페이지의 크기가 작아지게 되면, root page table 자체가 페이지 하나에 있을 수 없게 된다.
→ root page table 의 페이지가 어디있는지 알 수 있는 또 다른 페이지 테이블이 필요하게 된다. ⇒ 3단계 페이지 테이블

⇒ 2^10 으로 페이지 크기를 정했을 때, root page table, 2단계 table, 3단계 table 의 크기를 계산하라!

각 단계의 Page Table 크기를 계산할 줄 알아야 한다.

Address Translation for Hierarchical page table

내가 원하는 데이터나 instruction 은 파란색 위치에 존재한다.

이 위치에 있는 데이터나 instruction 을 읽으려면, 나는 여기 주소가 필요하다.

이 주소는 offset + Frame# 로 결정된다.

⇒ 나는 이 프레임의 번호가 필요하다. offset은 virtual address 에서 바로 온다.

프레임 번호를 알려면, 2단계 페이지 테이블을 확인해야한다.
2단계 페이지 테이블 중 하나의 엔트리만 나와있는 것이다.

2단계 페이지 테이블은 너무 크기 때문에 각각의 페이지테이블이 어디에 들어있는지 root page table 안에 들어 있다.

root page table 안에는 내가 원하는 instruction 이나 data 를 포함하고 있는 페이지 프레임 정보가 들어 있는 페이지 테이블이 어떤 프레임에 들어있는지 하는 정보가 들어있다.

Register 안에는 root page table 시작 주소가 들어있다.
Virtual Address 최대 크기는 32bit
⇒ 프로그램의 최대 크기 = 4Gbytes (2^32 bytes, 32bit)

• 12bit = offset
• 20 bit = page#
  • 10 bit = root page table 에서 내가 원하는 entry를 찾는데 사용한다.
  • 10 bit = 내가 찾는 page table의 시작 주소

Q. 앞에 10bit, 10bit 로 Virtual Address 를 나누었는데 왜 나누었을까?

페이지 크기를 2^10 으로 줄임 → offset 크기 = 2^20
⇒ 3단계 페이지 테이블 필요
⇒ Virtual Memory → 32 → 22(32-10) | 10

22(32-10)10(offset)

큰 페이지 테이블은 중간 페이지가 존재한다.
한 페이지의 Index 값의 최대 크기 → 2^10 (배열의 크기)
= 한페이지의 크기/엔트리의 크기 → 2^12/2^2 = 2^10 (10bit 필요)

⇒ 2^10 개의 원소를 포함하는 배열

한 페이지에 들어있는 엔트리의 개수 만큼 인덱스가 필요하다.

• 페이지 테이블 장점?
  ↳ 정해져있다. (녹음듣기)
• 페이지 테이블 단점?
  ↳ 앞뒤로 굉장히 많은 페이지 테이블이 존재한다.

몇 단계로 만들지는 시스템 개발자가 처음에 결정하는 것이다.

• root → 2단계 → 데이터
• root → 2단계 → 3단계 → 데이터

장점

메모리를 읽어야 하는 횟수가 정해져 있다. (단계에 따라 2번, 3번, ...)

단점

페이지 테이블의 크기가 커질수록, 원하는 페이지가 메모리에 없을 확률이 높아진다.
⇒ 메모리 뿐만 아니라, 하드디스크에 가서 페이지 테이블 정보를 읽어와야 한다.
→ 메모리에 비해 하드디스크는 접근 시간이 길다.

Inverted Page Table

Page Table의 대부분의 엔트리들은 Presence bit가 0이다.
↔ 하지만 나는 1인것만 있으면 된다.

⇒ Presence bit 가 1인것만 뽑아서 내가 Page Table을 만들자!

각 프로세스마다 두, 세개의 엔트리만 존재하게 될 것 이다.

One page table entry for each page frame

• 각 페이지가 들어 있는 페이지 프레임 순으로 저장 해야 한다. → 실제 Physical memory 에 어느 Process에

내 프로그램의 몇번째 페이지가 어디에 있나를 저장하는 것이 아니라, 거꾸로 실제 Physical Memory에 0번 프레임에 어느 프로세스의 어느 페이지가 들어있나를 저장하는 것이다.

따라서 이 페이지 테이블은 Page table의 k번째 entry에는 k번째 page frame에 저장된 프로세스와 page에 대한 정보가 저장된다.

페이지 테이블 요소가 포함하는 것

Each entry in the page table includes:

1. Page number

2. Process identifier

the process that owns this page.

어떤 프로세스인지 알아야 한다. 여러 프로세스가 존재할 수 있기 때문

• 1번 프로세스의 0번 페이지
• 100번 프로세스의 0번 페이지
• ...

3. Control bits

includes flags, such as valid, referenced, etc

4. Chain pointer

the index value of the next entry in the chain.

없어도 되긴 하는데, 없으면 내가 원하는 페이지를 찾는데 굉장히 오래 걸린다.

내가 원하는 페이지가 어느 프레임에 있는지 최대한 빠르게 찾기 위해서 사용된다.

Hashing Function

• Page number portion of a virtual address is mapped into a hash value
• Hash value points to inverted page table
• Fixed proportion of real memory is required for the tables regardless of the number of processes

Inverted Page Table Structure

Hash Function Input

페이지 번호 필요

Hash Function Output

10으로 나눈 나머지 X

10으로 나눈 나머지가 같은 애들끼리 링크로 연결되어 있을 때, 각 링크의 시작점 O
⇒ 나머지가 3인 링크의 시작점이 몇번 Frame 에 있는지 알려준다.

ex) 나머지가 3인 링크의 시작점, 나머지가 1인 링크의 시작점, 나머지가 5인 링크의 시작점, ...

0번 엔트리에는 실제 physical memory frame 0번에 어떤 프로세스의 어떤 페이지가 들어 있는지 정보가 들어 있다.

for문을 돌리며, x[i].page#와 x[i].ID 가 인풋값과 일치하는 프로세스를 찾는다.

Chain

Chain 이 없으면 2^m 번 메모리(메모리 전체)를 읽어야 한다.
메모리 3번 읽기 → 내 데이터 읽기

장점

Page Table 의 크기가 작다.

two-hierarchy
→ Page Table 의 크기 = 4Gbyte
→ 2단계 Page Table의 크기 = 4Mbyte
↑ 이게 프로세스 하나당 존재

Inverted Page Table
한 Entry 크기, Entry 개수 ⇒ Inverted Page Table 계산 가능 ⇒ 메모리에 있을 확률 ↑

단점

최악의 경우, 메모리 안에 들어 있는 페이지의 나머지가 모두 3인 경우, 결국 전체를 훑어야하기 때문에 시간 소요가 커지게 된다.

위의 그림은 16개의 페이지 프레임을 가지는 메모리이다.

각각의 Inverted Page Table 에는 페이지#, 프로세스#, Chain Pointer 가 존재한다.

Chain Pointer 에는 다음 Chain Pointer가 존재하는 다음번 엔트리의 위치가 들어있다.

Paging System

Paging System 은 프로그램을 Page 크기로 나누는 것이다.
주소를 붙일 때 주소는 논리주소가 되는데, Page# + Offset 과 같이 표현한다.

Relocation

Relocation → Page Table 을 사용한다.

Page Table 에서 1번이면, 페이지 1번라는 뜻이고,
이 1번 페이지가 페이지 프레임 몇번에 들어있는지 하는 프레임 번호를 얻어온다. 
얻은 프레임 번호를 앞쪽에 적고, 뒤에는 offset을 그대도 사용한다.
프레임번호 + offset ⇒ Physical Address 가 된다.

Paging System 에서 알아야 하는 것

• 가상주소 적는 방법
• Physical Address 로 변환하는 방법
• 계산하는 과정

Protection

Memory 를 이용하려면 Relocation 과 Protection 이 완벽하게 해결이 되어야 한다.

프로그램이 페이지가 3개라, 위의 그림에서 진한 파랑색 부분이 프로그램이 사용중인 프레임인데, Protection 이 지켜지려면 자신에게 할당된 프레임 부분의 주소만 사용해야 한다.

자신에게 할당된 프레임 안에 있는 데이터나 코드는 사용할 수 있지만, 다른 사람에게 할당된 것은 사용해서는 안된다.

Offset

일단, 10bit offset 은 신경 쓸 필요가 없다.
10 bit offset 을 이용해서 내 페이지를 벗어나는 데이터를 access 할 수 있는 방법은 없다.
한 페이지 안에 10bit로, 1024줄이 존재한다. → 10 bit 를 벗어날 수는 없다.

10bit 는 한 페이지 안에 있는 코드나 데이터만 access 할 수 있는 비트이다. 이 페이지를 벗어나는 비트를 10bit로는 access 할 수 없다.

⇒ 따라서 어차피 offset은 10bit 범위를 벗어나는 숫자를 만들 수 없으므로, offset 의 범위는 신경쓰지 않아도 된다.

Page Number

Page가 0번 1번 2번 페이지까지만 있다고 할 때, 3번 페이지라는 말을 하면, 문제가 될 수 있다. 3번 위치에 적혀있는 프레임이 내 프레임이 아니라 다른 사람 프레임일 수 있다.

페이지 번호 <= 페이지 테이블 길이 만 확인하면 된다.

크기 계산

• 이 시스템에서 프로그램의 최대크기무엇일까?
• 한 페이지의 크기는 몇일까?
• 한 프로그램은 최대 몇개까지의 페이지를 가지고 있을 수 있을까?
• 메모리의 크기는 얼마일까?

000

위에서는 3bit로만 주소를 표현할 수 있다.
3bit 이므로 000 ~ 111 까지 8(2^3)개의 주소를 표현할 수 있다.
⇒ 8개의 주소를 표현할 수 있다. ⇒ 크기가 8인 메모리까지 주소 표현이 가능하다.

2bit 10진수로 주소를 표현하는 경우, 0~99 까지 주소를 표현할 수 있다.
⇒ 2bit 를 사용하면 100번지를 표현할 수 없기 때문에 메모리 크기가 100을 넘어 갈 수 없다.

크기 들을 얘기할 때는 주소를 어디까지 붙일 수 있는지 만 확인하면 된다.
↳ 주소를 어디까지 붙일 수 있는지 는 bit 수로 확인할 수 있다.

Logical Address (프로그램의 최대 크기)

프로그램의 Logical Address 를 표현하는데 16bit 를 사용한다. 프로그램의 최대 크기는 2^16 byte 이다. 그것보다 넘어가는 크기는 주소 표현을 할 수 없기 때문에 사용할 수 없다.

Physical Address (메모리 크기)

Physical Address 는 16bit 를 사용한다. Physical Address 는 Memory 의 실제 주소이므로 이 시스템의 메모리 크기는 2^16 byte 이다.
16 bit 의 Physical Address 를 사용하고 있기 때문에 2^16 크기가 넘어가는 메모리의 어떤 공간은 주소를 붙일 수 없다.

offset (한 페이지의 크기, 페이지 번호의 크기)

offset 은 10 bit 이다. 즉, 한 페이지의 크기는 2^10 이다.

전체 주소가 16 bit 인데, 그 중 10 bit가 offset 이므로 나머지 6 bit 가 페이지 번호를 표현하는 부분이다.

따라서 페이지 번호는 6bit 이므로 페이지 숫자는 최대 2^6개까지 페이지가 존재할 수 있다. 그 이상의 페이지는 표현할 수 없다.

Segmentation

Segmentation 을 사용해야 하는 이유?

페이징 시스템은 메모리를 동일한 크기의 프레임 으로 나누어서 페이지 프레임 크기에 맞추어서 프로세스를 자른다.
⇒ 이렇게 여러 페이지를 만들어 낸다.

그러다보면, 프로세스이므로 위에서 부터 페이지 크기로 잘라내어 가니까 어떤 페이지 안에는 반은 PCB, 반은 Program 코드가 들어갈 수 있다. 또 어떤 페이지 안에는 반은 Program 코드, 반은 Data 가 들어가게 된다.

PCB 는 OS 가 접근하는 영역이므로 Code 가 접근할 수 없다.
relative address 는 프로세스의 시작 주소가 아닌, 프로그램의 시작 주소를 기준으로 Base Register 에 둔다.
⇒ 이 얘기는, 이 프로그램에서 사용하는 relative address 로는 PCB 영역을 접근할 수 없다는 의미이다.

그런데 이걸 Page 단위로 다르게 되면 하나의 페이지에 PCB와 CODE 가 같이 있게 되면, 고민이 되게 된다. 이 페이지를 User 가 access 할 수 있게 해야하는지? 없게 해야할지?

프로그램 코드와 데이터가 같이 들어 있는 페이지에서는 Code 는 Share 하고 Data 는 Share 하지 않는 경우가 많기 때문에 어떻게 접근해야할지 고민해야 한다.

Segmentation Logical Address

같은 크기로 나누는 것이 아니라, 의미 있는 크기로 나누어야 한다.

프로그램을 나눌 때

• PCB → 하나의 Segment
• Program Code → 하나의 Segment
• Data → 하나의 Segment
• Stack → 하나의 Segment

⇒ 의미 있는 크기로 나누었기 때문에 Protection 과 Sharing 이 쉬워진다.
↳ 길이는 제각각이지만, 논리주소를 사용하므로 최대 길이 가 필요하다. (논리주소를 사용하기 위해서는 Offset 의 bit 수, Segment 번호의 bit 수가 정해져 있어야 한다.)

• 첫번째 segment 는 크기가 750 byte
• 두번째 segment 는 크기가 1950 byte

우리가 관심 있는 건 1502의 코드인지 데이터 인지를 segment 시스템에서 표현하면, 1502 - 750 = 752 offset 이 나오게 된다.

Relative Address 를 Paging 에서 사용하는 Logical Address 로 바꿀 때는 이진수가 그대로였지만(page 를 자른다는게 bit 를 오른쪽 왼쪽으로 움직이는 것이라서), Segmentation 에서 사용하는 Logical Address 로 바꿀 때는 이진수가 변하는 것(빼야하기 때문에)을 확인할 수 있다.

Segmentation

• All segments of all programs do not have to be of the same length
• There is a maximum segment length
• Addressing consist of two parts - a segment number
  and an offset
• Since segments are not equal, segmentation is similar to dynamic partitioning

• 모든 segment 의 길이는 다르다.
• 최대 길이의 segment 가 존재한다.
• Addressing 작업에는 segment number 와 offset 이 포함된다.
• segment 의 길이가 다르기 때문에, segmentation 은 dynamic partitioning 기법을 사용해야 한다.
  → paging 을 할 수 없기 때문이다. 하지만, 여기서는 연속되게 들어가지 않아도 된다.

내가 어떤 segment 를 메모리에 넣으려면, 그만큼 공간을 달라고 해야한다. 필요한 공간을 dynamic partitioning 기법으로 할당을 받아야 한다.

앞에서의 dynamic partitioning 은 프로그램 전체가 연속된 공간에 들어가야 했었다.
⇒ 공간이 있어도 연속되지 않으면 프로그램이 들어갈 수가 없어 External Fragment 가 발생했었다.

그런데 여기서는 segment들이 메모리의 연속된 공간에 들어가지 않아도 된다. 여기저기 빈칸이 있다면 segment들을 집어 넣기만 하면 된다.
⇒ External Fragment가 큰 문제가 안될 수 있다.

Relocation 과 Protection

연속된 공간에 넣는다고 가정했을 때는, Base Register와 Bound Register 를 사용했다.

그런데, 연속되지 않은 segment 들이 여러개이므로, 각각의 segment 들이 memory 여기저기에 할당이 되어 있다. 각 segment 마다 base register 값과 bound register 값이 필요하다. 그래야지만 relocation과 protection 을 할 수 있다.

ex) segment가 3개라면 각 segment 의 시작점을 가지고 있는 base 값과 
각 segment 의 길이 (마지막 지점을 나타냄) 를 가지고 있는 bound 값, 
⇒ 이렇게 한 세트씩 3세트가 필요하다.

Register 에 저장하기에는 Register 가 충분하지 않으므로 테이블에 저장할 것이다.

Segment Table

Relocation 을 위한 Base
Segment Table 은 Segment 마다 0번 Segment, 1번 Segment, ... 각각의 Segment 가 실제 메모리 안에 Physical Address 로 몇 번지에 저장되어 있나 하는 시작점 위치를 Base 값에 저장한다.

Segment Table 의 Base 값에는 각 Segment 의 시작 위치 가 적혀있다. 각 Segment 의 시작 위치라는 것은 Offset 0 이 어디에 있는지를 나타내는 것이므로, 이 시작위치에 Offset 값을 더하면, 실제 Physical Address 가 나오게 된다.

Base 에 있는 것은 Offset 0인 문장의 위치

⇒ Relocation 할 때는 Offset + Base 실제 Physical Address 를 만든다. (덧셈)

Protection 을 위한 Length
Length 는 나한테 할당된 공간을 넘어가는 지를 보는 것이기 때문에
이 Length 값은 Base + Length = 내가 차지하는 공간의 마지막 지점 이라는 뜻이다.
거기를 넘어가면 다른 사람의 코드라는 의미이다.

⇒ 따라서 offset 과 length 를 비교 한다.
비교해서 offset 이 length 보다 작거나 같으면 안전한거지만, 그렇지 않으면 프로그램을 종료해야 한다.

Relocation

Offset + Base = Physical Address

Protection

Offset <= length

Q.

• segment → 4 bit 사용
  ⇒ 한 프로그램 당 최대 몇개의 segment 를 가질 수 있는가? → 2^4
• offset → 12 bit 사용
  ⇒ segment 의 최대 크기 → 2^12
• 전체 logical address → 16 bit 사용
  ⇒ 이 시스템에서 프로그램의 최대 크기? → 2^16
• Physical Address 를 16 bit 사용
  ⇒ 메모리 크기 → 2^16

Q. segment table 한 entry 의 길이?

한 entry(원소) 안에는 Length 값과 Base 값을 가지고 있다.

Base 값은 이 segement가 physical address 몇번지에서 시작되는지를 나타내기 때문에 physical address 이다.
physical address 가 16bit 이므로 Base 값은 16bit 를 사용한다.

Length 는 하나의 Segment 의 최대길이를 넘어가지 않아야 하는데, Segment 최대 길이는 12bit 이므로 length 도 12bit 이다.

⇒ segment table 한 entry 의 길이는
Base 의 길이 + Length 의 길이
= Physical Address 의 길이 + Segment 의 길이
= 16 + 12 = 28 bit

Memory Management

• Subdividing memory to accommodate multiple processes
• Memory needs to be allocated efficiently to pack as many processes into memory as possible

우리가 사용하고 있는 메모리 시스템은 프로그램 전체를 통으로 집어넣을 수 없다.
메모리 크기에 비해 프로그램의 크기가 굉장히 큰 것도 있고, 동시에 여러 프로그램들을 실행시키고 싶어서 가능한 많은 프로그램을 메모리에 올려 놓으려는 측면도 있다. 그러다보니 프로그램의 일부만 메모리에 올라와서 실행을 하게 되는 시스템이 구현되었다. 이를 Virtual Memory System 이라고 한다.

Virtual Memory System 은 8장에서 조금 더 자세히 배우고 7장은 그 이전 단계를 배우게 된다.

이 때는 프로그램 전체를 메모리에 다 집어 넣었다.
프로그램이 실행을 하려면, 프로그램 전체가 메모리에 들어 있어야만 실행이 되는 상태인 것이다.
이러한 시스템을 Real Memory System 이라고 한다.

Real Memory System 에서 메모리 관리를 어떻게 하는지에 대해 알아보도록 하자.

한번에 한 프로세스만 메모리에 들어가는 것이 아니기 때문에 여러 프로세스들이 메모리에 들어 있어야 한다.

메모리를 잘 나누어서 여러 프로세스들을 메모리에 넣고 동시에 여러 프로세스들을 실행시키고 싶은데,
이때 가능한 많은 프로세스가 메모리에 들어가면 좋을 것이다.

메모리 공간을 잘 나눠서 최대로 많은 프로세스들을 메모리에 집어 넣고 실행을 시키고자 하는 것이 목적이다.

Memory Management Requirements

프로세스 여러개를 메모리에 집어 넣을 때, 해결되어야만 하는 아주 중요한 문제가 존재한다.

1. 🌟 Relocation 🌟

프로그램은 PCB, Data, Stack으로 이루어져 있다.

Jump O

Jump 명령: 코드를 순차적으로 실행하다가 어느 지점으로 이동해서 실행하는 명령

프로그램 코드를 보면, 굉장히 많은 Jump 명령들이 존재 → Jump + 몇번지

• A 함수 호출 → A 함수로 Jump
• if 문의 조건에 맞지 않아 else로 이동 → Jump
• 반복문: 처음으로 돌아가기 → Jump

Jump X

Jump 하지 않는 애들 → Data 읽기

⇒ 프로그램 코드는 대부분 뒷 부분에 주소가 존재한다.

프로그램을 Compile 할 때는, 이 프로그램이 메모리 어디 들어가는지 알 수 없다.
⇒ 실제 코드하나하나 데이터 하나하나가 메모리 몇 번지에 있는지 알 수 없기 때문에, 그냥 간단하게 0번지를 기준으로 Compile 한다.

Compile실제 Memory 번지

ex) 100번지에 있는 데이터를 가져와라 라고 하는 명령어
	⇒ 3100번지에 있는 데이터를 가져와라 라는 명령어로 바뀌어야 한다.

일단 Compile 을 해둔 다음, 메모리 몇번지에 들어갈지 확정이 된 다음, 주소를 다 바꿀 수는 없고,
그렇게 되면 프로그램이 메모리에 들어갈 때 시간이 어마어마하게 많이 걸린다.
⇒ 간단하게 주소를 바꿀 수 있는 방법이 필요하다.

위와 같이 주소를 다 바꿀 수는 없다. → 시간 소요가 많다.
⇒ Rellocation (재배치) 를 이용한다.

Rellocation : 프로그램 안에 있는 주소 값들을 실제 주소에 맞게 전부 다시 재배치하는 과정이다.

2. 🌟 Protection 🌟

프로그램이 메모리에 들어 있을때,
이 프로그램은 1000번지 ~ 1050번지에 들어 있다.

당연히 여기 있는 모든 주소들은 1000~1050번지까지의 코드나 데이터를 access 하는 주소여야 한다.

그런데 갑자기 900번지에 있는 데이터를 가져와라 라는 코드가 튀어나오거나,
2000번지에 있는 코드로Jump 해라 라는 코드가 튀어나오면,
뭔가 잘못된 것이다.

→ 이 경우에는 프로그램을 실행시킬 수 없다.

Protection : 각 프로세스에 할당된 메모리 영역 이내에서만 데이터나 코드를 access 하는지 확인하는 과정이다.

Protection 이 지켜지지 않으면 프로그램을 종료해야 한다.

3. Sharing

서로 다른 프로세스가 공통으로 어떤 메모리 영역을 access 해야하는 경우가 있는데, 이를 시스템이 지원해주어야 한다.

앞으로 얘기할 것

1. 메모리 어떻게 잘 잘라서 최대한 많은 프로세스 메모리에 집어 넣고 실행을 시킬 수 있을까?
2. 메모리를 잘라서 실행을 시키는 과정에서 🌟 Relocation , Protection 을 어떻게 할 것인가?
   → 이 두 문제가 해결이 안되면, 프로그램을 실행시킬 수 없다.

Partitioning

Fixed Partitioning

고정된 크기로 메모리를 아예 잘라놓고 시작한다.

좋은점: 메모리를 딱 n등분 했을 때 → 각 Partion의 시작점이 이미 정해져있다.
⇒ Relocation 작업이 따로 필요하지 않다. / Relocation 작업이 간단하다.

나쁜점: 공간의 크기를 맞추기 어렵다. 프로세스의 크기가 메모리 공간의 크기에 맞는지 안맞는지 알기 어렵기 때문에 공간의 낭비 가 생길 수 있다.

ex) 프로그램을 Compile 할 때, 
1000번지에 들어가서 실행하고 싶으면, 1000번지 기준으로 Compile 하면 된다. 
3000번지에 들어가서 실행하고 싶으면, 3000번지 기준으로 Compile 하면 된다. 

Equal-size partitions

• 같은 크기로 자르기
• 문제점
  1. Partition 보다 큰 프로그램 크기 → 실행 불가
  2. Partition 보다 작은 프로그램 → 실행 불가
     ↳ 우리의 목표는 최대한 많은 프로그램을 동시에 실행시키는 것이기에,
     남은 빈공간을 이용해서 다른 프로그램을 실행을 시키고 싶은데,
     이 시스템에서는 Fixed Partitioning 이라 Compile 을 할 때부터, 각 Partition 의 시작점에 맞춰서 하기 때문에 빈공간을 이용할 수 없다.

Unequal-size partitions

• 다양한 크기로 자르기
• 컴파일할 때 크기 확인
  (Compile을 할 때, 내 프로세스의 크기가 8M라 8M 메모리에 들어가면 되겠다 싶으면, 8M Partition에 맞춰서 Compile 하면 된다.)
• 메모리 공간 낭비가 덜하진 않다.
  → 반 이상 낭비될 수 있다.
  ↳ 특정 크기의 프로세스의 수요가 많아 특정 크기의 메모리 공간은 대기하는 프로세스가 많지만, 수요가 적은 크기의 메모리 공간은 이용되지 않고 낭비될 수 있다.

⇒ Equal-size Fixed Partitioning 보다 낫다고 할 수 없다.

Dynamic Partitioning

메모리 크기가 고정된 Partition X → 프로그램의 크기만큼 메모리를 자른다.

External fragmentation problem

External fragmentation : 프로세스와 프로세스의 사이

Dynamic Partitionin 의 가장 큰 문제점이다.

⇒ Can resolve using compaction

External fragmentation problem 을 해결하는 유일한 방법 : Compaction ⇒ 모든 프로세스들을 위로 올려 붙여서 공간을 확보한다.
↳ 전체 프로세스를 전부 다시 읽어서 다시 써야한다.
⇒ 시간이 어마어마하게 오래 걸린다.

↑ 위의 그림은 메모리가 효율적으로 사용되는 것처럼 보인다.
프로세스와 프로세스 사이에 공간이 하나도 없다.

↑ 하지만, 프로세스가 작업을 끝내거나, Swap Out이 된다면, 프로세스는 메모리 바깥으로 나가게 된다.

이렇게 되면, 메모리안에 프로세스와 프로세스 사이에 사용할 수 없는 빈 공간 (짜투리 공간) 이 생기게 된다.

이 빈 공간을 합치면 프로세스 다시 실행시킬 수 있지만, 떨어져 있는 각각의 짜투리 공간으로는 프로세스를 실행시키지 못하고 공간이 낭비되게 된다.

Dynamic Partitioning Placement Algorithm

프로세스를 어느 공간에 배치할까? → Compaction 횟수랑 관련이 있다.

Operating system must decide which free block to allocate to a process

• Best-fit
• First-fit
• Next-fit
• Worst-fit

가능한 Dynamic Partitioning 을 사용하면서, 가능한 Compaction 횟수를 줄여야 한다.

Free Block : 메모리의 빈 공간

Best-fit

• 전체를 탐색 O
  ⇒ 서치 시간이 증가한다.
• External fragmentation 가 적어 Compaction이 적은 공간을 찾아 프로세스에게 공간을 할당한다.
• Free Block 이 너무 많으면, 전체 Free Block 전부를 검색하기엔 시간이 너무 오래 걸린다.

ex) 새로운 프로그램 16M 를 어디에 배치해야 External fragmentation 가 적어, 
Compaction이 적게 할 수 있을까?

프로세스의 크기인 16M와 제일 가까운 18M에 16M 프로세스를 집어 넣는다. 
⇒ 2M가 남는다.
⇒ External fragmentation 최소

First-fit

• 전체 탐색 X
  ⇒ Free Block 전체를 서치할 시간에 Compact 를 더 하자
• 처음부터 탐색: 위에서부터 프로세스 크기에 맞게 할당 가능한 첫 번째 공간 찾기
  → 항상 앞에서부터 할당하므로, 앞쪽은 굉장히 작은 짜투리 공간만 남아 있을 것
  ⇒ 앞쪽은 프로세스를 할당할 수 없는 경우가 많아 밑으로 한참내려가야 한다.

Next-fit

• 전체 탐색 X
  ⇒ Free Block 전체를 서치할 시간에 Compact 를 더 하자
• 마지막으로 allocation 한 부분 이후부터 탐색한다.
  ⇒ 뒤쪽에 훨씬 더 큰 공간이 남아 있을 수 있다.
• first-fit 보다 좋다.

Worst-fit

• 제일 안맞는 공간을 찾는 것 : 내 프로그램이 메모리에 들어가고 제일 빈 공간이 큰 곳을 찾는다.
• 내 프로그램 → 빈 공간
  ⇒ 남아 있는 공간 중 제일 큰 공간 을 할당한다.
  ⇒ 제일 External fragmentation 가 크다.
• 사용하는 이유: 제일 큰 공간이기 때문에 여러 프로세스가 들어갈 수 있다.

Buddy System

Dynamic Partition과 Fixed Partition 의 단점을 피한 시스템

• Entire space available is treated as a single block of 2^U
• If a request of size s such that 2^(U-1) < s <= 2^U, entire block is allocated
  • Otherwise block is split into two equal buddies
  • Process continues until smallest block greater than or equal to s is generated

어떤 크기의 메모리가 필요할 때
→ 그 크기의 메모리를 나눠주는 것 X
→ 그 크기보다 큰 2^U 공간을 할당해준다.

알아야 할 것
1. 할당 받는 공간의 크기를 알아야 한다.
2. 이 공간을 아무렇게 떼어 주는 게 아니라, 항상 메모리를 반씩 나누어 나한테 할당해 줄 수 있는 크기만큼 잘라졌을 때, 그 공간을 할당해준다.

	ex) 10k 의 공간이 필요할 때 → 16k를 할당해준다.
    8k <= 10k <= 16k

• External fragmentation X
• Compaction X
• 단, Internal Fragmentation O

100k 보다 큰 2^u 값 = 2^7 = 128

100k 크기의 프로세스를 메모리에 할당
→ 메모리 1M 를 반으로 나누면 512k, 512k buddy가 만들어지는데, 여전히 100k 보다 크므로 두개 중 하나만 다시 반으로 나눈다.
→ 512k 를 반으로 나누어 256k, 256k Buddy 가 만들어지는데 아직 100k 보다 크므로 이를 다시 반으로 나눈다.
→ 64k, 64k Buddy 가 만들어지는데 이는 100k 보다 작으므로 100k 프로세스는 128k 공간에 할당된다.
→ 이렇게 되면, 28k 가 남게되어 Internal Fragmentation 이 발생하게 된다.

→ 프로세스에게 메모리 공간을 할당하고 프로세스가 종료하고 나면,
Buddy 끼리 다시 합친다.
→ 큰 공간으로 가지고 있는다.
↳ 이 공간을 최대한 크게 가지고 있어야 크기가 큰 프로그램도 실행시킬 수 있기 때문이다.
→ 공간을 합칠 때는, 같은 Buddy끼리만 합칠 수 있고, 다른 Buddy 끼리는 합칠 수 없다.

Fixed Partition 의 단점 극복: 공간이 최대 메모리의 크기랑 같은 프로그램의 크기 실행시킬 수 있다. Fixed Partition은 고정된 Partition으로 나누어 놨기 때문에 프로그램의 크기가 최대 Partition의 크기보다 크면 실행을 할 수 없다.
→ 여기서는 전체 메모리 크기도 사용하여 프로그램을 실행시킬 수 있다.
⇒ Fixed Partition 의 크기 제한이 없다: 프로그램 크기와 상관 없이 모든 프로그램을 실행시킬 수 있다.

메모리를 자르고 다시 합치는 과정에서 External Fragmentation 이 존재하지 않는다. Partition 과 Partition 사이에 뭔가 남아있는 것이 없고, Compaction 을 하지 않는다.
단, Internal Fragment 가 존재한다.

Internal Fragment

Partition 과 Partition 사이의 공간이 아니라 나에게 주어진 Partition 내부의 공간 이 남는 것

Internal Fragment 는 나에게 할당된 공간의 반을 넘어갈 수 없다.
적어도 반보다 작다.
→ 만약, 내게 할당된 공간의 반보다 더 작은 프로그램이었으면 한번 더 반으로 잘랐을 것이다.

Address

• 메모리를 어떻게 나누지?
• 어느 공간으로 들어가지?

Fixed Partition 내가 어느 공간으로 들어갈지 미리 정하면, Compile 할 때, 아예 그 공간에 맞춰서 Compile 하기 때문에 Relocation이 필요없다.

그러나, 같은 크기의 Partition 은 내가 Compile 할 때 Fix 해 놓으면, 그쪽 줄에 서 있는 프로세스가 많으면, 다른 곳에 공간이 있어도 실행을 할 수 없다.
⇒ Fix 를 안해 놓는 것이 좋다.

UnEqual Size Partition 같은 경우도, 내가 8M 크기에 맞추어 딱 Compile을 해 놓았는데, 8M 크기의 공간에는 자리가 없고, 그보다 큰 12M 쪽은 자리가 있을 겨우, 큰 공간에 가서 실행을 할 수도 있지만 미리 fix 해 놔서 이용할 수 없다.
⇒ 따라서 Compile 할 때 Relocation 을 미리 해 두는 것은 좋지 않다.

이런 경우 어떻게 Relocation 을 할 수 있을까?
↳ Base Register와 Bound Register 를 이용한다.

↓ 밑에와 같은 경우에 Base Register와 Bound Register 를 사용할 수 있다.

• Fixed Partition 을 사용하는데, Compile 할 때 Relocation 을 미리하지 않은 경우
• Dynamic Partition 과 Buddy System 의 경우
  (이 두 시스템은 어차피 내 프로그램이 어디에 들어갈지 알 수 없기 때문에 미리 Compile 을 해둘 수 없다. )

Logical Address

• reference to a memory location independent of the
  current assignment of data to memory
• translation must be made to the physical address

실제 위치랑 상관 없이, 어떠한 논리적인 방법으로 주소를 표현하는 것

Paging System 에서는 Logical Address 를 사용해서 주소를 표현한다.
→ 페이지 번호 와 offset 으로 표현한다.

offset : Page 안에서 몇번째 줄에 있는지를 나타낸다. (줄은 0번부터 시작)

몇번째 Page 의 몇번째 줄(Offset)에 있다고 표현하는 것이다.

↳ 1번 페이지의 476번째 줄에 있다는 것을 의미한다.

Relative Address

address expressed as a location relative to some
known point

0번지 기준으로 계산한 번지이다.

특정 번지를 기준으로 컴파일 한다.
→ 대부분 0번지 기준으로 컴파일 한다.

프로그램이 메모리 어디에 들어갈지 알 수 없는 상황이기 때문에 0번지에 들어간다고 가정하고 Compile 을 한다.

실제 프로그램 안에는 모든 주소가 relative address 로 되어 있다

Physical Address

the absolute address or actual location in main memory

실제주소를 나타낸다.
⇒ 진짜 메모리 몇번지에 데이터나 코드가 있는지?

Relocation = Relative Address → Physical Address

Registers Used during Execution

Hardware Suport for Relocation

Base Register

Relocation 은 Base Register 를 사용한다.

Base Register : 프로그램은 PCB + Data + Stack 으로 이루어져 있는데, Base Register 안에는 프로그램 코드의 메모리 (physical) 시작 주소가 적혀 있다.

프로그램 코드의 시작 주소 이지, 프로세스 코드의 시작 주소가 아니다! 프로세스의 시작 주소는 오른쪽 main memory 의 제일 윗 부분 (PCB 의 시작부분) 이다.

프로그램은 PCB 밑에부터 들어가게 된다.
0번지를 기준으로 Compile을 하면 PCB 밑에 부분의 번지를 0번지라고 생각하고 Compile 하는 것이다. 즉, 이 프로그램 앞에 PCB가 붙을 것을 생각하지 않고, 내가 출발지라고 생각하고 0번지로 Compile 한다.

이 프로그램 Code와 Data의 모든 주소는 Program의 시작점에 맞춰져 있다.
⇒ Base Register 의 값은, 프로그램 코드의 시작 주소이다.

만약, 이 프로세스의 프로그램 코드가 3000번지에 적재가 됐다고 가정한다면, 
Base Register에 3000이 들어가야 한다.

Relocation 작업

명령어를 IR 로 가져온다.
명령어 분석 → 앞쪽에 Operation Code, 뒷쪽에 주소 O

만약 jump|200 으로 적혀 있다면, 실제로는 3200번지로 이동해야 한다.
200은 Relative Address 를 가르킨다.
⇒ 3200 번지가 실제 데이터가 있는 위치이다.

⇒ Base Register + Relative Address
= 프로그램 코드의 시작 주소 + IR 의 뒷부분의 주소 부분
= Physical Register
⇒ 실제 Data 가 위치하는 주소

Protection 작업

이 프로그램 코드는 3000~5000 번지 사이에 들어 있다.
⇒ 당연하게도 이 프로그램 안에서 사용하는 모든 주소(Physical Address)는 3000~5000 사이여야 한다.

1000 번지나 5000번지를 가져오라고 하면, 이 프로세스에게 할당된 코드의 범위를 넘어 남의 코드를 가져오는 것이므로, 프로그램을 중단 시켜야 한다.

→ 이를 확인하는 방법: Bound Register

Bound Register

Bound Register : 프로그램 코드의 제일 마지막 부분의 주소를 넣어둔다.
Physical Address <= Bound Register 인지 비교한다.

• 만약 Physical Address <= Bound Register → 내 프로그램 영역
  ⇒ 점프하거나 데이터를 가져오면 된다.
• 만약 Physical Address > Bound Register
  ⇒ 프로그램 인터럽트가 걸리게 된다.

Physical Address = Base Regiser 에 Relatice Address 를 더한 값

Q. 이 시스템에서는 프로세스가 100개가 동시에 실행이 되고 있다. 메모리 안에 프로그램이 100개가 들어 있다. Base Register와 BoundRegister가 몇개씩 필요할까?

100개 X 1개 O

주소를 변환하는 과정(Relocation)은 실행하면서 하는 것이다.
⇒ 즉, 실행을 할때만 Base Register와 BoundRegister가 필요하다는 뜻이다.
⇒ CPU 가 하나이면, 시스템 안에 프로세스가 몇개가 있든 상관 없이, 딱 한 명만 실행한다.
⇒ BaseRegister와 BoundRegister는 하나씩만 있으면 된다.
→ 실행을 시작할 때 BaseRegister와 BoundRegister 값을 세팅한다.

ex) A Program 실행 → B Program 실행 
	⇒ BaseRegister와 BoundRegister 값이 새로 세팅된다.

필요한 가정

프로그램을 메모리에 집어 넣을 때, 이 프로그램을 자를 수가 없다.
⇒ BaseRegister와 BoundRegister로 Relocation과 Protection을 하는 것은 프로세스가 연속된 공간에 할당된다 는 가정이 필요하다.

↓ 모두 프로그램을 연속된 공간에 할당하는 시스템들이다.

• Compile 할 때 Relocation 을 미리하지 않은Fixed Partition
• Dynamic Partition
• Buddy System

단점

• 공간 낭비가 존재한다.
  (공간 낭비가 적은 Buddy System 도 최악의 경우 프로그램이 2^u +1 의 크기를 갖으면, 공간 낭비가 심해지게 된다.)
• 실제 위치와 상관이 없다.

Paging System

메모리와 프로그램을 잘라서 사용하는 시스템

• Partition memory into small equal-size chunks and divide each process into the same size chunks
• The chunks of a process are called pages and chunks of memory are called frames
• Operating system maintains a page table for each process
  • contains the frame location for each page in the process
  • memory address consist of a page number and offset within the page

우리의 목표는 메모리에 최대한 빈큼 없이 최대한 많은 프로그램을 넣는 것이다!

그러므로 프로그램을 자르자!
↳ 프로그램을 자르려면 어떤 크기로 잘라야 하는지 기준이 있어야 한다.

Page Frame

먼저 메모리를 잘라야 한다.
메모리를 같은 크기로 자를거고, 이 잘라놓은 한조각 한조각을 Page Frame 이라고 한다.

Page

프로그램도 Page Frame 크기에 맞추어 잘라야 한다.

프로그램을 자른 한 조각을 Page 라고 한다.

⇒ Page Frame 안에 Page 를 집어 넣는다.

Assignment of Process Pages to Free Frames

↑ 위의 그림은 전체 메모리와 프로그램을 15조각으로 나눈 것이다.

• A 프로그램은 4Page 이므로 4Page Frame 을 차지하게 된다.
• B 프로그램은 3Page 이므로 3Page Frame 을 차지하게 된다.

• C 프로그램은 4Page 이므로 4Page Frame 을 차지하게 된다.
• B 프로그램은 Swap Out 하게 되어 3개의 free block 이 생기게 된다.
• D 프로그램은 5Page이다.
  → 만약 이 시스템이 Dynamic Partitioning 이었다면 D 프로그램은 실행시키지 못했을 것이다.
  ↳ D 프로그램은 4, 5, 6 Frame 에도 들어갈 수 없고, 11, 12, 13, 14 Frame 에도 들어갈 수 없다.
  → 이 시스템은 Paging System 이기 떄문에 D 프로그램은 실행이 가능하다.

Paging System 은 페이지들이 연속적이지 않은 공간에 들어가도 된다.
⇒ 최대한으로 공간을 사용한다.
⇒ External Fragment X ← Frame 크기 = Page 크기 이기 때문
⇒ Internal Fragment 는 1개 존재 가능
↳ 프로그램을 Page 크기로 나누는 것이기 때문에,
만약 프로그램이 Page의 배수가 아닌 경우 마지막 Page는 Frame 보다 조금 작을 수 있다.
⇒ Internal Fragment 가 존재할 수는 있지만, Internal Fragment 는 아래의 그림 처럼 ↓ 전체 프로그램 에 딱 한 Page 만 발생하게 된다.

정리

이 방식보다 더 메모리 공간을 낭비 없이 사용할 수 있는 방법은 없다.
Paging System 은 가장 완벽한 시스템이다.

• External Fragment X
• Compaction X
• Internal Fragment 있기는 하지만, 프로그램 중에 딱 1페이지만 있는 거기 때문에 무시할 수 있을 정도이다.

• Bound Register와 Base Register 사용불가 ← 연속적으로 프로그램이 메모리 공간에 할당되지 않기 때문이다.
  ⇒ Bound Register와 Base Register을 사용해서 Relocation, Protection 을 구현할 수 없다.

다른 방식으로 Relocation, Protection 을 해야 한다.
⇒ Page Table 을 사용한다.
↳ 각 프로세스마다 Page Table 이 존재한다.

Page Tables for Example

밑에와 ↓ 같은 것들을 Page Table 에 적을 것이다.

• 프로세스의 0번 Page 가 메모리 몇번 Frame 에 들어있나?
• 프로세스의 1번 Page 가 메모리 몇번 Frame에 들어있나?

프로세스 B 는 메모리에 없는 상태이다.

Free frame list : 사용하고 있지 않은 공간

Page# 와 Frame# 는 밑에와 ↓ 같이 2차원 배열이 아니라, 1차원 배열 을 이용해서 나타낸다.

• Page# → Index#
• Frame# → 배열[Page#]

→ X

Logical Address

(a) 는 Partitioning, Dynamic Sytem이든, Fixed 이든, Buddy System 이든, Relative address 를 사용한 것이다.
→ 화살표로 표시된 위차가 1502 번지이다.
⇒ 내가 1502 번지에 있는 데이터를 읽고 싶은 것이다.

(b) 는 Paging System에서 Logical Address로 표현한 것이다.

• 얘를 일정한 크기의 Page 로 잘랐다.
• 여기서는 Page 의 크기를 1K 로 가정했다.
  → 1K = 2^10 = 1024 (byte)
• 따라서 1502 번지는 Page1 의 478 번지(offset)가 된다.
  → 1502 - 1024 = 478 (byte)

즉, (a) → (b) 로의 변화는 별도의 계산이 따로 필요하지 않다.
추가로 아무것도 하지 않아도 된다.
→ 해석만 다르다.

이진수가 동일하다 → 주소: 몇번 페이지인지 알아야 한다.
→ 계산 방법: 내 주소 / 페이지 크기

Compile 을 할 때, Relative Address 를 이용하면 0번지를 기준으로 Compile 하면 된다.
그런데, Logical Address 를 사용하려면 Page 번호와 offset 으로 표현해야 한다.
Relative Address Compile 하던 Compiler 를 Logical Address 를 기준으로 Compile 하는 Compiler 로 바꾸려면, 어떤 계산을 추가로 해야할까?
⇒ 추가로 아무것도 안해도 된다.
⇒ 2진수는 동일하다. 내가 어떤 주소를 줬을 때 이게 어떤 페이지인지 알아야 한다. 몇 번 페이지인지 알려면, 내 주소를 페이지 크기로 나누어야 한다.

Paging

위의 예시에는 페이지 하나당 1K이므로, 1024줄 씩 존재한다.
위의 예시에서 Physical Address 에서

• frame# = 6
  (현재 frame 앞에 1024*6 줄의 코드가 존재한다. 6번째 frame 에 위치한다.)
• offset = 476

Logical Address 에서 Page 번호는 Process Page Table 을 통해 Page Frame 번호로 바뀌게 되고,
이렇게 얻게 된 Page Frame 번호와 Logical Address 에서 얻은 offset 으로 physical Address 를 얻는 relocation 작업을 진행한다.

내가 어떠한 Page Frame 으로 들어가든지, offset 의 변화는 없다.

2진수 계산

• 곱하기 2 → 왼쪽으로 한칸 움직인다.
• 나누기 2 → 오른쪽으로 한칸 움직인다.

⇒ 2^10 → 왼쪽으로 10칸 움직인 것
⇒ 6*2*10 = 000110 0000000000
⇒ + 478(offset) ⇒ 000110 0111011110 = Physical Address

Deadlock Avoidance Logic

시스템의 상태 설명
(global data structure)

• resource[m] : 원래 이 시스템 안에 자원이 각각 몇개씩 있는지?
• avaiavble[m] : 그 자원들 중, 할당 후 남아있는 자원?
• claim[n][m] : 모든 프로세스가, 나는 이 타입의 자원을 몇개까지(최대 동시 요청 가능) 요청할거다 라는 걸 미리 OS에게 미리 얘기해주는 것
• alloc[n][m] : 실제 각각의 프로세스들이 현재 가지고 있는 자원, 어떤 자원이 몇개인지?

Resource allocation algorithm

safe인지 unsafe인지 판단하기 전, 두 가지 조건이 존재한다.
→ 시스템이 safe인지 unsafe한지 판단할 필요도 없는 그런 상황을 말한다.

1. 첫 번째 if 문

if(alloc[i, *] + request[*] > claim[i, *])
	<error>;

프로세스가 현재 가지고 있는 값 + 프로세스가 자원 요청한 값 > 프로세스가 처음 OS에게 요청할거라고 말한 자원의 최대치
⇒ Error → 시스템 실행 불가, 프로그램 종료

* 은 모든 자원을 의미한다.

ex) 자원이 5개일 때, request[*] = [1 2 3 1 1]

alloc[i, *] +  request[*]  > claim[i, *]
[4 4 4 4 4] + [1 2 3 1 1 ] > [5 5 5 5 5]
⇒ Error

2. 두 번째 else-if 문

else if(request[*] > available[*])
	<suspend process>;

프로세스가 요청한 자원 값 > 현재 할당 가능한 자원의 개수
⇒ Suspend , 오류는 아님. 자원을 줄 수 없는 상태임.

3. 마지막 else 문

safe 인지, unsafe 인지를 결정한다.

먼저, 자원을 줬다고 가정한다.

새로운 상태 정의하기

alloc[i, *] = alloc[i, *] + request[*];  // request 만큼 자원을 할당
available[*] = available[*] - request[*]; // request 만큼 자원을 할당

이제 새로운 상태가 safe 인지, unsafe 인지를 결정한다.

• safe 할 경우
  → 자원 할당
• unsafe 할 경우
  → 원래의 상태로 환원시킨 후 프로세스를 Suspend 한다.

Deadlock Avoidance Logic(2)

test for safety algorithm
(banker's algorithm)

current available : 자원이 현재 몇개가 있는지? (임시 변수)

rest : 프로세스 집합

1. 모든 프로세스들을 전부 rest 에 넣는다.
2. 하나씩 뺀다. → deadlock 없이 무사히 종료시킬 수 있는, safe 하게 되는 애들
3. rest 공집합 O → 모든 애들이 safe
4. rest 공집합 X → 어떤 프로세스가 종료 불가, unsafe

코드 분석

current available 에 available 값을 복사해서 집어 넣기.
↓
rest에 모든 프로세스 집어 넣기.
↓
while문 돌기
↓
지금 현재 남아 있는 자원을 가지고(available 에 남은 자원을 가지고), 종료할 수 있는 프로세스가 있는지 살펴본다.
↓
Pk를 먼저 볼건데, 조건은 다음과 같다.
요청할 최대 자원 값 - 내가 현재 가지고 있는 자원 값
즉, 앞으로 더 요청할 값이 현재 할당가능한 자원보다 작거나 같은지?

claim[k, *] - alloc[k, *] <= currentavail;
//요청할 최대 자원 값 - 내가 현재 가지고 있는 자원 값 (앞으로 더 요청할 값) <= 현재 할당가능한 자원

자원이 할당 가능하면, Pk가 종료하게되고 Pk가 갖고 있던 자원을 모두 반납하게 될 것이다.

currentavail = currentavil + alloc [k, *];
// Process k가 갖고 있던 자원을 반납한다.

↓
rest 집합에서 Pk를 제외한다.

↓
while 문이 멈추는 때 는 두가지 경우가 있다.

1. 모든 프로세스가 다 빠져나가서 남아있는 프로세스가 없는 경우
2. 더 이상 종료할 수 있는 프로세스가 없는 경우

↓
while문을 빠져나오면 이제 rest 집합이 비었는지를 확인한다.

• rest 공집합 O → 모든 애들이 safe
• rest 공집합 X → 어떤 프로세스가 종료 불가, unsafe

Deadlock Avoidance Restrictions

• Maximum resource requirement must be stated in advance.
• There must be a fixed number of resources to allocate.

Banker's algorithm → Not optimal

1. 프로세스가 필요한 최대 자원 요청이 미리 말해져야 한다. (Compiler가 파악 가능하다.)
   • 이때 요청하는 자원은 동시에 필요한 자원이 아닐 수 있다.
   • 지속적으로 필요한 자원이 아닐 수도 있다.
   • 필요하지 않을 수도 있다.
2. Resource 개수가 정해져야 한다. (일정해야 한다.)
   • 자원의 개수가 늘어나는 것은 상관 없지만, 줄어들어선 안된다.

Deadlock Detection

Deadlock prevention strategies are very conservative;

• limit access to resources and impose restrictions on processes.

Deadlock detection strategies do the opposite

• Resource requests are granted whenever possible.
• Regularly check for deadlock

Deadlock prevention 이나 Deadlock avoidence 는 굉장히 많은 비용을 요구하는 방식이다.
⇒ 프로세스를 리스타트 시킨다든가, 자원을 줄 수 있는데도 주지 않는다든가, 시작을 지연 시키든가, ... ← 프로세스의 입장에서 불리하다.

↔ Deadlock detection 은 일단 자원을 달라고 하면 준다. (물론 자원이 있는 경우만!)
프로세스의 자원 요청 → 자원이 있으면(available) 할당
대신, 이렇게 요청하는대로 자원을 다 줘버리면 deadlock 이 발생할 수 밖에 없다.
⇒ 주기적으로 데드락을 감지할 것이다!

Deadlock 은 90% 이상 프로세스 두 개 사이에서 발생한다.

처음에는 두 프로세스 사이에서 Deadlock 이 발생했지만, 이 프로세스들이 가지고 있는 자원들을 요청한 다른 무고한 프로세스들이 block 되고, 또 프로세스가 가지고 있는 다른 자원을 요청한 프로세스가 block 되는 등의 시스템 전체가 block 되는 상황이 발생될 수 있다.
⇒ 따라서 처음 두 프로세스가 Deadlock 에 걸렸을 때, 재빨리 Deadlock 을 발견해 내어 시스템 전체가 멈추는 상황을 막는다!

A Common Detection Algorithm

필요한 것

Use a Allocation matrix and Available vector as previous

Allocation matrix : 원래 필요하다. 원래 OS가 해야하는 많은 일중에, 제일 중요한 일이 자원을 관리하는 일이다. 당연히, 어떤 자원을 어떤 프로세스에게 몇개 주었는지 잘 기록해놔야 한다. 즉, Allocation matrix 는 원래 필요한 것이다.

Available vector : 원래 필요하다. 자원이 몇개 남아있는지 OS가 모르면 안된다.

request matrix Q

request matrix : 각 프로세스들이 어떤 타입의 자원을 몇개 요청하는지?

요청을 했는데 할당 받지 못한 자원이 몇 개인지를 나타낸다.

아직 할당이 안된 자원만 해당 매트릭스에 씌여진다.
할당이 안된 이유?

• 다른 사람이 그 자원을 사용 중이기 때문에
• 자원이 있긴 있는데 OS가 다른일을 하느라 바빠서 자원을 할당해주지 못했기 때문에

Where Qij indicates that an amount of resource j is
requested by process i

Unmark

First ‘un-mark’ all processes that are not deadlocked

• Initially that is all processes

모든 프로세스들을 unmark 하고 프로세스들을 쫙 줄세우고 하나씩 mark 한다.

이 프로세스는 Deadlock이 아니다라고 확신할 수 있을 때 (0%) mark 한다.

• 모든 Process mark O → Safe
• 모든 Process mark X → Unsafe ⇒ Deadlock

Deadlock Detection

Request matrix : 각각의 프로세스들이 각각의 자원들을 몇 개씩 Request 했는데, 할당이 안된 자원의 개수

Allocation matrix : 각각의 프로세스들이 할당 받아 가지고 있는 자원의 수

Resource vector : 이 시스템에 있는 원래 자원의 수

Available vector : 할당 가능한 남은 자원의 수

Detection Algorithm

1. Mark each process that has a row in the Allocation matrix of all zeros.
   Allocation matrix 가 00000 인 프로세스를 mark 한다.
   ↳ P4 → Deadlock 이 아니라고 확신할 수 있는 이유?
   ↳ 앞의 Deadlock 이 걸리는 4가지 조건 중 Hold-and-Wait 에서 Hold 한 자원이 없기 때문이다.
2. Initialize a temporary vector W to equal the Available vector.
   W 는 Available Vector 이다. (copy)
3. Find an index i such that process i is currently unmarked and the ith row of Q is less than or equal to W.
   mark 가 안된 프로세스 중에서 request 값이 전부 W 값보다 작은 프로세스를 찾는다.
   • i.e. Qik ≤ Wk for 1 ≤ k ≤ m.
     Request ≤ Available ⇒ 할당 가능 O
   • If no such row is found, terminate

mark 가능 → Deadlock X
↳ 왜 자원을 줄 수 있는 것이 Deadlock이 아닌가?
↳ 앞의 Deadlock 이 걸리는 4가지 조건 중 Hold-and-Wait 에서 Wait 한 자원이 없기 때문이다.
→ 자원을 주면, Hold 는 하지만, Wait 는 하지 않는다.

⇒ Request 나 Allocation 이나 둘 중 하나는 0 이 되어야 mark 가 가능하다.

Avoidance Deadlock 과 같이 프로세스를 mark 하고 나면 mark 한 프로세스가 가지고 있던 자원을 다시 Available Vector에 반환한다.

P1
P2
P3 2✅: 00010 → request <= available ⇒ available + allocation 
									= 00001  + 00010
									= 00011
P4 1✅
P5

더 이상 request 를 만족시킬 수 있는 프로세스가 존재하지 않으면, while문을 빠져 나오게 된다.
이때 만약 모든 프로세스가 mark 되어 있다면, safe 이고, 모든 프로세스가 mark 되지 않는다면 unsafe 상태이다.

1. If such a row is found,
   • mark process i and add the corresponding row of the
     allocation matrix to W.
   • i.e. set Wk = Wk + Aik, for 1 ≤ k ≤ m

• Return to step 3.
• A deadlock exists if and only if there are unmarked
  processes at the end
• Each unmarked process is deadlocked.

Q. Mark 가 안된 프로세스가 한 개만 존재할 수 있는가?

존재할 수 없다.
Deadlock 은 최소 두 개의 프로세스가 있어야 발생할 수 있다.

Q. P1과 P2 가 Deadlock 에 걸렸을 때, 사이클이 포함된 Resource Allocation Graph 그리기

Deadlock이 걸리면, Resource Allocation Graph를 그렸을 때, 사이클이 존재한다.
이때 벡터들이 주어진다면, P1과 P2의 사이클이 포함된 Resource Allocation Graph 를 그릴 수 있어야 한다.

Recovery Strategies Once Deadlock Detected

• Abort all deadlocked processes
• Back up each deadlocked process to some previously
  defined checkpoint, and restart all process
• Successively abort deadlocked processes until deadlock no longer exists
• Successively preempt resources until deadlock no longer exists

Deadlock 이 감지 됐다면, Deadlock 이 걸리기 이전으로 되돌릴 수 있는 방법은 존재하지 않는다.

1. 방법은, Deadlock이 걸린 모든 프로세스를 Abort (중단) 하는 것이다.
   → Abort 했다는 뜻은 프로그램을 처음부터 다시 시작한다는 뜻이다. 즉, 지금까지 했던 작업들이 다 사라지는 것이다.
2. Deadlock 이 걸리기 전 가장 최신 지점으로 되돌린다. (save 한 시점)
   그것보다 프로세스를 실행시키면서 중간 중간 프로세스의 상태를 save 해둔다.
   그랬다가 Deadlock이 걸리면, Deadlock이 빠지기 전 상태로 프로세스를 되돌린다. 즉, 처음부터가 아닌 가장 최신 지점으로 되돌리는 것이다.
   → 이 방법은 어렵다, 다시 시작하려고 save 한 지점들 중 데드락이 걸리기 이전의 마지막 지점을 찾아야 한다.
3. 모든 프로세스를 Abort 하지 않고, 일부를 Abort 하고 Deadlock 이 존재하는지 확인한다.

이와 같이 두개의 사이클이 존재한다고 가정하자. (P3-P4 이중 사이클, 전체 사이클)

P3 을 Abort 하면 두개의 사이클이 지워진다.

P1을 Abort 하면 마지막 남은 사이클이 지워져서 더 이상 Deadlock 이 존재하지 않게 된다.

Abort 된 최소 1개 이상의 프로세스는 다시 프로세스를 처음부터 다시 시작해야 한다.

1. 모든 프로세스들은 주기적으로 자기 상태를 save 한다.
   (두번째와 세번째 방법은 섞은 방법이다.)
   → Deadlock 발견
   → 프로세스를 하나씩 하나씩 자원을 할당 받기 전의 상태로 되돌린다.
   → 한사람 되돌려서 Deadlock이 끝나면 거기서부터 시작하는 거고, 문제가 해결되지 않으면 다른 한사람은 자원 할당 받기 이전 상태로 되돌린다.
   → 문제가 해결되지 않으면 자원 할당 받기 전전상태로 되돌린다.
   → 순차적으로 프로세스들을 이전상태로 되돌려서 Deadlock 이 발생하기 전의 상황을 만들어 낸다.

Deadlock Prevent 와 Deadlock Avoidance 는 자원을 할당 받을 때마다 뭔가 action을 해주어야 한다.
즉, 1년 365일 내내 Deadlock Prevent 와 Deadlock Avoidance를 돌리고 있어야 한다는 뜻이다.

반면, Deadlock Detection은 Deadlock이 매일매일 발생하는 것이 아니기 때문에 매일 이 알고리즘을 돌려야하는 것이 아니라, 자원할당에 문제가 있을 때만 이 알고리즘을 돌리면 된다.
→ 프로세스가 자원을 요청했는데, 자원할당 될 때까지 시간이 이상하게 오래걸릴 때 싶을 때만 Deadlock Detection을 하면 된다.
⇒ Deadlock Prevent 와 Deadlock Avoidance에 비해 Deadlock Detection은 실행 빈도가 낮다.

Deadlock Detection 에서 시스템의 실행 상태를 중간 중간 저장하는데, 사실 원래 백업을 목적으로 저장하고 있는 시스템들이 많다. 그렇게 때문에 추가로 필요한 것은 어느 지점이 데드락이 발생하지 않았던 가장 최근 지점인가 이정도의 노력만 해주면 된다.

Dining Philosophers Problem
식사하는 철학자 문제

Deadlock 과 관련된 유명한 문제이다.

둥그런 원탁에 다섯명의 철학자가 앉아있다.
철학자들은 생각을 하다가 밥을 먹다가 생각을 하다가 밥을 먹다가를 반복한다.
밥을 먹으려면 포크 두개가 필요하다.
각각의 철학자는 자기 왼편의 포크와 오른편의 포크를 사용해서 면을 덜어서 밥을 먹고 밥을 다 먹고 나면 포크를 놓을 것이다.
포크1을 철학자 P0와 P1이 동시에 사용할 수 없다.
즉, 두 사람 중 한 사람이 포크를 잡으면 나머지 한 사람은 기다려야 하는 상황이다.

The Problem

Devise a algorithm that will allow the philosophers to eat.
1. No two philosophers can use the same fork at the same time (mutual exclusion)
2. No philosopher must starve to death (avoid deadlock and starvation)

우리는 이 철학자들이 굶어 죽지 않고(Starvation, Deadlock), 생각하고 밥먹는 행위를 계속하기를 바란다.

A frist Solution using Semaphore

Solution이라고 적혀 있지만, 문제를 해결하는 방법이 아니라, 문제가 발생할 가능성이 있는 알고리즘이다. 세마포를 이용한다.

5개의 포크를 세마포 5개라고 생각하면 된다.

세마포는 한 번에 한 프로세스만 접근 가능하므로 1로 초기화 되어 있다.
철학자들은 while 문을 반복하면서 생각(think())을 할 것이다.

생각을 한참하다가 밥을 먹을 생각이 들면, 자신의 왼쪽 포크를 집을 것이다.
왼쪽 포크를 무사히 집으면, 오른쪽 포크를 집을 것이다.

• semWait(fork[i]) → 철학자의 왼쪽 포크는 철학자의 id 와 같다.
• semWait(fork[i+1]) → 철학자의 오른쪽 포크는 철학자의 id+1 과 같다.
• P4와 같은 경우는 자신의 왼쪽 포크가 0번이기 때문에 modular를 한다.

왼쪽과 오른쪽 포크 모두 무사히 집으면 밥을 먹는다.

밥을 다 먹고 나면, 오른편 포크를 놓고, 그 다음 왼편 포크를 놓는다.
그러면 포크의 값이 다시 0에서 1로 바뀌게 된다.

그리고 다시 생각을 한다.

문제가 되는 상황은, 동시에 밥을 먹어야겠다고 생각이 들었을 때다.

본인의 왼쪽 포크를 집은 후 TIMEOUT이 걸린 상황이다.

모두가 fork를 하나씩 잡고 상대편이 fork를 놓기만을 기다리며 굶어죽어가는 상황이다.

Avoiding deadlock

위의 문제를 피할 방법.

문제를 해결하기 위하여 room 이라는 세마포를 하나 더 만들었다.
초기값은 4이다.

밥을 먹기 위해서는 room 라는 세마포를 통과해야 한다.

room 에는 최대 4명까지 철학자가 들어가서 식사가 가능하다.
⇒ 즉, 한명은 기다려야 한다.

밥 먹는 곳(최대 4명만 들어갈 수 있는)과 생각하는 곳을 구분해놨다고 생각하면 좋다.

Q. Deadlock 이 없는지 어떻게 확신할 수 있을까?

포크가 5개가 있고, 사람이 4명이 있으므로 적어도 한 사람은 포크를 집고 밥을 먹을 수 있다. 그리고 그 사람이 밥을 다 먹고 포크를 놓고 밖으로 나오면, 밖에 있던 사람이 안으로 들어 올 수 있고, 내려놓은 포크 양쪽에 있던 사람들은 밥을 먹을 수 있게 된다.

결국 순차적으로 밥을 먹을 수 있게 된다.

room 의 값을 3으로 해도 Deadlock 은 발생하지 않는다.
이 경우, 최대 3명의 철학자가 room 으로 들어갈 수 있고, 2명은 포크를 집어 밥을 동시에 먹을 수 있게 된다.

하지만, room 의 값을 5이상 6으로 하면 Deadlock 이 발생하게 된다.

Q. Circular Wait을 Prevent 하는 방식(deadlock prevention)으로 이 해결하라!

deadlock prevention 은 모든 작업에 번호 할당한다.
→ 자원을 할당할 때 번호순으로 할당한다.
↳ 이 작업은 이미 포크에 번호가 붙여 있으므로 따로 작업을 하지 않아도 된다.

모든 포크에 번호가 붙어 있으므로, 자원 할당을 번호순으로 할 수 있는 방법을 답안지에 적으면 된다...

(deadlock은 존재하지 않는다.)

A solution using a Monitor

condition 변수

monitor 를 사용할 때는 condition 변수가 존재한다.
→ condition 변수는 Queue 이다.
(프로세스들이 기다리는 Queue를 의미한다.)
→ condition 변수를 몇 개를 둘까 생각해야한다.
→ Queue 는 포크의 개수만큼 필요하다.
↳ Queue 를 하나만 두고 철학자들을 하나의 Queue 에서 기다리게 하면, 포크를 잡을 수 있다면 안기다리지만, 포크를 옆 사람이 잡고 있으면 난 기다려야 한다.
하나의 Queue 에서 기다리면, 내가 원하지 않은 포크를 사용한 사람이 나를 데려와서 내가 필요하지 않은 포크를 사용하게 할 수 있다.
⇒ 다섯개의 포크를 각 기다리는 사람들을 다른 곳에서 기다리게 하기 위해서 forkReady 라는 다섯개의 Queue 를 사용한다.

fork 변수

여기서의 fork 는 세마포가 아니라 boolean 변수이다.

fork == true → 아무도 포크를 사용중이지 않다는 뜻이다.
fork == false → 누군가가 포크를 사용중이라는 뜻이다.

get_forks()

포크를 잡는 함수이다.

제일 먼저하는 일은 현재 프로세스의 왼쪽과 오른쪽 포크의 id를 결정하는 것이다.

• 왼쪽 포크 id == 프로세스 id
• 오른쪽 포크 id == (프로세스 id + 1) mod 5

왼쪽과 오른쪽 포크가 사용중인지 확인한다.

• 만약, 왼쪽 포크가 이미 사용중이라면, cwait()를 이용해서 대기 Queue로 들어가게 된다.
  그렇지 않으면, 왼쪽 fork의 값을 false로 바꾼다.
• 오른편 fork 도 같은 방법으로 사용중인지 확인하고 cwait()로 대기하거나, 오른편 포크를 잡아 오른편 fork의 값을 false로 바꾼다.

아래쪽 코드

철학자가 생각하고 밥먹는 건 밖에서 진행한다.

즉, 밥 먹고 싶을때만 monitor 안으로 들어오고, 먹는건 밖에서 먹는다.

왜냐하면, 밥은 동시에 먹을 수 있어야 하는데, monitor 는 한 번에 하나의 프로세스만 진입 가능하기 때문이다.

release_forks()

밥을 다 먹고 포크를 놓을 때 다시 모니터로 들어오게 된다.

왼편 오른편 포크 번호를 결정한다.

• 왼편 포크를 놓을 때, 그냥 놓으면 안되고 포크를 잡으려고 기다리는 사람이 있는지 확인한다.
  • 만약 기다리는 사람이 있다면 → 깨워준다.
  • 만약 기다리는 사람이 없다면 → fork 값을 true로 바꿔준다.
• 오른편 포크를 놓을 때도 포크를 잡으려고 기다리는 사람이 있는지 확인한다.
  • 만약 기다리는 사람이 있다면 → 깨워준다.
  • 만약 기다리는 사람이 없다면 → fork 값을 true로 바꿔준다.

왜 monitor를 이용한 Solution에서는 Deadlock 이 발생하지 않을까? 🌟

아까 Deadlock이 발생했던 코드를 다시 보면,

왼편 포크 잡고 오른편 포크 잡고 밥 먹고, 오른편 포크 놓고 왼편 포크 놓고 했는데 Deadlock 이 발생했었다.

A solution using a Monitor도 똑같이 왼편 포크 잡고 오른편 포크 잡고 밥 먹고, 왼편 포크 놓고 오른편 포크 놨는데, Deadlock 이 발생하지 않는다.

포크 놓는 순서가 달라서 Deadlock이 발생하고 안발생하고 하지는 않는다.
포크를 놓는 순서에 상관 없이, signal 을 주는 순서이기 때문에
여기서는 내 왼편과 오른편 사람 중에서 오른편 사람 먼저 밥을 먹게 하고 왼편을 먹게 하고 아니면 왼편을 먼저 먹게 하고 오른편을 먹게 하고의 차이이다.
→ 밥을 먹기 시작하는 순서가 달라진다고 변하는 것은 없다.

다른 이유로 이 Solution 은 Deadlock 이 없는 Solution 이다.
↳ 이유가 무엇일까?

Monitor 안에서는 TIMTOUT이 걸리지 않아서 → X,

왜냐하면 위의 문제가 발생하는 코드는 왼편 포크를 잡고, 오른편 포크를 잡는 사이에 TIMTOUT이 발생해서 문제가 발생했던 것이었다.

하지만, 모니터 코드에서도 왼편 사람이 포크를 잡은 후 TIMEOUT이 걸릴 수 있다.
⇒ TIMEOUT이 걸리지 않는다고 하는 말은 옳지 않다.

문제가 발생하는 코드에서는 왼편 포크를 잡고 TIMEOUT이 걸려서 CPU를 내 오른편에 있는 사람이 뺏어 갔는데, 그 사람이 내 오른편 포크를 뺏어갔다.

• 왼편 fork → Timeout → 오른편 사람 → CPU → 내 오른쪽 fork 가져감

하지만 모니터를 이용한 solution에서도 TIMEOUT은 걸릴 수 있다.
내가 왼편 포크를 잡고 TIMEOUT 이 걸렸는데, 여기서 중요한 점은, monitor 안에서 TIMEOUT 이 걸렸다는 점이다.
monitor 의 가장 중요한 특성이 monitor 안에는 한 번에 한 프로세스만 들어올 수 있다는 점이다.
⇒ 즉, 내가 monitor 안에서 TIMEOUT 이 걸려서 CPU 를 뺏겨도, 다른 사람은 monitor 안에 들어올 수 없다. (다 monitor 밖에서 대기를 하는 것이다.)

monitor 안에 들어올 수 없다 == 내 오른편 포크를 뺏어갈 수 없다.
⇒ Deadlock 이 발생하지 않는다.

일단 monitor 안으로 들어가면, 왼쪽 포크를 잡고, 오른편 포크를 잡을 때까지 TIMEOUT이 걸려서 얼마나를 Ready Queue에서 기다리든지 전혀 상관 없이, 나는 일단 왼편 포크를 잡으면 오른편 포크도 잡게 된다.

monitor → 한 번에 하나의 프로세스만 들어올 수 있다. → 포크 두 개를 동시에 잡거나 / 아예 안 잡거나 둘 중 하나만 가능

⇒ Deadlock X

deadlock을 아예 발생시키지 않으면 좋지만, deadlock을 막을 수 없는 경우가 존재한다.
⇒ OS가 deadlock을 막아줘야 한다.

Deadlock 정의

A set of processes is deadlocked when each process in the set is blocked awaiting an event that can only be triggered by another blocked process in the set.

• Deadlock 이 발생하기 위해서는 최소한 둘 이상의 프로세스가 필요하다.
• block 이 되어야 한다. (프로세스가 멈추지 않고 실행하고 있으면 deadlock이 아니다.)
• block 이 되었다고 해서 무조건 deadlock은 아니다.
  ↳ block 이 존재하면 이 block 을 깨워줄 이벤트가 존재한다.
• ex) semWait(s), semSignal(s), ...
• 한 프로세스가 block 이 되고, 그 이벤트를 해 줄 프로세스가 같이 block 된 것을 deadlock 이라고 한다. ⇒ 영영 deadlock 상태에서 빠져나올 수 없다.

즉, deadlock 의 조건은 두 가지이다.

1. 최소 두 개 이상의 프로세스가 block 상태이다.
2. block 상태에서 빼 줄 수 있는 이벤트를 실행하는 프로세스가 같이 block 이 되는 상황이다.

Deadlock 예시

• s1과 s2가 전부 초기값이 1이다.

이 block 상태를 해결하려면 서로의 프로세스가 semSignal()을 해주어야 하는데 semSignal() 를 줄 프로세스가 같이 block됐기 때문에 block 상태에서 아무도 빠져나올 수 없다.
⇒ 두 프로세스가 Deadlock에 빠졌다.

Deadlock 발생 조건 네가지

다음의 네가지 조건을 모두 만족해야 Dealock 이 발생한다.

1. Mutual Exclusion

only one process may use a resource at a time.

한번에 하나의 프로세스만 자원을 사용할 수 있어서 Dealock 이 발생한다.

2. Hold-and-Wait

a process may hold allocated resources while awaiting assignment of others.

다들 자신의 자원을 1개 이상 가지고 있고, 다른 프로세스에게 자원을 하나 이상 요청할 때 Dealock 이 발생한다.
만약 자원을 가지고 있지 않거나, 자원을 요청하지 않으면 Dealock 이 발생하지 않는다.

Process A: s1 통과 O, s2 통과 X
Process B: s2 통과 O, s1 통과 X

3. No Preemption

no resource can be forcibly removed from a process holding it.

할당된 resource를 강제로 빼앗지 못하기 때문에 Dealock 이 발생한다.

semaphore 값을 0 → 1로 강제로 바꿀 수 없다.

4. Circular Wait

a closed chain of processes exists, such that each process holds at least one resource needed by the next process in the chain.

Process 1: 자원 A를 가짐 & Process 2 에게 자원 B 요청 
Process 2: 자원 B를 가짐 & Process 1 에게 자원 A 요청

                        Process 1
                            ↑ ↓   (cricular)
                        Process 2

Resource Allocation Graphs

OS는 프로세스가 시스템 안에서 자원을 요청하고 할당받는 사이에 이와 같은 Cricular Wait가 발생하는지 알아보기 위해 Resource Allocation Graph를 그릴 수 있다.

ex) semaphore 의 값이 5라면, 네모 안에 ● 은 5개 존재하게 된다.

오른쪽의 그림은 사이클이 있는 것처럼 보이지만 사이클이 존재하지 않는다.
Ra 타입 자원이 한 개가 아니라 3개이기 때문에,
OS가 요청을 받아주면, P1에게도 자원이 할당될 수 있다.

위와 같은 Resource Allocation Graph 는 드물다.
보통 사이클은 두 프로세스 사이에서 주로 나타난다.

P1과 P2 사이에서 사이클이 발생해 Deadlock이 발생한다.
P1과 P2가 원래 가지고 있던 자원이 존재하고, 이 자원들을 필요로 하는 프로세스들이 존재한다. 이와 같이 P1과 P2에 엮인 나머지 Process들이 존재한다.

P1과 P2에 엮인 나머지 Process 들은 Deadlock 과 관련이 없지만, P1과 P2와 관련이 있어 block이 되어 시스템이 정지되게 된다. ⇒ 심각

Dealing with Deadlock

Deadlock을 해결하는 3가지 방법이 존재한다.

1. Prevent Deadlock

방지
→ 자원 할당 과정에서
다음의 시점에 미리 규칙을 세워둔다.

• 자원 요청 시점
• 자원 할당 시점
• 자원 할당이 거절 됐을 때 어떻게 할 것인지 하는 것 까지

2. Avoid Deadlock

회피
→ 자원 요청
→ OS가 검사
↳ 자원을 할당해 줬을 때, Deadlock이 발생하는지 검사 후 발생하지 않으면
자원 할당 O, 발생하면 자원 할당 X

3. Detect Deadlock

1번 Prevent Deadlock 과 2번 Avoid Deadlock 은 Deadlock 발생 자체를 방지한다면, 3번 Detect Deadlock 은 시스템에서 Deadlock 이 발생하는 건 일단 방치 한다.
그렇기 때문에 제일 비용적으로 좋다.

대신 빠르게 감지하고 Deadlock 이 발생한 두 프로세스를 중지시킨다.
→ 나머지 프로세스들은 정상적으로 작동한다.
⇒ 전체 시스템은 정상적으로 작동한다.

Deadlock Prevention Strategy

Deadlock 을 발생시키는 4가지 조건 중 어느 한 조건을 만족하지 않는 상황을 만든다.
단, Mutual Exclusion은 무조건 지켜져야 한다.
↳ 나머지 조건을 방지하는 방식으로

Design a system in such a way that the possibility of deadlock is excluded.

Mutual Exclusion

Mutual Exclusion 은 무조건 지켜져야 한다.

Hold and Wait

Require a process request all of its required resources at one time.

Hold와 Wait를 동시에 만족해야 Deadlock 이 발생하기 때문에 Hold가 안되게 한다.

• 처음 프로세스 실행 → 필요한 자원 한번에 요청 → OS가 자원을 한번에 줄 수 있으면 준다. → 자원을 Hold만 한다. Wait 하지 않는다.
  ↳ Q. 애초에 필요한 자원은 어떻게 알 수 있지?
  → Compiler가 이미 프로그램 전체를 프로세스로 만들기 위해 훑기 때문에 자원을 파악하는데는 문제가 없다.
• 자원 준비가 다 안됐을 경우 (5개 중 4개만 준비) ⇒ block
  → 나중에 1개가 가능해도, 다른게 다시 준비가 안될 경우가 있기 때문에 다시 block 될 수 있는데 결국 Starvation 문제를 유발할 수 있다.

이론적으로 시스템에 적용할 수 없다.

No Preemption

• Process must release resource and request again.
• OS may preempt a process to require it releases its resources.

자원을 뺏는다.

자원을 바로 뺏을 수 없기 때문에, 만약, OS가 모종의 이유로 일정 시간 동안 자원을 할당하지 않으면,
해당 프로세스가 가진 자원을 전부 뺏고, 처음부터 다시 시작한다.

이론적으로 시스템에 적용할 수 없다.

Circular Wait

Define a linear ordering of resource types.

Circular Wait를 방지한다.

모든 자원에 정수 번호를 붙인다. 번호순으로 자원을 요청한다.

필요한 자원요청 자원

↑ 위와 같이가 아니라 밑에와 ↓ 같이 요청한다.

필요한 자원요청 자원

즉, 내가 필요한 자원의 순서대로가 아니라, 번호 순서대로 요청해야 하기 때문에 필요 없는 자원도 요청하게 될 수 있어 자원 낭비의 가능성이 존재하게 된다.

이론적으로 시스템에 적용할 수 있다.

Q. 정말 이렇게 하면 Deadlock이 방지 될 수 있을까? (증명)

Cycle이 생기려면 회색 박스의 두 상황을 동시에 만족해야하는데,
불가능한 상황이기 때문에 모순이 발생한다.

R1의 수와 R2의 수가 동시에 서로에게 클 수 없다.

Deadlock Avoidance

Process가 자원을 요청하거나 실행을 시도할 때, OS가 시작을 해도 좋겠다 혹은 보류해야겠다 또는 이 자원을 할당해도 좋겠다 혹은 보류해야겠다 등의 결정을 계속 하는 것.
(당연히 Deadlock이 발생하지 않는 방식으로 결정해야 한다.)

가정: 프로세스가 얼마나의 자원을 요청할지 미리 알고 있어야 한다.

A decision is made dynamically whether the current resource allocation request will, if granted, potentially lead to a deadlock.

Requires knowledge of future process requests.

Two Approaches to Deadlock Avoidance

1. Process Initiation Denial

Do not start a process if its demands might lead to
deadlock.

프로세스가 실행을 시작할 때 실행을 시킬지 말지를 결정하는 방식.

2. Resource Allocation Denial

Do not grant an incremental resource request to a process if this allocation might lead to deadlock.

리소스를 달라고 요청했을 때, 리소스를 줄지 말지를 결정하는 방식.

Process Initiation Denial Deadlock Avoidance

A process is only started if the maximum claim of all current processes plus those of the new process can be met.
↳ 프로세스가 자신이 필요한 자원 최대를 OS에게 미리 보고 → OS가 검사 → 내가(OS) 가진 Resource를 Process들이 전부 사용해도 부족한지, 안부족한지 검사한다.
⇒ Optimal 하지 않다.

Process1과 Process2가 위와 같이 자원을 원하고, 겹치는 자원을 겹치는 시간대에 요구하지 않아도, OS는 둘 중하나만 실행한다.
⇒ Optimal 하지 않다.

Not Optimal

Assumes the worst that all processes will make their maximum claims together.

Determination of Safe State (Process Initiation Denial)

Claim matrix : 지금 이 시스템에는 R1, R2, R3 세가지 타입의 자원이 있다.
각 프로세스가 나는 각 타입의 자원을 몇개를 쓸거다 라고 하는 자원 사용의 최대치를 말한다.

P1, P2, P3, P4이 동시에 도착한 것이 아니라 P1 → P2 → P3 → P4 의 순으로 순서대로 도착했다.

Resource Vector R : 시스템이 가진 리소스의 개수

P1, P2 는 실행을 시작할 수 있지만, P3는 실행을 시작하지 못한다 (Block).

Resource Allocation Denial Deadlock Avoidance

가장 구현 가능성이 높다.

banker’s algorithm

Referred to as the banker’s algorithm.

↳ banker’s algorithm 이라고 불린다.

프로세스 실행 → 자원을 요청 → OS가 자원을 줄 수도, 안줄 수도 있다.

가정: 시스템 안에서 리소스 개수는 변하지 않는다.

Consider a system with fixed number of resources.

• State of the system is the current allocation of resources to process.
• Safe state is where there is at least one sequence that does not result in deadlock.
• Unsafe state is a state that is not safe.

시스템의 상태 정의

현재 이시각, 프로세스에 자원이 몇개씩 할당되는가?

safe

safe : 현재시스템 상태에서 지금 실행하고 있는 프로세스들을 deadlock에 걸리지 않고, 무사하게 실행시킬 수 있는 시퀀스가 존재하는 상태.

unsafe

unsafe : 지금 상태는 deadlock은 아니지만, 어떤 순서로 실행하던 결국 deadlock이 발생하게 되는 상태.

Determination of Safe State (Deadlock Avoidance)

A system consisting of four processes and three resources.

Claim matrix : 각각의 프로세스들이 자원을 최대 얼마나 요구할것이다라고 하는 것

Allocation matrix : 현시점에서 각각의 프로세스들이 자원을 얼마나 할당 받았나 라고 하는 것

Resource Vector R : 시스템이 가진 리소스의 개수

Claim-Allocation : C - A, Claim matrix에서 Allocation matrix를 뺀 값이다. 즉, 각각의 프로세스들이 앞으로 더 요청할 자원의 최대치를 의미한다.

Available vector : 프로세스들에게 할당하고 남은, 시스템 안에 남아 있는 자원

Is this a safe state?

→ Deadlock 없이 Process들이 무사히 종료할 수 있는가?
↳ 누가 종료가 가능한지를 따져봐야 한다.

제일 먼저 누가 종료 가능? → P2가 제일 먼저 종료할 수 있다.

종료할 수 있다의 의미: 지금 현재 남아있는 자원인 Available vector에 있는 자원을 전부 주면 종료할 수 있다는 의미이다.

즉, C-A <= Available vector (C-A의 값이 Available vector의 값보다 작거나 같으면 된다,)

⇒ P2가 먼저 무사히 종료가능하다. ↔ P1, P3, P4는 종료 불가능
⇒ P2가 먼저 종료 했다고 가정 → P2에 할당 됐던 자원을 모두 반환.

↳ 다음에 종료할 프로세스? → Banker's Algorithm
⇒ 1번부터 (보통 for문으로 구성되기 때문이다.) ⇒ P1 종료

프로세스가 종료하면 그저 자기가 가지고 있던 자원을 반납한다. (Allocation maxtrix 만큼)

여기서의 state는 초기의 상태, 밑에 ↓ 그림의 상태를 말하며, safe한 것을 알 수 있다.

Determination of an Unsafe State

초기 상태 (a)에서 P1에게 자원 R1과 R3 (1 0 1)를 할당한다.
남은 Available vector로는 아무것도 종료할 수 없으므로 Unsafe인 것을 알 수 있다.

프로세스 → 자원 요청
↳ OS가 자원을 바로 주는게 아니라, 주었다 치고 상태를 검사한다. (b)처럼
→ safe이면 자원을 할당해주고, unsafe이면 자원할당을 거절한다.
→ (b) 는 unsage였기 때문에 (a)로 다시 환원한다.

Banker's algorithm

자원을 요청할 때마다 OS가 검사를 진행하고 (이 자원을 줬다 가정하고 자원을 준 상태가 safe 상태인지 확인) 자원을 할당할지 말지를 결정하는 것

문제

https://www.acmicpc.net/problem/2475

data= list(map(int, input().split()))
sum=0
for i in range(5):
    sum += data[i]*data[i]
res=sum%10

print(res)

문제

https://www.acmicpc.net/problem/2468

from collections import deque
import sys
input= sys.stdin.readline

def bfs(x, y, k):
  dx = [1, -1, 0, 0]
  dy = [0, 0, -1, 1]

  q= deque()
  q.append([x, y])
  visited[x][y] = 1

  while q:
    a, b = q.popleft()
    for i in range(4):
      nx = a + dx[i]
      ny = b + dy[i]
      if 0 <= nx < n and 0 <= ny < n and field[nx][ny] > k and visited[nx][ny] == 0:
        visited[nx][ny] = 1
        q.append([nx, ny])

n = int(input())
field = []

max_list = []

max_num = 0
for _ in range(n):
  field.append(list(map(int, input().split())))

for i in field:
  for j in i:
    if max_num < j:
      max_num = j

for k in range(max_num + 1):
  visited = [[0] * n for _ in range(n)]
  count = 0
  for i in range(n):
    for j in range(n):
      if field[i][j] > k and visited[i][j] == 0: 
        bfs(i, j, k)
        count += 1
  max_list.append(count)

print(max(max_list))

문제 해결

BFS를 이용하여 풀었고, 방문조건을 확인하였고 꽤 쉽지 않은 BFS문제였다