UNIT 3 Array in C#

 Memory Hierarchy

Memory hierarchy is arranging different kinds of storage present on a computing device based on speed of access. The memory in a computer can be divided into five hierarchies based on the speed as well as use. The processor can move from one level to another based on its requirements. The five hierarchies in the memory are registers, cache, main memory, magnetic discs, and magnetic tapes. The first three hierarchies are volatile memories which mean when there is no power, and then automatically they lose their stored data. Whereas the last two hierarchies are not volatile which means they store the data permanently. 

Let us discuss each level in detail:

Level-0 − Registers

The registers are present inside the CPU. As they are present inside the CPU, they have least access time. Registers are most expensive and smallest in size generally in kilobytes. They are implemented by using Flip-Flops.

Level-1 − Cache

Cache memory is used to store the segments of a program that are frequently accessed by the processor. It is expensive and smaller in size generally in Megabytes and is implemented by using static RAM.

Level-2 − Primary or Main Memory

It directly communicates with the CPU and with auxiliary memory devices through an I/O processor. Main memory is less expensive than cache memory and larger in size generally in Gigabytes. This memory is implemented by using dynamic RAM.

Level-3 − Secondary storage

Secondary storage devices like Magnetic Disk are present at level 3. They are used as backup storage. They are cheaper than main memory and larger in size generally in a few TB.

Level-4 − Tertiary storage

Tertiary storage devices like magnetic tape are present at level 4. They are used to store removable files and are the cheapest and largest in size (1-20 TB).

We can infer the following characteristics of Memory Hierarchy Design from the above figure:

 

1.      Capacity:
It is the global volume of information the memory can store. As we move from top to bottom in the Hierarchy, the capacity increases.

2.      Access Time:
It is the time interval between the read/write request and the availability of the data. As we move from top to bottom in the Hierarchy, the access time increases.

3.      Performance:
Earlier when the computer system was designed without Memory Hierarchy design, the speed gap increases between the CPU registers and Main Memory due to large difference in access time. This results in lower performance of the system and thus, enhancement was required. This enhancement was made in the form of Memory Hierarchy Design because of which the performance of the system increases. One of the most significant ways to increase system performance is minimizing how far down the memory hierarchy one has to go to manipulate data.

4.      Cost per bit:
As we move from bottom to top in the Hierarchy, the cost per bit increases i.e. Internal Memory is costlier than External Memory.

Memory Function

Memory is an information processing system; therefore, we often compare it to a computer. Memory is the set of processes used to encode, store, and retrieve information over different periods of time

Encoding

We get information into our brains through a process called encoding, which is the input of information into the memory system. Once we receive sensory information from the environment, our brains label or code it. We organize the information with other similar information and connect new concepts to existing concepts. Encoding information occurs through automatic processing and effortful processing.

Storage

Once the information has been encoded, we have to somehow retain it. Our brains take the encoded information and place it in storage. Storage is the creation of a permanent record of information. In order for a memory to go into storage (i.e., long-term memory), it has to pass through three distinct stages: Sensory Memory, Short-Term Memory, and finally Long-Term Memory. These stages were first proposed by Richard Atkinson and Richard Shiffrin (1968). Their model of human memory , called Atkinson and Shiffrin’s model, is based on the belief that we process memories in the same way that a computer processes information.

 

Retrieval

The act of getting information out of memory storage and back into the desktop, and you can work with it again. The retrieval of information from a computer is the process of getting it back.. You must be able to retrieve information from memory in order to process and perform any job.

Mono Programming and Multi Programming Model

Mono Programming

In mono-programming, memory contains only one program at any point of time. Whereas in multiprogramming memory contains more than one user program.
In case of mono-programming, when the CPU is executing the program and I/O operation is encountered, then the program goes to I/O devices, during that time the CPU sits idle. Thus, in mono-programming CPU is not effectively used i.e., CPU utilization is poor. In mono-programming the CPU sits idle while I/O operation is being performed.

Multi Programming

In multiprogramming, when one user program contains I/O operations, CPU switches to the next user program. Thus, the CPU is made busy all the times. A single user cannot keep the CPU busy all the times. Hence multiprogramming increases CPU utilization by organizing jobs(programs), so that CPU is busy at all times by executing some user program or the other.
In multiprogramming, the OS picks one of the jobs from job pool and sends the job to CPU. When an I/O  operation is encountered in that job, OS allocates I/O devices for that job and allocates CPU to the next job in the job pool.
In multiprogramming, most of the time CPU is busy.
Advantages of multiprogramming are,

