# :writing_hand: ==LECTURE OPERATING SYSTEM (CONT.)==
## :pushpin: Chapter :seven: : Memory Management
:::info
:book: Các vấn đề phát sinh khi quản lý bộ nhớ
* Chuyển đổi địa chỉ tương đối trong chương trình thành các địa chỉ tuyệt đối / địa chỉ thực lưu trữ trong bộ nhớ chính - `Address binding (Relocation)`.
* Quản lý bộ nhớ đã cấp phát và chưa cấp phát.
* Các kỹ thuật cấp phát bộ nhớ sao cho:
* Ngăn chặn các tiến trình xâm phạm đến vùng nhớ đã cấp phát cho các tiến trình khác.
* Cho phép nhiều tiến trình có thể dùng chung một phần bộ nhớ của nhau.
* Mở rộng bộ nhớ để có thể lưu trữ được nhiều tiến trình đồng thời.
:::
### I. Fundamentals
#### 1. Address space - `không gian địa chỉ ảo / vật lý`
* **Virtual (or logical) address** - `địa chỉ ảo (địa chỉ logic)`: generated by CPU (là những địa chỉ do bộ xử lý CPU tạo ra và thao tác) thường được đánh từ 1 đến kích thước vùng nhớ.
* **Virtual address space** - `không gian địa chỉ ảo của tiến trình`: all logical addresses (program address space) $\to$ là tập hợp tất cả các địa chỉ ảo của một tiến trình (không gian địa chỉ chương trình).
* **Physical address** - `địa chỉ vật lý`: actual addresson physical(or main) memory $\to$ là địa chỉ thực trong bộ nhớ chính, địa chỉ vật lý còn gọi là địa chỉ tuyệt đối / địa chỉ thực.
* **Physical address space** - `không gian địa chỉ vật lý của tiến trình`: all physical addresses (memory address space) $\to$ là tập hợp tất cả các địa chỉ vật lý tương ứng với các địa chỉ ảo.
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434473348_441135001637734_2672448044906028571_n.png?_nc_cat=108&ccb=1-7&_nc_sid=5f2048&_nc_ohc=0gngNlBD0LcAb7nzJ3D&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QHbhOAmmKJCNFUaXjwpUhqNA6h4bEdrsS2o_xwKoPOvrg&oe=6645DABA></center>
:::spoiler Tại sao các chương trình phải làm việc dựa trên địa chỉ ảo ?
**++Đáp án:++** Tại vì thực tế khi trình biên dịch hoặc CPU làm việc với không gian địa chỉ của tiến trình, trình biên dịch hay CPU không thể biết được các vị trí mà tiến trình nạp vào bộ nhớ chính nằm ở đâu. Chỉ có MMU mới có thể xử lý được việc chuyển đổi và tìm kiếm các địa chỉ ô nhớ phù hợp để nạp chương trình vào bộ nhớ chính.
:::
#### 2. Address binding (Relocation)
* Thông thường, các chương trình lưu trữ trên đĩa cứng đều là dạng file thực thi nhị phân (binary execuable file). Để có thể được thực thi thì chương trình phải được mang vào bộ nhớ chính, một process sẽ được tạo ra để đảm nhận việc thực thi này. Tùy thuộc vào trình quản lý bộ nhớ được sử dụng trong hệ thống, process có thể được di chuyển qua lại giữa disk và memory trong suốt quá trình thực thi của nó.
* Các địa chỉ trong ô nhớ có thể được biểu diễn dưới nhiều kiểu khác nhau theo các bước như sau. Các địa chỉ trong source code có dạng symbolic (kí tự - là các biến, hằng, con trỏ, ...). Trình biên dịch sẽ tự động kết nối các symbolic address này vào các địa chỉ tương đối (là nhưngx địa chỉ trong chương trình thực thi dưới dạng file nhị phân execuable code sau khi được biên dịch tùy từng ngôn ngữ). Tiếp theo, bộ linker hoặc loader sẽ lại liên kết chuyển đổi các địa chỉ tương đối này tới các địa chỉ thực tuyệt đối trong bộ nhớ chính. Việc liên kết chuyển đổi này có thể xảy ra và được hoàn thành tại một trong những thời điểm sau:
* **Thời điểm biên dịch - `Compile time`**: Nếu tại thời điểm biên dịch, ta có thể biết chính xác vị trí mà tiến trình sẽ được nạp vào trong bộ nhớ, trình biên dịch có thể phát sinh ngay mã tuyệt đối (absolute code) trỏ thẳng tới các địa chỉ tuyệt đối (address code). Tuy nhiên, nếu về sau có sự thay đổi vị trí của tiến trình trong chương trình, cần phải biên dịch lại chương trình.
* Ví dụ: các chương trình .com chạy trên hệ điều hành MS-DOS có mã tuyệt đối ngay khi biên dịch.
* **Thời điểm nạp - `Load time`**: Nếu tại thời điểm biên dịch, ta chưa thể biết được vị trí chính xác mà tiến trình sẽ được nạp vào bộ nhớ thì trình biên dịch chỉ phát sinh mã tương đối (relocatable code) sử dụng các địa chỉ tương đối (relocatable address). Khi nạp chương trình vào trong bộ nhớ, hệ điều hành sẽ chuyển các địa chỉ tương đối thành các địa chỉ tuyệt đối do đã biết vị trí bắt đầu lưu trữ tiến trình còn nếu không thì quá trình chuyển đổi liên kết này sẽ bị kéo dài cho đến khi nào ta biết vị trí bắt đầu tiến trình, tức là thời điểm để nạp chương trình vào bộ nhớ chính. Khi có sự thay đổi vị trí lưu trữ, cần nạp lại chương trình để thực hiện lại việc chuyển đổi địa chỉ, không cần biên dịch lại chương trình.
* **Thời điểm thực thi - `Execution time`**: Nếu có nhu cầu di chuyển tiến trình từ vùng nhớ này sang vùng nhớ khác trong quá trình tiến trình xử lý, thì việc chuyển đổi địa chỉ sẽ được thực hiện vào lúc tiến trình thực thi. Chức năng chuyển đổi địa chỉ do phần cứng cung cấp gọi là MMU (Memory Management Unit). Các hệ điều hành thường dùng việc chuyển đổi theo cách này.
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434189556_784901460241954_8848592225058063847_n.png?_nc_cat=110&ccb=1-7&_nc_sid=5f2048&_nc_ohc=yNHMHR0ZGOUAb5hSWf0&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdWuRs5nd5jyixajpiORYUdIwjJlTGVt-4sq8f7Fyfpr5g&oe=6645E8CF></center>
:::spoiler Xem thêm
* Mapping from one address space to another address space.
* Address binding can be done using:
* Thời điểm biên dịch - `Compile time`
* Thời điểm nạp - `Load time`
* Thời điểm thực thi - `Execution time`
:::
#### 3. Memory Management Unit (MMU)
* Khi chương trình nạp vào bộ nhớ, các địa chỉ tương đối trong chương trình được CPU chuyển thành địa chỉ ảo, khi thực thi, địa chỉ ảo được hệ điều hành kết hợp với phần cứng MMU chuyển thành địa chỉ vật lý. Tóm lại chỉ có khái niệm địa chỉ ảo nếu việc chuyển đổi địa chỉ xảy ra vào thời điểm xử lý, khi đó tiến trình chỉ thao tác trên các địa chỉ ảo, địa chỉ vật lý chỉ được xác định khi thực hiện truy xuất bộ nhớ vật lý.
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434391529_783234457097941_2033426814948802534_n.png?_nc_cat=101&ccb=1-7&_nc_sid=5f2048&_nc_ohc=zC4GcVjB2OMAb4E79Xu&_nc_oc=Adh8slaE0QFFc9L--o9yCMBQrBC9EhKNCHFfQVrIpF5tXZ5u9g0JLF0SPqgWnR9o4VeZTZXKwgxhRuBlRMWPCu2P&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFPD8YzYMpXkG0vHktlqG0NUwQAmyaZ86LYdj5G-_FHkw&oe=6645DA5F></center>
* Tất cả các user program đều không bao giờ nhìn thấy địa chỉ vật lý thực của bộ nhớ, chúng chỉ làm việc với logical address mà thôi. Việc chuyển đổi từ logical address sang physical address được thực thi bởi phần cứng. Vị trí cuối cùng của địa chỉ bộ nhớ vật lý được trỏ đến sẽ không được xác định cho tới khi hoàn tất việc chuyển đổi.
* Trong chương trình MMU, giá trị trong sổ đăng ký lại được thêm vào mọi địa chỉ được tạo ra bởi quá trình người dùng tại thời điểm nó được gửi đến bộ nhớ.
* Chương trình sử dụng thỏa thuận với địa chỉ logic, nó không bao giờ nhìn thấy các địa chỉ vật lý thực.
* Ví dụ: Consider a simple scheme which is a generalization of the base-register scheme
* The base register now called relocation register
* The value in the relocation register is added to every address generated by a user process at the time it is sent to memory
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434799197_7404052809684441_3939608058995401533_n.png?_nc_cat=108&ccb=1-7&_nc_sid=5f2048&_nc_ohc=M5t0sLmL1TMAb4pv7jw&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdXctxTD0eiz3b6sKZv5jd7mOZfyl9j_-ElQDw9IAOFXLw&oe=66462F75></center>
#### 4. Memory management
* Allocation / Deallocation
:::spoiler Xem thêm
* Hệ điều hành cần lưu trữ thông tin về phần bộ nhớ đã cấp phát và phần bộ nhớ chưa cấp phát. Nếu đã cấp phát thì cấp cho tiến trình nào. Khi cần cấp phát bộ nhớ cho một tiến trình thì làm sao tìm được phần bộ nhớ trống thích hợp nhanh chóng và khi bộ nhớ bị phân mảnh thì cần dồn bộ nhớ lại để tận dụng bộ nhớ và để tiến trình thực thi nhanh hơn.
:::
* Address binding (Relocation): mapping địa chi ở vùng không gian này sang địa chỉ ở vùng không gian khác.
* Protection: trong hệ thống đa chương, hệ thống sẽ chứa nhiều tiến trình tại một thời điểm, hệ điều hành cần đảm bảo rằng vùng nhớ của các tiến trình này không được truy cập bất hợp lệ vào tiến trình khác.
* Sharing: chia sẻ các vùng nhớ dùng chung bởi nhiều tiến trình.
---
:::success
:book: Có hai mô hình dùng để cấp phát bộ nhớ cho một tiến trình là:
* **Cấp phát liên tục**: tiến trình được nạp vào một vùng nhớ liên tục.
* **Cấp phát không liên tục**: tiến trình được nạp vào một vùng nhớ không liên tục.
:::
### II. Contiguous Memory Allocation - `Cấp phát vùng nhớ liên tục`
:::info
:notebook_with_decorative_cover: Chú ý thêm đây là phần mô hình hoạt động còn trong bài giảng chỉ bàn về các chiến lược để cấp phát tiến trình nạp vào vùng nhớ liên tục.
Có hai mô hình cấp phát bộ nhớ liên tục là: mô hình **Linker - Loader** hoặc mô hình **Base & Limit**.
:::spoiler Xem thêm
1. Mô hình **Linker - Loader**
* Chương trình được nạp vào một vùng nhớ liên tục đủ lớn để chứa toàn bộ chương trình. Hệ điều hành sẽ chuyển các địa chỉ tương đối về địa chỉ tuyệt đối (địa chỉ vật lý) ngay khi nạp chương trình, theo công thức: ==`địa chỉ tuyệt đối = địa chỉ bắt đầu nạp đầu tiên + địa chỉ tương đối`==
* Ví dụ: xét chương trình P.exe có lệnh JUMP 0X200. Giả sử chương trình được nạp tại địa chỉ 0X300, khi đó địa chỉ tương đối 0X200 sẽ được chuyển thành địa chỉ vật lý là: 0X200 + 0X300 = 0X500
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434746559_749832303938188_1092341227289639093_n.png?_nc_cat=102&ccb=1-7&_nc_sid=5f2048&_nc_ohc=VF6b6etbLv8Ab7NRec5&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QHHqaO1kVRI6ACBSv70iJZilQ_IyjDgBKNAGh9_5rPm_A&oe=66471622></center>
* Chương trình khi nạp vào trong bộ nhớ cho thực thi thì được gọi là tiến trình, vậy trường hợp này các địa chỉ trong tiến trình là địa chỉ tuyệt đối, còn địa chỉ trong chương trình là địa chỉ tương đối.
* Nhận xét:
* Vì việc chuyển đổi địa chỉ chỉ thực hiện vào lúc nạp nên sau khi nạp không thể di chuyển tiến trình trong bộ nhớ.
* Do không có cơ chế kiểm soát địa chỉ mà tiến trình truy cập, nên không thể bảo vệ một tiến trình bị một tiến trình khác truy xuất bộ nhớ của tiến trình một cách trái phép.
2. Mô hình **Base & Limit** (giống với Address Protection)
* Giống như mô hình **Linker - Loader** nhưng phần cứng cần cung cấp hai thanh ghi, một thanh ghi nền (base register) và một thanh ghi giới hạn (límit register). Khi một tiến trình được cấp phát vùng nhớ, hệ điều hành cất vào thanh ghi nền địa chỉ bắt đầu của vùng nhớ cấp phát cho tiến trình, và cất vào thanh ghi giới hạn kích thước của tiến trình.
* Khi tiến trình thực thi, mỗi địa chỉ ảo (địa chỉ ảo cũng chính là địa chỉ tương đối) sẽ được MMU so sánh với thanh ghi giới hạn để đảm bảo tiến trình không truy xuất ngoài phạm vi vùng nhớ được cấp cho nó. Sau đó địa chỉ ảo được cộng với giá trị trong thanh ghi nền để cho ra địa chỉ tuyệt đối trong bộ nhớ.
* Nhận xét:
* Có thể di chuyển các chương trình trong bộ nhớ vì do tiến trình được nạp ở dạng địa chỉ ảo, khi tiến trình được di chuyển đến một vị trí mới, hệ điều hành chỉ cần nạp lại giá trị cho thanh ghi nền, và việc chuyển đổi địa chỉ được MMU thực hiện vào thời điểm xử lý.
* Có thể có hiện tượng phân mảnh ngoại vi (external fragmentation). Có thể áp dụng kỹ thuật "dồn bộ nhớ" (memory compaction) để kết hợp các mảnh bộ nhớ nhỏ rời rạc thành một vùng nhớ lớn liên tục, tuy nhiên cần đòi hỏi nhiều thời gian xử lý.
* Vấn đề nảy sinh khi kích thước của một tiến trình tăng lên trong quá trình xử lý mà không còn vùng nhớ trống gần kề để mở rộng vùng nhớ cho tiến trình. Có hai cách giải quyết:
* **Dời chỗ tiến trình:** di chuyển tiến trình đến một vùng nhớ khác đủ lớn để thỏa mãn nhu cầu tăng trưởng của tiến trình.
* **Cấp phát dư vùng nhớ cho tiến trình:** cấp phát dự phòng cho tiến trình một vùng nhớ lớn hơn yêu cầu ban đầu của tiến trình.
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434785516_1179133499840654_3780879031886823631_n.png?_nc_cat=110&ccb=1-7&_nc_sid=5f2048&_nc_ohc=vSDBmFBM9MEAb7dsiIF&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QElJIH9OXyBnsCT_BZZnOe9HZE2iabCR4SjwTXPNaJd-A&oe=66473AD7><p>
<b>Dành chỗ trống để tiến trình có thể phát triển trong mô hình cấp phát liên tục</b>
</p></center>
Tiến trình luôn được lưu trữ trong bộ nhớ suốt quá trình xử lý của nó nên tính đa chương sẽ bị hạn chế bởi kích thước bộ nhớ và kích thước của các tiến trình trong bộ nhớ. Giải pháp là khi tiến trình bị khóa (đợi tài nguyên, đợi một sự kiện, ...) hoặc tiến trình sử dụng hết thời gian CPU dành cho nó, nó có thể được chuyển tạm thời ra bộ nhớ phụ (đĩa, ...) và sau này được nạp trở lại vào bộ nhớ chính để tiếp tục xử lý (kỹ thuật swapping).
:::
#### 1. Characteristics
* Process: indivisible and must be loaded into a contiguous partition in the main memory.
* (Physical / Main) memory: divided into different partitions before (fixed - partitions) or during(variable partitions) process loading.
#### 2. Fixed - partitions
* Fixed-partitions:created before process loading.
* Partition size may not be suitable to the process' needs.
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/437940656_1477274313212432_8452966860100562891_n.png?_nc_cat=109&ccb=1-7&_nc_sid=5f2048&_nc_ohc=dgufznbk7-8Ab6e_kwg&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdV0x7WleprblLOXmIVOUTn8Wdoc4YGx5w1FjuIq9Go7nw&oe=6645DBAA></center>
#### 3. Variable - partitions
* Variable partitions: created during process loading
* Hole: block of available memory
* Partition allocated to a process is fit for the process' needs.
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434716126_1592316628222458_2239139739196799829_n.png?_nc_cat=111&ccb=1-7&_nc_sid=5f2048&_nc_ohc=Cpj3Q4GDpqgAb6G6h1G&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdWjGmJl7TUqVotSsrnJ9wbaAYbSOgH1CXYyW7kMy8TvWA&oe=6645F5BE></center>
#### 4. Memory Allocation Strategies
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/432407360_455144456945726_2016824446903979318_n.png?_nc_cat=100&ccb=1-7&_nc_sid=5f2048&_nc_ohc=58p6KMvuGi4Ab711fkv&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdXWwj8o5HfNxzL4LcX0LnR-6XojSxxbxqb6U049oqeznA&oe=6645DFAE></center>

