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번 위치에 적혀있는 프레임이 내 프레임이 아니라 다른 사람 프레임일 수 있다.

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

---

크기 계산

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

0	0	0

위에서는 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