Scheduler

I. Giải thuật sử dụng

Multi-Level Queue (MFQ)

II. Mô tả giải thuật

Mỗi process với cùng độ ưu tiên sẽ được đặt vào cùng một hàng đợi ready-queue.
MLQ policy: Khi hàng đợi P thực hiện đủ số lần slot (slot = MAX_PRIORITY - prio) thì tạm dừng, chuyển thực thi cho hàng đợi Q có ưu tiên thấp hơn. Khi các hàng đợi có độ ưu tiên thấp đã thực hiện hết số lần slot cho phép sẽ quay lại lần lặp kế tiếp với P là hàng đợi có độ ưu tiên cao được thực thi trước với số lần slot được tính.
CPU thực thi mỗi process theo RR-style. Sau khi hết time slice, process được đưa vào cuối hàng đợi với độ ưu tiên như cũ. CPU tiếp tục chọn process theo MLQ policy để thực thi.

III. So sánh với các giải thuật scheduler khác

Nhược điểm của các giải thuật khác:

FCFS: CPU phải thực thi 1 process liên tục cho đến khi kết thúc -> tăng waiting time đối với các process có CPU burst ngắn.
SJF: Không thể biết chính xác CPU time của process kế tiếp, có khả năng gây ra starvation.
RR: Time slice lớn -> FCFS. Time slice nhỏ -> context switch.
PS-normal: có khả năng gây ra starvation.

Ưu điểm của MFQ:

Response time: Các process có độ ưu tiên cao được thực thi trước.
Not starvation: Mỗi ready-queue có số lần slot nhất định trong chu kì thực thi của các hàng đợi.
Fairly: Giải thuật cho mỗi hàng đợi là Round Robin.

IV. Triển khai

Priority Queue
- void enqueue(struct queue_t *q, struct pcb_t *proc): Thêm 1 process proc vào cuối hàng đợi q.
- struct pcb_t *dequeue(struct queue_t *q): Lấy 1 process từ đầu hàng đợi q.
Scheduler
- struct pcb_t *get_mlq_proc(void): Lấy 1 process từ ready-queue theo MLQ policy, sử dụng khóa mutex để bảo vệ hàng đợi.

V. Kết quả

TEST 1:

Input

sched:
4 2 3
0 p1s 1
1 p2s 0
2 p3s 0

p1s:
1 10
calc
calc
calc
calc
calc
calc
calc
calc
calc
calc

p2s:
20 12
calc
calc
calc
calc
calc
calc
calc
calc
calc
calc
calc
calc

p3s:
7 11
calc
calc
calc
calc
calc
calc
calc
calc
calc
calc
calc

Output: Kết quả chi tiết trong /output/sched.output.
Gantt diagram:

TEST 2:

Input

sched_0:
2 1 2
0 s0 4
4 s1 0

s0:
12 15
calc
calc
calc
calc
calc
calc
calc
calc
calc
calc
calc
calc
calc
calc
calc

s1:
20 7
calc
calc
calc
calc
calc
calc
calc

Output: Kết quả chi tiết trong /output/sched_0.output.
Gantt diagram:

TEST 3:

Input

sched_1:
2 1 4
0 s0 4
4 s1 0
6 s2 0
7 s3 0

s0:
12 15
calc
calc
calc
calc
calc
calc
calc
calc
calc
calc
calc
calc
calc
calc
calc

s1:
20 7
calc
calc
calc
calc
calc
calc
calc

s2:
20 12
calc
calc
calc
calc
calc
calc
calc
calc
calc
calc
calc
calc

s3:
7 11
calc
calc
calc
calc
calc
calc
calc
calc
calc
calc
calc

Output: Kết quả chi tiết trong /output/sched_1.output.
Gantt diagram:

Memory Management

I. Các modules trong memory system

Memory-Modules

1. MM-VM Virtual Memory