* **First - fit**: the process will be placed in the **first** free space which can contain it (chọn đoạn trống đầu tiên đủ lớn).
* **Best - fit**: the process will be placed in the **smallest** free space which can contain it (chọn đoạn trống nhỏ nhất nhưng đủ lớn để thỏa mãn nhu cầu).
* **Worst - fit**: the process will be placed in the **largest** free space which can contain it (chọn đoạn trống lớn nhất).
#### 5. Address Protection
* **Reallocation register** (base register): lower physical address limit (address min) of the memory region occupied by the process while it is executing.
* **Limit register** : upper physical address limit (address max) of the memory region occupied by the process while it is executing.
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434710090_1086523522648614_1088210264371798807_n.png?_nc_cat=103&ccb=1-7&_nc_sid=5f2048&_nc_ohc=EPzpl5U6mN8Ab6P5Uoc&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QGjexx9AGm-osarSyoFFh8WeZmsHE7UD1b1BGyKLj6YhA&oe=6645E43F></center>
#### 6. Address Binding
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434883617_478810127832770_7594968037438646661_n.png?_nc_cat=108&ccb=1-7&_nc_sid=5f2048&_nc_ohc=J3ER8TOi-FIAb4nZnjL&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFvs77zR4pxxprULhAsHyO2eXIp88ZGp2fjIIBN6MfViw&oe=6645EBC3></center>

