LINUX INTERNALS - Computer Science and Engineering

1 LINUXINTERNALSP eter Chubb and Etienne Le BIT OF HISTORY Ken Thompson and Dennis Ritchie in 1967 70 USG and BSD John Lions 1976 95 Andrew Tanenbaum 1987 LINUX Torvalds 1991 NICTA Copyrightc 2011 From Imagination to Impact2 The history of UNIX-like operating systems is a history of peoplebeing dissatisfied with what they have and wanting to do some-thing better. It started when Ken Thompson got bored with MUL-TICS and wanted to write a Computer game (Space Travel). Hefound a disused PDP-7, and wrote an interactive operating sys-tem to run his game. The main contribution at this point was thesimple file-system abstraction. (Ritchie 1984)Other people found it interesting enough to want to port it to othersystems, which led to the first major rewrite from assembly toC.

2 In some ways UNIXwas the first successfully portable Ritchie & Thompson (1974) was published, AT&T becameaware of a growing market for UNIX. They wanted to discourageit: it was common for AT&T salesmen to say, Here s what youget: A whole lot of tapes, and an invoice for $10 000 . Fortunatelyeducational licences were (almost) free, and universities aroundthe world took up UNIXas the basis for teaching and University of California at Berkeley was one of those univer-NICTA Copyrightc 2011 From Imagination to Impact2-1sities. In 1977, Bill Joy (a postgrad) put together and releasedthe first Berkeley Software Distribution in this instance, themain additions were a pascal compiler and Bill Joy BSDs contained contributed code from other universities,including UNSW.

3 The BSD tapes were freely shared betweensource licensees of AT&T s Lions and Ken Robinson read Ritchie & Thompson (1974),and decided to try to use UNIXas a teaching tool here. Ken sentoff for the tapes, the department put them on a PDP-11, andstarted exploring. The license that came with the tapes alloweddisclosure of the source code for Education and Research so John started his famous OS course, which involved readingand commenting on the Edition 6 source 1979, AT&T changed their source licence (it s conjectured, inresponse to the popularity of the Lions book), and future AT&TNICTA Copyrightc 2011 From Imagination to Impact2-2licencees were not able to use the book legally any more.

4 UNSW obtained an exemption of some sort; but the upshot was that theLions book was copied and copied and studied around the , the licence change also meant that an alternative wasneeded for OS universities stopped teaching OS at any depth. One stand-out was Andy Tanenbaum s group in the Netherlands. He andhis students wrote an OS called Minix which was (almost) sys-tem call compatible with Edition 7 UNIX, and ran on readily avail-able PC hardware. Minix gained popularity not only as a teach-ing tool but as a hobbyist almost open source 1991, Linus Torvalds decided to write his own OS after all,how hard could it be? to fix what he saw as some of theshortcomings of Minix.

5 The rest is Copyrightc 2011 From Imagination to Impact2-3 NICTA Copyrightc 2011 From Imagination to Impact2-4 ALITTLE BIT OF HISTORY Basic concepts well established Process model File system model IPC Additions: Paged virtual memory (3 BSD, 1979) TCP/IP Networking (BSD , 1983) Multiprocessing (Vendor Unices such asSequent s Balance , 1984)NICTA Copyrightc 2011 From Imagination to Impact3 The UNIX core concepts have remained more-or-less the samesince Ritchie and Thompson published their CACM paper. Theprocess model and the file system model have remained thesame. The IPC model (inherited from MERT, a different real-timeOS being developed in Bell Labs in the 70s) also is the there have been some significant most important of these were Paged Virtual Memory (intro-duced when UNIXwas ported to the VAX), which also introducedthe idea of Memory-mapped files; TCP/IP networking, Graphi-cal terminals, and multiprocessing, in all variants, master-slave,SMP and NUMA.

6 Most of these improvements were from outsideBell Labs, and fed into AT&T s product via an open-source the late 80s the core interfaces were standardised by theIEEE, in the so-called POSIX Copyrightc 2011 From Imagination to Impact3-1 ABSTRACTIONSL inux KernelFilesThread of ControlMemory SpaceNICTA Copyrightc 2011 From Imagination to Impact4As in any POSIX operating system, the basic idea is to abstractaway physical memory, processors and I/O devices (which canbe arranged in arbitrarily complex topologies in a modern sys-tem), and provide threads, which are gathered into processes (aprocess is a group of threads sharing an address space and afew other resources), that access files (a file is something thatcan be read from or written to.)

7 Thus the file abstraction incor-porates most devices). There are some other features provided:the OS tries to allocate resources according to some system-defined policies. It enforces security (processes in general can-not see each others address spaces, and files have owners).NICTA Copyrightc 2011 From Imagination to Impact4-1 PROCESS MODEL Root process (init) fork()creates (almost) exact copy Much is shared with parent Copy-On-Writeavoids overmuch copying exec()overwrites memory image from a file Allows a process to control what is sharedNICTA Copyrightc 2011 From Imagination to Impact5 The POSIX process model works by inheritance. At boot time,an initial process (process 1) is hand-crafted and set running.

8 Itthen sets up the rest of the system in Copyrightc 2011 From Imagination to Impact5-1 FORK()ANDEXEC() A process can clone itself by callingfork(). Most attributescopied: Address space (actually shared, marked copy-on-write) current directory, current root File descriptors permissions, etc. Some attributesshared: Memory segments markedMAPSHARED Open filesNICTA Copyrightc 2011 From Imagination to Impact6 First I want to review the UNIX process model. Processes clonethemselves by callingfork(). The only difference between thechild and parent process after afork()is the return value fromfork() it is zero in the child, and the value of the child sprocess ID in the parent.

9 Most properties child are logicalcopiesof the parent s; but open files and shared memory segments aresharedbetween the child and the particular, seek operations by either parent or child will affectand be seen by the other Copyrightc 2011 From Imagination to Impact6-1 FORK()ANDEXEC()..01234567 File descriptor tableProcess Bfork()dup()Open file descriptorOffsetIn kernel descriptor tableProcess ANICTA Copyrightc 2011 From Imagination to Impact7 Each process has a file descriptor table. Logically this is an arrayindexed by a small integer. Each entry in the array contains a flag(theclose-on-execflag and a pointer to an entry in anopenfile table. (The actual data structures used are more complexthan this, for performance and SMP locking).)

10 When a process callsopen(), the file descriptor table is scannedfrom 0, and the index of the next available entry is returned. Thepointer is instantiated to point to anopen file descriptorwhich inturn points to an in-kernel representation of an index node aninode which describes where on disc the bits of the file canbe found, and where in the buffer cache can in memory bits befound. (Remember, this is only a logical view; the implementa-tion is a lot more complex.)A process canduplicatea file descriptor by callingdup()ordup2(). Alldupdoes is find the lowest-numbered empty slot inNICTA Copyrightc 2011 From Imagination to Impact7-1the file descriptor table, and copy its target into it.