UNIT 4

Memory Management

4.1 Basic bare machine

The vacant Machine and Resident Monitor aren't directly associated with the software system however whereas we tend to study regarding memory management these elements are extremely necessary to check, therefore let’s study them one by one then their operating.

Bare Machine:

So primarily vacant machine is logical hardware that is employed to execute the program within the processor while not exploitation the software system. As of now, we've got studied that we tend to can’t execute any method while not the software system. However affirmative with the assistance of the vacant machine we can try this.

Initially, once the operational systems aren't developed, the execution of Associate in Nursing instruction is finished directly on hardware while not exploitation any intrusive hardware, at that point the sole downside was that the vacant machines acceptive the instruction in mere machine language, thanks to this those one that has decent information regarding laptop field are ready to operate a laptop. Therefore, when the event of the software system vacant machine is noted as inefficient.

Resident Monitor:

In this section, if we tend to state however the code runs on vacant machines, then this component is employed, therefore primarily, the Resident Monitor could be a code that runs on vacant Machines.

The resident monitor works like an Associate in a Nursing software system that controls the directions and performs all necessary functions. It additionally works as a job sequencer as a result of it additionally sequences the task and sends them to the processor.

After programming, the task Resident monitors hundreds of the programs one by one into the most memory in keeping with their sequences. One most significant issue regarding the resident monitor is that once the program execution occurred there the United States of America no gap between the program execution and therefore the process goes to be quicker.

The Resident monitors are divided into four elements:

1. Management Language Interpreter

2. Loader

3. Utility

4. Interrupt the process

Fig 1 – Memory layout

These are explained below.

1. Management Language Interpreter:

The first part of the Resident monitor is a management language interpreter that is employed to browse and do the instruction from one level to a successive level.

2. Loader:

The second {part of| a part of} the Resident monitor that is that the main part of the Resident Monitor is Loader that hundreds all the required system and application programs into the most memory.

3. Device Driver:

The third part of the Resident monitor is a utility that is employed for managing the connecting input-output devices to the system. Therefore primarily it's the interface between the user and therefore the system. It works as an Associate in the Nursing interface between the request and response. Request that user-created, utility responds that the system produces to satisfy these requests.

4. Interrupt Processing:

The one-fourth because the name suggests, it processes the all occurred interrupt to the system.

KEY TAKEAWAY

The vacant Machine and Resident Monitor aren't directly associated with the software system however whereas we tend to study regarding memory management these elements are extremely necessary to check, therefore let’s study them one by one then their operating.

Bare Machine:

So primarily vacant machine is logical hardware that is employed to execute the program within the processor while not exploitation the software system. As of now, we've got studied that we tend to can’t execute any method while not the software system. However affirmative with the assistance of the vacant machine we can try this.

4.2 Resident monitor

In this section, we tend to square measure planning to discuss regarding resident monitor in the operating system or resident monitor in memory management. Just in the case of the resident monitor system, for the memory organization, memory is partitioned off or divided into two partitions.

One among the partition or memory portion having beginning addresses is occupied by the software or OS Code. This software code your time conjointly referred to as kernel or resident monitor. Kernel or a resident monitor is that the real portion wherever all the functionalities of software square measure outlined or coded.

The second memory partition aside from the kernel area or resident monitor area is understood as the user address area. User’s program or application square measure loaded during this portion of memory or user address area.

The user program mustn’t be able to modify one thing into the monitor area of the memory. Thus what we have got an inclination to primarily would love is the protection of the resident monitor or protection of the kernel against any user program.

So however kernel or a resident monitor is protected against the user program?

Fence address is that the boundary address at wherever resident monitor address area ends and user address area starts from the address simply once the fence address. This fence address shields the resident monitor.

Whenever the user program tries to access any of the memory locations and therefore the program will generate the address of the memory location that's to be accessed. This address is generated by the central processor and conjointly grasp as a logical address.

This logical address is compared with the worth of the fence address as shown in the following figure. 

Figure 2: Protection of Monitor Space using fence address.

Must check each memory reference against the fence ( mounted or variable ) in hardware or register.

If the user-generated address or logical address  < fence address, then smuggled access. Or invalid address. This represents that the user program is attempting to access the resident monitor half or kernel.

So a blunder or lure is generated and therefore the access isn't allowed. During this means resident monitor keep safe from a user program.

If the address generated by the central processor or user program address is bigger than the fence address then this can be legitimate access and access is allowed.

KEY TAKEAWAY

In this section, we tend to square measure planning to discuss regarding resident monitor in the operating system or resident monitor in memory management. Just in the case of the resident monitor system, for the memory organization, memory is partitioned off or divided into two partitions.

One among the partition or memory portion having beginning addresses is occupied by the software or OS Code. This software code your time conjointly referred to as kernel or resident monitor. Kernel or a resident monitor is that the real portion wherever all the functionalities of software square measure outlined or coded.

4.3 Multiprogramming with fixed partitions

The earliest and one among the only technique which might be accustomed load quite one processes into the most memory is fastened partitioning or Contiguous memory allocation.

In this technique, most memory is split into partitions of equal or different sizes. The software system invariably resides within the 1st partition whereas the opposite partitions are often accustomed to store user processes. The memory is assigned to the processes in a contiguous approach.

In fastened partitioning,

1. The partitions cannot overlap.

2. A method should be contiguously gifted in a very partition for the execution.

There area unit numerous cons of exploiting this method.