### III. Swapping
#### 1. Principles
* Process can be swapped in and out between memory and backing store (fast disk).
* Purpose: increasing the number of processes loading into the main memory at the same time $\to$ swapping process in backing store region.
* Reason: trong hệ thống đa chương, kích thước của main memory là giới hạn, không thể nào nạp hết tất cả tiến trình vào hệ thống giới hạn. Chúng ta sẽ cần một phân vùng hỗ trợ thêm một phân vùng đặc biệt ngoài bộ nhớ phụ (secondary memory) có kích thước lớn hơn main memory rất nhiều.
* Disadvantages: truy xuất ổ đĩa rất chậm (vì kích thước truy xuất lớn) và CPU không thể nào thao tác với các dữ liệu nằm trên ổ đĩa được (CPU chỉ thao tác trên registers, cache, CPU memory hay main memory)
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434437238_1255104745894421_2316439559651077534_n.png?_nc_cat=105&ccb=1-7&_nc_sid=5f2048&_nc_ohc=99qSzpiMUDgAb6KnwPq&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdURziKXe5R5jRzL4Dazn9Zt0Lhp69_QWvgrx_hLgF3xkA&oe=6645D7B0></center>
* Backing store: là một phần vùng đặc biệt nằm trên ổ đĩa ngoài (secondary memory - fast disk) dành riêng cho việc swapping. Tất cả các tiến trình hay dữ liệu của người dùng không được nằm trong vùng backing store này, chỉ có những tiến trình đang được thực thi trên CPU mới nằm trên backing store. Tiến trình nào đang xử lý bởi CPU bắt buộc phải đẩy vào main memory, tiến trình nào đó không được xử lý bởi CPU thì đẩy vào backing store để chờ CPU xử lý.
#### 2. Memory Management with Bitmap
* Memory is divided into allocation units (several bytes or kilobytes), each of them is managed by a bit in the bitmap:
* **0**: free unit
* **1**: occupied unit
<center><img src = https://examradar.com/wp-content/uploads/2019/03/Memory-Management-with-Bitmap.png?x60543></center>
#### 3. Memory Management with Linked List
* Memory allocation is managed by a linked list of segments:
* **H**: free segment (hole between two processes).
* **P**: occupied segment by a process.
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434757602_763320222568682_4219017809411277626_n.png?_nc_cat=101&ccb=1-7&_nc_sid=5f2048&_nc_ohc=WWCf_sH9S14Ab7X45kJ&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_AdWfLXVz1iZWIXffmJ8yl03Dub_sY3ywtYWpS-fS-9jp0A&oe=6646099F></center>
* Trước khi tiến trình X kết thúc, có 4 trường hợp có thể xảy ra và khi tiến trình X kết thúc, hệ điều hành cần gom những nút trống gần nhau.
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434692886_1179903013392273_5607718406045980009_n.png?_nc_cat=111&ccb=1-7&_nc_sid=5f2048&_nc_ohc=cPa9A61yQcYAb6pSKQC&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFmf-FHVoSwhWsWvOB3RHYiWNj729F-OBNXOeJpTSfWOA&oe=6646DB6D></center>
#### 4. Swap Time
* Assume that:
* Process ${\bf P}_1$: $1024$ MBs
* Transfer rate between memory and backing store : $50$ MBs/s
* Total swap time $= 2 \times ( \displaystyle \frac{1024}{50}) = 40.96$ (s)
### IV. Issue: Fragmentation
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434409413_397830593215216_8325805772508258355_n.png?_nc_cat=110&ccb=1-7&_nc_sid=5f2048&_nc_ohc=_fpG0535tzkAb5j-f5o&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QHECPjXY5R6udr6DG404vMojbMAIrscAN1fAndlbfcAeA&oe=6645E6B0></center>

