Segmentation

Inefficiency of the Base and Bound Approach

• Heap, Stack은 Dynamic하다.
• 그러면 중간에 비어있는 공간 있을거임.
• 생각보다 빈공간이 넓다.
• 아까까진 모양 손상 없이 그대로 올라간다고 가정했었음.
• 그런데 그대로 적재하는건 비효율적임.

1. 공간이 매우 커보임. Big chunk of “free” space
2. free space가 남아있는 physical memory보다 크면 실행이 안될 것임.
3. 커버 가능한 실제 메모리 공간이 없을 수 있음.

Segmentation

💡 Segment : Stack, Heap, Code, Data.

그래서 시도하는 방법은 Segment 단위로 적재하자는 것. 나눠서 하면 몇가지 문제를 해결할 수 있음.

💡 Segmentation : Segment 단위로 나눠서 관리하는 것

의미가 있는 segment(code, stack, heap…) 단위로 나누자. 그리고 따로따로 올리면 physical memory 아무곳에나 올려둘 수 있음. 그리고 커지고 줄어드는 걸 대응하기 쉬움. 공간을 효율적으로 쓸 수 있다는 것.

but, 나눠서 올리기 때문에 관리가 더 어려워짐. 그리고 주소 변환을 할 때는 base, bounds 레지스터들만 가지고 덧셈하면 됐는데 각 조합별로 base, bounds들이 필요해짐.

Placing Segment In Physical Memory

이전 챕터에서는 통째로 올려놓았는데, 이제는 각 Segment별로(Code, Heap, Stack) 올라간다.

각 Segment 별로 어디서 시작하는지 size는 몇인지 알아야함.

💡 physical address = offset + base 💡 offset = virtual address - start address of segment

→ offset 은 상대적인 위치

Address Translation on Segmentation

예를 들어 instruction에 접근하고 싶은데 이 코드의 segment가 32K 에 위치해 있고, offset은 100이므로 실제 메모리 공간에서 32K + 100 = 32868 위치에서 찾을 수 있다.

• Heap은 4 KB에서 시작하는데 4200번에 data 있으면 offset 4200-4096 = 104
• 즉 104에서 base 더한 값에서 찾을 수 있음.

Segmentation Fault or Violation

• bound register의 역할이 있었음.
• Heap이 만약 4KB이면 전체 bound가 2KB라 가정해본다.
• 그리고 7KB에 접근하라는 access 요청이 들어옴.
  

• 할당된 곳이 아닌데 접근 요청이 나왔으니 Segmentation Fault가 발생한다.
• 이렇게 오류가 난것을 알려주는 것이 bound register의 역할임.

Which Segment Are We Referring To?

• 어떤 Segment꺼인지(Code, Heap, Stack).. 알아내야함

Referring to Segment

• cpu가 어떤 주소를 요청하면 physical address로 변환 해야하는데 이 주소가 어느 Segment꺼인지 알아내야함.
• 그래서 약속 하나를 함.
• 주소 중 최상위 비트 두개로 어떤 Segment를 얘기하는지 식별하기로 함.
  • code = 00, heap = 01, 10, stack = 11

Referring to Stack Segment

→ Psudocode

• Virtual Address를 뱉으면 만약 14개 비트 정도 있다고 하면 상위 2 bits를 얻기 위해 SEG_MASK를 and한다. 0&1 → 0, 1&1→ 1
• 그렇게 어떤 Segment인지 알 수 있음.
• 그 다음 상대 주소인 offset값을 얻어낼 수 있음. 마찬가지로 하위 12개 비트를 얻기 위해 OFFSET_MASK 값과 and하여 얻을 수 있음.
• offset이 bound 넘어가면 error 발생시키고 그렇지 않으면 base + offset 하여 physAddr 구할 수 있음.
  

하지만, 생각해야 할게 하나 더 있음.

Stack은 아래에서 시작해서 위로 올라오는 듯한 모습임. (=backward)

그니까 방향에 대한 얘기도 해야하지 않을까

Positive direction = 1, negative direction = 0

• Segment Table을 보니 Stack은 물리적인 주소에 28K부터 적재되어 있다.
• virtual address가 15KB라 하면 11 1100 0000 0000
• 제일 상위 2비트가 11이므로 Stack이다. offset = 1100 0000 0000 = 3KB
• 12비트의 경우 최대 4KB까지 구현 가능