1. Internal Fragmentation

If the scale of the method is lesser than the entire size of the partition some size of the partition gets wasted and stays unused. This is often a wastage of the memory and is referred to as internal fragmentation.

As shown within the image below, the four MB partition is employed to load solely the three MB method and therefore the remaining one MB got wasted.

2. External Fragmentation

The total unused area of varied partitions can not be accustomed load the processes even supposing there's an area on the market however not within the contiguous type.

As shown within the image below, the remaining one MB area of every partition can not be used as a unit to store a four MB method. Although the adequate area is obtainable to load the method, the method won't be loaded.

3. Limitation on the scale of the method

If {the method|the method} size is larger than the scale of most sized partition then that process can not be loaded into the memory. Therefore, a limitation is often obligatory on the method size that's it can not be larger than the scale of the biggest partition.

4. Degree of instruction execution is a smaller amount

By Degree of multiprogramming, we tend to merely mean the most variety of processes that may be loaded into the memory at a similar time. In fastened partitioning, the degree of instruction execution is fastened and less because the scale of the partition can not be varied in line with the scale of processes.

Fig 3 – Contiguous memory allocation

KEY TAKEAWAY

The earliest and one among the only technique which might be accustomed load quite one processes into the most memory is fastened partitioning or Contiguous memory allocation.

In this technique, most memory is split into partitions of equal or different sizes. The software system invariably resides within the 1st partition whereas the opposite partitions are often accustomed to store user processes. The memory is assigned to the processes in a contiguous approach.

4.4 Multiprogramming with variable partitions

In operating systems, Memory Management is the function responsible for allocating and managing the computer’s main memory. Memory Management function keeps track of the status of each memory location, either allocated or free to ensure effective and efficient use of Primary Memory.

There are two Memory Management Techniques: Contiguous, and Non-Contiguous. In Contiguous Technique, the executing process must be loaded entirely in the main memory. Contiguous Technique can be divided into:

1. Fixed (or static) partitioning
2. Variable (or dynamic) partitioning

Variable Partitioning –
 

It is a part of the Contiguous allocation technique. It is used to alleviate the problem faced by Fixed Partitioning. In contrast with fixed partitioning, partitions are not made before the execution or during system configure. Various features associated with variable Partitioning-

1. Initially, RAM is empty and partitions are made during the run-time according to the process’s need instead of partitioning during system configure.
2. The size of the partition will be equal to the incoming process.
3. The partition size varies according to the need of the process so that the internal fragmentation can be avoided to ensure efficient utilization of RAM.
4. The number of partitions in RAM is not fixed and depends on the number of incoming processes and the Main Memory’s size.

Fig 4 – Dynamic partitioning

There are some advantages and disadvantages of variable partitioning over fixed partitioning as given below.

Advantages of Variable Partitioning –

1. No Internal Fragmentation:
   In variable Partitioning, space in main memory is allocated strictly according to the need of the process, hence there is no case of internal fragmentation. There will be no unused space left in the partition.
2. No restriction on Degree of Multiprogramming:
   More processes can be accommodated due to the absence of internal fragmentation. A process can be loaded until the memory is not empty.
3. No Limitation on the size of the process:
   In Fixed partitioning, the process with a size greater than the size of the largest partition could not be loaded and the process can not be divided as it is invalid in the contiguous allocation technique. Here, In variable partitioning, the process size can’t be restricted since the partition size is decided according to the process size.

Disadvantages of Variable Partitioning –

1. Difficult Implementation:
   Implementing variable Partitioning is difficult as compared to Fixed Partitioning as it involves the allocation of memory during run-time rather than during system configure.
2. External Fragmentation:
   There will be external fragmentation despite the absence of internal fragmentation.

For example, suppose in the above example- process P1(2MB) and process P3(1MB) completed their execution. Hence two spaces are left i.e. 2MB and 1MB. Let’s suppose process P5 of size 3MB comes. The space in memory cannot be allocated as no spanning is allowed in contiguous allocation. The rule says that process must be continuously present in the main memory to get executed. Hence it results in External Fragmentation.

Now P5 of size 3 MB cannot be accommodated despite the required available space because in contiguous no spanning is allowed.

KEY TAKEAWAY

In operating systems, Memory Management is the function responsible for allocating and managing the computer’s main memory. Memory Management function keeps track of the status of each memory location, either allocated or free to ensure effective and efficient use of Primary Memory.

There are two Memory Management Techniques: Contiguous, and Non-Contiguous. In Contiguous Technique, the executing process must be loaded entirely in the main memory. Contiguous Technique can be divided into:

1. Fixed (or static) partitioning
2. Variable (or dynamic) partitioning

4.5 Protection schemes

Protection and security need that laptop resources like hardware, software, memory, etc. area unit protected. This extends to the software system similarly because of the information within the system. This could be done by making certain integrity, confidentiality, and handiness within the software system. The system should be a shield against unauthorized access, viruses, worms, etc.

Threats to Protection and Security

A threat could be a program that's malicious and results in harmful effects for the system. A number of the common threats that occur during a system area unit.

Virus

Viruses area unit typically little snippets of code embedded during a system. They're dangerous and might corrupt files, destroy information, crash systems, etc. they will additionally unfold additional by replicating themselves PRN.

Trojan Horse

A bug will on the Q.T. Access the login details of a system. Then a malicious user will use these to enter the system as a harmless being and work mayhem.