#### 1. External Fragmentation - `Phân mảnh ngoại vi`
* Hiện tượng phân mảnh ngoại vi gặp trong trường hợp cấp phát động, bộ nhớ không được chia thành các phân vùng với kích thước cố định mà các phân vùng sẽ được hình thành loading các tiến trình vào bộ nhớ chính.
* **External Fragmentation** : free spaces are not contiguous to contain another process (là hiện tượng tổng vùng nhớ trống đủ để thỏa mãn yêu cầu, nhưng các vùng nhớ này lại không liên tục nên không đủ để cấp cho một tiến trình khác).
* **Solution**: memory compaction - `kỹ thuật dồn bộ nhớ`
* Technique used to combine free memory spaces into a larger free space.
:::spoiler Giải thích
* Khi gặp hiện tượng external fragmentation, có thể áp dụng kỹ thuật "dồn bộ nhớ" để kết hợp các mảnh bộ nhớ nhỏ rời rạc thành một vùng nhớ lớn liên tục, tuy nhiên kỹ thuật này đòi hỏi nhiều thời gian xử lý.
* Ví dụ: sự phân mảnh ngoại vi của bộ nhớ, các tiến trình liên tục ra vào bộ nhớ, sau một thời gian dài sẽ để lại các vùng nhớ nhỏ mà không thể chứa bất kỳ tiến trình nào.
:::
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434480312_1815291088980081_691631926289085597_n.png?_nc_cat=104&ccb=1-7&_nc_sid=5f2048&_nc_ohc=ESXmZn5BdrgAb791MKo&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QEg-wN59hPTs2Q2Oz_58QDoMsvx3bQSyVHx3_cFuYRU5g&oe=6645FFEF></center>
#### 2. Internal Fragmentation
* Hiện tượng phân mảnh nội vi gặp trong trường hợp cấp phát tĩnh, tức là bộ nhớ đã chia sẵn thành các phân vùng với kích thước cố định.
* **Internal fragmentation**: internal partition allocated to a process can not be used for another process.
* **Solution:** best-fit allocation (chọn đoạn trống nhỏ nhất nhưng đủ lớn để thỏa mãn nhu cầu chứa tiến trình đó).
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434732701_1111346810085019_9165232818703915899_n.png?_nc_cat=100&ccb=1-7&_nc_sid=5f2048&_nc_ohc=9UyPmEsBsiUAb4TyY51&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFki2qiU3Dy_Ds2RxHNQamijweyKD0xtQVIa0ToAI0Y_g&oe=6645EAE1></center>
---
## :pushpin: Chapter :eight: : Virtual Memory
### I. Fundamentals
#### 1. Basic definitions
* The entire program needs to be in memory to execute.
* **Dynamic linking** - linking ís delayed until execution time.
* **Static loading** - system libraries and program code combined by the loader into the binary program image.
* **Dynamic loading** - load postponed until execution time.
* Routine is not loaded until it is called.
* Better *memory-space utilization*; unused routine is never loaded.
* All routines kept on disk in relocatable load format
* Useful when large amounts of code are needed to handle infrequently occurring cases
* No special support from the operating system is required
* Implemented through program design
* *OS can help by providing libraries to implement dynamic loading*
* Small piece of code, stub, used to locate the appropriate memory-resident library routine
* Stub replaces itself with the address of the routine, and executes the routine
* Operating system checks if routine is in the memory address space of the process
* If not in address space, add to address space
* Dynamic loading is particularly useful for libraries
* System also known as *shared libraries*.
* Consider applicability to patching system libraries.
* Versioning may be needed.
* **Overlays**
* Only some parts of a process that are currently executing will be loaded into memory.
* Chương trình sẽ thực thi từng overlays (mỗi overlays sẽ bao phủ một phần của chương trình) một (sẽ nạp tuần tự overlays vào main memory) $\to$ lập trình viên cần phải thiết kế làm sao để ứng với từng overlays có thể bao phủ chương trình trọn vẹn và cho ra một kiến trúc phù hợp nhất.
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434841962_1135558664137383_5073149182127224920_n.png?_nc_cat=111&ccb=1-7&_nc_sid=5f2048&_nc_ohc=zJ284GTVwQsAb6aOeuW&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QE9zHHlG2Bbf6zn5Q2QkLy8z8itvkiC9mDTV1ASUT3tEw&oe=66472C84></center>
$\implies$ Đây là những khái niệm cơ bản để chúng ta có thể giúp hệ thống cho phép một tiến trình không cần phải nằm toàn bộ vào bộ nhớ chính để thực thi mà chỉ có thể nằm một phần trong main memory, phần còn lại chưa được thực thi thì nằm trong backing store của ổ đĩa (bộ nhớ ảo).
#### 2. Virtual Memory
* Không gian bộ nhớ ảo chia tiến trình thành nhiều trang nhỏ $\to$ chỉ nạp những trang cần thực thi vào physical memory thông qua memory map, những trang không cần thực thi thì sẽ lưu trữ trong backing store sau khi không thể mapping vào physical memory.
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434705653_1728550814220638_642112997923399672_n.png?_nc_cat=101&ccb=1-7&_nc_sid=5f2048&_nc_ohc=1GdB0KlBzYkAb5FFLLb&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QHiMkdX0LONCAHU27OfDvAMMBoOfJb_KmXIVr1OKCMYUQ&oe=66473D2A></center>