Support for Sharing

• Segment 단위로 하면 메모리 공간을 효율적으로 쓸 수 있고
• 또다른 장점은 Sharing이 쉽다는 것이다.
  

• 근데 방향 외에도 생각할 것이 Segment 별 역할임.
  • code는 instruction을 담아두므로 write X, Read O, Execute도 가능해야함.
  • Heap은 Read, Write 가능 실행할 건 없음.
  • 이런식으로 Protection도 존재해야함.
• 프로세스 공유자원 동기화해서 일기만 하는건 문제 없는데 누가 write하려고 하면 문제가 생기곤 했음. Heap, Stack은 write 기능이 있어 share가 어렵지만 code는 share가 쉬움.
• 그래서 segment 별로 share가 되는게 있고 안되는게 있지만 나눠서 적재했기 때문에 명확해져서 share 할 여지가 생긴다.

Fragmentation

💡 Fragmentation 단편화 : Segmentation이 완벽하지 않아서 생기는 문제?

프로그램을 통째로 올렸을 때 Physical Memory 그림임.

프로세스마다 크기가 다를 수 있음. 하나의 프로세스를 종료한 뒤 새로운 프로세스를 실행시킴. 또 다른 프로세스를 종료하고 다른 프로세스를 시작하면서 굉장히 많은 전환 작업이 발생함.

이때 발생하게 되는 빈 공간을 Hole이라 함.

💡 **Hole** : 프로세스가 쓸 수 있는 메모리 덩어리

Holes 마다 사이즈가 다 다르고 흩어져있음.

합치면 제법 큰 공간이 될 텐데 흩어져있어서 이 공간을 사용하지 못한다는 문제가 있음.

그래서 어디를 쓰고 있는지 hole이 어디있는지 os는 확실하게 알고 있어야함.

초록색은 현재 할당되고 있는 것. 흰색은 종료된 것 = hole

hole 관리를 해야함.

비어있는 공간을 free list라 불렀음.

이 상황에서 새로운 프로세스를 생성하려고 함. 크기는 25

이것이 Dynamic Storage-Allocation Problem

• first-fit : 가장 처음에 만족하는 hole (최초 적합)
• best-fit : 남아있는 공간을 효율적으로 선택하는 것 (최적 적합)
• worst-fit : 가장 큰 공간에다가 할당 (최악 적합)

Fragmentation은 두개로 나눌 수 있음.

• External(외부) 단편화 → hole 들을 위로 당기면 안될까? 이것이 바로 compaction 기법 → 통째로 올리든 segment로 올리든 크기가 제각각이라 hole이 생기는 문제
  
• Internal(내부) 단편화 → 메모리 공간을 단위로 나눠서 할당 해 줬는데 다 안쓸 수도 있음. 할당해준 공간을 다 쓰지 못해서 생기는 hole을 Internal fragmentation이라고 함. paging에서 나타나는 문제 → paging(무조건 동일한 사이즈 할당) 하는데 다 안써서 남는 공간이 생기는 문제
  

Memory Compaction

• segment 단위로 적재하면 external fragment가 발생한다.
• 주기적으로 한쪽으로 모아두자 = 위로 올려보자 = 커다란 hole로 만들어서 효율적으로 사용하자 → Compaction
  
• 하지만 cost가 조금 있다. 올리는 동안 서비스 공지 이런 느낌.
  

Segmentation: Pros & Cons

Pros

• 프로그램 통째로 올린거에 비해 메모리 공간을 더 효율적으로 사용할 수 있다.
• paging과 비교해보면 internal fragmentation가 발생하지 않는다.
  • 사실 internal < external이다.
• 주소 변환이 조금 더 복잡해지는 건 사실이지만, 페이징보단 쉽다.
• sharing이 쉽다. 대표적으로 code segment가 Read-only였기에 공유가 가능했다.
• segment를 마음대로 적재 가능하다.

Cons

• 외부단편화(external fragmentation) 발생한다.
• 할당 했는데 그 안에서도 쓰지 않는 공간이 있을 수도 있다.