Computer Science

Key unit competency:

To be able to explain the role of operating system in Memory Management

Introductory Activity

1. What do you think of the above figure?

2. What do you understand by the central processing unit? Discuss parts of the central processing unit?

3. Examine the role of input and output devices in the above figure?

4. Does the computer has a memory? Differentiate a memory and a storage?

5. Investigate the role played by CD Rom, Floppy Drive, Hard drive and RAM in the above figure?

6. What is the name given to the computer program in the execution? Where does it managed from?

7. Analyze the role of BUS in the above figure?

8. Discuss how programs in execution are managed?

9. Discuss how multiprogramming is achieve in computer?

9.1. UNDERSTANDING COMPUTER MEMORY

Learning Activity 9.1.

Uwera Joanna is a student in senior 6 in HEG at Lycee de Kigali, she is brilliant students in History because she has the good ability to memorize and she is worried about the second term exam of history. The history teacher has said that the exam will cover senior 4, 5 and 6. The issue with Uwera is that she can’t remember what she learnt in senior 4, 5 and senior 6 term 1. She only remembers very well what was learnt only in second term of senior 6.

Please answer the questions below:

1. Discuss your ability of remembering events happened into your life

2. Are you able to think of 2 situations at the simultaneously?

3. In which part of brain that store what you have memorize or any information

4. Explain why Uwera is able to remember better what she learnt in learnt in second term of senior 6 than what she learnt in senior 4, 5 and senior 6 term 1.

5. Does the computer remember everything? explain how

9.1.1. Definition of computer memory

A computer memory is just like a human brain. It is used to store data and instructions. Computer memory is the storage space in the computer where data is to be processed and instructions required for processing are stored.

The memory is divided into large number of small parts called cells. Each location or cell has a unique address, the addresses varies from zero to memory size minus one.

Memory is the part of the computer that holds data and instructions for processing. The memory works closely with the central processing unit and computer memory is separated from the central processing unit. Memory stores program instructions and data for the programs in the execution.

For example: if the computer memory stores 64 characters, it keeps 64 bytes , then this memory unit has 64 * 1024 = 65536 kbytes.

Computer memory is also known as place in the computer where data is kept. The computer memory is in two different types

1. RAM (Random Access Memory) that is also known as primary memory, main storage, internal storage, main memory, volatile memory and all these terms are used interchangeably in computer science. This kind of memory stores data for short period of time.

2. ROM (Read Only Memory) olso known as permanent memory, non volatile memory. This kind of memory stores data for long period of time.

Computers need a memory because the memory is the place where the processor (central processing unit) does its work.

Note:

•The more memory size in the computer, the better processes execution.

•With more memory , your computer run fast

•With more computer memory in the computer, you can work on larger documents.

9.1.2. The role of memory in the computer

The main memory holds temporary instructions and data needed by a program in the execution in order to complete any computing tasks. The main memory enables the Central Processing Unit to access instructions and data stored in memory very quickly.

The central processing unit (CPU) loads an application program from the hard disk, such as a word processing into the main memory. When a program is loaded in the main memory, it allows the application program to work efficiently and the CPU can access it from the main memory.

9.1.3. Memory Organization

A memory unit is the collection of storage units. The memory unit stores the binary information in the form of bits. Generally, computer memory is classified into 2 categories:

•Volatile Memory: The memory loses its data, when power is the computer switched off.

•Non-Volatile Memory: The memory is a permanent storage and does not lose any data when power is the computer switched off. Slower than primary memories.

9.1.4 Characteristics of computer

memoryComputer memory is characterized by its function, capacity, and response times. There are only 2 operations that can be performed on the computer memory: Read and Write

•Read operation is performed when information is transferred from the memory to another device.

•Write operation is performed when information is transferred from another device to the memory.

Note:

•A memory that performs both read and write is RAM.

•ROM can only be written

The performance of a memory system is defined by two different measures: the access time and the cycle time.

•Access time is also known as response time or latency refers to how quickly the memory can respond to a read or a write operation request.