#### 3. Non - contiguous Memory Allocation
* Process is divided into different parts and loaded into various memory partitions, which can be **non-contiguous**.
* Two fundamental techniques: **Segmentation** (liên quan đến lập trình viên nhiều hơn) and **Paging** (có sự hỗ trợ của hệ thống và phần cứng hệ thống).
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434518834_1169673801119262_2996167817633093987_n.png?_nc_cat=103&ccb=1-7&_nc_sid=5f2048&_nc_ohc=swdyxkLzqOgAb5GQaHV&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFIIBaGmaQ9_hZqYBAViUNtpR8ANT3AuYiX2DwUtEzJ3Q&oe=6647591F></center>
### II. Segmentation
#### 1. Principle
* A process is divided into segments (varying in size) and loaded in non-contiguous partitions in the memory.
* Two registers associated: **base** and **limit**
* **Base** (Relocation): the starting physical address of the segment $\to$ lưu vị trí địa chỉ đầu tiên
* **Limit**: length of the segment $\to$ kiểm soát kích thước.
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434492951_1117471486213469_1851317887882359710_n.png?_nc_cat=102&ccb=1-7&_nc_sid=5f2048&_nc_ohc=Z0Gznwk2u-IAb63a8r3&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QG-SAtebMX3nbSadQpCAZd3MdQYGpHavBfzxlfW7JCh9A&oe=6647524E></center>
#### 2. Address Binding and Protection
* Logical address contains two parts: **`<s: segment number, d: offset>`**
* Offset: relative address within a segment, ranges from **0 to (limit – 1)**
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434912389_738774971762167_3852092999725422141_n.png?_nc_cat=101&ccb=1-7&_nc_sid=5f2048&_nc_ohc=0jHJsCA-C8gAb7pO8lI&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QEbBXfqshNviqSZXBk4z4EF0RriLbu_31rfAPmdcZa-0Q&oe=66472E01></center>
* **Segment Table**
* Used for segment - memory mapping
* Each table entry contains base and limit values of a segment.
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434682011_1551294008840767_4978198708122238460_n.png?_nc_cat=111&ccb=1-7&_nc_sid=5f2048&_nc_ohc=H7dryuPrFugAb4EGQCr&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFg48ntFhpvZwaZtU0rnUyp_mudnS2BGUEzeoJckfTJvQ&oe=66475ED2></center>
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434716123_383302588018506_6189380658751158720_n.png?_nc_cat=107&ccb=1-7&_nc_sid=5f2048&_nc_ohc=2jDQc-40BJYAb7SOw4X&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QE92epAh83YyM2luNVnSbdHrgDmKjy5DyoaC9AvK7RnkQ&oe=664740FC></center>
### III. Paging
#### 1. Priciples
##### a. Memory Allocation with Paging
* Process divided into fixed-size pages (page là trong virtual memory space)
* Memory divided into fixed-size frames (frame là trong physical memory space)
* A page will be loaded into one frame
* Page size = Frame size (This size is defined by computer systems)
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/435855061_806762021358980_4309436130146028969_n.png?_nc_cat=101&ccb=1-7&_nc_sid=5f2048&_nc_ohc=ViA47N_QZBUAb7oEGkJ&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QGStW1Y_SoDR46978r60JAdjPWMR0GnWes6ERFAk5WW0Q&oe=6647470D></center>
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434837332_769251251968974_6678345439508610742_n.png?_nc_cat=106&ccb=1-7&_nc_sid=5f2048&_nc_ohc=smqV-Qg0f9cAb4dNHI5&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QErbXKLVSypBfl93Oc_uiO2mbLtAI6mHMyxP8BlbxPqVA&oe=6647618A></center>
##### b. Logical and Physical Address
* Logical address contains two parts: **`<p: page number, d: offset>`**
* Offset: relative address within a page, starting at 0
* Physical address contains two parts: **`<f: frame number, d: offset>`**
* Offset: relative address within a frame, starting at 0
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434746559_316106578168065_3126241928644048026_n.png?_nc_cat=107&ccb=1-7&_nc_sid=5f2048&_nc_ohc=CoVvMMq5vHEAb5VEhc9&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QGEqFLEp5B0gVRR_14V3sUcWGwPtIWOgUPXZFvsjWOF2A&oe=664731AF></center>
##### c. Address representation
* A logical address can be represented as:
* **<p, d>**
* **Absolute value** within logical address space
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434729170_1216729859290114_5271685531574232573_n.png?_nc_cat=109&ccb=1-7&_nc_sid=5f2048&_nc_ohc=mzI9K4OeSpIAb6VheoD&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QHvCK6hxejP1u3ig0P_bSA1gVHtp1PHGAV4EHsQ5-m6HA&oe=6647650D></center>
##### d. Logical and Physical Address with Paging
* **Each address points to a byte-addressable in the memory**
*(Note: If memory is word-addressable, each address, generally, points to a 4-byte word)*
$\implies$ Size of a page (and frame): $2^4$ bytes = $16$ bytes
$\implies$ Size of logical address space: $2^{16}$ bytes = $64$ KB
$\implies$ Size of physical memory: $2^{12}$ bytes = $4$ KB
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434877468_1341965806474306_5758075573541118352_n.png?_nc_cat=101&ccb=1-7&_nc_sid=5f2048&_nc_ohc=Qq2C-Tl8DaAAb5BQk_b&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFwXtPNuJjgwKWSTt8zHC7JNxInBt2IDbhww_FRYJwVPg&oe=6647666C></center>
* Paging example for a system that uses:
* Physical memory of $32$ bytes.
* Page size of $4$ bytes.
* $4$ - bit logical address space.
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434773578_432485932663935_4484445760745622812_n.png?_nc_cat=100&ccb=1-7&_nc_sid=5f2048&_nc_ohc=uX2RYI4KLz0Ab6dRphU&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QEhhrPOYMk8uQs7MT5MrTDTKhD3rJMVIo-K-pL1vCnSPg&oe=6647417A></center>
##### e. Address Binding and Protection
* **Page Table**
* Used for page – frame mapping
* A table entry corresponding to a page consists of:
* Page number
* Frame number where the page is found in the memory
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434697532_3715005502103826_910275792865936888_n.png?_nc_cat=106&ccb=1-7&_nc_sid=5f2048&_nc_ohc=gWh_MLadZAcAb63N2vM&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QETmCrc38pHpAkbNs79nGieBlZHQLBwC_1tRfp72jwB4A&oe=66474A1E><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434688261_1570064223537567_5903140641401460889_n.png?_nc_cat=100&ccb=1-7&_nc_sid=5f2048&_nc_ohc=3NkPqiiXWuwAb744c6_&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFaL4XkcDKs0BWIVboUaI4kQkY3BHQ-9SP619SARkTYPg&oe=66476BA3></center>
* Contain page information.
* Depend on the operating system.
* **Frame Number**: Xác định Page Table sẽ nằm ở frame number nào trong physical memory.
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434354129_3241005386196271_532725646284220958_n.png?_nc_cat=103&ccb=1-7&_nc_sid=5f2048&_nc_ohc=EV-RR_DEy74Ab6iuYso&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QGtYZEonWqY0XGabfUUcTwM_pD4LbFc8MSVXEBE0eKL8Q&oe=66474067></center>
* **Valid / Invalid bit (called as Present / Absent bit)**
Các bit này cho biết page đã được load vào main memory hay chưa ? Vì với kỹ thuật virtual memory, không nhất thiết phải nạp toàn bộ các trang của một tiến trình vào main memory, chúng ta chỉ nạp một số pages vào physical memory, một số trang còn lại ở backing store. Vấn đề là CPU chỉ thao tác với main memory, nếu CPU truy cập một page mà page đó nằm ở backing store thì hệ thống phải nạp page đó ở backing store vào main memory $\to$ giải quyết vấn đề CPU nhận biết page nào đang nạp và page nào đang ở backing store.
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434688266_1158932155286442_89678224358817042_n.png?_nc_cat=100&ccb=1-7&_nc_sid=5f2048&_nc_ohc=c4Ai7HmLsaUAb4-A2B1&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QE9AsxItj5y9IhT-YaR3Z-mNFQXt_zNNCZsWsgmS4-u8A&oe=66473701></center>
* **Protection bit (called as Read / Write bit)**
Các bit này chỉ định page này read-only hay là read / write.
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434447775_315928854619593_3881466840423373209_n.png?_nc_cat=106&ccb=1-7&_nc_sid=5f2048&_nc_ohc=mfUMsHyNAFUAb6X6vGG&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QEgBIDWgMR4sIljuDYlc8VJYWlheImBoGQafBI_gsHhOg&oe=6647551E></center>
* **Caching**
Cache là bộ nhớ trong gần với CPU hơn là main memory, nguyên tắc truy cập bộ nhớ là bộ nhớ nào càng gần CPU thì càng có kích thước nhỏ hơn và khả năng truy cập càng nhanh,
Để gia tăng hiệu suất, một vài trường dữ liệu được lưu ở cache để khi CPU cần thì CPU truy cập vào cache, không cần ra bộ nhớ chính.
Những page có quyền caching hay không caching (1 - tức là, page này khi bị truy cập phải yêu cầu CPU phải lấy dữ liệu mới nhất ngoài bộ nhớ chính chứ không phải dữ liệu đang lưu tạm ở cache).
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434713187_458862503200049_7033115038198407085_n.png?_nc_cat=109&ccb=1-7&_nc_sid=5f2048&_nc_ohc=RAVuvvSMDOgAb5MMX5w&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFFKssxdMnIzlcNwszZa21yrk6j1QtJmO5SEt6KOc834g&oe=66476C29></center>
* **Referenced bit** và **Modified bit**
* Hai bit kế tiếp thường được sử dụng khi chúng ta có nhu cầu page replacement.
* Referenced bit: cho biết tại chu kỳ đồng hồ kế trước, page này có được truy cập tới hay không.
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/437858477_765062042305980_1640230433391183942_n.png?_nc_cat=109&ccb=1-7&_nc_sid=5f2048&_nc_ohc=zSwdDWMbCGEAb4pSFQs&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QEFqe1KiubZz7JTmbYmicb7IgVcWWrcDDNhqHqx3VngMw&oe=66473801></center>
* Modified bit (Dirty bit): cho biết page này đã được cập nhật hay chưa.
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434462970_281734578359199_5810538628737443187_n.png?_nc_cat=106&ccb=1-7&_nc_sid=5f2048&_nc_ohc=jBQKQ37A8ZIAb6d-2Go&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QG9FUsMA2tKu3848CXnJIhxMENZSGcNAn1FYQMbS91H6g&oe=66474CAD></center>