Trap Door

A door could be a security breach that will be a gift during a system while not the data of the users. It is exploited to hurt the info or files during a system by malicious folks.

Worm

A worm will destroy a system by exploiting its resources to extreme levels. It will generate multiple copies that claim all the resources and do not permit the other processes to access them. A worm will stop working an entire network during this method.

Denial of Service

This variety of attacks don't permit legitimate users to access a system. It over-whelms the system with requests therefore it's swamped and can't work properly for alternative users.

Protection and Security strategies

The different strategies that will offer shield and security for various laptop systems area unit.

Authentication

This deals with distinguishing every user within the system and ensuring they're WHO they claim to be. The software system makes certain that each user's area unit genuine be-fore they access the system. The various ways in which to form certain that the user's area unit authentic are:

• Username/ positive identification

Each user features a distinct username and identification combination and that they have to be compelled to enter it properly before they will access the system.

• User Key/ User Card

The users have to be compelled to punch a card into the cardboard slot or use their key on a data input device to access the system.

• User Attribute Identification

Different user attribute identifications that may be used area unit fingerprint, eye retina, etc. These area units distinctive for every user and area unit compared with the present samples within the information. The user will solely access the system if there's a match.

Time identification

These passwords offer a great deal of security for authentication functions. A 1-time identification is generated solely for login on every occasion a user desires to enter the system. It can not be used over once. The assorted ways in which a 1-time identification is enforced area unit area unit

• Random Numbers

The system will enkindle numbers that correspond to alphabets that area unit pre-ar-ranged. This mix is modified anytime a login is needed.

• Secret Key

A hardware device will produce a secret key associated with the user id for login. This key will modification anytime.

KEY TAKEAWAY

Protection and security need that laptop resources like hardware, software, memory, etc. area unit protected. This extends to the software system similarly because of the information within the system. This could be done by making certain integrity, confidentiality, and handiness within the software system. The system should be a shield against unauthorized access, viruses, worms, etc.

4.6 Paging

• In Operating Systems, Paging is a storage component used to recover processes from the secondary storage into the main memory as pages.
• The primary thought behind the concept of paging is to isolate each process as pages. The main memory will likewise be partitioned as frames.
• One page of the process is to be fitted in one of the frames of the memory. The pages are supposed to be store at the various locations of the memory however the need is consistently to locate the contiguous frames or holes.
• In this design, the operating system recovers data from secondary storage in same-size blocks called pages. Paging is a significant piece of virtual memory usage in current operating systems, utilizing secondary storage to give programs a chance to surpass the size of accessible physical memory.
• Support for paging has been taken care of by hardware. Nonetheless, ongoing structures have actualized paging by intently coordinating the hardware what's more, operating system, and particularly on 64-bit microprocessors.

Basic Method

• The fundamental technique for actualizing paging includes breaking physical memory into fixed-sized blocks called frames and breaking logical memory into blocks of a similar size known as pages.
• When a process needs to be executed, its pages are stacked into any accessible memory frames from their source (a file system or the support store).
• The backing store is partitioned into fixed-sized blocks that are of a similar size as the memory frames.
• The hardware support for paging is represented in the figure below. Each address created by the CPU is partitioned into two sections: a page number (p) and a page offset (d).

Fig 5 - Paging Hardware

Paging Hardware

• The page number is utilized as a list into a page table. The page table contains the base location of each page in physical memory.
• This base location is joined with the page offset to characterize the physical memory address that is sent to the memory unit. The paging model of memory has appeared in the figure below.

Fig 6 - Paging model of logical and physical memory

• The page size (like the frame size) is characterized by the hardware. The size of a page is regularly a power of 2, differing between 512 bytes and 16 MB for every page, contingent upon the computer architecture.
• The choice of a power of 2 as a page size makes the interpretation of a logical address into a page number and a page offset especially simple.
• If the size of the logical address space is 2m, and page size is 2n addressing units (bytes or words) then the high-request m - n bits of a logical address assign the page number, and the n low-request bits assign the page offset.
• Along these lines, the logical address is as per the following:

Where p is an index into the page table and d is the displacement inside the page.

• Since the operating system is overseeing physical memory, it must know of the assignment subtleties of physical memory-which frames are allotted, which frames are accessible, what number of total frames there are, etc.
• This data is commonly kept in a data structure considered a frame table. The frame table has one section for each physical page frame, demonstrating whether the last mentioned is free or designated and, on the off chance that it is allotted, to which page of which process or processes.

Hardware Support

• The hardware usage of the page table should be possible by utilizing committed registers. Be that as it may, the use or register for the page table is agreeable just if the page table is small.
• On the off chance that the page table contains an enormous number of sections, at that point, we can utilize TLB (translation Look-aside cushion), an extraordinary, little, quick look into hardware cache.
• The TLB is acquainted with fast memory.
• Every passage in TLB comprises of two sections: a tag and a value.
• At the point when this memory is utilized, an item is compared with all tags at the same time. If the item is discovered, at that point comparing value is returned.

Fig 7

Main memory access time = m

If the page table is kept in main memory,

Successful Access time = m(for page table) + n(for specific page in page table)

KEY TAKEAWAY

• In Operating Systems, Paging is a storage component used to recover processes from the secondary storage into the main memory as pages.
• The primary thought behind the concept of paging is to isolate each process as pages. The main memory will likewise be partitioned as frames.
• One page of the process is to be fitted in one of the frames of the memory. The pages are supposed to be store at the various locations of the memory however the need is consistently to locate the contiguous frames or holes.

