This report consists of the research, investigation and documentation of area relating to the Operating system (OS) and Computer System Architecture (CSA). There are two sections in this report, the first section is about memory management in UNIX and second section consists of discussion about usage of registers in a modern computer.
The first section includes how the memory is being partition in UNIX. In addition, this report also discuss about the strategies used by UNIX in memory management. Besides, this report also identifies the problems faced by the strategies and solutions to overcome the problem.
In the second section, the report explains about the usage of registers in a computer. The types of the general registers and register size will also been identified. Besides, the report will also discussed about two different organisation types of registers.
According to Leon (2007), UNIX is an operating system (OS) is software that manages hardware and software resources of a computer. UNIX was first developed in the 1960s and has been constant development ever since. UNIX is one of the most widely used operating systems in industry, government and education. It is a stable, multi-user, multi-tasking system for servers, desktops and laptops.
UNIX Memory Management
Memory is an important resource in computer. Memory management is the process of managing the computer memory which consists of primary memory and secondary memory. The goal for memory management is to keep track of which parts of memory are in use and which parts are not in use, to allocate memory to processes when they need it and de-allocate it when they are done. UNIX memory management scheme includes swapping and demand paging.
The simplest form of memory management is splitting up the main memory into multiple logical spaces called partition. Each partition is used for separate program. There are 2 types of memory partitioning:-
Single Partition Allocation
Single partition allocation only separates the main memory into operating system and one user process area. Operating system will not able to have virtual memory using single partition. Using single partition is very ineffective because it only allows one process to run in the memory at one time.
C:\Users\Eric\Desktop\hssn pic\single partition.jpg
Figure 1.1: Single Partitioning (Drawn by Kim)
Multiple Partition Allocation
Most of the operating system nowadays is using multiple partitions because it is more flexible. Multiple partition allocation enabled multiple programs run in the main memory at once. Each partition is used for one process.
There are two different forms of multiple partition allocation, which is fixed partitioning and variable partitioning. Fixed partitioning divides memory up into many fixed partitions which cannot be change. However, variable partitioning is more flexible because the partitions vary dynamically in the later as processes come and go. Variable partitioning (Variable memory) has been used in UNIX.
C:\Users\Eric\Desktop\hssn pic\fix variable partition.jpg
Figure 1.2: Fixed Partitioning and Variable Partitioning (Drawn by Kim)
UNIX Memory Management Strategies
Overlays
Program will be place into memory during execution. However, a large program will divide into small pieces and loading the pieces as they needed. Overlays will replace the new pieces with the program which is unused. UNIX is using this technique to run a new program by fork the running process which is also known as fork-exec. The overlays technique is illustrated below.
C:\Users\Eric\Desktop\hssn pic\overlay.jpg
Figure 1.3: Overlay Process (Drawn by Kim)
Swapping
Swapping consists of bringing in each process in physical memory entirely and running it. When the process is no longer in use, the process will be terminated or is swapped out to disk.
The procedure of swapping is illustrated in figure 1.3 below.
C:\Users\Eric\Desktop\hssn pic\swapping.jpg
Figure 1.4: Swapping (Drawn by Kim)
Initially only process A is in memory. Then process B is swapped into memory from disk. After that, process A terminates or swapped out to disk. Then process C is swapped into the free space.
External Fragmentation Problem
The size of each process is different, therefore when the processes is been swapped in and out, there will be a multiple holes in the memory because UNIX is using variable partitioning.
C:\Users\Eric\Desktop\hssn pic\holes.jpg
Figure 1.5: External Fragmentation (Drawn by Kim)
Solution
There are two techniques to solve this problem, which are memory compaction and fit in the process using algorithms
Compaction
C:\Users\Eric\Desktop\hssn pic\compaction.jpg
Figure 1.6: Compaction (Drawn by Eric)
Memory compaction moves all the processes upward as far as possible, so that all the free memory is placed in one large block. However, it is not a good idea because it requires a lots of CPU time.
Most processes will grow as they run, and the processes data segments can grow, as in many programming languages, the process will grow. If there is a hole is next to the process, it can be allocated and the process is allowed to grow into the hole. Therefore it is good to allocate some extra memory whenever a process is swapped in or out.
Figure 1.7: Allocating Space for Growing Data (Extracted from http://www.cs.rpi.edu/~hollingd/opsys-fall2006/notes/Chapter4/Chapter4.pdf , 22 April 2011)
Algorithms
There are three different types of algorithm can be used to loads the program wherever the memory space is unused, which is first fit, best fit and worst fit.
Algorithms
Descriptions
First Fit
The memory manager scans along the list and allocates the first space to fit the process. First fit is a fast algorithm because it searches as little as possible.
Best Fit
The memory manager scans the whole list and takes the smallest hole that will fit the process. Best fit is slower than first fit because it must search the whole list every time it is called.
Worst Fit
The memory manager scans the whole list and takes the largest available hole, so that the hole broken will be big enough to be useful.
Virtual Memory
UNIX operating system allows user to fully utilize the physical memory installed in the system as well as part of the hard disk called swap space which have been designated for use by the kernel while the physical memory is insufficient to handle the tasks.
Virtual memory managers will create a virtual address space in secondary memory (hard disk) and it will determine the part of address space to be loaded into physical memory at any given time. The benefit of virtual memory relies on separation of logical and physical memory.
C:\Users\Eric\Desktop\hssn pic\VR.jpg
Figure 1.8: Logical Memory and Physical Memory (Drawn by Kim)
Demand Paging
Paging is a memory allocation strategy by transferring a fixed-sized unit of the virtual address space called virtual page whenever the page is needed to execute a program. As the size of frames and pages are the same, any logical page can be placed in any physical frame of memory.
Every processes will be logical divided and allocate in the virtual address space. There is a page table in the virtual memory to allocate and keep tracking of the pages to map into the frames.
C:\Users\Eric\Desktop\hssn pic\paging pic.jpg
Figure 1.9: The relation between virtual addresses and physical memory addresses is given by the page table (Drawn by Kim)
UNIX will perform page swapping only when the program needs a certain page. This procedure is called demand paging. The page will be paged into the memory only when it is needed to execute. The whole process will not be paged into the memory, only the pages needed are swapped in.
Demand paging decreases the paging time and physical memory needed because only the needed pages will be paged and the reading time of the unused pages can be avoided.
C:\Users\Eric\Desktop\hssn pic\deand paging.jpg
Figure 1.10: Demand paging (Drawn by Kim)
As the example in the figure, only page 6, 7, 8 and 9 is needed in Process A. Therefore, only pages 6, 7, 8 and 9 will be paged into the memory.
Page Fault Problem
A page fault occurs when a program try to use a page that is not in the memory, due to demand paging will only paged the pages into the memory when it is needed. For example in figure 1.9, if the program try to use Page 1 for Process A in memory, the operating system will interrupt occurs as a result of trying access a missing page because Page 1 is not paged in the memory.
Solution for Page Fault
C:\Users\Eric\Desktop\hssn pic\Page Fault Handling.jpg
Figure 1.11: Page Fault Handling (Retrieved from Slides Material: Chapter 17 slides 6)
The diagram above illustrated the steps in handling page fault. When page fault occurs during program execution, the kernel will first locate the missing page on the backing store (disk). After located the page, it will find a free memory frame in the physical memory and copy into it. The page table will be reset after that and the instruction will be restart.
Problem- No Free Frames
When all the frames in the memory is been used, the other problem will occurs. This will cause the pages is unable to paged into the memory.
Solution- Page Replacement Algorithms
Solution for no free frames problem is to find a memory frame that is idle and free the frame using a page replacement algorithm. There are three common types of page replacement algorithm such as First in First out (FIFO), Optimal and Least Recently Used (LRU).
UNIX is using least recently used algorithm for page replacement. The least recently used algorithm replaces the page that has not been used for the longest time, on the assumption that the page will not be needed again. The page table will record every time the page being referenced, and when page replacement is needed, every page will be checked to find the oldest recorded time.
Conclusion
Every operating system has different memory management. UNIX also has their exclusive memory management strategies to manage the memory resource optimally. UNIX is using multiple and variable partitioning so that the memory can be stored and use more flexible.
UNIX uses overlays and swapping to replace the unused program. However, it is facing external fragmentation problem and solve by loading the program into memory by using best fit algorithm.
Besides, UNIX also fully utilized the virtual memory (physical memory and swap space) by using demand paging. It allows user to store physical memory in the hard disk because the RAM memory was always insufficient.
Frequently Ask Question (FAQ)
What is a Kernel Memory?
UNIX owns a (semi-)private memory space called Kernel memory. Kernel uses RAM to keep itself memory resident to ensure that user programs do not overwrite or corrupt the kernel /user's data structures. Strong memory protection is implemented in kernel memory management to keep users from corrupting the system area.
C:\Users\Eric\Desktop\kernel.jpg
Figure 1.12: Kernel memory (Drawn by Kim)
What is fork in UNIX?
Fork is a function used to duplicate a process. The newly created process is called "Child" and the original process called "Parent".
What is the difference between Swapping and Paging?
Swapping
Paging
- Bringing in each process in physical memory entirely and running it.
- Only the needed pages to execute the program will be swapped in.
- Not using Virtual Memory.
- Use advantage on Virtual Memory.
- Process size must be equal or less than main memory.
- Process size can be greater than main memory.
- Less flexible in handling memory.
- More flexible in handling memory.
Limitations
Level of Understanding
Too many technical terms used by the information resources are difficult to understand by a degree level 1 student.
Dissimilar Information
Some facts might have different explanation due to different websites or books with different authors.
Section 2: Computer System Architecture
Usage of Registers in a Modern Computer
Introduction
Register is a temporary high-speed storage area holds data and instructions. According to Englander (2000), a register is a permanent storage location within the Central Processing Unit (processor) used for a particular, defined purpose. A register is used to hold a binary value temporarily for storage, manipulation and simple calculations.
Register are located at the top level of memory hierarchy. It is the fastest memory in the hierarchy because the processor can access register in the shortest time. The frequency of access by the processor (locality of reference) is also highest. However, the memory capacity of register is the smallest and most expensive compare to the other memory storage.
C:\Users\Eric\Desktop\hssn pic\memory hierarchy.jpg
Figure 2.1: Memory Hierarchy (Drawn by Kim)
Reasons for Registers
Register are one of the main components in the CPU (Processor). Function of registers is to hold data being processed, stores data while ALU computes it, stores instruction being executed, a memory or I/O addresses to be accessed, or keep track the status of the computer or the conditions of calculations.
C:\Users\Eric\Desktop\hssn pic\CPU.jpg
Figure 2.2: Central Processing Unit (Processor) (Drawn by Kim)
There are many different types of registers, each register within the CPU perform its specific role.
Types of Registers
Generally registers can be grouped into two major categories, which include:
User-Visible Registers
Control and Status Registers
However, according to Stallings (2007), there is not a clean separation of registers into these two categories. For example, on some machines the program counter is user visible (e.g VAX), but on many it is not.
User-Visible Registers
C:\Users\Eric\Desktop\hssn pic\user vis reg.jpg
Figure 2.3: Types of User-visible Registers (Drawn by Kim)
User-visible registers are those registers used by the machine- or assembly-language programmer to minimize main memory references by optimizing use of registers. These registers can be categorized into following different types:
General Purpose Register - Used to hold data for arithmetic, logical, and addressing operations as well as results.
Data Register- Only can be used to hold data and cannot be employed in the calculation of an operand address.
Address Register- Used for storing the memory location of data and instruction to be used by a program. They may use in general purpose addressing modes or may be constant to a particular addressing mode. For example:-
Segment pointers- Used for machine with segmented addressing
Index Register- Used for indexed or auto indexed addressing.
Stack Pointer- Used during the sub-routine nesting and stack based arithmetic.
Condition codes (flags)- Condition codes only partially visible to user. Flags are used to set the result of CPU hardware operation and determine whether some instruction should or should not execute.
Control and Status Registers
Control and status registers are used to control the operation of the CPU. Most of these registers are not visible to user.
There are four registers are fundamental to instruction execution:
Program counter (PC)- Contains the address of an instruction to be fetched
Instruction Register (IR)- contains the next instruction to be executed
Memory Address Register (MAR)- contains the address of a location in memory
Memory Buffer Register (MBR) - receives instructions and data from the memory or transfer data to memory as needed by processor.
Program Status Word (PSW)
PSW contain status information and condition codes (flags). Some of these may be user visible. The common flags include:
Sign: Contains the sign bit of the result of the last arithmetic operation
Zero: Set when the result is 0.
Carry: Set if an operation resulted in a carry (addition) into or borrow (subtraction) out of a high-order bit. Used for multiword arithmetic operations.
Equal: Set if a logical compare result is equal
Overflow: Used to indicate arithmetic overflow
Interrupt enable/disable: Used to enable or disable interrupts
Supervisor: Used to determine whether CPU is executing in supervisor or user mode. Some of the instructions/ memory can only be executed/ accessed in supervisor mode.
Organization types of Registers
Every organization or manufacture will have their unique ways to allocate their registers in the microprocessor. In this section, we will look into two different registers organization which is from Motorola and Intel: the Motorola MC68000 and Intel 8086.
Both Motorola MC68000 and Intel 8086 are 16-bit microprocessors that were designed at about the same period. Figures 2.4 And 2.5 illustrates each register organization. The figures only contain purely internal registers such as memory buffer register (MBR), are not included.
Motorola MC68000
C:\Users\Eric\Desktop\hssn pic\mc68000.jpg
Figure 2.4: MC68000 Register Organization (Drawn by Kim)
The Motorola MC68000 contains eight data registers and nine address registers. The width of both register is in 32bit. The use of data registers are for data manipulation and addressing as index register. The register also allows 8, 16, and 32 bit data operations. Both data registers and address registers are also used as stack pointers, one for users and the other one for the operating system.
Address registers contains two numbered 7 register because only one can be used at a time. The MC68000 also includes a 32-bit program counter that holds the address of instruction going to execute and a 16-bit status register to keep track of special condition of computer such as power failure and internal computer error.
Intel 8086
C:\Users\Eric\Desktop\hssn pic\intel 8086.jpg
Figure 2.5: Intel 8086 Registers Organization (Drawn by Kim)
The Intel 8086 is come up to with different way in register organization. The 8086 contains a set of general registers, four 16-bit pointer and index registers, four 16-bit segment registers and program status registers.
General Registers
The general registers consist of accumulator register (AX), base register (BX), count register (CX) and data register (DX). Intel is naming the registers A, B, C, D accordingly using acronyms meaning. These four registers could be accessed as bytes. Therefore, instructions could individually access the low-order or high-order byte of the registers. For example, accumulator (AX) consists of AL and AH.
Pointer and Index Registers
Besides, the pointer and index registers consists of base pointer (BP), stack pointer (SP), source index (SI) and destination index (DI). The base pointer is used as a pointer to the base of a stack within memory. Stack pointer are used to keep track of the location within a stack. However, source index and destination index are used to keep track of location within an array.
Segment Registers
Segment registers are generally used to implicit. There are also four segment registers which is code segment (CS), data segment (DS), stack segment (SS) and extra segment (ES). CPU instructions will be stored in code segment. Data segment will be used to hold most memory references.
Program Status Registers
Program Status Register includes an instruction pointer and a set of 1bit status and control flags. Instruction pointer will hold the address of instruction going to execute.
Conclusion
Registers play an important role in the processor, as it will hold the data computed by ALU and instructions fetched by the Control Unit. There are many different types of registers, each register will perform specific role. However, different processor will have different registers organization to maximize the usage of the processor.
Frequently Ask Question (FAQ)
What is Central Processing Unit (CPU)?
CPU is act like the brain of a computer, where all the processing takes place. CPU will interpret and carries out basic instruction to operate a computer. CPU is also known as microprocessor.
What is the different between cache and register?
Cache is part of the Random Access Memory (RAM) that store frequently accessed data. Register is part of the processor that temporary store runtime values, storage address, computer instruction and others. However, processor can access data faster from register than cache.
What flags are available in Program Status Register of Intel 8086?
According to Englander (2000), there are nine flags available in program status register of Intel 8086. The figure below shows the name and function of each flag.
C:\Users\Eric\Desktop\hssn pic\x86 flags.jpg
Figure: Intel 8086 Flags (Extracted from The Architecture of Computer Hardware and System Software by Englander I., 2000, chapter 12: Three system Examples)
Limitations
Lack of Updated Information
Latest detailed technology information is not possible to find through websites or books due to the website and books in library are not updated enough.
Level of Understanding
Some information shown in books or websites are too technical for a degree level one student to understand the idea.
Appendices
Layered Architecture of the UNIX system(Extracted from Fundamentals of Computer Technology, 2007 by LEON.A. and LEON. M.)
Text Segment
Initialized Part of Data Segment
Uninitialized Part of Data Segment
Heap Storage
Stack Segment
Environment Variables, etc
Low Address
High Address
The UNIX-style Memory layout (Extracted from Operations Systems by Gary Nutt 1997, Chapter 11: Memory Management)
Registers (Extracted from: http://schoolnet.gov.mt/keith.aquilina/resources/storage/Data_registers.htm )
C:\Users\Eric\Desktop\hssn pic\appen.jpg
A simplified view of CPU (Extracted from: http://www.just2good.co.uk/cpuInstruction.php)
