The Linux Operating System

Linux is a freely distributable clone of the UNIX operating system created by Linus Torvalds. In 1991 Linus was a student at the University of Helsinki in Finland and the only operating system that Linus could afford was a very simple UNIX clone named Minix written by Andrew Tanenbaum. Linus found Minix to be lacking and decided to write his own operating system to satisfy his needs and as a way of exploring the Intel 80386 hardware.

 From April 1991 to October 1991 Linus worked in assembly language on low-level portions of the operating system. In October Linux was far from complete but it was stable enough that Linus posted a USENET message to comp.os.minix asking for help with the project and switched to using C as the primary development language.

 From a humble beginning of a student's Intel 386-based operating system Linux has grown to become one of the most popular versions of UNIX in the world. As the popularity of Linux has grown, so have the number of platforms that run Linux. Among the current platforms are the DEC Alpha, PowerPC, Sun SPARC, MIPS and Intel 86. Projects for porting Linux to other platforms such as the Motorola 680x0, Power Macintosh, Fujitsu AP1000+ and Palmtop computers are underway.

 The same reasons that drove Linus to create Linux drove many of the other early Linux developers. Namely, some personal need that was not available to them in other operating systems. With no thought of direct profit or marketing deadlines driving the developers the result has been an operating system full featured and stable. Linux is so stable that users have reported uptimes of more than a year without an error, crash or the need to reboot. At last report one site reported an uptime of over 600 days.

 It is noteworthy that it is users and not developers or marketing that has driven the growing popularity of Linux. While commercial development of Linux software has been slow in the past that is starting to change. Carlton Doe, the Database Administrator at Associated Food Stores Inc. and director of advocacy for the International Informix Users Group, reports that the number one requested product from Informix was a Linux version of their Dynamic Server. Other large developers such as Corel, Oracle and Sybase are starting to take notice of the growing Linux community and port their software to Linux.

 One of the first things that a new Linux user notices is the user interface. Not only can Linux' user interfaces differ from other systems', it can differ from user to user. Linux allows the choice of user interfaces on a case by case basis because the user interface is not part of the operating system; the user interface is implemented by user applications. Only low-level system calls necessary to a user interface are provided by the operating system.

 By implementing the user interface through user applications Linux allows the utmost in flexibility and user choice. Not only can a user choose which user interface or interfaces they want use they can even choose to have no interface at all. The choice of the initial user interface is made at system boot-up.

 Before the user interface can be brought online, Linux first needs to examine the hardware looking for available resources. Linux performs this examination directly without using the BIOS. By using specialized routines to access the hardware directly, Linux is able to find and automatically configure resources that traditionally are hard to auto-detect.

 One method that Linux uses to carry out this auto-detection is to enable all hardware interrupts and have a given device driver attempt to cause its device to generate an interrupt. If the driver is successful in causing the interrupt, the interrupt is checked to see if it is already in use and assigned to the device if found to be available. Available does not necessarily mean that the interrupt is not in use. Linux provides mechanisms for the sharing of interrupts among devices. An interrupt is found to be shareable if the first device to allocate the interrupt allows the sharing.

 After the hardware is found and configured the next step in the boot process that Linux performs is to start a program named init. There are many different versions of init. Exactly what init does varies with each version and the system on which it is run. All versions of init share some commonality in that they all perform some sort of routine system startup tasks. The last step that all versions of init perform is the starting of other processes. Figure 1 illustrates the steps init might take to start a remote login session.

 Init first performs the fork() system call, which makes a copy of the process, refereed to as a child process, from the init process. Upon startup the child process executes the system call exec("/sbin/getty"), which starts the proper login session. The login in turn executes other programs necessary to perform the login and ultimately to perform some user task.

 In this example there is an important difference between the fork() and exec() system calls; the fork() system call does not wait for the child process to finish. This difference allows init to start many different processes running at the same time.