4.7 Segmentation

• Memory segmentation is a computer (primary) memory management method of division of a PC's primary memory into segments or sections.
• In a computer system utilizing segmentation, a reference to a memory area incorporates a value that distinguishes a segment and an offset (memory area) inside that segment.
• Segments or sections are likewise utilized in object files of compiled programs when they are connected into a program image and when the image is stacked into memory.

• A process is isolated into Segments. The chunks that a program is partitioned into which are not the majority of similar sizes are called segments.
• Segmentation gives the user's perspective on the process which paging does not give.
• Here the user's view is mapped to physical memory.
• There are kinds of segmentation:
  1. Virtual memory segmentation – Each process is partitioned into various segments, not which are all inhabitants at any one point in time.
  2. Simple Segmentation – Each process is partitioned into various segments, which are all stacked into memory at run time, however not continuously.
• There is no straightforward connection between logical addresses and physical addresses in segmentation. A table is maintained to stores the data about all such segments and is called Segment Table.
• Segment Table – It maps two-dimensional Logical address into one-dimensional Physical address. It's each table entry has:
  • Base Address: It contains the beginning physical address where the fragments reside in memory.
  • Limit: It determines the length of the fragment.

Fig 8 – Logical view of segmentation

• Segments, as a rule, compare to regular divisions of a program, for example, singular schedules or data tables so division is commonly more noticeable to the programmer than paging alone.
• Different segments might be made for various program modules, or various classes of memory utilization, for example, code and data portions. Certain segments might be shared between programs.

Why Segmentation is required?

• Till now, we were utilizing Paging as our main memory management system. Paging is more near to the operating system instead of the User.
• It isolates all the processes into the type of pages regardless of the way that a process can have some overall parts of functions which should be stacked on a similar page.
• The operating system couldn't care less about the User's perspective on the process. It might separate a similar function into various pages and those pages could conceivably be stacked simultaneously into the memory. It diminishes the productivity of the system.
• It is smarter to have segmentation which partitions the process into segments. Each segment contains the same sort of capacities, for example, the main function can be incorporated into one segment and the library capacities can be incorporated into the other segment.

Translation of Logical Address into Physical Address

Fig 9 – Logical and physical address

• The address generated by the CPU is partitioned into:
  • Segment number (s): Number of bits required to speak to the portion.
  • Segment balance (d): Number of bits required to speak to the size of the fragment.

Advantages-

• No Internal fragmentation.
• Segment Table consumes less space in contrast with the Page table in paging.

Disadvantages-

• As processes are stacked and expelled from the memory, the free memory space is broken into little pieces, causing External fragmentation.

KEY TAKEAWAY

• Memory segmentation is a computer (primary) memory management method of division of a PC's primary memory into segments or sections.
• In a computer system utilizing segmentation, a reference to a memory area incorporates a value that distinguishes a segment and an offset (memory area) inside that segment.
• Segments or sections are likewise utilized in object files of compiled programs when they are connected into a program image and when the image is stacked into memory.

4.8 Paged segmentation

Pure segmentation is not very popular and not being used in many of the operating systems. However, Segmentation can be combined with Paging to get the best features out of both the techniques.

In Segmented Paging, the main memory is divided into variable size segments which are further divided into fixed-size pages.

1. Pages are smaller than segments.
2. Each Segment has a page table which means every program has multiple page tables.
3. The logical address is represented as Segment Number (base address), Page number, and page offset.

Segment Number → It points to the appropriate Segment Number.

Page Number → It Points to the exact page within the segment

Page Offset → Used as an offset within the page frame

Each Page table contains various information about every page of the segment. The Segment Table contains information about every segment. Each segment table entry points to a page table entry and every page table entry is mapped to one of the pages within a segment.

Fig 10 – Logical address

Translation of logical address to a physical address

The CPU generates a logical address which is divided into two parts: Segment Number and Segment Offset. The Segment Offset must be less than the segment limit. Offset is further divided into a Page number and Page Offset. To map the exact page number in the page table, the page number is added to the page table base.

The actual frame number with the page offset is mapped to the main memory to get the desired word on the page of a certain segment of the process.

Fig 11

Advantages of Segmented Paging

1. It reduces memory usage.
2. Page table size is limited by the segment size.
3. The segment table has only one entry corresponding to one actual segment.
4. External Fragmentation is not there.
5. It simplifies memory allocation.

Disadvantages of Segmented Paging

1. Internal Fragmentation will be there.
2. The complexity level will be much higher as compare to paging.
3. Page Tables need to be continuously stored in the memory.

KEY TAKEAWAY

Pure segmentation is not very popular and not being used in many of the operating systems. However, Segmentation can be combined with Paging to get the best features out of both the techniques.

In Segmented Paging, the main memory is divided into variable size segments which are further divided into fixed-size pages.

1. Pages are smaller than segments.
2. Each Segment has a page table which means every program has multiple page tables.
3. The logical address is represented as Segment Number (base address), Page number, and page offset.

4.9 Virtual memory concepts