Không gian địa chỉ bộ nhớ ảo bao gồm:
- Memory Area (mỗi area đại diện cho các segment của 1 process: data segment, code segment, stack segment, heap segment,...). Trong Assignment, ta chỉ sử dụng 1 memory area tương ứng vmaid = 0.
- Mỗi Memory Area bao gồm các Memory Region (region đang được sử dụng và region đang free).
Lợi ích của việc thiết kế multiple segments:
- Tổ chức bộ nhớ tốt hơn, dễ dàng quản lý và truy xuất dữ liệu: Stack segment quản lý các local variables và các function calls, Heap segment quản lý việc cấp phát động, Code segment quản lý các câu lệnh được thực thi,...
- Giảm context switching: Khi CPU switch giữa các processes hoặc threads, chỉ những segments cần thiết mới được restore trở lại CPU để tiếp tục thực thi. Điều này hiệu quả và nhanh hơn thay vì restore toàn bộ không gian địa chỉ.
Các operations trên virtual memory bao gồm:
- ALLOC: cấp phát 1 region memory.
- FREE: giải phóng 1 region memory.
- READ: đọc 1 byte giá trị tại 1 ô nhớ trong region memory.
- WRITE: ghi 1 byte giá trị vào 1 ô nhớ trong region memory.

2. MM-Memory Management

Mỗi process có 1 module Memory Management với vai trò mapping virtual address sang physical address, cụ thể:
- Giữ địa chỉ page table directory của process. Page table sẽ ánh xạ mỗi logical address sang page table entry.
- Quản lý địa chỉ các virtual memory area (segment) của process.
- Quản lý các memory region đang được sử dụng của process.
- Quản lý danh sách các page được map với frame trong physical memory theo cơ chế FIFO.
Memory Management quản lý logical address theo cơ chế paging (mỗi page là một không gian địa chỉ với kích thước cố định). Cấu trúc logical address 22 bit trong assignment được chia thành 2 mức, bao gồm 14 bit page number và 8 bit page offset.
Có những lợi ích và bất lợi nếu chia logical address nhiều hơn 2 mức:
- Giảm thiểu memory overhead: Thay vì sử dụng một page table duy nhất, ta có thể sử dụng nhiều page table nhỏ hơn, chỉ những page table được sử dụng mới được load vào physical address.
- Đối với các hệ thống lớn (64-bit), việc chia logical address thành nhiều mức sẽ giúp giảm thiểu memory overhead nhưng lại khó quản lý nên cũng không mang lại hiệu quả.
Lợi ích và bất lợi của segmentation with paging:
1. Lợi ích:
  - Quản lý các segment với các page hiệu quả hơn so với việc quản lý từng địa chỉ.
  - Tránh external fragmentation.
2. Bất lợi:
  - Internal fragmentation vẫn xảy ra vì kích thước trang là cố định.
  - Tăng độ phức tạp của việc quản lý.

3. MEMPHY-Memory Physical

Không gian địa chỉ bộ nhớ vật lý bao gồm:
- RAM: Bộ nhớ chính, có thể được truy xuất trực tiếp bởi CPU.
- SWAP: Bộ nhớ thứ cấp, không được truy xuất trực tiếp bởi CPU, kích thước lớn hơn RAM và số lượng nhiều (assignment dùng 4 SWAP).
Các opearions trên physical memory bao gồm:
- READ: directly đối với RAM và sequentially đối với SWAP.
- WRITE: directly đối với RAM và sequentially đối với SWAP.

II. Triển khai

ALLOC
- ```
  int find_victim_page(struct mm_struct *mm, int *retpgn)
```
  Tìm một "victim" page trong virtual memory:
  - Lấy một page từ cuối hàng đợi fifo_pgn mà mm đang quản lý, lưu số thứ tự của page đó vào retpgn.
- ```
  int alloc_pages_range(struct pcb_t *caller, int req_pgnum, struct framephy_struct **frm_lst)
```
  Cấp phát các frame trên RAM và lưu trong danh sách frm_lst:
  - Lặp qua req_pgnum lần. Ở mỗi bước lặp, kiểm tra có thể cấp phát 1 frame trong RAM. Nếu được, thêm frame vừa được cấp phát vào đầu danh sách frm_lst. Nếu không, thực thi bước kế tiếp.
  - Tìm một frame vicfpn trong RAM và thay thế nó bằng một free frame swpfpn trong SWAP. Việc lựa chọn một vicfpn cần tìm một "victim" page vicpgn trong virtual memory bằng hàm find_victim_page.
  - Nếu việc tìm vicpgn hoặc lấy một swpfpn trong SWAP thất bại thì giải phóng toàn bộ các frame đã được cấp phát trước đó và trả về lỗi.
  - Swap vicfpn trong RAM với swpfpn trong SWAP.
  - Set page table entry tương ứng với vicpgn bằng hàm pte_set_swap, thêm swpfpn vào đầu danh sách frm_lst.
