Introducing serel $Id: serel-overview.txt,v 1.3 2002/08/10 02:07:22 leni Exp $ Copyright (c) 2002 by Leni Mayo Disclaimer No liability for the contents of this document can be accepted. Use the concepts, examples and information at your own risk. There may be errors and inaccuracies that could be damaging to your system. While this is unlikely, you should proceed with caution, and the author does not take any responsibility. All copyrights are held by their respective owners, unless specifically noted otherwise. Use of a term in this document should not be regarded as affecting the validity of any trademark or service mark. Naming of particular products or brands should not be seen as endorsements. Feedback Feedback is most welcome for this document. Send your additions, comments and criticisms to the following email address : serel (at) fastboot.org. serel's primary purpose is to help general-purpose operating systems boot faster. This document provides an overview of how serel works. ---------------------------------------------------------------------- Table of Contents 1. Introduction 2. Dependencies 3. Expressing Dependencies 4. Visualisation 5. How fast is it? References A. Example dependencies B. Sample log file for visualisation List of Tables 1. Phases of boot List of Examples 1. Visualisation example A-1. expressing dependencies via xml/rdf A-2. special comments in boot scripts A-3. Direct use of synchronisation primitives ---------------------------------------------------------------------- 1. Introduction serel provides synchronisation primitives to init [1] that allow a computer's services to start and run in parallel. This reduces boot time because service startup is often the most time-consuming phase of the boot process, and because dependencies between services seem to be relatively rare. serel is designed to be useful on a wide array of operating system platforms, even though there is considerable diversity in the way that operating systems start services [me00]. Aiming to support diversity, serel is designed so as not to be responsible for starting services. Init starts services; platforms are free to use the serel framework in diverse ways. In order for serel to be usable as early as possible within user-space, the implementation does not depend on any services started by init. Table 1. Phases of boot +------------------------------------------------------------------------+ | Phase | Description | |-------------------------+----------------------------------------------| | Bios | The bios locates and initialises hardware. A | | | boot loader may run. Control passes to the | | | kernel. | |-------------------------+----------------------------------------------| | Kernel | The kernel starts and passes control to init | | | in user space. | |-------------------------+----------------------------------------------| | User-space - "basic" | The "basic" services may include: filesystem | | services | check and mount, load and initialise device | | | drivers, and initialise system time. . | |-------------------------+----------------------------------------------| | User-space - "optional" | The "optional" services may include: | | services | logging, networking, mail, network | | | filesystems, web server, the windowing | | | system etc. | +------------------------------------------------------------------------+ The name "serel" derives from "SErvices and RELationships". The name hints at the core idea - that explicit service relationships allows operating systems to boot faster. serel is open-source software, licensed under the GNU General Public Licence, Version 2. More information on serel is available at http://www.fastboot.org. ---------------------------------------------------------------------- 2. Dependencies When services start sequentially, dependencies are implicit in the order of startup. Parallelism benefits from explicit dependencies. serel allows dependencies to be expressed as: * xml - serialisation of the W3C's Resource Description Format [wc00] * special comments inside boot scripts, as per the Linux Standard Base Specification [lsb] * synchronisation primitives usable from within boot scripts Examples are shown in Appendix A. These options offer comparable expressive power to each of the actors with an interest in dependencies: system administrators, OS vendors, and service developers. Integrity of the dependencies is critical to a healthy boot. serel aggregates dependencies into graphs, which may correspond to a runlevel, a switch between runlevels, or other granularities such as "network" or "windows". Graphs are tested for integrity prior to committing to parallel boot. [2] [3] It is not assumed that dependencies for all services are known at boot time. Best-effort handling of "unknown" services involves starting such services after all parallel services have finished and retaining the order of startup from the non-serel boot. Other approaches are possible. ---------------------------------------------------------------------- 3. Expressing Dependencies Dependencies expressed via xml and boot script comments are enforced before a script executes. In addition, scripts can call the synchronisation primitives directly. This allows scripts to get work done before blocking, resulting in superior run-time performance. [4] In choosing whether to express dependencies via xml and boot script comments or make direct calls to the synchronisation primitives, developers face a tradeoff: improved performance vs. increased maintenance costs. For resource-constrained platforms such as embedded systems, serel can be rebuilt so as to entirely exclude the use of xml or boot-script infrastructure, resulting in a daemon with a reduced memory footprint. Dependencies expressed via xml and boot scripts are compiled into a database in order to optimise run-time queries. This database only gets rebuilt when something changes, which explains why second and subsequent boots can be faster than the first. ---------------------------------------------------------------------- 4. Visualisation When services start sequentially, responsibility for slow boot times is shared among many services. When services start in parallel, boot time is a function of those few services that lie on the critical path. Example 1. Visualisation example ----> keytable ---> 3rd last (2.26s) / / start ------> syslog ------ \\ \ 8.95s \\ ===> sendmail =====> last(18.49s) \\ 9.54s // ===> network ==== \ ---> sshd ---> 2nd last (12.66s) The image above shows services, relationships, timings, and the critical path. The image is a visualisation of the log file shown in Appendix B. The three leftmost services have no dependencies. Once started, they run to completion in parallel. sendmail blocks until both syslog and network have completed. network ran for 9.54 seconds, sendmail ran 8.95 seconds, not counting the time it spent waiting for network and syslog to finish. Red edges show the critical path of network followed by sendmail, running for a total of 18.49 seconds. Can this system boot faster? For this system to boot faster, either dependencies along the critical path must be untangled, or the individual services must be made to boot faster. Removing sendmail altogether would change the critical path to network followed by sshd, reducing boot time by about 5.8 seconds. Visualisation credits serel visualisation was inspired by the W3C RDF validation service. Analysis of the RDF is built on top of the Redland platform. The image is generated by AT+T's excellent GraphViz. ---------------------------------------------------------------------- 5. How fast is it? serel 0.3.2 has been measured as reducing the boot time of the last phase of boot by as much as 38%. The reduction in boot time due to parallelism is highly dependent upon configuration, the smallest reduction measured to date is 8%. The patches for rc under Red Hat Linux and Debian GNU/Linux have a similar function. When booting to a multiuser runlevel, rc starts the serel daemon, confirms the integrity of the dependencies, and runs the S??* scripts in parallel. The default configuration generates the visualisation log file whenever the history database changes. The present serel implementation aims for robust delivery of a few core features, and leaves ample scope for future boot time improvement. ---------------------------------------------------------------------- References [go00] Gooch, Richard. Linux Boot Scripts, http://www.atnf.csiro.au/people/rgooch/linux/boot-scripts/index.html [lsb] Linux Standard Base Specification, Section 19. System Initialization, Comment conventions for init scripts, http://www.linuxbase.org/spec/refspecs/LSB_1.1.0/gLSB/initscrcomconv.html [me00] Mewburn, Luke. The Design and Implementation of the NetBSD rc.d system, http://www.mewburn.net/luke/papers/rc.d.pdf [sv00] Sanchez, Wilfredo, and Van Vechten, Kevin. SystemStarter and the Mac OS/X Startup Process, http://cory.eecs.berkeley.edu/~kevinvv/SystemStarter.html [wc00] Resource Description Framework, W3C , http://www.w3.org/RDF ---------------------------------------------------------------------- A. Example dependencies Here are three alternative ways of expressing "sendmail depends on network and syslog". Example A-1. expressing dependencies via xml/rdf Example A-2. special comments in boot scripts #!/bin/bash # # sendmail This shell script takes care of starting and stopping sendmail. # ### BEGIN INIT INFO # Provides: sendmail # Required-Start: syslog network ### END INIT INFO # # ... Example A-3. Direct use of synchronisation primitives #!/bin/bash # # sendmail This shell script takes care of starting and stopping sendmail. # ... # if [ $1 = "start" ]; then serelc --provide sendmail serelc --need syslog serelc --need network ... fi ... ---------------------------------------------------------------------- B. Sample log file for visualisation The image shown in Example 1 is generated from the following log file. Notes [1] On many *nix systems, the first user-space process is named init. init (or a child like rc) is responsible for starting system services. [2] Early releases of serel distributed default dependencies by inserting special comments within boot scripts. This approach carries a number of undesirable properties, including the burden of maintaining dependencies scattered across dozens of files. serel now distributes default dependencies in a single xml configuration file. [3] Apple's OS/X 10 starts it's services in parallel [sv00]. Dependencies are expressed via xml configuration files, one per service. [4] See also: simpleinit [go00].