##### f. Demand Paging
* Loading only the pages which are currently executing by the CPU into memory
* Swapping zone (backup zone): a portion of hard disk used for containing all pages of active processes in the system
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434823177_2398053737057928_8280976185734458435_n.png?_nc_cat=107&ccb=1-7&_nc_sid=5f2048&_nc_ohc=IvA_DcseJE4Ab4lHQXg&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QF5NRj7da9FSk_QHMVWUZo2qCKfgCKbh_-s9nXVpwGK7g&oe=66474287></center>
##### g. How to know if a page is presented or absent ?
* Verify present/absent bit
* 1 (or V): valid page (i.e., the page has been loaded into the memory)
* 0 (or I): invalid page (i.e., the page is still placed in the swapping zone (fast disk))
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434393039_3119106121555644_2579614575587739620_n.png?_nc_cat=103&ccb=1-7&_nc_sid=5f2048&_nc_ohc=l8RJbOJ_caEAb7quJNL&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QGCLjWksE3ewQ5YcxPOvX4bZyTg9sLQwKHnrb4xRSk1mg&oe=66476183></center>
##### h. Page Fault Handling
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434860810_448744627529890_6961807114921373613_n.png?_nc_cat=105&ccb=1-7&_nc_sid=5f2048&_nc_ohc=eooM8nmsl1UAb5k2_sF&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QH3wqxHvmB9k_tdE9PxskBurfbu6pUhklVqystcVmNjqg&oe=66475E36></center>

##### i. Effective Memory-Access Time (EAT or EMAT)
* Khi hệ thống bị lỗi trang thì hệ điều hành sẽ mất nhiều thời gian dẫn đến tốc độ xử lý chậm hơn đối với một trang đã được nạp sẵn vào bộ nhớ chính.
* Công thức: $${\bf EAT} = ({\bf 1} - {\bf p}) \times {\bf t_m} + {\bf p} \times {\bf t_p}$$
* ${\bf p}:$ page fault ratio (probability of occurring a page fault) ($0 \leq {\bf p} \leq 1$)
* ${\bf t_m}:$ memory-access time
* ${\bf t_p} >> {\bf t_m}:$ page-fault service time (swap-in, swap-out, restart instruction, ...)
* Nhận xét: công thức này dùng để đánh giá hiệu quả khi chúng ta truy xuất một trang mà có nhiều lỗi trang xảy ra, thời gian xử lý truy xuất tăng lên.
##### k. Translation Lookaside Buffers (TLBs) - `Bộ đệm tìm trang`
* **High-speed cache** memory for containing a **few of page table entries**, which have been most **recently or frequently used**.
* Number of entries generally ranges from 64 to 1024 entries
* Page lookup with **TLBs**
* If page number is presented in TLBs (**TLB hit**)
$\to$ No need to access the Page Table for address binding
* If page number is not presented in TLBs (**TLB miss**)
$\to$ Access Page Table for address binding
* Used to reduce Effective memory-access time (EAT)
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/437909435_261802456922844_8471670836256686043_n.png?_nc_cat=111&ccb=1-7&_nc_sid=5f2048&_nc_ohc=BKzBywQJ1-IAb43_Vh-&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QEfoT--V0oUh-WikJyD4j4lc--JSdxtuCdu4jTvFshn7w&oe=66475728></center>
##### l. EAT (or EMAT) with TLBs support
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434529762_778252060922909_5963388573730162263_n.png?_nc_cat=103&ccb=1-7&_nc_sid=5f2048&_nc_ohc=UIPkpkhsrBgAb6eiHfp&_nc_oc=Adg9Xml-8lD1Uv1ShysaaKxWNtAdCagyIH15sp05y1JnBC7X8BwBjx2nJhxUPQ6d-VGU-hUy5omx9_byTyztfoXr&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFB4MQSemxWwOLfgaNQlvFjkIzRCUO96_4Jw8IHP0CZ3A&oe=664756E2></center>