1. CPU utilization is high.
2. Higher job throughput.

Throughput is the amount of work done in a given time interval.
Throughput = Amount of time CPU is utilized / Total time for executing the program. 

 

Sharing and Protection(Requirements of Memory Management System)

1. Sharing

Sharing refers to the ability of multiple processes to access the same memory space in a controlled and safe manner. Instead of loading several copies of the same program or data into memory, the operating system allows processes to share a single copy, saving both time and space. For example, when several processes use the same system library or file, it is more efficient to load one copy into memory and let all processes share it. Memory management ensures that this sharing is done safely, using mechanisms such as shared memory regions and inter-process communication (IPC), without compromising data integrity or process security.

2. Protection

Protection is the requirement that ensures one process cannot interfere with another process’s memory, whether accidentally or maliciously. When multiple programs run simultaneously, there is always a risk that one program may try to read or write into another program’s memory space or even into the memory reserved for the operating system. To prevent this, memory management applies protection mechanisms such as segmentation, paging, and access rights (read, write, or execute permissions). For example, a user program cannot directly access the memory occupied by another program or the OS kernel unless it is explicitly granted access.

3. Relocation

Relocation is the ability to move a process from one memory address to another without affecting its execution. Since processes are not always loaded into the same location and may be swapped during execution, the OS must ensure they still run correctly. This is achieved using base and limit registers, paging, or segmentation. For example, a program may run at address 1000 in one execution and 5000 in another, but relocation allows it to function normally in both cases.

4. Logical Organization

Logical organization provides programs with a logical view of memory instead of its physical layout. Programs are divided into units such as code, data, and stack, and the OS ensures these segments are mapped correctly to physical memory. Mechanisms like segmentation, paging, and virtual memory make this possible. For instance, a program can treat its data and instructions separately without worrying about their actual physical addresses.

5. Physical Organization

Physical organization refers to how RAM is managed and allocated among processes. Since memory is limited, it must be used efficiently while avoiding fragmentation. The OS uses allocation strategies like first-fit or best-fit, along with paging and segmentation, to manage memory effectively. For example, memory is divided into pages that are dynamically assigned to processes by the Memory Management Unit (MMU).

Memory Management Techniques (Strategies)

Memory management is an essential function of the operating system that handles the allocation and deallocation of main memory to different processes. There are two main types of memory management techniques: Contiguous Memory Management and Non-Contiguous Memory Management.

1. Contiguous Memory Management

In contiguous memory management, each process occupies a single continuous block of physical memory. This technique is easy to implement but may suffer from fragmentation problems. It is further divided into two types: Single Contiguous Memory Management and Multiple Partitioning.

a) Single Contiguous Memory Management

This is the simplest memory management method used in early computer systems. The main memory is divided into two parts — one for the operating system and the other for a single user process. It is simple and easy to manage, but only one process can run at a time, causing poor memory and CPU utilization.

b) Multiple Partitioning

In this technique, the main memory is divided into multiple partitions, allowing several processes to be loaded and executed simultaneously. It improves CPU utilization and supports multiprogramming. Multiple partitioning is of two types: Fixed Partitioning (Static) and Variable Partitioning (Dynamic).

Fixed Partitioning (Static Partitioning)

In fixed partitioning, the main memory is divided into a fixed number of partitions during system setup. Each partition can hold only one process, and the partitions may be equal or unequal in size.

Advantages:

·         Simple and easy to implement.

·         Low operating system overhead.

Disadvantages:

·         Causes internal fragmentation, as small processes waste space within partitions.

·         Leads to external fragmentation, since free spaces between partitions cannot be combined.

·         The number of partitions limits the degree of multiprogramming.

Variable Partitioning (Dynamic Partitioning)

In variable partitioning, memory is divided dynamically according to the size of the processes. Partitions are created at runtime based on process requirements, allowing better utilization of memory.

Advantages:

·         No internal fragmentation, as memory is allocated exactly as needed.

·         Allows a higher degree of multiprogramming since more processes can fit in memory.