• Virtual memory is a memory management functionality of an operating system (OS) that utilizes hardware and software to enable a computer to make up for physical memory deficiencies by incidentally moving data from random access memory (RAM) to disk storage.
• Virtual address space is expanded utilizing active memory in RAM and inactive memory in hard disk drives (HDDs) to frame contiguous addresses that hold both the application and its data.
• Virtual Memory is a storage allocation plot in which secondary memory can be tended to just as it were a piece of main memory.
• The addresses a program may use to reference memory are recognized from the addresses the memory system uses to distinguish physical storage locales, and program created addresses are interpreted consequently to the relating machine addresses.
• The size of virtual storage is constrained by the addressing plan of the computer system and the measure of secondary memory is accessible not by the genuine number of the main storage locations.
• Virtual memory was created when physical memory - the installed RAM - was costly.
• Computers have a limited measure of RAM, so memory can run out, particularly when numerous programs keep running simultaneously.
• A system utilizing virtual memory utilizes a segment of the hard drive to copy RAM. With virtual memory, a system can stack bigger programs or various programs running simultaneously, enabling everyone to work as though it has vast memory and without obtaining more RAM.
• While duplicating virtual memory into physical memory, the OS partitions memory into page files or swap files with a fixed number of addresses. Each page is put away on a disk and when the page is required, the OS copies it from the disk to fundamental memory and makes an interpretation of the virtual addresses into real addresses.
• Current microprocessors expected for universally useful use, a memory management unit, or MMU, is incorporated with the hardware.
• The MMU's main responsibility is to interpret a virtual address into a physical address. A fundamental model is given underneath −

Fig 12 Memory address

• It is a procedure that is actualized utilizing both hardware and software. It maps memory addresses utilized by a program, called virtual addresses computers, into physical addresses in c memory.
  1. All memory references inside a process are logical addresses that are powerfully converted into physical addresses at run time. This implies a process can be swapped all through fundamental memory with the end goal that it involves better places in primary memory at various times throughout execution.
  2. A process might be broken into some pieces and these pieces need not be constantly situated in the main memory during execution. The blend of dynamic run-time address interpretation and utilization of page or portion table allows this.
• On the off chance that these attributes are available, at that point, not every one of the pages or portions do not have to be available in the main memory during execution. This implies the required pages should be stacked into memory at whatever point is required.
• Virtual memory is designed utilizing Demand Paging or Demand Segmentation.

KEY TAKEAWAY

• Virtual memory is a memory management functionality of an operating system (OS) that utilizes hardware and software to enable a computer to make up for physical memory deficiencies by incidentally moving data from random access memory (RAM) to disk storage.
• Virtual address space is expanded utilizing active memory in RAM and inactive memory in hard disk drives (HDDs) to frame contiguous addresses that hold both the application and its data.
• Virtual Memory is a storage allocation plot in which secondary memory can be tended to just as it were a piece of main memory.

4.10 Demand paging

• As per the idea of Virtual Memory, to execute some process, just a piece of the process should be available in the main memory which implies that a couple of pages may be available in the main memory whenever.
• The difficult task is to decide which pages should be kept in the main memory and which should be kept in the secondary memory because we can't state ahead of time that a process will require a specific page at a specific time.
• Subsequently, to beat this issue, there is an idea called Demand Paging is presented. It proposes keeping all pages of the frames in the secondary memory until they are required. That means, it says that don't stack any page in the main memory until it is required.
• Demand paging says that pages should possibly be brought into memory if the executing process requests them. This is frequently known as lazy evaluation as just those pages requested by the process are swapped from secondary storage to main memory.

Fig 13 – Swapping memory

• On the other hand in pure swapping, where all memory for a process is swapped from secondary storage to main memory during the process start execution.
• To implement this process needs a page table is utilized. The page table maps logical memory to physical memory.
• The page table uses a bitwise administrator to stamp if a page is valid or invalid. A valid page is one that is present in the main memory. An invalid page is one that is present in secondary memory.
• At the point when a process attempts to get to a page, the following steps are followed as shown in the figure below:

Fig 14

1. If the CPU attempts to call a page that is as of now not accessible in the main memory, it creates an interrupt showing memory access fault.
2. The OS places the interrupted process in a blocking state. For the execution to continue the OS must call the required page into the memory.
3. The OS will scan for the required page in the logical address space.
4. The required page will be brought from logical address space to physical address space. The page replacement algorithms are utilized for deciding which page is to be replaced with the new page in the physical address space.
5. Updates will be made to the page table accordingly.
6. The sign will be sent to the CPU to proceed with the program execution and it will put the process again into a ready state.

• Henceforth at whatever point a page fault happens these steps are performed by the operating system and the required page is brought into memory.

Advantages

• Demand paging, instead of loading all pages right away:
• Just loads pages that are requested by the executing process.
• As there is more space in the main memory, more processes can be stacked, decreasing the context switching time, which uses a lot of resources.
• Less loading latency happens at program startup, as less data is gotten from secondary storage and less data is brought into main memory.
• As main memory is costly contrasted with secondary memory, this method helps altogether decrease the bill of material (BOM) cost in advanced cells for instance. Symbian OS had this element.

Disadvantage

• Individual programs face additional latency when they access the page for the first time.
• Minimal effort, low-control implanted systems might not have a memory management unit that supports page replacement.
• Memory management with page replacement algorithms turns out to be somewhat increasingly intricate.
• Conceivable security dangers, including weakness to timing attacks.
• Thrashing may happen because of repeated page faults.

KEY TAKEAWAY