##### m. What if no free frames?
* Kích thước của bộ nhớ vật lý luôn luôn bị giới hạn, số lượng frames còn trống trong physical memory bị giới hạn, và tùy vào tình trạng hiện thời, nếu như tất cả các frames của physical memory đều đã chứa ít nhất một trang của một tiến trình nào đó rồi, không còn free frames. Lúc này, khi CPU cần truy cập đến dữ liệu B nằm trong page 1 mà page này đang invalid, có nghĩa là hệ thống phải ra ngoài backing store nạp page này vào nhưng không còn khung trang trống thì cần nạp làm sao ? $\to$ nhu cầu thay thế trang (Page Replacement) bằng cách chọn một victim page và đẩy victim page đó ra backing store.
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434714664_461710082884336_2116742661194550293_n.png?_nc_cat=103&ccb=1-7&_nc_sid=5f2048&_nc_ohc=LLJYWbNp1XwAb5U9arW&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFoTlMX6ffA4kH0sxOP5cks5Ed84hXGTO-3WHUt_clagg&oe=66474CC4></center>
##### n. Page Replacement
* Which page can be the victim ? $\to$ tùy thuộc vào chiến lược thay thế trang mà hệ thống đó đang áp dụng sẽ chọn ra victim page nào.
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434730846_451734404033809_1374373258395634082_n.png?_nc_cat=110&ccb=1-7&_nc_sid=5f2048&_nc_ohc=JqZAzsUOCVcAb5t32FO&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QHDk-ZDk4fISYI3f2HQ1jqsGMCrdoooEAf8csIpLzgUbg&oe=66476FB3></center>
#### 2. Page Replacement Algorithms
##### a. FIFO
* Based on the principle of “First In First Out”
* Pros: Simplicity
* Cons:
* What if frequently referred pages or system pages moved out?
* Belady’s anomaly: là hiện tượng số lượng lỗi trang có thể tăng lên khi số lượng khung trang sử dụng tăng lên.
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/437851694_406400708853253_3431044949093113530_n.png?_nc_cat=105&ccb=1-7&_nc_sid=5f2048&_nc_ohc=bEKK3GVsnmUAb4pS_3P&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QHgSNkiHbKC-BjC4y4UtpeA5J1xUBaOh_s4IXtg4Z4s8g&oe=66478119></center>
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434470399_5923351767788829_7638923965138868367_n.png?_nc_cat=110&ccb=1-7&_nc_sid=5f2048&_nc_ohc=pvBKn7rXoB0Ab4dJKQv&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFO7jxdOzntcRBkj6ZULkmMdlF9ph6bQHObzoW3BvKA6w&oe=6647813E></center>
##### b. Optimal
* Look at the future, replace the page that will not be referred to for the longest time
* Pros: Best performance
* Cons: How to know the future?
* 9 page faults
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/437876521_3677355699188354_2925393505914974613_n.png?_nc_cat=102&ccb=1-7&_nc_sid=5f2048&_nc_ohc=BQ2jZ1Tyk4AAb4L9ybb&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QHWxUbAowO2Kwq4Cd1WmFQfVtmnvh7YA808Dmc0-VjkbA&oe=66478506></center>
##### c. Least Recently Used (LRU)
* Look at the past, replace the page that has not been referred to for the longest time.
* Pros: Possible implementation
* Cons: Need hardware support
* 12 page faults
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434850317_1121125482258765_2328501932974396566_n.png?_nc_cat=100&ccb=1-7&_nc_sid=5f2048&_nc_ohc=oTsy46N4WQcAb4-7Kme&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QHKJyQqtS-cqPUILN8nNxIn9EOXcgzDKnd84xb7NGr3ug&oe=66476FAF></center>
##### d. Second Chance
* Enhanced version of FIFO
* A page will be given a second chance if its referenced bit is set to 1
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434719181_904896411377033_1795904074564283298_n.png?_nc_cat=110&ccb=1-7&_nc_sid=5f2048&_nc_ohc=-k9ZJalgDW0Ab4wFRT4&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QGrwVGhZp1bv-Cy5pCeNgJvwqcHVtAuGQ8Q7GK41ScQVA&oe=6647759B></center>
##### e. And other ...
* Not Recently Used (NRU)
* Not Frequently Used (NFU)
* WSClock
* ...
##### f. Issue: Thrasing
* **More time paging than executing because page faults occur at a very high rate.**
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434437249_1463577404280592_7385180241209852035_n.png?_nc_cat=111&ccb=1-7&_nc_sid=5f2048&_nc_ohc=SDFOU45ma6AAb4L75rl&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QHbWPg9xGXoodVij2hbGMg6lt_LJAQ1t3DbDkOqht5Cpg&oe=6647641E></center>
#### 3. Paging with Large Address Space
##### a. Issue
* Let’s consider:
* A system with a $64$-bit logical address space
* Page size: $4$KB ($2^{12}$)
$\to$ No. of page table entries may be $2^{64-12} = 2^{52}$ entries
* Assume page table entry size of 4 bytes
$\to$ Page table size can be 254 bytes ~ 16 million GB
* Even in a 32-bit system, page table can have 1 million entries
* Disadvantages :anguished:
* Loading huge page tables into memory ?
* Lookup in a page table consisting of 1 million entries ?
##### b. Hierarchical (or Multilevel) Paging
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/437785210_3862419170652689_4125368605664126806_n.png?_nc_cat=104&ccb=1-7&_nc_sid=5f2048&_nc_ohc=jylCXVmDFPMAb6Ew4qs&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFE3FihPbC18_qdZiqVNApKiMKZQJ7j3HrMDA6IzwXmBQ&oe=664760AB></center>

##### c. Hashed Page Table
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434727673_733408485543114_4861017302865514160_n.png?_nc_cat=104&ccb=1-7&_nc_sid=5f2048&_nc_ohc=hk512pStNywAb7X1VH0&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFynGNN0PpVI71UsiWimevL67j2bgq0V-oE2jPv7RIh0w&oe=66474D30></center>

##### d. Inverted Page Table
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/432484004_1153590648985535_464593311366483429_n.png?_nc_cat=102&ccb=1-7&_nc_sid=5f2048&_nc_ohc=fXmqYiIBwAkAb5mV4QM&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QHFaIULu6BwQ7SfsBGGwLHlbjHUVZxgjL6X6OZWZXrYOg&oe=66474772></center>

---
## :pushpin: Chapter :nine: : I/O Management
### I. Overview
#### 1. Recall: Computer System Structure
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434837333_445406737845354_8061719197025217996_n.png?_nc_cat=107&ccb=1-7&_nc_sid=5f2048&_nc_ohc=qVg0OB1xETUAb5WN2pR&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QEZ1jaTZRqjC6UQ20rs7kOoWtFA6OS3ja_4glxnjc2HAg&oe=664875BF></center>

#### 2. I/O System Layers
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/437851709_928564795416933_586528946875598962_n.png?_nc_cat=102&ccb=1-7&_nc_sid=5f2048&_nc_ohc=ag7NGTY-ijQAb5mxNVI&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QEA-KfaKTeKD7HoHrEtNoACGRDzcpMBG5RsoHlhZp37iQ&oe=66487B7B></center>

#### 3. Recall: Interrupt
* Interrupts are signals emitted by hardware or software to alert an event to the system
* Hardware interrupts are emitted by devices, generally, to inform that they finish their task (e.g., hard drive controller generates interrupt indicating I/O completion).
* Software interrupts are emitted by user programs, generally, when invoking a system call.
* Traps are emitted by the CPU itself to indicate some errors or exceptions.

### II. Principles of I/O Hardware
#### 1. Recall: I/O System Layers
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434088005_741240621455819_7848776764350625575_n.png?_nc_cat=105&ccb=1-7&_nc_sid=5f2048&_nc_ohc=ovtpQm_iavYAb4AZ8e0&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QEaLFt4htTfvvZryT7d8b-UGMc9sB5MUIV9-awEeblkLQ&oe=66486277></center>

#### 2. I/O Devices
* Block devices
* Store and transfer data in fixed-sized and addressable blocks
* E.g.: hard disks, USB
* Character devices
* Accept and transfer data in a stream of characters
* Generally, not addressable and not be stored permanently
* E.g.: keyboards, mice, printers
#### 3. Other I/O device: Clocks (or Timers)
* Clocks are used to maintain the datetime of systems and to synchronize systems activities by causing **clock (timer) interrupts**
* The crystal generates a periodic signal to decrement the counter
* When the counter reaches zero, an interrupt occurs, then the counter is reset from the holding register
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/437608249_1879533822564544_2081391515801360382_n.png?_nc_cat=109&ccb=1-7&_nc_sid=5f2048&_nc_ohc=GDKDNxp_vpkAb6pxKOr&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFmVOpv66qNCxnJiKOyDHYroEfZ6Imjg0D3yWYM6uGaKg&oe=6648669A><p>
<b>A programable interval clock (timer)</b>
</p></center>
#### 4. I/O device structure
* Mechanical component
* The device itself (e.g: monitor, printer, hard disk)
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434737906_1164155271662609_1953220584749659657_n.png?_nc_cat=103&ccb=1-7&_nc_sid=5f2048&_nc_ohc=JBL2A6pHQJQAb52WZHg&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QEKYv4rbwTGi1Ulx6fP2Z0UO_zPiBxBKxqkaz_l7RlipQ&oe=66488374></center>
* Electronic component (Device controller or adapter)
* Consisting of chips, which acts as an intermediate layer between devices and OS
* Integrated into I/O devices or attached to the computer I/O bus
##### 5. Device Controller (or Adapter) Structure
* Contains data buffer and registers
* Data (-in and -out) buffer for storing I/O data
* Status register for storing device status *(command-ready, busy, error)*
* Command (or control) register for storing instructions sent by the CPU
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434751871_287293751091543_4220685824596517855_n.png?_nc_cat=109&ccb=1-7&_nc_sid=5f2048&_nc_ohc=AAPDduBOaJ4Ab7XMC0R&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QEQyn9TdrCk6BI24Y-HxLnTPbgTjjWLB9YQIBArfvTxZg&oe=66487EB3></center>
#### 6. I/O Techniques
##### a. Programmed I/O (Polling)
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434439864_930261098783651_7654939181321003186_n.png?_nc_cat=101&ccb=1-7&_nc_sid=5f2048&_nc_ohc=YiFvup4d_bQAb6VIAG3&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QHEviitVGnw_NSFi4tfWY4eNGuO1oVCj54pX1a6C1A3IQ&oe=66487D3F></center>

