L-5.9: What is Paging | Memory management | Operating System

Summary

This script explains the concept of paging in memory management, where a process is divided into fixed-sized pages that fit into frames of main memory. It uses process P1, sized 4 bytes with a page size of 2 bytes, to illustrate how the process is split into two pages and mapped into main memory frames. The script details the importance of matching page and frame sizes for efficient memory use and introduces the Memory Management Unit (MMU), which translates logical addresses generated by the CPU into physical addresses using page tables. It also discusses the binary numbering system's role in addressing and the process of mapping logical addresses to physical addresses to fetch data.

Takeaways

• 📚 Paging is a memory management technique where a process is divided into fixed-size pages that fit into frames of main memory.
• 🔢 The script uses a process 'P1' with a 4-byte size and a page size of 2 bytes, resulting in 2 pages for the process.
• 📉 The main memory is depicted as 16 bytes, requiring 8 frames of 2 bytes each, aligning with the page size for efficient memory usage.
• 📈 The number of frames is calculated by dividing the total memory size by the frame size, emphasizing the importance of matching page and frame sizes.
• 🧭 The CPU is unaware of the paging structure and requires a method to locate the correct byte within main memory, introducing the need for address mapping.
• 🗺️ The Memory Management Unit (MMU) is responsible for converting the CPU's logical address into a physical address using page tables.
• 📝 Each entry in the page table corresponds to a page in the process, indicating the frame in which that page is stored.
• 🔑 The logical address generated by the CPU consists of a page number and an offset within the page, crucial for locating the correct byte.
• 🔄 The process of accessing a byte involves translating the logical address to a physical address, which includes determining the frame number and frame offset.
• 🔢 The script explains the binary representation of addresses, emphasizing the need for the same number of bits for page offsets and frame offsets.
• 🔍 A simple example illustrates the process of the CPU requesting a byte, accessing the page table, locating the frame, and fetching the byte from the correct position in memory.

Q & A

What is the purpose of paging in memory management?

Paging in memory management is used to split a process into equally sized pages that can be inserted into the frames of main memory, allowing efficient allocation and utilization of memory.

What is the process size and page size in the given example?

In the example, the process size (P1) is 4 bytes and the page size is 2 bytes.

How many pages does a process have if its size is 4 bytes and the page size is 2 bytes?

A process of 4 bytes with a page size of 2 bytes will have 2 pages.

Why should the page size and frame size be the same in a paging system?

Page size and frame size should be the same to ensure that a page can fit into a frame without any fragmentation, allowing for compact storage and retrieval.

How many frames are there in a 16-byte main memory with a frame size of 2 bytes?

With a main memory size of 16 bytes and a frame size of 2 bytes, there would be 8 frames.

What is the significance of binary numbering in the context of memory addresses?

Binary numbering is used to represent memory addresses in a compact form, starting from 0, which is crucial for mapping and accessing bytes within pages and frames.

What is the role of the Memory Management Unit (MMU) in a paging system?

The Memory Management Unit (MMU) is responsible for converting the logical address generated by the CPU into an absolute address using page tables, facilitating the retrieval of data from main memory.

How does the CPU know which frame a particular byte is located in?

The CPU uses the logical address, which consists of a page number and a page offset, to access the page table. The page table then provides the corresponding frame number where the byte is located.

What is the difference between a logical address and a physical address?

A logical address is the address generated by the CPU that consists of a page number and an offset, while a physical address is the actual memory location where the data is stored, consisting of a frame number and a frame offset.

How many bits are required to represent the physical address in a 16-byte main memory?

In a 16-byte main memory, 4 bits are required to represent the physical address, with 3 bits for the frame number and 1 bit for the frame offset.

Why is it important for the bits of page offset and frame offset to be the same?

The bits of page offset and frame offset must be the same to ensure that the sequence and positions of bytes within a page are maintained when they are mapped to a frame in main memory.

Outlines

00:00

📚 Paging and Memory Management Basics

This paragraph introduces the concept of paging in memory management, where a process is divided into fixed-size pages that fit into frames of main memory. The example given has a process size of 4 bytes with a page size of 2 bytes, resulting in two pages. The main memory is 16 bytes, and the number of frames is calculated by dividing the memory size by the frame size, which is also 2 bytes. The paragraph emphasizes the importance of matching page and frame sizes for efficient memory utilization and the role of the CPU in executing the process without awareness of the paging structure.

05:06

🔍 Address Mapping and Memory Management Unit (MMU)

The second paragraph delves into the process of address mapping, where the CPU's request for a specific byte is translated into an absolute address in main memory. It explains the role of the Memory Management Unit (MMU) and page tables in this translation. The MMU uses the page table, which contains entries for each page of the process, to convert the logical address generated by the CPU into a physical address. The example illustrates how bytes from a process are stored in different frames and how the MMU locates the correct byte by using the page table.