• As per the idea of Virtual Memory, to execute some process, just a piece of the process should be available in the main memory which implies that a couple of pages may be available in the main memory whenever.
• The difficult task is to decide which pages should be kept in the main memory and which should be kept in the secondary memory because we can't state ahead of time that a process will require a specific page at a specific time.

4.11 Performance of demand paging

Demand Paging

According to the concept of Virtual Memory, to execute some process, only a part of the process needs to be present in the main memory which means that only a few pages will only be present in the main memory at any time.

However, deciding, which pages need to be kept in the main memory and which need to be kept in the secondary memory, is going to be difficult because we cannot say in advance that a process will require a particular page at a particular time.

Therefore, to overcome this problem, there is a concept called Demand Paging is introduced. It suggests keeping all pages of the frames in the secondary memory until they are required. In other words, it says that do not load any page in the main memory until it is required.

Whenever any page is referred to for the first time in the main memory, then that page will be found in the secondary memory.

After that, it may or may not be present in the main memory depending upon the page replacement algorithm which will be covered later in this tutorial.

What is a Page Fault?

If the referred page is not present in the main memory then there will be a miss and the concept is called Page miss or page fault.

The CPU has to access the missed page from the secondary memory. If the number of page faults is very high then the effective access time of the system will become very high.

What is thrashing?

If the number of page faults is equal to the number of referred pages or the number of page faults are so high so that the CPU remains busy in just reading the pages from the secondary memory then the effective access time will be the time taken by the CPU to read one word from the secondary memory and it will be so high. The concept is called thrashing.

If the page fault rate is PF %, the time taken in getting a page from the secondary memory and again restarting is S (service time) and the memory access time is ma then the effective access time can be given as;

1. EAT = PF X S + (1 - PF) X (ma)   

KEY TAKEAWAY

Demand Paging

According to the concept of Virtual Memory, to execute some process, only a part of the process needs to be present in the main memory which means that only a few pages will only be present in the main memory at any time.

However, deciding, which pages need to be kept in the main memory and which need to be kept in the secondary memory, is going to be difficult because we cannot say in advance that a process will require a particular page at a particular time.

Therefore, to overcome this problem, there is a concept called Demand Paging is introduced. It suggests keeping all pages of the frames in the secondary memory until they are required. In other words, it says that do not load any page in the main memory until it is required.

4.12 Page replacement algorithms

• Page replacement algorithms are the procedures utilizing which an Operating System chooses which memory pages to swap out, write to disk when a page of memory should be allocated.
• Paging happens at whatever point a page fault happens and a free page can't be utilized for allocation reason accounting to reason that pages are not available or the quantity of free pages is lower than required pages.
• At the point when the page that was chosen for replacement and was paged out, is referenced once more, it needs to read in from disk, and this requires I/O completion.
• This process decides the nature of the page replacement algorithm: the lesser the time waiting for page-ins, the better is the algorithm.
• A page replacement algorithm takes a gander at the restricted data about getting to the pages given by hardware and attempts to choose which pages ought to be replaced to limit the complete number of page misses while offsetting it with the expenses of primary storage and processor time of the algorithm itself.
• There is a wide range of page replacement algorithms. We assess an algorithm by running them on a specific string of memory reference and registering the number of page issues,
• There are two main parts of virtual memory, Frame allocation, and Page Replacement. It is imperative to have the ideal frame allocation and page replacement algorithm. Frame allocation is about what number of frames are to be designated to the process while the page replacement is tied in with deciding the page number which should be supplanted to make space for the mentioned page.

What if the algorithm is not optimal?

1. If the quantity of frames which are dispensed to a process isn't adequate or exact at that point, there can be an issue of thrashing. Because of the absence of frames, a large portion of the pages will reside in the main memory and consequently, more page faults will happen.

Nonetheless, on the off chance that OS allots more frames to the process, at that point there can be an internal discontinuity.

2.     On the off chance that the page replacement orithmalgorithm isn't ideal, at that point, there will likewise be the issue of thrashing. On the off chance that the number of pages that are supplanted by the mentioned pages will be referred sooner rather than later at that point, there will be a progressively some swap-in and swap-out and along these lines, the OS needs to perform more replacements then common which causes execution inadequacy.

3.     In this manner, the assignment of an ideal page replacement calculation is to pick the page which can restrict the thrashing.

Types of Page Replacement Algorithm

• There are different page replacement algorithms. Every algorithm has an alternate strategy by which the pages can be replaced.

First in First out (FIFO) –

• This is the least difficult page replacement algorithm. In this algorithm, the operating system monitors all pages in the memory in a queue, the oldest page is in the front of the line. At the point when a page should be replaced page in the front of the queue is chosen for removal.
• Example Consider page reference string 1, 3, 0, 3, 5, 6 with 3-page frames. Find several page faults.
• At first, all slots are vacant, so when 1, 3, 0 came they are distributed to the unfilled spaces — > 3 Page Faults.
• At the point when 3 comes, it is in memory so — > 0 Page Faults.
• At that point 5 comes, it isn't available in memory so it replaces the oldest page space i.e 1. — >1 Page Fault.
• 6 comes, it is likewise not available in memory so it replaces the most established page space i.e 3 — >1 Page Fault.
• At long last when 3 come it isn't available so it replaces 0 — > 1-page fault

• Belady's anomaly – Belady's anomaly demonstrates that it is conceivable to have more page faults when expanding the number of page frames while utilizing the First in First Out (FIFO) page replacement algorithm. For instance, on the off chance that we consider reference string 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4 and 3 slots, we get 9 all-out page faults, however, on the off chance that we increment spaces to 4, we get 10-page faults.