Running more than one process at a time is referred to as multitasking and in order for an operating system to multitask it must keep track of process information. Linux keeps track of this information in a doubly linked list of process data structures.

 The process data structures contain information for such things as memory usage, scheduling information, process ID, and process state: running; waiting; stopped; dead.

 To perform multitasking Linux uses a scheduler that examines this process information and decides which process to run next. The scheduler employs a prioritized, preemptive, round robin, FIFO algorithm. If the scheduler finds any real-time processes then those will get higher weighting than ordinary processes. The weight for a normal process is its time-slice; the length of time it is allowed to run at one time. For a real-time process its weighting is its time-slice plus 1000. This means that if there are any runnable real-time processes in the system then these will always be run before any normal runnable processes. The current process having consumed some of its time-slice is at a disadvantage if there are other processes with equal priority in the system. That is as it should be. If several processes have the same priority, the one nearest the front of the run queue is chosen. The current process will be put on the back of the run queue. In a balanced system with many processes of the same priority, each one will run in turn.

 If the next process to run is not the current process, then the current process must be suspended and the new one made to run. When a process is running it is using the registers and physical memory of the CPU and of the system. Each time it calls a routine it passes its arguments in registers and may stack saved values such as the address to return to in the calling routine. When a process is to be suspended all of its machine state, including the program counter and all of the processor's registers, must be saved in the process's data structure. Then, all of the machine state for the new process must be loaded. This is a system dependent operation, no CPUs do this in quite the same way but there is usually some hardware assistance for this act.

 If the previous process or the new current process uses virtual memory then the system's page table entries may need to be updated.

 Virtual memory is the process of using a disk as an extension of RAM so that the effective size of usable memory grows correspondingly. The operating system writes the contents of a currently used block of memory to the hard disk so that the memory can be used for another purpose. When the original contents are needed again, they are read back into memory. This is all made completely transparent to the user. Programs running under Linux only see the larger amount of memory available and do not notice that parts of the memory resides on the disk from time to time. Of course, reading and writing the hard disk is slower than using real memory, so the programs do not run as fast. The part of the hard disk that is used as virtual memory is called the swap space.

 Linux implements virtual memory using a paged, demand loading, copy-on-write algorithm. The physical memory is divided into 4K segments called page frames. The page frames are allocated and loaded with information as processes actually reference the information. This demand loading applies to processes as well; portions of a process not reference will not be loaded into memory. Any page frames that are used but have not been referenced for a period of time will be unloaded and the space freed for future use. This unloading happens even if other processes do not need the space. This allows the operating system to save time in loading pages when they are needed.

 The copy-on-write feature of Linux' virtual memory enables processes to share physical memory without the processes being aware of the sharing. Processes can share the same area as long as they do not try to write to it. When a process writes to a shared area the operating system first copies the memory page to another page frame and redirects the writing process to that page frame.

 Copy-on-demand is used in a variety of system functions; from the loading of executable and data files to the storage of system information in memory. In general, anything found to be redundant that is held in memory shares one copy of the information until something tries to modify the information.

 An example of this is the afore mentioned fork() system call. It was stated earlier that fork() was used to create copies of the init process. If fork() was allowed to make copies of the init process you could run out of memory just getting the system running. Instead when Linux executes a fork() it does not copy the process but simply copies the process structure and adds the new structure to the running process queue. Both the old and new processes run in the same memory space and the operating system ensures that the processes do not over write each other.

 Figure 2 illustrates just how quickly we could run out of memory if copying processes took place. In this example init has forked five times with httpd forking nine times and bash forking once. Without copy-on-write we would have twenty-three processes taking up memory; with copy-on-write we only have ten processes in memory. It is important to note that the init used in this example is much smaller than would be typically found in an actual system. Therefore, the real-world differences can be even greater than depicted here.

 As was mentioned at the beginning of this paper, the source code for the Linux operating system is freely available to anyone who wants it. Some might think that this would result in an operating system that was less secure than other operating systems that kept the source code a closely guarded secret. This typically has not been the case with Linux. While it is true that Linux has its share of security holes and the openness of the source code allows those holes to be exploited easier, the openness allows holes to be found and fixed faster. With people all over the world working to fix security holes the holes are generally fixed in a matter of hours or days and not the weeks or months that other operating systems typically take. Often the speed at which the holes are fixed is so great that the security problems are fixed before they can be announced to the public. This rapid response time is a great boon to the security of the Linux operating system and results in an overall more secure system.

 The overall security of Linux relies heavily on the UNIX user ID, group ID schema. In this schema each user is assigned a unique ID and possibly is assigned one or more group IDs. These IDs are checked against any file that a given user tries to access and only those with the correct permissions are allowed access. File permissions are assigned to each user for read, write and execute and the permissions are assigned on a file by file, directory by directory, basis. System resources such as printers and modems are also assigned permissions as if they where files. These permissions give the operating system the ability to control who has access to information and system resources, and who does not.

 Linux extends the UNIX user ID, group ID schema to make it easier to manage groups of users. Linux performs this extension by mandating that all users are assigned a private group. This private group has only one member, the user in question. By mandating that all users have a group assigned Linux is able to use the current group ID of a user in determining resource access permissions. The result of this extension is that files created by one member of a group are automatically accessible by all group members and files created by a private group are accessible to just the one user. The results can be achieved by other implementations of UNIX but not with the transparency afforded by Linux.

 The Linux operating system has stood the test of time and has grown to meet its users needs. If it can withstand the growing pains as it makes its transition to a mainstream operating system it should be around for many years to come.