##### b. Interrupt-driven I/O
* Interrupt Controller is integrated on the mainboard to detect and to handle interrupts sent by I/O devices
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434732701_732072545764444_3868575387941452192_n.png?_nc_cat=108&ccb=1-7&_nc_sid=5f2048&_nc_ohc=OAdII3Si-pQAb5JoUts&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QH5WYBkfR-jQDxtBd2-OJFnW4DRQgxzkaPcTZDjW-pbOA&oe=664880D8></center>
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/437864716_1575115563283403_7559648730547620878_n.png?_nc_cat=108&ccb=1-7&_nc_sid=5f2048&_nc_ohc=o49OZiiOXcYAb5OUsoZ&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QE02R-cGR3Gwco77zY-xfhqlzGMlF8TPibkRA8P_LD3FA&oe=66488997></center>
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434749095_796879385333532_2840169050452776061_n.png?_nc_cat=110&ccb=1-7&_nc_sid=5f2048&_nc_ohc=oVEbS1OSWs4Ab7B20xr&_nc_oc=Adjzs9C4GTgEoT0g5Lc4vHume7oU2_EPHY30-8IjcOtZolZWIRcf6vRa2mBd93HwvNBb3Kka2kiAvgm4pVAwucDN&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFdfXbGOgqNrWRcEYZqk_HffQNmB49TOKf_LIlkF4YJKg&oe=664871F2><p>
<b>Example of reading data from disks</b>
</p></center>
##### c. Direct Memory Access (DMA)
* DMA is an I/O technique that allows I/O devices to access directly to the memory without CPU intervention
* Require support of DMA controller (i.e., a hardware device integrated into each I/O device or on the motherboard for regulating transfers to various devices)
* DMA controller can interact directly with the memory and I/O devices independent of CPU
* A DMA controller consists of:
* Control register for specifying transfer information (e.g.: I/O port, direction)
* Count register for specifying no. of bytes/words to be transferred
* Memory address registers for specifying the desired address in the memory where data is available (read) or to be stored (write)
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434834892_883783200218884_2779618697501092027_n.png?_nc_cat=102&ccb=1-7&_nc_sid=5f2048&_nc_ohc=R4WwhAFedE0Ab6aLPEn&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QEpP83m7NESJm-ZOfhLKhWyD58UD2IyVzJvKrhF63sAuw&oe=66488C77></center>
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434754618_723757303004379_3651824773552172044_n.png?_nc_cat=107&ccb=1-7&_nc_sid=5f2048&_nc_ohc=zk2V8QF7dy0Ab6do8VE&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QEVEnIMoERWiA_qwQFZh4VZLt7VOTTf5w4s7k95ZzmPvQ&oe=664892C3><p>
<b>Example of reading data from disks</b>
</p></center>
##### d. Example of Reading Data
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434439864_385657950955401_7974910946219384481_n.png?_nc_cat=103&ccb=1-7&_nc_sid=5f2048&_nc_ohc=ObL3tMRHy1YAb5_sjnW&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QE0YkyjagLjmShJQZ-nR6opXb3NuWe80C_lDpSgH1H4Fw&oe=66487ACE></center>
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434448845_455780386895428_158478407532927549_n.png?_nc_cat=105&ccb=1-7&_nc_sid=5f2048&_nc_ohc=APBDKL--0HQAb5cpUtb&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QHjdPR10Kvg9VNt75uWeQ9QK1zW48YRiJd8NAWVmKC_BA&oe=66488CE2></center>
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434557088_1531759190889622_3589134673297290467_n.png?_nc_cat=106&ccb=1-7&_nc_sid=5f2048&_nc_ohc=lhBWE-tETtsAb7ZnEHh&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QHmcDmlVR1ATzyJRFkAZY5WrBQWQjVIKCl2M0hPzEdeFA&oe=66487F26></center>

##### e. Summary
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434777799_949931873581038_440035215713084640_n.png?_nc_cat=105&ccb=1-7&_nc_sid=5f2048&_nc_ohc=thCIsxIIlXkAb6oIOuB&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QH9f7ExNUPYCJ-sJQjKIFuLZXDE8BPg3__TLpjI8fuprg&oe=66489007></center>

### III. Principles of I/O Software
#### 1. Recall: I/O System Layers
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434710087_751159950332261_6835519188511725242_n.png?_nc_cat=111&ccb=1-7&_nc_sid=5f2048&_nc_ohc=irWNIHz9wlsAb6ymNRi&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFesM9LdEzKTZmVlx0BsyQNFAGlsKp_S-QmrL8SzADvsw&oe=66487BDA></center>

#### 2. User level libraries
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434862789_1383002842361704_7398859493649964839_n.png?_nc_cat=107&ccb=1-7&_nc_sid=5f2048&_nc_ohc=-H2_THWRG-UAb42Zkeo&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QExYmoBjkVnU9S8zBoOZCQef5tU6AOnIAqpqOJ4iOcwbw&oe=66486E44></center>

#### 3. Device Drivers
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434700157_729170492756484_4239486332658955212_n.png?_nc_cat=106&ccb=1-7&_nc_sid=5f2048&_nc_ohc=QA7cbBnVQP0Ab6YGIGD&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QElQhyTu5IwVfOl3wkFaypKvFUIgs5RHLM2qBBvWFB1ag&oe=66486B2B></center>

#### 4. Device-Independent (OS) Software
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/437971931_1082110429562992_6736640356753977397_n.png?_nc_cat=102&ccb=1-7&_nc_sid=5f2048&_nc_ohc=pmYsOfjeyYsAb4luzUw&_nc_oc=Adj52VyXIO7eoY_6sGL3ULG-XoN6SjBBmDYqp8NTixSATwl3HjF45hL1P77qjUnC0-_gtUnOqkKZGs3qt1hTNtFG&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFY8Rdy_QjGpoBlcP2uJE7tPlTfkAB1Hg7QIYr2ciaDLQ&oe=664884EB></center>

#### 5. Interrupt Handlers
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434692886_1103468600933636_4396474912866015244_n.png?_nc_cat=107&ccb=1-7&_nc_sid=5f2048&_nc_ohc=24GuvVrtEqMAb6QcGMV&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QG7mEP5fP8hHFgICCfQ4h78ARUTP-SxF5i8OHGTCC9JAg&oe=6648816E></center>