Optimal Page replacement

• This algorithm replaces the page which won't be alluded to for such a long time in the future. Although it cannot be implementable however it very well may be utilized as a benchmark. Different algorithms are contrasted with this regarding optimality.
• Example: Consider the page references 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, with 4 page frame. Discover number of page faults.

• At first, all openings are vacant, so when 7 0 1 2 are assigned to the unfilled spaces — > 4 Page faults
• 0 is as of now there so — > 0 Page fault.
• At the point when 3 came it will replace 7 since it isn't utilized for the longest length of time in the future— >1 Page fault.
• 0 is as of now there so — > 0 Page fault.
• 4 will replace 1 — > 1 Page Fault.

• Presently for the further page reference string — > 0 Page fault since they are as of now accessible in the memory.
• Optimal page replacement is flawless, yet unrealistic by and by as the operating system can't know future requests. The utilization of Optimal Page replacement is to set up a benchmark with the goal that other replacement calculations can be examined against it.

Least Recently Used

• This algorithm replaces the page which has not been alluded to for quite a while. This algorithm is only inverse to the optimal page replacement algorithm. In this, we take a look at the past as opposed to gazing at the future.
• Example- Consider the page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 with 4 page frames. Find number of page faults.

• At first, all openings are vacant, so when 7 0 1 2 are apportioned to the vacant spaces — > 4 Page fault
• 0 is now their so — > 0 Page fault.
• At the point when 3 came it will replace 7 since it is least as of late utilized — >1 Page fault.
• 0 is now in memory so — > 0 Page fault.
• 4 will happens of 1 — > 1 Page Fault
• Presently for the further page reference string — > 0 Page fault since they are as of now accessible in the memory.

KEY TAKEAWAY

• Page replacement algorithms are the procedures utilizing which an Operating System chooses which memory pages to swap out, write to disk when a page of memory should be allocated.
• Paging happens at whatever point a page fault happens and a free page can't be utilized for allocation reason accounting to reason that pages are not available or the quantity of free pages is lower than required pages.
• At the point when the page that was chosen for replacement and was paged out, is referenced once more, it needs to read in from disk, and this requires I/O completion.

4.13 Thrashing

• Thrashing is computer action that allows little or no progress, as memory or different resources have turned out to be depleted or too limited to even perform required functions.
• At this point, a pattern normally creates in which a request is made to the operating system by a process or program, then the operating system attempts to find resources by taking them from some different process, which in turn makes new demands that can't be fulfilled.
• In a virtual storage system (an operating system that deals with its local storage or memory in units called pages), thrashing is a condition wherein extreme paging operations are occurring.
• A system that is thrashing can be seen as either an exceptionally moderate system or one that has stopped.
• Thrashing is a condition or a circumstance when the system is spending a noteworthy segment of its time adjusting the page faults; however, the genuine processing done is truly insignificant.

Fig 15

• The fundamental idea included is that if a process is assigned too few frames, at that point, there will be an excess of and too successive page faults.
• Thus, no work would be finished by the CPU and the CPU use would fall definitely.
• The long-term scheduler would then attempt to improve the CPU usage by loading some more processes into the memory in this way expanding the level of multiprogramming.
• This would bring about a further decline in the CPU usage setting off a chained response of higher page faults followed by an expansion in the level of multiprogramming, called Thrashing.

Reasons for Thrashing

It brings about extreme performance issues.

1. If CPU use is too low then we increase the level of multiprogramming by acquainting another process with the system. A global page replacement algorithm is utilized. The CPU scheduler sees the diminishing CPU utilization and builds the level of multiprogramming.
2. CPU use is plotted against the level of multiprogramming.
3. As the level of multiprogramming expands, CPU use likewise increases.
4. If the level of multiprogramming is expanded further, thrashing sets in, and CPU use drops sharply.
5. So, now, to expand CPU usage and to quit thrashing, we should diminish the level of multiprogramming.

Methods to Handle Thrashing

We previously observed Local replacement is superior to Global replacement to abstain from thrashing. Be that as it may, it likewise has drawbacks and not suggestible. Some more strategies are

Working Set Model

• This model depends on the locality. What region is stating, the page utilized as of recently can be utilized again, and the pages which are adjacent to this page will likewise be utilized.
• Working set methods state that set of pages in the latest D time.
• The page which finished its D amount of time in working set naturally dropped from it.
• So the precision of the working set relies upon the D we have picked.
• This working set model abstains from thrashing while at the same time keeping the level of multiprogramming as high as could be expected under the circumstances.

Page Fault Frequency

• It is some immediate methodology than the working set model.
• When thrashing happens we realize that it has a few frames. Also, on the off chance that it isn't thrashing, that implies it has an excessive number of frames.
• In light of this property, we allocate an upper and lower bound for the ideal page fault rate.
• As indicated by the page fault rate we assign or remove pages.
• On the off chance that the page fault rate becomes less than the limit, frames can be expelled from the process.
• So, if the page fault rate becomes more than the limit, a progressive number of frames can be distributed to the process.

Furthermore, if no frames are available because of the high page fault rate, we will simply suspend the processes and will restart them again when frames will be available.

KEY TAKEAWAY