10:06

📝 Logical and Physical Addressing in Paging

This paragraph explains the distinction between logical and physical addresses in the context of paging. It discusses how the CPU generates a logical address based on the page size and the number of pages, and how this address is then converted into a physical address that points to the exact location in main memory. The explanation includes the binary representation of addresses and the calculation of the number of bits required to represent different ranges of numbers, emphasizing the importance of the page number and page offset in accessing the correct byte.

15:07

🔢 Understanding Logical and Physical Address Conversion

The fourth paragraph focuses on the conversion process from logical to physical addresses. It provides a detailed explanation of how the CPU's request for a byte is translated into a physical address using the page table. The paragraph clarifies the concept of frame number and frame offset, and how they are represented in binary to form the physical address. The example demonstrates the process of accessing a specific byte by first identifying the page number and then locating the frame within that page.

20:14

🗂️ Page Table Usage and Data Fetching

This paragraph describes the use of page tables in mapping logical addresses to physical addresses and the process of fetching data from main memory. It explains how the CPU's request for a byte is handled by consulting the page table to find the corresponding frame number, and then accessing the correct byte within that frame. The paragraph also provides an example of how the CPU's address for a byte is represented and converted to locate the data in main memory.

25:18

🔄 Bit Sequence and Physical Address Formation

The final paragraph discusses the importance of maintaining the sequence of bits when forming physical addresses. It emphasizes that the bits representing the frame number and frame offset must remain unchanged to ensure accurate data retrieval. The paragraph concludes with a brief overview of the entire process, from the CPU's generation of a logical address to the MMU's role in mapping it to a physical address and fetching the required byte.

Keywords

💡Paging

Paging is a memory management technique used in operating systems to allocate memory to processes. In the context of the video, paging involves splitting a process into fixed-size units called pages. These pages are then mapped into frames in the main memory. The video explains that the process size is 4 bytes and the page size is 2 bytes, resulting in two pages per process. Paging is crucial for efficient memory utilization and isolation of processes.

💡Process

A process in computing is an instance of a program that is being executed by the system. In the video, 'process P1' refers to a specific process with a size of 4 bytes. The process is the entity that is being managed by the memory management system, and its size and structure are important for determining how it is divided into pages and how those pages are mapped into memory.

💡Page

In the context of the video, a page is a unit of data storage in a computer's virtual memory. The video describes how a process is divided into pages, each of which is 2 bytes in size. Pages are the basic unit of data that are moved between the main memory and secondary storage, and they are managed by the paging system.

💡Frame

A frame, as explained in the video, is a unit of storage in the main memory that corresponds to a page in virtual memory. The video mentions that the main memory is divided into frames, each of which is 2 bytes in size, to accommodate the pages. Frames are the physical storage locations in the memory where the pages are loaded.

💡Memory Management Unit (MMU)

The Memory Management Unit (MMU) is a hardware component that facilitates the translation of logical addresses generated by the CPU into physical addresses in the main memory. The video emphasizes the role of the MMU in the paging system, where it uses page tables to map virtual addresses to physical addresses, allowing the CPU to access the correct data in memory.

💡Page Table

A page table is a data structure used in the paging system to map virtual addresses to physical addresses. The video explains that each process has its own page table, which contains entries for each page in the process. The page table entry for a page indicates the frame in which that page is stored in the main memory.

💡Logical Address

A logical address is the address generated by the CPU when it requests data from memory. The video describes how the CPU generates a logical address, which consists of a page number and an offset within the page. This logical address is then translated by the MMU into a physical address using the page table.

💡Physical Address

A physical address is the actual address of a byte in the main memory. The video explains the conversion process from a logical address to a physical address, which involves determining the frame number and the offset within that frame. The physical address is used by the system to access the data in the main memory.

💡Byte Addressable

The term 'byte addressable' refers to the ability of a memory system to access memory at the byte level. The video mentions that main memory is byte addressable, meaning that each byte can be individually accessed. This is important for the paging system, as it allows for precise control over where each byte of data is stored and retrieved.

💡Mapping

Mapping, in the context of the video, refers to the process of converting a logical address generated by the CPU into a physical address that can be used to access data in the main memory. The video explains that this mapping is done by the MMU using page tables, which associate virtual addresses with physical addresses.

Highlights

Paging divides a process into equally sized pages for main memory frames.

Process P1 is 4 bytes, with a page size of 2 bytes, resulting in 2 pages.

Process P1 is split into pages 0 and 1, each containing bytes 0-1 and 2-3.

Main Memory is 16 bytes, with page and frame sizes kept the same for compatibility.

The number of frames is calculated by dividing memory size by frame size, resulting in 8 frames.

Main Memory is byte-addressable, meaning it represents memory through bytes.

CPU is unaware of the paging strategy and requests data by byte number.