- ```
  int vmap_page_range(struct pcb_t *caller, int addr, int pgnum, struct framephy_struct *frames, struct vm_rg_struct *ret_rg)
```
  Mapping các page tại địa chỉ addr với các frame trong danh sách frames:
  - Duyệt qua các page, set frame page table entry tương ứng với các page bằng hàm pte_set_fpn. Sau đó chèn các page đó theo thứ tự vào đầu danh sách fifo_pgn.
- ```
  int vm_map_ram(struct pcb_t *caller, int astart, int aend, int mapstart, int incpgnum, struct vm_rg_struct *ret_rg)
```
  Mapping virtual memory có kích thước aend - astart với RAM:
  - Cấp phát trên RAM số lượng frame bằng với số page incpgnum trên virtual memory bằng hàm alloc_pages_range, lưu các frame sau khi cấp phát thành một danh sách frm_lst.
  - Nếu cấp phát thành công, map các page tại địa chỉ mapstart với các frame trong danh sách frm_lst bằng hàm vmap_page_range.
- ```
  int inc_vma_limit(struct pcb_t *caller, int vmaid, int inc_sz)
```
  Tăng kích thước vùng nhớ của vmaid lên một khoảng bằng inc_sz:
  - Kiểm tra vmaid nếu tăng kích thước có bị tràn qua các vmaid lân cận. Nếu có, trả về lỗi (return -1), ngược lại thực thi bước kế tiếp.
  - Dịch con trỏ sbrk và vm_end của vmaid lên thêm 1 khoảng bằng inc_sz.
  - Tiến hành mapping virtual memory vừa được cấp phát sang physical memory trên RAM bằng hàm vm_map_ram.
- ```
  int __alloc(struct pcb_t *caller, int vmaid, int rgid, int size, int *alloc_addr)
```
  Cấp phát cho region rgid một vùng nhớ với kích thước size, sử dụng khóa mutex để bảo vệ virtual memory:
  - Nếu kích thước vùng nhớ trống của area vmaid >= size thì cấp phát thành công.
  - Nếu không đủ vùng nhớ, tăng kích thước của area vmaid lên một khoảng bằng số lượng page vừa đủ chứa size bằng hàm inc_vma_limit.
  - Sau khi tăng kích thước thành công, cấp phát size cho rgid.
  - Thêm fragment do paging gây ra sau khi cấp phát (nếu có) vào danh sách vm_freerg_list của mm.
- ```
  int pgalloc(struct pcb_t *proc, uint32_t size, uint32_t reg_index)
```
  Thực thi hàm __alloc với vmaid = 0 và ghi kết quả vào file output.
FREE
- ```
  int __free(struct pcb_t *caller, int vmaid, int rgid)
```
  Giải phóng vùng nhớ rgid, sử dụng khóa mutex để bảo vệ virtual memory:
  - Nếu rgid < 0 hoặc rgid > PAGING_MAX_SYMTBL_SZ hoặc size rgid = 0, trả về lỗi (return -1).
  - Gán kích thước của vùng nhớ rgid bằng 0, thêm vùng nhớ vừa được giải phóng vào danh sách vm_freerg_list mà mm quản lý.
- ```
  int pgfree_data(struct pcb_t *proc, uint32_t reg_index)
```
  Thực thi hàm __free với vmaid = 0 và ghi kết quả vào file output.
