Introduction To Linux Operating System Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

According to B.Shelly et al. (2012, p.15) Operating System is defined as a set of program that coordinates all the activities among computer hardware devices. The Operating System or also known as OS allows the users to communicate with the computer and other software. In today's world where computers are commonplace there are various types of operating system such as Microsoft's Windows, Mac OS; Apple's operating system, Linux OS and so on.

Linux is a Unix-like operating system developed from a kernel is created by Linus Trovalds a graduate from University of Helsinki of Technology, Finland. Worldwide group of volunteers collaborated in developing this operating system through the Internet. Linux is also free and open source. Besides that, it is also meant to be used as an alternative to other operating system such as Windows, Mac OS, MS-DOS, Solaris and so on. Linux is also known as an interface between computer or server hardware and the program which run on it.

Furthermore, Linux is also a multitasking, multi-user operating system that acts like UNIX in terms of kernel behavior, and peripheral support. The kernel of the Linux operating system is monolithic; it is built out of various modules that handle the several aspect of the operating system such as file systems, memory management, process scheduling and many more.File:Tux.svg

Figure Tux the penguin is the mascot for Linux

(Image Source: accessed on 30th December 2012

1.1 Memory Management of Linux Operating System

The purpose of a memory management would be to enhance the use of Random Access Memory; RAM. Linux kernel provides Virtual memory for their programs. The operating system allocates a portion of storage medium, the hard disk and functions as an additional RAM.

The virtual memory is distributed into numerous fixed-sized chunks which are known as Pages, the most common size are 4 Kbytes or 8 Kbytes In order to execute programs efficiently, the operating systems chooses on which pages should be retained in the hard disk, in order to carry out these, there are some algorithms. The various aspect of Linux memory management would be by Paging, Data structures, and Memory area management.

1.1.1 Paging

Paging is a memory management scheme. Logical address space of a process is divided into fixed sized blocks known as Pages and also divides the physical memory into number of equal sized blocks known as Frames. In order to translate the logical to physical address, a Page Table is needed.

Figure Simple Paging Structure to translate address.

(Image Source: Ramani Yellapragada, May 26, 2003 From Linux Memory Management, accessed on 30th December 2012)

"Linux uses three level paging strategies; each page table is referred to 10bits" (Yellapragada, 2003, p5). This strategy is appropriate for both 32-bit and 64-bit architecture. Each of these page tables is stored in a page frame.

Figure Paging in Linux

(Image Source: Yellapragada.R, May 26, 2003 From Linux Memory Management, accessed 30th December 2012)

As explained by (Yellapragada.R, 2003, p6), referring to Figure 3, there are three levels of page tables, each of these are stored in a page frame. In the Global Directory have several addresses of page tables for the Middle Directory, which comprises addresses of Page Tables that point to the desired Page Frames. Besides that, the Middle Directory has 0 bits for the 32 bits architectures. In each of this process it has its very own page table for Global Directory and sets of Page Tables.

To switch the context, cr3 register value corresponding to the new process's page tables is required to be changed. On the other hand, to handle the page table there are various macros and functions provided. To develop virtual address translation speed, Translation Lookaside Buffer (TLBs) is provided. Linux retains a software cache; an array of page frames for allocation and deallocation of page tables or pages.

1.1.2 Data Structures

Another memory management aspect of Linux would be data structures. The user process can run in two modes which are user mode or kernel mode during the execution. The first 3GB of processors pages are addressable in both the user and kernel mode; the last GB is only addressable in kernel mode. Therefore, the kernel requires differentiating between page frames that comprehends pages belonging to the kernel or user code and data structures.

The kernel also needs to keep track of which frames are free and occupied; this information is retained in an array of descriptors for every single page frame in the structure known as page.

Figure Array of descriptor of each page frames in Page

(Image Source: Ramani Yellapragada, May 26, 2003 From Linux Memory Management, accessed 30th December 2012)

Buddy System Algorithm is used by Linux kernel to allocate groups of contiguous page frames. The Buddy System Algorithm was invented by Harry Markowitz in the year 1963 and described by Kenneth C.Knowlton in year 1965; it divides memory into partitions to satisfy the requested memory suitability. The above structures operate based on the providence of various macros and functions.

1.1.3 Memory Area Management

Linux uses a system to handle memory areas which is the Slab Allocator and uses also the Buddy system to get new page frames. The information about the memory free areas in each page frame is used to be kept. Memory management comprises competent fulfillment of memory needs in processes from limited amount of memory. Programs requests blocks of memory that might involve several pages. The operative way of handling such issue is by allocating groups of contiguous pages at the same time dealing with external fragmentation.

The Buddy System Algorithm allocates blocks of certain pre-defined sizes, which are usually in power of two. The maintenance of the list that defines certain blocks sizes. When a memory requests the allocator, it rounds the requests to the nearest block size it searches at the free block list of the required block size. When the demanded list are found, the blocks are allocated to the process and marks as unavailable, if it is not found, a free list of next larger size is searched. If such lists if found, process is assigned to the process and adds it to the other half and next to the lower size free list.

The name Buddy algorithm represents on the way the page frame are released, the free buddy blocks are merged together as a pair into a age frame of 2k. They are located in contiguous memory addresses, merging process is repeated recursively until the largest block size is achieved or no free lists are available. This system is also used to maintain unavailable page frames and then assigns it to processes.

1.2 Problems in Linux Memory Management

The Linux operating system has a slight hitches or problems on the memory management mechanism. Linux uses Buddy System Algorithm in the memory area management to overcome external fragmentation; where it is a contiguous memory allocation when it comes to memory requirements are varying sizes. This reasons the memory space to be fragmented non-contiguously preventing to fulfill large requests (Yellapragada, 2003, p2).

The problem that arises by using Buddy System Algorithm would be internal fragmentation. This problems arises when the requested memory size is less than the allocated memory, this results in the excess memory in bytes goes to waste. The unusable memory is within the allocated region (Yellapragada, 2003, p7).

In order to handle the problem with memory management area, Linux resolves this issue by introducing Slab Allocator System

1.2.1 Solution; Slab Allocator System

The slab allocator system is used by Linux operating system to overcome internal fragmentation and also acts as a software cache for memory requirements less than the size of a page. In the year 1994, this system was developed for Sun Microsystem Solaris 2.4 operating system. The slab allocator system in Linux developed in a way that the memory areas as objects comprising of data and techniques to operate such data. The existing memory created object in memory is re-used, so that similar memory requests could use the same objects.

Besides that, slab allocator also benefits in a way that recurrent requests of memory can be handled competently which lessens internal fragmentation. When hardware cache is used, slab allocation strategy is more beneficial. A part of the main memory is used for objects by the slab allocator. The memory is organized into caches, where later than it divides into slabs. There one or more page frames that contains allocated free objects in each slab. The frames are obtained from the Buddy System. These frames are not released unless free frames are needed (Yellapragada, 2003, p7).

1.2.2 Solution; Genetic Algorithms

John Holland at University of Michigan introduced Genetic Algorithm in United States in the 1970s. in the computer science filed of artificial intelligence, a Genetic Algorithm is a heuristic search which stimulates the process of natural evolution, it used to produce valuable to function optimization and search problems by using techniques such as inheritance, mutation, selection, and crossover.

Based on journal written by (Rosso, C. 2006, p1) an approach for improving memory efficiency and internal memory fragmentation by finding the optimal configuration of a segregated free lists data structure. In the journal it is stated that that proposed for using self-tuning system using genetic algorithm with an recently announce in Linux kernel mailing list, a patch has been submitted to tune the Linux operating system using genetic algorithms. (Rosso,C. 2006, p3).

Genetic Algorithm is used in contexts by numerous scientific community and engineers to solve chosen scenario. The stimulator environment is used to examine internal fragmentation; the optimization function has several parameters such as the bin size and amount of chunks for each bin. The minimum and maximum value of bin size and word processor word size are in bytes. The GA format means the parameters are encoded in fixed size string the genetic algorithm (Rosso, C.p3).However, the genetic algorithm has a problem as shown in Figure 5.

Figure the Genetic Algorithm (GA) encoding problem.

(Image Source: Christian Del Rosso, May 20, 2006 From Reducing Internal Fragmentation in Segregated Free Lists using Genetic Algorithms, pages 3, accessed 26th January 2013)

However, the experiment has proved that using this approach it is able to have an optimal configuration for the specific scenario, the industry realm "if it works, it is fine" it proves that more quantified evidence is needed to use this method to solve internal fragmentation in Linux. (Rosso,C. p4)

In, conclusion this prove s that the slab allocator used by Linux operating system is equally effective in managing memory and improves the system 's overall cache utilization and bus balance. Besides that, Genetic Algorithm is another approach that can be used to reduce internal fragmentation in segregate free list, but there is a problem in the encoding sequence but by configuring these problems it can be used as a another solution to decrease internal fragmentation.