<span class="text_page_counter">Trang 1</span><div class="page_container" data-page="1">

1

HANOI UNIVERSITY OF SCIENCE AND TECHNOLOGY

<b>SCHOOL OF INFORMATION AND COMMUNICATION TECHNOLOGY</b>

<b>MINI PROJECT REPORT</b>

Group 14

Phùng Đình Gia Huy20214960Nguyen Quốc Trung20214976Phan Vĩnh Đăng

Hoàng Duy Anh

2021495520214944

</div><span class="text_page_counter">Trang 2</span><div class="page_container" data-page="2">

The proposed study aims to develop an illustration program that demonstrates the method of memory allocation using Paging. Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory. This scheme permits the physical address space of a process to be noncontiguous, which makes the process of swapping more efficient and simplifies the management of memory. The illustration program will provide a visual representation of how paging works, making it easier for users to understand the concept. The development of this program will contribute to the field of computer science education by providing a practical tool for learning about memory management in operating systems.

1. Memory Translation with Paging strategies – Page Table...4

2. Page Replacement Algorithms in Operating System...5

</div><span class="text_page_counter">Trang 3</span><div class="page_container" data-page="3">

<b>I. Introduction</b>

Memory management is a critical aspect of computer systems, influencing performance, multi-tasking capabilities, and overall system efficiency. One of the widely used memory management techniques is ‘Paging’, a method that allows memory to be non-contiguous, thereby optimizing usage and simplifying memory allocation. Despite its significance, the concept of Paging can be challenging to grasp, particularly for those new to computer science.

This paper introduces an illustration program designed to visually demonstrate the process of memory allocation using Paging. The program aims to provide an interactive and engaging way to understand this complex concept, but in an pretty easy way as to make it accessible to a broader audience. By bridging the gap between theoretical understanding and practical application, this program hopes to enhance learning and contribute to computer science education.

Firstly, we will go through some fundamental knowledge about this topic:

1. Physical Memory:

Physical memory refers to the actual hardware RAM (Random Access Memory) installed on the motherboard. It’s the memory you can touch, unlike virtual memory, which is a method of creating memory by swapping data between RAM and a hard drive.

2. Logical Memory:

Logical memory, also known as virtual memory, is an abstract layer that gives programs the impression they have contiguous working memory (an address space), independent of the underlying physical memory structure. It allows each program to act as if it has exclusive use of the main memory.

3. Paging:

Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory. This scheme permits the physical address space of a process to be non-contiguous, which makes the process of swapping more efficient and simplifies the management of memory. In paging, the physical memory is divided into fixed-size blocks called page frames, which are the same size as the pages used by the process.

4. Page Frame:

A page frame is a fixed-sized block in physical memory space. In the context of paging, the physical memory is divided into fixed-size blocks called page frames. These are the same size as the pages used by the process. When a process requests memory, the operating system allocates one or more page frames to the

</div><span class="text_page_counter">Trang 4</span><div class="page_container" data-page="4">

process and maps the process’s logical pages to the physical page frames.

5. Page:

A page, also known as a memory page or virtual page, is a fixed-length contiguous block of virtual memory. It is described by a single entry in a page table of an operating system. It is the smallest unit of data for memory management in an operating system that uses virtual memory. In paging, memory is divided into fixed-size blocks called pages, and processes are allocated memory in terms of these pages

These concepts are integral to understanding how memory management works in computer systems, particularly in the context of this topic.

<b>II. Method</b>

1. Memory Translation with Paging strategies – Page Table

Memory is one of the most important host resources. For workloads to access global system memory, we need to make sure virtual memory addresses are mapped to the physical addresses. The physical address space is your system RAM, the memory modules inside your ESXi hosts, also referred to as the global system memory. When talking about virtual memory, we are talking about the memory that is controlled by an operating system, or a hypervisor like vSphere ESXi. Whenever workloads access data in memory, the system needs to look up the physical memory address that matches the virtual address. This is what we refer to as memory translations or mappings.

To map virtual memory addresses to physical memory addresses, page tables are used. A page table consists of numerous page table entries (PTE).

</div><span class="text_page_counter">Trang 5</span><div class="page_container" data-page="5">

One memory page in a PTE contains data structures consisting of different sizes of ‘words’. Each type of word contains multiple bytes of data. Executing memory translations for every possible word, or virtual memory page, into physical memory address is not veryefficient as this could potentially be billions of PTE’s. We need PTE’s to find the physical address space in the system’s global memory, so there is no way around them.To make memory translations more efficient, we use page tables to group chunks of memory addresses in one mapping. Looking at an example of a DWORD entry of 4 bytes;A page table covers 4 kilobytes instead of just the 4 bytes of data in a single page entry. For example, using a page table, we can translate virtual address space 0 to 4095 and say this is found in physical address space 4096 to 8191. Now we no longer need to map all the PTE’s separately and be far more efficient by using page tables.

2

.

Page Replacement Algorithms in Operating System

In an operating system that uses paging for memory management, a page replacement algorithm is needed to decide which page needs to be replaced when a new page comes in.

A page fault happens when a running program accesses a memory page that is mapped into the virtual address space but not loaded in physical memory. Since actual physical memory is much smaller than virtual memory, page faults happen. In case of a page fault, Operating System might have to replace one of the existing pages with the newly needed page. Different page replacement algorithms suggest different ways to decide which pageto replace. The target for all algorithms is to reduce the number of page faults.

These are the Page Replacement Algorithms which are used in the study:1. First-In-First-Out (FIFO): This is the simplest page replacement algorithm. In

FIFO, the operating system keeps track of all pages in memory in a queue, with theoldest page at the front. When a page needs to be replaced, the page at the front of the queue is selected for removal.