READ
- ```
  int pg_getpage(struct mm_struct *mm, int pgn, int *fpn, struct pcb_t *caller)
```
  Lấy frame fpn tương ứng với page pgn:
  - Nếu frame online (frame đang được lưu trên RAM ), trả về fpn. Nếu frame offline (frame đang được lưu trên SWAP), thực thi bước kế tiếp.
  - Tìm 1 "victim" page vicpgn trong virtual memory bằng hàm find_victim_page và lấy 1 free frame swpfpn từ SWAP. Nếu thành công, thực thi bước kế tiếp.
  - Swap vicfpn tương ứng vicpgn trong RAM với swpfpn trong SWAP.
  - Swap tgtfpn tương ứng pgn trong SWAP với swpfpn trong RAM.
  - Set swap page table entry tương ứng với vicpgn bằng hàm pte_set_swap.
  - Set frame page table entry tương ứng pgn bằng hàm pte_set_fpn.
  - Thêm pgn vào danh sách fifo_pgn của mm, trả về fpn.
  Hình vẽ mô tả:
- ```
  int pg_getval(struct mm_struct *mm, int addr, BYTE *data, struct pcb_t *caller)
```
  Đọc giá trị của ô nhớ tại địa chỉ addr và lưu vào data:
  - Lấy page number và page offset từ addr.
  - Lấy frame number trong RAM hoặc SWAP tương ứng với page number trong virtual memory bằng hàm pg_getpage.
  - Nếu thành công, kết hợp frame number và page offset trả về physical memory. Đọc giá trị của địa chỉ vật lý này trong bộ nhớ vật lý bằng hàm MEMPHY_read.
- ```
  int __read(struct pcb_t *caller, int vmaid, int rgid, int offset, BYTE *data)
```
  Thực thi hàm pg_getval để đọc 1 byte giá trị ô nhớ ở vị trí offset trong vùng nhớ rgid vào data, sử dụng khóa mutex để bảo vệ virtual memory.
- ```
  int pgread(struct pcb_t *proc, uint32_t source, uint32_t offset, uint32_t destination)
```
  Thực thi hàm __read với vmaid = 0 và ghi kết quả vào file output.
WRITE
- ```
  int pg_setval(struct mm_struct *mm, int addr, BYTE value, struct pcb_t *caller)
```
  Ghi value vào ô nhớ tại địa chỉ addr:
  - Lấy page number và page offset từ addr.
  - Lấy frame number trong RAM hoặc SWAP tương ứng với page number trong virtual memory bằng hàm pg_getpage.
  - Nếu thành công, kết hợp frame number và page offset trả về physical memory. Ghi value vào địa chỉ vật lý này trong bộ nhớ vật lý bằng hàm MEMPHY_write.
- ```
  int __write(struct pcb_t *caller, int vmaid, int rgid, int offset, BYTE value)
```
  Thực thi hàm pg_setval để ghi 1 byte value vào ô nhớ ở vị trí offset trong vùng nhớ rgid, sử dụng khóa mutex để bảo vệ virtual memory.
- ```
  int pgwrite(struct pcb_t *proc, BYTE data, uint32_t destination, uint32_t offset)
```
  Thực thi hàm __write với vmaid = 0 và ghi kết quả vào file output.

III. Kết quả

TEST 1:

Input

os_1_singleCPU_mlq:
2 1  8
1 s4   4
2 s3   3
4 m1s  2
6 s2   3
7 m0s  3
9 p1s  2
11 s0  1
16 s1  0

Output: Kết quả chi tiết trong /output/os_1_singleCPU_mlq.output
Show RAM:

Time slot 6: CPU thực thi lệnh alloc 300 0 của process m1s

===== PHYSICAL MEMORY AFTER ALLOCATION =====
PID=3 - Region=0 - Address=00000000 - Size=300 byte
print_pgtbl: 0 - 512
00000000: 80000001
00000004: 80000000
Page Number: 0 -> Frame Number: 1
Page Number: 1 -> Frame Number: 0
================================================================

Time slot 7: CPU thực thi lệnh alloc 100 1 của process m1s

===== PHYSICAL MEMORY AFTER ALLOCATION =====
PID=3 - Region=1 - Address=0000012c - Size=100 byte
print_pgtbl: 0 - 512
00000000: 80000001
00000004: 80000000
Page Number: 0 -> Frame Number: 1
Page Number: 1 -> Frame Number: 0
================================================================

Time slot 8: CPU thực thi lệnh free 0 của process m1s