• Thrashing is computer action that allows little or no progress, as memory or different resources have turned out to be depleted or too limited to even perform required functions.
• At this point, a pattern normally creates in which a request is made to the operating system by a process or program, then the operating system attempts to find resources by taking them from some different process, which in turn makes new demands that can't be fulfilled.
• In a virtual storage system (an operating system that deals with its local storage or memory in units called pages), thrashing is a condition wherein extreme paging operations are occurring.

4.14 Cache memory organization

The data or contents of the main memory that are used frequently by the CPU are stored in the cache memory so that the processor can easily access that data in a shorter time. Whenever the CPU needs to access memory, it first checks the cache memory. If the data is not found in the cache memory, then the CPU moves into the main memory.

Cache memory is placed between the CPU and the main memory. The block diagram for a cache memory can be represented as:

Fig 16 – Cache memory

The cache is the fastest component in the memory hierarchy and approaches the speed of CPU components.

The basic operation of cache memory is as follows:

• When the CPU needs to access memory, the cache is examined. If the word is found in the cache, it is read from the fast memory.
• If the word addressed by the CPU is not found in the cache, the main memory is accessed to read the word.
• A block of words one just accessed is then transferred from the main memory to cache memory. The block size may vary from one word (the one just accessed) to about 16 words adjacent to the one just accessed.
• The performance of the cache memory is frequently measured in terms of a quantity called hit ratio.
• When the CPU refers to memory and finds the word in the cache, it is said to produce a hit.
• If the word is not found in the cache, it is in main memory and it counts as a miss.
• The ratio of the number of hits divided by the total CPU references to memory (hits plus misses) is the hit ratio.

KEY TAKEAWAY

The data or contents of the main memory that are used frequently by the CPU are stored in the cache memory so that the processor can easily access that data in a shorter time. Whenever the CPU needs to access memory, it first checks the cache memory. If the data is not found in the cache memory, then the CPU moves into the main memory.

4.15 Locality of reference

The locality of reference refers to a phenomenon in which a computer program tends to access the same set of memory locations for a particular period. In other words, Locality of Reference refers to the tendency of the computer program to access instructions whose addresses are near one another. The property of locality of reference is mainly shown by loops and subroutine calls in a program.

Fig 17 – Loops and subroutine calls

1. In the case of loops in the program control processing unit repeatedly refers to the set of instructions that constitute the loop.
2. In the case of subroutine calls, every time the set of instructions are fetched from memory.
3. References to data items also get localized which means the same data item is referenced again and again.

Fig 18

In the above figure, you can see that the CPU wants to read or fetch the data or instruction. First, it will access the cache memory as it is near to it and provides very fast access. If the required data or instruction is found, it will be fetched. This situation is known as a cache hit. But if the required data or instruction is not found in the cache memory then this situation is known as a cache miss. Now the main memory will be searched for the required data or instruction that was being searched and if found will go through one of the two ways:

1. The first way is that the CPU should fetch the required data or instruction and use it and that’s it but what, when the same data or instruction is required again.CPU again has to access the same main memory location for it and we already know that main memory is the slowest to access.
2. The second way is to store the data or instruction in the cache memory so that if it is needed soon again shortly it could be fetched in a much faster way.

Cache Operation:
It is based on the principle of locality of reference. There are two ways with which data or instruction is fetched from main memory and get stored in cache memory. These two ways are the following:

1. Temporal Locality –
   Temporal locality means current data or instruction that is being fetched may be needed soon. So we should store that data or instruction in the cache memory so that we can avoid again searching in the main memory for the same data.

Fig 19

When the CPU accesses the current main memory location for reading required data or instruction, it also gets stored in the cache memory which is based on the fact that the same data or instruction may be needed in near future. This is known as temporal locality. If some data is referenced, then there is a high probability that it will be referenced again shortly.

2.     Spatial Locality –
Spatial locality means instruction or data near to the current memory location that is being fetched, may be needed soon shortly. This is slightly different from the temporal locality. Here we are talking about nearly located memory locations while in the temporal locality we were talking about the actual memory location that was being fetched.

Fig 20

Cache Performance:
The performance of the cache is measured in terms of the hit ratio. When the CPU refers to memory and find the data or instruction within the Cache Memory, it is known as a cache hit. If the desired data or instruction is not found in the cache memory and the CPU refers to the main memory to find that data or instruction, it is known as a cache miss.

Hit + Miss  = Total CPU Reference

Hit Ratio(h) = Hit / (Hit+Miss)

The average access time of any memory system consists of two levels: Cache and Main Memory. If Tc is time to access cache memory and Tm is the time to access main memory then we can write:

Tavg = Average time to access memory

Tavg = h * Tc + (1-h)*(Tm + Tc)

KEY TAKEAWAY

The locality of reference refers to a phenomenon in which a computer program tends to access the same set of memory locations for a particular period. In other words, Locality of Reference refers to the tendency of the computer program to access instructions whose addresses are near one another. The property of locality of reference is mainly shown by loops and subroutine calls in a program.

References:

1. Silberschatz, Galvin and Gagne, “Operating Systems Concepts”, Wiley

2. Sibsankar Halder and Alex A Aravind, “Operating Systems”, Pearson Education

3. Harvey M Dietel, “ An Introduction to Operating System”, Pearson Education

4. D M Dhamdhere, “Operating Systems: A Concept-based Approach”, 2nd Edition,

5. TMH 5. William Stallings, “Operating Systems: Internals and Design Principles ”, 6th Edition, Pearson Education