Mapping is required to convert the CPU-generated address into an absolute address.

Memory Management Unit (MMU) performs address mapping using page tables.

Page tables have entries equal to the number of pages in a process.

Logical addresses generated by the CPU consist of a page number and a page offset.

Physical addresses represent the location in main memory, with bits allocated for frame number and frame offset.

MMU converts logical addresses to physical addresses to fetch data from the correct frame.

A simple example demonstrates how the CPU requests byte 1, which is mapped to byte 5 in Main Memory.

Page tables are essential for mapping logical addresses to physical addresses in memory.

The MMU ensures that the correct byte is fetched from Main Memory based on CPU requests.

Transcripts

So in Paging we split a process into equally sized pages and insert it into the frames of main memory

Let's assume we have a process P1 whose process size is 4 bytes and page size is 2 bytes

So total size of the process, as we have assumed, is 4 bytes and size of a single page is 2 bytes

And number of pages per process will be 4/2 bytes whose answer is 2 bytes

Now I have shown it here that the process P1 is split into two pages 0 and 1 in which the numbers 0, 1, 2 and 3

We have seen before

So there are 4 bytes in the process

If we start numbering the bits as per binary system because binary numbering starts from 0

I have represented these bytes (here) as 2 bytes per page thus dividing the process

So in Main Memory too

We have 16 byte Main Memory

And we have discussed earlier

On why page size and frame size should be same

So that if we divide a process into pages then one of the pages can be taken and fitted in the frame in compact

Means the page should fit in the frame as it is

So that's why we have taken the page size and frame size same always

The number of frames can be calculated by dividing the memory size (16 Bytes) by the frame size (2 Bytes)

That I have already represented here

But always remember that number of frames (here) is 8 and whenever we start binary numbering or even in arrays

We have numbered the pages 0-7

Now what is it representing internally?

We have 16 Bytes of Main Memory which means I can store data upto 16 bytes

Now I have just named these bytes

We know that Main Memory is Byte Addressable

Which means we represent the memory through bytes only

That is whenever CPU demands

Now we easily take the bytes out and give to the CPU through which we get to be proved that

This is just a representation of dividing process into pages and Memory into frames

Here remember an important point that

CPU has started executing P1

When CPU is executing P1 there arises a problem that

CPU doesn't know that you have created process pages and fitted them into memory frames

Whenever CPU executes a process it just calls the data or instructions of the process

Means, among the bytes 0,1,2 and 3 of P1 if CPU says

This byte - But

Where is it actually? It is in the Main Memory in pages form as we have seen that

So here let's say

What I am doing is let's say these

The blocks or frames 1 and 2 are already filled

So the Page 0 of P1 has come here and Page 1 of P1 has come here

Let's say this one is also filled

Let us fill these frames too so that you will get cleared on the concept of inserting data into frames

So we have assumed that Page 0 and Page 1 of P1 has been inserted into Frame 2 and Frame 4 of the Main Memory respectively

Which implies the bytes 0 and 1 of P1 have occupied the places of bytes 4 and 5 of Frame 2 and bytes 2 and 3 of P1 have occupied the places of bytes 8 and 9 of Frame 4

And that the bytes in P1 have been stored in their respective places in Main Memory

Now irrespective of the knowledge about our paging strategy CPU is simply asking for byte 3 of P1

So if we want to give byte 3 to CPU from Main Memory it may be allocated anywhere in random which means it can be stored anywhere in the Main Memory

Now here we need Mapping

The address generated by the CPU

That is not the Absolute address

CPU needs data from here but it has generated the address 3. So I need such a technique which converts the address of 3 to address to 9 and give me that data

This is what we call as Mapping

This Mapping is getting done by the Memory Management Unit (MMU)

The MMU converts the address generated by the CPU into Absolute address

For this conversion the MMU uses Page Tables

You can check it out how

Every

If every process has pages then I need more than one page tables

We use a simple concept here

We are creating page table of P1 and how many entries will it have?

How many entries will a page table have? It is the number of pages in the process

In the sense how many pages are in P1?

Then how many entries will be here?

This entry is Page 0

Now where is Page 0, look at it carefully, where is it? In frame 2 of Main Memory

So what does it contain? The frame number

So whenever I want to access a page of a process I will get to know of the frame number from which I will fetch its data

Likewise I will access Page 1 of P1 from Frame 4

Now if the CPU asks for any byte, for example byte 3 here, we don't know where it is located

First of all we have to locate the page number of byte 3

So that I can go to that page, let's say it is located either at Page 0 or at Page 1

If it is at Page 1 then I should check Frame 4 and fetch the data

Now how does it work? CPU generates the address called Logical Address, which is very important point

Made of two factors

How much is the page size?

How many bits do we need to represent two bytes?

If we have two numbers, what may be the numberNs?

How many bits do I require to represent 0 and 1? Only 1