Disadvantages:

·         More complex to implement, as allocation occurs during runtime.

·         May still cause external fragmentation, as small gaps appear after processes are removed.

Non-Contiguous Memory Management Techniques

Non-contiguous memory management allows a process to be stored in scattered, non-adjacent memory locations. This method helps utilize memory efficiently and reduces fragmentation. The main techniques are Virtual Memory, Paging, and Segmentation.

1. Virtual Memory

Virtual memory is a feature of the operating system that lets a computer use a portion of the hard disk as an extension of RAM. When physical memory becomes full, parts of programs that are not currently in use are moved to a disk area called the paging file (or swap space). This allows larger programs to run and supports multitasking even with limited RAM.

How It Works:
Programs use logical (virtual) addresses, which the system translates into physical addresses in RAM. The process is divided into parts, and only the required parts are loaded into memory when needed. This is done using page tables or segment tables. Virtual memory works through two methods:

1.      Demand Paging – Loads only the required pages of a process.

2.      Demand Segmentation – Loads only the required segments of a process.

Advantages:

·         Supports running large programs with limited RAM.

·         Allows multitasking and efficient memory use.

Disadvantages:

·         May slow down performance due to disk access (thrashing).

·         Complex to manage and increases system overhead.

2. Paging

Paging divides both logical and physical memory into fixed-size blocks. Logical memory blocks are called pages, and physical memory blocks are called frames. When a program runs, its pages are loaded into available frames, even if they are not next to each other. The page table keeps track of the mapping between pages and frames.

Paging removes external fragmentation since processes can use any free frame, but internal fragmentation may still occur when the last page is not completely filled.

Advantages:

·         Eliminates external fragmentation.

·         Makes memory usage more efficient.

Disadvantages:

·         Causes internal fragmentation.

·         Overhead in maintaining the page table.

3. Segmentation

Segmentation divides a program into variable-size segments such as code, data, and stack. Each segment represents a logical part of the program and can be stored in non-contiguous memory locations. The segment table records the base address and length of each segment.

Segmentation provides a logical view of memory and makes management easier, but it can still cause external fragmentation because segment sizes vary.

Advantages:

·         Logical grouping of related data and code.

·         Reduces external fragmentation compared to contiguous allocation.

Disadvantages:

·         Still prone to external fragmentation.

·         Requires extra overhead to maintain the segment table

Internal and External Fragmentation

In an operating system, fragmentation refers to the inefficient use of memory that occurs when free memory space is broken into small pieces, making it difficult to allocate memory effectively. There are two main types of fragmentation: Internal Fragmentation and External Fragmentation.

1. Internal Fragmentation

Internal fragmentation occurs when memory is divided into fixed-size blocks, and the memory allocated to a process is slightly larger than the memory it actually requires. The unused space within the allocated block becomes wasted and is called internal fragmentation.

In other words, the difference between the allocated memory and the memory actually required by a process is known as internal fragmentation.

Example:

The above diagram clearly shows the internal fragmentation because the difference between memory allocated and required space or memory is called Internal fragmentation. 

If a process requires 18 KB of memory and the system allocates a fixed block of 20 KB, the remaining 2 KB of unused memory inside that block is internal fragmentation.

Causes:

·         Occurs in fixed-size partitioning or paging, where each process is assigned a fixed block size.

·         Happens because the process rarely uses the entire allocated space.

Effects:

·         Leads to wastage of memory inside partitions.

·         Decreases overall system efficiency.

2. External Fragmentation

External fragmentation occurs when there is enough total free memory space to satisfy a process’s request, but the memory is not contiguous. Since the available free spaces are scattered throughout memory, the process cannot be allocated even though total free space is sufficient.

Example:
If several small free blocks exist between allocated blocks (e.g., 10 KB, 15 KB, and 30 KB), a process requiring 50 KB cannot be loaded even though total free memory is 55 KB, because the blocks are not continuous.

Causes:

·         Occurs in variable-size partitioning and segmentation.

·         Happens when processes are loaded and removed frequently, leaving scattered holes in memory.

Solutions:

·         Compaction: Rearranges memory contents to combine scattered free spaces into one large block.

·         Paging or Segmentation: Divides memory into non-contiguous parts to utilize free spaces effectively.