===== PHYSICAL MEMORY AFTER DEALLOCATION =====
PID=3 - Region=0
print_pgtbl: 0 - 512
00000000: 80000001
00000004: 80000000
Page Number: 0 -> Frame Number: 1
Page Number: 1 -> Frame Number: 0
================================================================

Time slot 9: CPU thực thi lệnh alloc 100 2 của process m1s

===== PHYSICAL MEMORY AFTER ALLOCATION =====
PID=3 - Region=2 - Address=00000000 - Size=100 byte
print_pgtbl: 0 - 512
00000000: 80000001
00000004: 80000000
Page Number: 0 -> Frame Number: 1
Page Number: 1 -> Frame Number: 0
================================================================

Time slot 34: CPU thực thi lệnh free 2 của process m1s

===== PHYSICAL MEMORY AFTER DEALLOCATION =====
PID=3 - Region=2
print_pgtbl: 0 - 512
00000000: 80000001
00000004: 80000000
Page Number: 0 -> Frame Number: 1
Page Number: 1 -> Frame Number: 0
================================================================

Time slot 35: CPU thực thi lệnh free 1 của process m1s

===== PHYSICAL MEMORY AFTER DEALLOCATION =====
PID=3 - Region=1
print_pgtbl: 0 - 512
00000000: 80000001
00000004: 80000000
Page Number: 0 -> Frame Number: 1
Page Number: 1 -> Frame Number: 0
================================================================

Time slot 48: CPU thực thi lệnh alloc 300 0 của process m0s

===== PHYSICAL MEMORY AFTER ALLOCATION =====
PID=5 - Region=0 - Address=00000000 - Size=300 byte
print_pgtbl: 0 - 512
00000000: 80000003
00000004: 80000002
Page Number: 0 -> Frame Number: 3
Page Number: 1 -> Frame Number: 2
================================================================

Time slot 49: CPU thực thi lệnh alloc 100 1 của process m0s

===== PHYSICAL MEMORY AFTER ALLOCATION =====
PID=5 - Region=1 - Address=0000012c - Size=100 byte
print_pgtbl: 0 - 512
00000000: 80000003
00000004: 80000002
Page Number: 0 -> Frame Number: 3
Page Number: 1 -> Frame Number: 2
================================================================

Time slot 54: CPU thực thi lệnh free 0 của process m0s

===== PHYSICAL MEMORY AFTER DEALLOCATION =====
PID=5 - Region=0
print_pgtbl: 0 - 512
00000000: 80000003
00000004: 80000002
Page Number: 0 -> Frame Number: 3
Page Number: 1 -> Frame Number: 2
================================================================

Time slot 55: CPU thực thi lệnh alloc 100 2 của process m0s

===== PHYSICAL MEMORY AFTER ALLOCATION =====
PID=5 - Region=2 - Address=00000000 - Size=100 byte
print_pgtbl: 0 - 512
00000000: 80000003
00000004: 80000002
Page Number: 0 -> Frame Number: 3
Page Number: 1 -> Frame Number: 2
================================================================

Time slot 60: CPU thực thi lệnh write 102 1 20 của process m0s

===== PHYSICAL MEMORY AFTER WRITING =====
write region=1 offset=20 value=102
print_pgtbl: 0 - 512
00000000: 80000003
00000004: 80000002
Page Number: 0 -> Frame Number: 3
Page Number: 1 -> Frame Number: 2
================================================================
===== PHYSICAL MEMORY DUMP =====
BYTE 00000240: 102
===== PHYSICAL MEMORY END-DUMP =====
================================================================

Time slot 61: CPU thực thi lệnh write 102 1 1000 của process m0s

===== PHYSICAL MEMORY AFTER WRITING =====
write region=2 offset=1000 value=1
print_pgtbl: 0 - 512
00000000: c0000000
00000004: 80000002
Page Number: 0 -> Frame Number: 0
Page Number: 1 -> Frame Number: 2
================================================================
===== PHYSICAL MEMORY DUMP =====
BYTE 00000240: 102
BYTE 000003e8: 1
===== PHYSICAL MEMORY END-DUMP =====
================================================================

Simple Operating System