One is 0 and other is 1

Similarly let's say we have total 8 numbers

8 numbers means the numbers that I have are 0 to 7

If I have 8 numbers the numeric range I have now is from 0 to 7

So zero is represented as 000 and seven is represented as 111 which shows that I need at most 3 bits to represent numbers of this range

But if I want to represent numbers beyond 8 I need 4 bits

The numbers in 0 to 7 are 8

And to represent this numeric range

A very important point on numbers on which we are discussing, say, we have 16 numbers

My numeric range is between 0 and 15

If 15 is the largest number of the range then it is represented with 4 bits (ie) 1111

We are not talking about values but the numbers are 16 in the range

If 15 is the largest number of the range then it is represented with 4 bits

If my page size is 2 bytes then I need only 1 bit to represent it

Here I have Page number and given number of Pages per process is also 2. So I only need 1 bit to represent it (ie) 0 and 1

If I have 2 bits 0 and 1 I need only 1 bit space to represent it and we are given space here

Now the point is the CPU generated address is 3

So to represent 3 in Binary

I have written the page number here as 1

Here the main point is I have to access the Page 1 of the page table in P1

We have 2 bytes in each page

I have to select zeroth byte or first byte

I have reached the Page number but I have to choose among the zeroth byte or the first byte to fetch

That is represented in this byte where I have written 1 which means I have to select the second byte

This might be a little confusing but one point to remove it is we should start numbering from 0

For example if I have 2 rows of students where there are 2 students at row 0: student 0 and student 1

Start numbering from 0 now here for byte 3 we have to go to page 1 and access the second byte

To represent second byte we use 1 in Binary numbering

In the sense if we go to Page 1 we select second byte in it (ie) byte 1 and yes we have fetched this byte

To fetch this byte we have to convert logical address to absolute address

Means I have to convert the logical address 3 to absolute address 9

To convert to 9 we have to use

As we discussed earlier that logical address generated by CPU should be converted into physical address

Now that I know about logical address which consists of page number and page offset

Let's see about physical address

Physical address represents the location of the byte to be searched

The number of bits to represent the physical address depends on the size of the Main Memory

Memory address is byte addressable so nothing to be done as byte is minimum

Let's take 16. To represent 16 in binary we need 4 bits as discussed before

So total bits of physical address is 4 bits

In this the first one represents frame number and the next one represents frame offset

Frame offset means frame size

To represent 2 bytes we need 1 bit in the sense

And if you have an iota of doubt you can check

8 numbers in 0-7 where for 0 it is 000 and for 7 it is 111 so in total we need 3 bits which is used here

Total bits to represent physical address are 4 in number in which 3 of them are for frame number and 1 is for frame offset or frame size

So pay attention here that the address 3 generated by CPU has to be converted into physical address 9

To convert we know we have to go to frame 4 in page 1 of P1

It is given page 1 and in there we have frame 4 which we accessed too

Here we accessed the page 1 successfully

How do we represent 4 in binary?

Frame 4 is theoretical but CPU takes only binary values as per which 4 is represented as 100

And frame offset which means frame size

Moreover the bits of page offset and frame offset should be same always

Because if we want the second page of page 1 of P1 then it will also be located in the second position in the respective frame

This is a simple concept

In this page this is first roll number and this is second roll number

So if we shift places of these two to right here then their places will be retained as it is here too

Here without changing their sequence we shifted their places to somewhere which is unknown distant

So in normal terms I need the second byte and in binary terms I need the byte 1 from the frame 4

This represents frame 1 and not frame 0

Therefore I will fetch data from byte 9 and give it to CPU

So it is summarised that CPU generates the logical address

CPU just tells the byte number it needs which we should convert into logical address to access the page number which again should be converted into physical address to access the frame number

Now let's review this concept even faster with a simplest example

CPU says I need byte 1

It needs byte 1

Now that the CPU has generated the address of byte 1 how can we represent it?

If we have two bit space for representation we represent it as 01

Which means

We need byte 1 in page 0 (ie) this one which we wanted

After we went to the page table to check the page 0, it says that it is located at frame 2 in Main memory to which we bounced again

In that, I need to pick the byte 5

We got to know that it is located at frame 2 in which 2 can be represented as 010 in binary

2 can be represented as 010 when represented in 3 bits

And this bit will remain as it is of page offset as we are not changing the sequence of the bits

So can you guess what value comes in decimal?

Now I will get the data from the same location as that of byte 5

So we need Page tables to map from logical address to physical address of a byte

Now after CPU generates a byte address, we find the corresponding page numbers in which we see the corresponding frame number to which we jump and fetch the required byte and give it to the CPU back

And the mapping from 1 to 5 is done by the Memory Management Unit and how?

Just remember this always

Which byte in it

There are two factors in physical address

These two bits will not change because

Bytes are placed as it is without any change