•Memory cycle time refers to the minimum period between two successive a read or a write operation requests.

9.1.5. Computer Memory

TypesMemory is primarily of three types: magnetic memory, semiconductor memory, optical memory and flash memory.

a. Magnetic Memory

Magneticmemory is the storage of data on magnetized medium. Magnetic storage uses different patterns of magnetization in a magnetisable material to store data and is a form of non–volatile memory.

Example of magnetic storage media is the hard disk.

In the magnetic storage media, the information is accessed using one or more read and write heads. They are used for storing data/information permanently and Central Processing Unit does not access these memories directly.

Characteristics of Magnetic Memory

•It is known as the backup memory.

•It is a non-volatile memory.

•Data is permanently stored even if power is switched off

.•It is used for storage of data in a computer.

b.Semi-conductor memory

Semiconductor memory is a digital electronic data storage device implemented with semiconductor electronic devices on an integrated circuit (IC). Example of semiconductor memory are: cache memory and primary memory

Cache Memory: Cache memory is a very high speed semiconductor memory which can speed up the CPU. It acts as a buffer between the CPU and the main memory.

Note: Data Buffer is a region of a physical memory storage used to temporarily store data while it is being moved from one place to another.

Cache memory is used to hold those parts of data and program which are most frequently used by the CPU. The parts of data and programs are transferred from the disk to cache memory by the operating system, from where the CPU can access them.

Primary Memory (Main Memory):Primary memory holds only those data and instructions on which the computer is currently working on.Main Memory isdirectly accessed by the CPU/ processor. It has a limited capacity and data is lost when power is switched off.

Note: Volatility: a memory is said to be volatile memory when it loses its content when the computer is powered off. All primary memories re volatile.

These memories are not as fast as cache memory. The data and instruction required to be processed resides in the main memory. It is divided into two subcategories RAM and ROM.

Characteristics of semiconductor memories

•These are semiconductor memories.

•Usually volatile memory.

•Data is lost in case computer is switched off

.•It is the working memory of the computer

.•Faster than magnetic memories.

c. Optical memory

Optical storage is the storage of data on an optically readable medium. Data is recorded by making marks in a pattern that can be read back with the aid of light, usually a beam of laser light precisely focused on a spinning optical disc.

Example of optical memory are: CD, DVD and BLUE RAY

d.Flash memory Flash

memory is a non-volatile memory chip used for storage and for transferring data between a personal computer and digital devices

Flash memory has the ability to be electronically reprogrammed and erased. It is often found in USB flash drives, MP3 players, digital cameras and solid-state drives.

9.1.6. The difference between memory and storage

The term memory refers to the amount of RAM installed in the computer whereas the term storage refers to the capacity of the computer’s hard disk. Computers have two kinds of storage: temporary and permanent. A computer’s memory is used for temporary storage, while a computer’s hard drive is used for permanent storage.

9.1.7. Memory Access Methods

Each memory type is a collection of numerous memory locations. To access data from any memory, first it must be located and then the data is read from the memory location.

Following are the methods to access information from memory locations:

•Random Access: main memories are random access memories, in which each memory location has a unique address. Using this unique address any memory location can be reached in the same amount of time in any order.

•Sequential Access: This methods allows memory access in a sequence or in order.

•Direct Access: In this mode, information is stored in tracks, with each track having a separate read/write head.

Application Activity 9.1.

1. Using clear example differentiate primary memory and secondary memory

2. Using clear example differentiate volatile memory and non-volatile memory

3. Discuss why main memory is considered as the working memory.

4. Differentiate computer memory and computer storage

5. Discus the computer memory hierarchy using a clear graphical representation

6. Discuss the access method for the following categories of storage devices

a)Magnetic storage,

b) optical storage ,

c) flash storage ,

d) semi-conductor storage

7. What do you understand about computer memory? In the table below, decide what is true for main memory and for secondary memory

9.2. LOGICAL AND PHYSICAL ADDRESS MEMORY SPACE