2. Least Frequently Used (LFU): LFU is a caching algorithm where the least

frequently used cache block is removed whenever the cache is overflowed. In LFU,the system checks the old page as well as the frequency of that page. If the frequency of the page is larger than the old page, it cannot be removed. 3. Least Recently Used (LRU): LRU is a page replacement algorithm where the

page to be replaced is the one that has not been used for the longest time. It workson the principle of locality of reference, which states that the paged that were accessed recently are more likely to be accessed again in the near future.

</div><span class="text_page_counter">Trang 6</span><div class="page_container" data-page="6">

4. Most Recently Used (MRU): The MRU algorithm replaces the page that has been used most recently. This algorithm is useful in situations where the older an item is,the more likely it is to be accessed.

5. Second Chance (or Clock) Algorithm: This is a variant of the FIFO algorithm. It uses a circular queue and gives a “second chance” to pages. If a page is selected for replacement but its reference bit is set (indicating it was recently used), it is given a second chance, and its reference bit is cleared. The page to be replaced is the one that has not been used since its last consideration.

III. Program description

1. Variables and Functions used in all 5 programs

<b>-</b>Variables and Constants:

Variables like page_fault_count, maximum_no_frame, free_frame andpage_hit are used to keep track of page faults, maximum frames as well asavailable free frames and page hits, respectively.

struct Page; struct Proc: These structs are used to represent a page and aprocess, respectively. These structs are distinct to each other in differentalgorithms.

• Proc swap_frames: This function takes a process Proc, a new page ID, and an old page ID. It swaps the frame information between the old and the new pages and return the updated process.

• void draw_frames: This function prints a visual representation of the physical memory frames and the associated page numbers.

• Function main():

The main simulation loop allows users to input page access requests. For each request, the program checks if the requested page is already present in physical memory. If the page is present, it is a page hit, and relevant information is displayed. In case of a page fault, the program allocates the page to an available frame. However, when it comes to the situation the physical memory is full, each program of each algorithm has its own wayto handle. Users can interactively input page access requests until they decide to quit by entering -1. The program provides visual feedback on each step, displaying the state of physical memory and relevant information about page hits and faults.

2.1. FIFO

</div><span class="text_page_counter">Trang 7</span><div class="page_container" data-page="7">

- struct Proc: Manages the page table and the eviction queue for the process. - page_table: Vector of pages representing the process's address space. - evict: Queue storing the recent access history of pages.

- struct Page: Represents a page in the process with attributes:

- occupied: Indicates whether the page is present in physical memory.

- frame_number: Stores the frame number in physical memory where the page is stored.

- struct Page: Represents a page in the process with attributes:

- occupied: Indicates whether the page is present in physical memory.

- frame_number: Stores the frame number in physical memory where the page is stored.

- update_hit:

This function is used when a page hit occurs, i.e., a requested page is found in memory. It increments the evict value of the hit page, indicating that the page has been accessed one more time.

- update_replace:

This function is used when a page needs to be replaced. It finds the page with the smallest evict value that is currently in memory (i.e., its occupied flag is true) and replaces it with the new page. After the swap, it resets the evict value of the replaced page to 0.

- Function main():

If physical memory is full, it triggers a page replacement by evicting the least frequently

</div><span class="text_page_counter">Trang 8</span><div class="page_container" data-page="8">

- struct Page: Represents a page in the process with attributes:

- occupied: Indicates whether the page is present in physical memory.

- frame_number: Stores the frame number in physical memory where the page is stored.

- update_hit:

This function is used when a page hit occurs, i.e., a requested page is found in memory. It removes the hit page from its current position in the eviction queue and moves it to the end, indicating it was recently used.

- struct Page: Represents a page in the process with attributes:

- occupied: Indicates whether the page is present in physical memory.

- frame_number: Stores the frame number in physical memory where the page is

</div><span class="text_page_counter">Trang 9</span><div class="page_container" data-page="9">

stored.- Function main():

If physical memory is full, it triggers a page replacement by evicting the most recently used page.

2.5. Second Chance (Clock)

- struct Proc: Manages the page table and the eviction queue for the process. - page_table: Vector of pages representing the process's address space. - evict: Vector storing pages.

- struct Page: Represents a page in the process with attributes:

- occupied: Indicates whether the page is present in physical memory.

- frame_number: Stores the frame number in physical memory where the page is stored.

- referenced: Flags whether the page has been recently referenced.

- update_replace: This function is used when a page needs to be replaced. It takes a Proc structure and a page ID as parameters. The function removes the first page from the evict vector and adds the new page to the end of the vector.

- Function main():

If physical memory is full, it triggers a page replacement by evicting the page that has notbeen used since its last consideration.

</div><span class="text_page_counter">Trang 10</span><div class="page_container" data-page="10">

1

IV. Task assignment

</div><span class="text_page_counter">Trang 11</span><div class="page_container" data-page="11">

1

V. Conclusion

In conclusion, the development of an illustration program for memory managementusing the Paging method has been explored. This program serves as a practical tool forunderstanding the complex process of memory allocation in operating systems. Byvisually representing how Paging works and allowing users to interact with the memorylayout, the program makes the concept of Paging more accessible and comprehensible.The use of such an illustration program can significantly enhance learning incomputer science, particularly in the areas of operating systems and memorymanagement. Future work could extend this program to illustrate other memorymanagement techniques or show more complex and in-depth techniques to illustratemore complicated memory management such as page sharing or multi-level paging.

</div><span class="text_page_counter">Trang 12</span><div class="page_container" data-page="12">

1

VI. Reference

[1]. GeeksforGeeks. Belady’s Anomaly in Page Replacement Algorithms. Retrieved from <small>