Learning Activity 9.2.

Consider a system in which a program can be separated into two parts: codes (Instructions) and data. The CPU knows whether it wants an instruction (instruction fetch) or data (data fetch or store). Therefore, two base and limit register pairs are provided: one for instructions and one for data. The instruction base and limit register pair is automatically read-only, so programs can be shared among different users. Discuss the advantages and disadvantages of this scheme.

9.2.1. Partitions

One of the first mechanisms used to protect the operating system and to protect processes from each other was the creation of partitions. A partition is a logical division of a memory that is treated as memory unit by operating system

The operating systems in order to manage memory partitions add two hardware registers to the memory address decoder: the base and limit registers. The base registers indicate where the partition starts in memory and the limit registerindicates the end of the partition.

When a process is placed into the main memory, the memory decoder adds on the value of the base register and the limit register address becomes `base + X’. Where X is the size the process.

There is a memory hard error, when the input address is lower than base address or higher than limit address.

9.2.2. Physical memory address

Physical address is a memory address that is represented in the form of a binary number on the address bus circuitry in order to enable the data bus to access a particular storage cell (partition) of main memory.

Physical Memory is the main memory and its location as seen by the operating system. Generally, the main memory address starts at location 0 and goes up to a top address set by the amount of the main memory.

9.2.3. Logical Memory address

When a process is loaded into the main memory, the CPU binds the base address and the limit address (baseand limit registers) of the memory partition where the process is going to reside in the main memory. The address generated by the CPU and added to the process to form the physical address is called as logical address.

Logical address is the memory partition address at which a process appears to reside from the perspective of an executing application program

In the partition system, all processes see memory partition as starting at address 0 defined by base register and going up to the end address defined by the limit register. The process in running in user mode (in execution) cannot modify the value base and limit register. The process sees its logical memory partition as fixed in size.

9.2.4. Address Binding Schemes

Computer memory uses both logical addresses and physical addresses to locate process in the main memory. Address binding allocates a physical memory location to a logical pointer by associating a physical address to a logical address, which is also known as a virtual address. There are 3 types of address binding:

a. Compile Time:

•If it is known in advance that where the process will be placed in memory then absolute code can be generated at the time of compilation

.•If we know in advance that a user process may store at starting from location R and that the generated code will start at that location and extend up from there.

•If at some later time starting location changes then it will be necessary to recompile this code.

b. Load Time:

•If it is not known at compile time that at which particular location the process will reside in memory when the compiler will generate relocatable code to find the address.

•In this case final binding is delayed until load time.

•In this case absolute address will be generated by the loader at the load time

c. Execution Time (Run Time):

•If the process can be moved during its execution from one memory segment to another then address binding must be performed at run time.

•A special hardware-MMU (Memory Management Unit) is used to generate physical addresses.

Note: The runtime mapping from virtual to physical address is done by the memory management unit (MMU) which is a hardware device.

9.2.5. Static Loading

While the operating loads program statically in the main memory then at the time of compilation the complete programs will be compiled and linked without leaving any external program (library or module). The linker combines the object program with object modules into an absolute program which also they are also included in logical addresses.

9.2.6. Dynamic Loading

When the operating loads dynamically program in the main memory then the operating loads only the part of the program(modules , libraries) .Then, operating system references the addresses of the others (library or modules) and they will be loaded in the memory when need by the CPU.

9.2.7. The difference between the static and dynamic loading

In static loading, the absolute program (and data) is loaded into memory in order for execution to start while in dynamic loading, dynamic routines of the library are stored on a disk in re-locatable form and are loaded into memory only when they are needed by the program.

9.2.8. Static vs Dynamic Loading

The choice between Static or Dynamic Loading is to be made at the time of computer program being developed.

9.2.9. Static Linking

As explained above, when static linking is used, the linker combines all other modules needed by a program into a single executable program to avoid any runtime dependency.

9.2.10. Dynamic Linking

When dynamic linking is used, it is not required to link the actual module or library with the program, rather a reference to the dynamic module is provided at the time of compilation and linking.

Application Activity 9.2.

1. What is memory address binding?

2. Discuss overlays in memory management?

3. Discuss the advantage of dynamic loading?

4. What do you understand by relocation register

5. Consider a logical address space of eight pages of 1024 words each, mapped onto a physical memory of 32 frames.a. How many bits are there in the logical address?b. How many bits are there in the physical address?

6. Explain the difference between logical and physical addresses?

9.3. ALLOCATING AND PLACING PARTITIONS IN MEMORY

Learning Activity 9.3.

Observe by comparing below 2 figures and answer questions.

1. Discuss why there is no a partition for the operating system

2. Discuss why memory has partitions of different size?

3. Investigate various algorithm used by the operating system to place processes into the main memory.

The operating system place the process into available partition. The first partition of the main memory is for the operating system and processes are chosen from the pool of programs waiting to be started (Waiting queue). The operating system chooses a partition size and physical location for a new process arriving in the main memory.

9.3.1. Single Partition Allocation

Single allocation is the simplest memory management technique where there is a partition reserved for the operating system and other partition are reserved for a single application.

The process of dividing the main memory into a set of non-overlapping blocks of memory is known as fixed partition. There are two types of fixed partitioning and they are:

9.3.2. Equal size partition

The size of each block in fixed partition will be equal. Any process less than the size of partitioning can be loaded in the fixed partition of equal size.

9.3.3. Unequal size partition

The size of each block in fixed partition is varied where processes are assigned to the blocks where it fits exactly: in other words, processes may be queued to use the best available partition. In the unequal size partition compared to equal size partition, memory wastage is minimized and may not give best throughput as some partitions may be unused.

The unequal size partitions use two types of queues where processes are assigned to memory blocks. They are multiple queue and single queue.

a. Multiple Queues

Each process is assigned to the smallest partition in which it fits and minimizes the internal fragmentation problem.

b.Single Queue

The process is assigned to the smallest available partition and the level of multiprogramming is increased.

Fixed size partitions suffer from two types of problems: they are overlays and internal fragmentation.

•Overlays: If a process is larger than the size of the partition then it suffers from overlaying problem in which only required information will be kept in memory. Overlays are extremely complex and time consuming task.

•Internal fragmentation: If process loaded is much smaller than any partition either equal or unequal, then it suffers from internal fragmentation in which memory is not used efficiently.

9.3.4. Dynamic partitioning

The dynamic partitioning requires more sophisticated memory management techniques. The partitions used are of variable length. When a process is brought into main memory, it allocates exactly as much memory as it requires. Each partition may contain exactly one process. The degree of multiprogramming is bound by the number of partitions. In this method when a partition is free a process is selected from the input queue and is loaded into the free partition. When the process terminates the partition becomes available for another process.

The problem with the dynamic memory allocation is that the memory becomes more and more fragmented and it leads to decline memory usage. This is called ‘external fragmentation’.

9.3.5. Placement Algorithm

They are algorithm used by the operating to decide which free block to allocate to a process. The below are Placement Algorithm.

ext-fit : it often leads to allocation of the largest block at the end of memoryFirst-fit: the algorithm favors allocation near the beginning of the main memory and it tends to create less fragmentation.

Best-fit searches for smallest block: the fragment left behind is small as possible, main memory quickly forms holes too small to hold any process.

Application Activity 9.3.

1. How is memory divided in the single contiguous memory management approach?

2. If, in a single contiguous memory management system, the program is loaded at address 30215, compute the physical addresses (in decimal) that correspond to the following logical addresses:

a) 9223

b) 2302

c) 7044

3. In a single contiguous memory management approach, if the logical address of a variable is L and the beginning of the application program is A, what is the formula for binding the logical address to the physical address?

4. If, in a fixed partition memory management system, the current value of the base register is 42993 and the current value of the bounds register is 2031, compute the physical addresses that correspond to the following logical addresses:

a) 104

b) 1755

c) 3041

5. Differentiate best fit and next fit allocation algorithms

9.4. MEMORY FRAGMENTATION

Learning Activity 9.4

.Followings are memory partition consecutively: 50 KB, 400 KB, 130 KB, 300 KB, 150 KB, and 70 KB (in that order). The following processes need to be assigned to the above partitions. The following memory space of each process (in order): A = 230 KB, B =180 KB, C = 130 KB, D = 120 KB, E = 200 KB.

Using the first fit method. Processes have been allocated to partition as follows:

•50 KB partition has no process assigned to it -> 50 KB free

•400 KB partition is assigned to processes A and C -> 40 KB free

•130 KB partition is assigned to process D -> 10 KB free

•300 KB partition is assigned to process B -> 120 KB free

•150 KB partition has no process assigned to it -> 150 KB free

•70 KB partition has no process assigned to it -> 70 KB free

Answer the following questions:

1. Calculate the total amount of free memory?

2. Think of the way these wasted memory can be reused

9.4.1. Memory Fragmentation

Fragmentation occurs in a memory allocation system, when there are many of the free blocks of memory that are too small and these small blocks of memory cannot satisfy any request. There are two type of memory Fragmentation: internal fragmentation and external fragmentation

9.4.2. Internal Fragmentation

Internal Fragmentation: Internal fragmentation is the space wasted inside of allocated memory partition. The Allocated memory partition may be slightly larger than requested memory size. This difference in size is a memory internal to a partition, but which is not used.

Now there are three free space areas in the memory, but they are not adjacent. Now a large process called process F is going to be loaded but neither of the free space block is not enough for process F. The addition of all the free spaces is definitely enough for process F, but due to the lack of adjacency that space is unusable for process F. This is called External Fragmentation.

9.4.4. Difference between Internal and External Fragmentation

The difference between Internal and External Fragmentation are following:

•Internal Fragmentation occurs when a fixed size memory allocation technique is used. External fragmentation occurs when a dynamic memory allocation technique is used.

•Internal fragmentation occurs when a fixed size partition is assigned to a program/file with less size than the partition making the rest of the space in that partition unusable. External fragmentation is due to the lack of enough adjacent space after loading and unloading of programs or files for some time because then all free space is distributed here and there.

•External fragmentation can be mined by compaction where the assigned blocks are moved to one side, so that contiguous space is gained. However, this operation takes time and also certain critical assigned areas for example system services cannot be moved safely. We can observe this compaction step done on hard disks when running the disk defragmenter in Windows.

•External fragmentation can be prevented by mechanisms such as segmentation and paging. Here a logical contiguous virtual memory space is given while in reality the files/programs are splitted into parts and placed here and there.

•Internal fragmentation can be maimed by having partitions of several sizes and assigning a program based on the best fit. However, still internal fragmentation is not fully eliminated.

Segmentation

Segmentation is a memory management technique in which each job is divided into several segments of different sizes, one for each module that contains pieces that perform related functions. Each segment is actually a different logical address space of the program.

When a process is to be executed, its corresponding segmentation are loaded into non-contiguous memory though every segment is loaded into a contiguous block of available memory.

Segmentation memory management works very similar to paging but here segments are of variable-length where as in paging pages are of fixed size.

A program segment contains the program’s main function, utility functions, data structures, and so on. The operating system maintains a segment map table for every process and a list of free memory blocks along with segment numbers, their size and corresponding memory locations in main memory. For each segment, the table stores the starting address of the segment and the length of the segment. A reference to a memory location includes a value that identifies a segment and an offset.

Swapping

Swapping is a mechanism in which a process can be swapped temporarily out of main memory (or move) to secondary storage (hard disk). The process makes that memory available to other processes. Later, the system can swap back the process from the secondary storage to main memory.

However performance is usually affected by swapping process, Swapping allow to run multiple and big processes in parallel. That’s the reason Swapping is also known as a technique for memory compaction.

Note that the total time taken by swapping process includes the time it takes to move the entire process to a secondary disk and then to copy the process back to memory, as well as the time the process takes to regain main memory.

Example:

Let us assume that the user process is of size 2048KB and on a standard hard disk where swapping will take place has a data transfer rate around 1 MB per second. The actual transfer of the 1000K process to or from memory will take

2048KB / 1024KB per second = 2 seconds = 2000 millisecondsNow considering in and out time, it will take complete 4000 milliseconds plus other overhead where the process competes to regain main memory.

Application Activity 9.4.

1. What do you understand by the dynamic memory allocation?

2. Discuss fixed partitions?

3. Differentiate internal fragmentation and external fragmentation?4. What is memory compaction? Discus reason why memory compaction is used.

9.5. VIRTUAL MEMORY CONCEPTS

Learning Activity 9.5.

Observe below picture and answer follow question

1. What do you think of picture above?

2. Discuss how a program is loaded from the secondary memory to the main memory?

3. Discuss the technic used by the operating system to move a process from the main memory to secondary memory?

4. Discuss what will happen if the program is greater than the main memory?

9.5.1. Memory segmentation

A Memory Management technique in which memory is divided into variable sized chunks which can be allocated to processes. Each chunk is called a Segment. A table stores the information 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 starting physical address where the segments reside in memory.

•Limit: It specifies the length of the segment.

Advantages of Segmentation:

•No Internal fragmentation.

•Segment Table consumes less space in comparison to Page table in paging.

Disadvantage of Segmentation:

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

9.5.2. Memory swapping

Swapping is a useful technique that enables operating system to execute programs by moving the program from and to the main memory. When the operating system needs data from the disk, it exchanges a portion of data (called a page or segment) in main memory with a portion of data on the disk.

9.5.3. Virtual memory

a. Understanding the virtual memory

Virtual memory is a technical concept that lets the execution of different processes which are not totally in memory. One main benefit of this method is that programs can be larger than the physical memory.

Virtual memory abstracts primary memory into a very large, consistent array of storage that divides logical memory as viewed by the user from that of physical memory. This technique is used to free programmers from the anxiety of memory storage limitations.

b.Uses of Virtual Memory

Virtual memory also permits processes for sharing files easily and for implementing shared memory. Moreover, it offers a well-organized mechanism for process creation. Virtual memory is not that easy to apply and execute. However, this technique may substantially decrease performance if it is not utilized carefully.

c. Virtual Address Space (VAS)

The virtual address space of any process is defined as the logical (or virtual) view of how any process gets stored in memory. Normally, this view is where a process begins at a certain logical address (addresses location 0) and then exists in contiguous memory.

Although, the fact is physical memory might be structured in the form of page frames arid where the physical page frames are assigned to a process that may not be adjacent to each other. It depends on to the memory management unit (MMU) which maps logical pages to physical page frames in memory.

9.5.4. Concept of Demand Paging

Think of how an executable program could have loaded from within a disk into its memory. One choice would be to load the complete program in physical memory at program at the time of execution. However, there is a problem with this approach, that you may not at first need the entire program in memory. So the memory gets occupied unnecessarily.

An alternative way is to initially load pages only when they are needed / required. This method is termed as demand paging. It is commonly utilized in virtual memory systems.

Using this demand paged virtual memory, pages gets only loaded as they are demanded at the time of program execution; pages which are never accessed will never load into physical memory.

A demand paging scheme is similar to a paging system with swapping feature where processes exists in secondary memory (typically in a disk). As you want to execute any process, you swap it into memory internally. Rather than swapping the complete process into memory, you can use a “lazy swapper”. A “lazy swapper” in no way swaps a page into memory unnecessarily unless that page required for execution.

9.5.5. Hardware Required for the Concept of Demand Paging

The hardware required for supporting demand paging is the same that is required for paging and swapping:

•Page table: Page table has the capability to mark an entry invalid or unacceptable using a valid-invalid bit.