UNIX for Apple’s Low-Cost Workstations

David S. H. Rosenthal
Information Technology Center
Camegie-Mellon University
Schenley Park
Pittsburgh PA 15213

A proposal prepared at the request of Steve Jobs, examining some technical and organizational aspects of providing a UNIX^[1] system appropriate to Apple's hardware and software culture.

1. What Are We Trying To Achieve?

Assuming that Apple's hardware looks like Table 1, none of the existing UNIX systems are adequate to produce a successful low-cost UNIX-based workstation that is broadly compatible with the Macintosh line.

Table 1 - Hardware Assumptions
Processor	MC68020
Memory	1M byte
Disk	40M byte
Display	0.5-1M pixels
Per-process VM	8M+

The objective should be to produce a system that:

Supports the display, including a user interface with all the responsiveness and flash of the Mac.
Supports the 4.2BSD system call interface^[2], including the DARPA network protocols.
Supports at least one virtual Mac; a UNIX process running Mac software in a window.

Achieving this requires three distinct software activities:

The basic UNIX system must be ported to the eventual hardware. development, MMU and interrupt structure support, This includes compiler and device drivers.

This activity is well-understood, and can be performed by existing software houses. Traditionally, the results of basic porting have been regarded as highly proprietary, in part because they have been partly or wholly owned by these software houses.
The UNIX kernel and utilities must be adapted to low-cost workstations. This includes changes throughout the system aimed at reducing resource consumption and improving responsiveness, and the integration of bitmap display support.

There is considerable consensus among UNIX experts about the many of the changes that are required. They affect largely machine-independent parts of the system. Sun Microsystems, at least, are attempting to make them. If these changes could be made available to Berkeley for inclusion in future distribution, it would materially reduce the danger of UNIX fragmenting into many incompatible and proprietary versions (and thus benefit both UNIX users and vendors).
A suitable user interface must be developed. This involves all the user-visible behavior of the window manager, and the development of the virtual Mac.

Apple has demonstrated expertise in this area. It would involve access to proprictary software such as Quickdraw, and Apple might well wish to keep the results proprictary. The ITC has demonstrated that software of this kind can be developed without impacting the kernel.

These activities could initially proceed in parallel, though they will need a period of integration before release. The next section examines the second activity in detail.

2. What Needs To Be Done To UNIX?

There are four broad areas of mismatch between UNIX and low-cost personal workstations:

UNIX requires too much physical memory. Typical MC68010-based workstations require 2M bytes to give adequate performance, of which the kernel alone can consume well over 512K.

It seems probable that by re-implementing the virtual memory system, by fitting the system to a specific hardware configuration, and by general tightening-up, the kernel could be reduced to about 150K bytes of text, most potentially in ROM, and about 50K of data. By implementing shared libraries, the size of user processes could be greatly reduced, giving acceptable performance on a JM byte system.
UNIX requires too much disk space. Installing a complete 42BSD system needs 60+M of disk.

Shared libraries and other techniques can probably make the system a comfortable fit on a a ask probably configured as an 8M root filesystem, 8M of swap space, and a 24M /usr filesystem with perhaps 6M of actual user files^[3].
UNIX doesn't provide sufficiently consistent and rapid response to interaction. Paging, swapping, and a scheduler designed to provide fairness under heavy timesharing loads can lead to embarrassing delays at times, for example when switching to a window that has been idle during intense activity elsewhere.

Changes to the scheduler and virtual memory system can provide a much more predictable and consistent response to user interaction, though they will never match that of a single- process Mac-like environment running on the same hardware.
UNIX’s model of interaction is based upon character terminals, not bitmap displays. The tty driver is no longer an appropriate basis for user interfaces. The tty driver can be moved into a user-level process, still providing support for existing UNIX applications. The virtual memory changes should implement an efficient shared memory scheme, allowing access to the display to be mediated by user-level processes rather than kernel support. A lightweight process mechanism should be implemented to support Smalltalk-style user interfaces.

All told, a team of 4-5 good, experienced people working for about a year could make a major difference to the suitability of UNIX for low-cost workstations.

3. How Can It Be Done?

The major factor affecting the decisions about how to perform the work is whether or not to make the system changes available to others. The case for doing so is:

Availability of the source for the system is a major selling point for Universities, presumably a major component of the eventual product's market.

Note, however, that this proposal does not address the question of a wholly public-domain UNIX clone, free of the AT&T license; duplicating the utilities would require an enormous effort, and convincing AT&T's lawyers that the system was really not UNIX would be nearly impossible.
Producing a system with the responsiveness and performance needed will require the best UNIX hacking talent. Providing the opportunity to make significant and urgent changes to the system in an accessible form is the best way of motivating the people with the necessary expertise, and persuading the companies they work for to let them participate.
Some of the changes required, for example to the scheduler and the process mechanism, will require extensions to the system call interface. Broad acceptance of the extensions would be a significant selling point for the eventual product.
Cooperating with the UNIX community to counteract AT&T's increasingly restrictive approach to UNIX would be valuable publicity, and would fit the image Apple has developed of a David against the Goliaths. It would also reduce Apple’s more negative image as secretive and defensive about its software, without risking any software in which they have a major investment.
The technical content of UNIX has been widely known for 10 years. The proposed changes are sound engineering rather than leading-edge research.

., The case against releasing the changes is:

They will take longer to develop if they are to be released, since contamination from proprietary code must be avoided.
Apple will be investing in making the changes, and their competitors will benefit to some extent from them.

Note that, while it might be desirable, it is not necessary to make source available for the low-level machine support, compilers, etc. developed during the basic port, nor for the Quickdraw analogue used to support the virtual Mac. Nor is it essential that the changes be released immediately. Provided that the commitment to release is credible, a period of a some months before it happens will not unduly compromise the potential gains.

3.1. Changes Proprietary

If it is not essential that the system changes be made freely available, the fastest and most effective way of getting them done is probably to contract with a outside organization to do them. In particular, Sun Microsystems has already done the basic port, is enthusiastic about making the necessary changes, and has much relevant expertise. Of course, their willingness to do a deal will depend on their perception of themselves as potential competitors in this market. Alternatively, there are many software houses with relevant expertise. In either case, consultations with UNIX experts in Universities should produce a detailed specification fairly quickly.

3.2. Changes Non-Proprietary

Ideally, the changes to the system should be distributed to the UNIX community, ideally by adding them to a subsequent Berkeley distribution. To be able to do so, they must be free of contamination from source owned by others. There are a number of possible sources of such contamination, especially:

The source of the low-level machine support in the kemels used by the system development team. They would have to use VAXen (whose machine support comes from Berkeley), or Apple machines running kernels owned by Apple (not licensed from an outside software ouse).
Other source licenses signed by the institution sponsoring the system development, if it were done outside Apple. For example, CMU (in common with many Universities) has signed a contaminating source license with Sun, and might be in a weak position to assert ownership of similar developments relating to the 4.2BSD kernel and bitmap displays.

An alternative approach to this problem is ot set up the project as a collaboration between several partics, each contributing their proprietary code and disclaiming individual ownership of the product.

Assuming that the contamination problems can be solved, at least four paths could lead to distributable sources:

Apple could contract with a University to perform the work. Universities such as C-MU, Stanford, MIT and Purdue have long histories of involvement in the development of UNIX, though, like Berkeley, they are finding it increasingly difficult to retain their expertise in the face of the demand for gurus. On the other hand, this makes hucrative contracts of this kind all the more important.
Because institutions now regard their UNIX gurus as valuable resources, to be retained at all costs, a scheme that drew on their expertise without removing them from their owners might be preferable. The necessary developments might be cast in the form of a “guru contest”. Competitors would be invited to submit design documents for one of the needed improve- ments. The best proposals would be selected, and given machines, the source and (say) nine months to implement their proposal. They would then all be locked into a hotel in a nice resort and not allowed out until they had integrated the results into a complete system. This might not result in the highest-quality code, but would generate wonderful publicity and feelings of involvement with the resulting system.
Apple might fund a specially-created team, either working internally, or as an independent company. This would be the most controllable option, but recruiting the necessary expertise would be difficult and time-consuming.
Alternatively, the specially-created team might be funded in concert with other UNIX works- tation suppliers also interested in these developments. This would take time to set up, but if it could be staffed by people seconded from the suppliers it might in the end be faster than recruiting from scratch. Public acceptance of the resulting system would probably be greater than one with Apple as its sole parent.

Note, however, that these paths will take longer than keeping the changes proprietary. Starting the group up if it doesn’t already exist will take time. If they are to work on Apple kernels, these must be developed before much of the work can be tested. Altematively, DEC VAXstations must be installed, and then the changes merged into the Apple systems before release.

Acknowledgments

The opmions expressed are those of the author, who tenders special thanks for valuable discussions to Mark Seiden (Lucasfilm), Jim McKie (CWI Amsterdam), Kirk McKusick (UC Berkeley) and Bill Joy (Sun Microsystems).

Appendices

A. Technical Details

Each of the four areas in which work needs to be undertaken on the UNIX system to adapt it to low-cost workstations is examined in some detail.

A.1. Less Memory

UNIX statically allocates part of the physical memory to the kernel code and data structures, and dynamically shares the rest among the wser processes. Both the kernel and the user processes are too large, m pact at least because the machines to which the system has been targeted make expending memory to gain performance a good trade-off.

A.1.1. The Kernel

The memory allocations of a typical MC68010 workstation running 4.2BSD are shown in Table 2^[4].

Table 2 - Memory Allocation
Use	Kbytes
Kernel Text	276
Kernel] Data	82
Network Buffers	88
File System Buffer Cache	152
User Processes	1450
Total	2048

The sizes of parts of the kernel devoted to specific functions are shown in Table 3.

Table 3 - Kernel Module Sizes
module	text	data	notes
Kernel	60648	15628	Includes autconfiguration
Tty Driver	13548	820
File System	31168	2420
Networking	67400	3980	TCP/IP and SNA
Virtual Memory System	26796	928
Devices	66560	18108	Supports all Sun devices
Total	266120	41884

Several approaches can reduce these sizes:

Re-examime those areas where memory has been traded for performance, especially the file system, and where the kernel implements multiple alternate functionality, especially the tty driver.
Re-implement VAX-specific areas, especially the virtual memory support. This is widely recognized as being poorly designed, too complex, and insufficiently isolated from the rest of the kemel. Re-implementation should unify kemel memory allocation mechanisms, combine buffer cache management and paging, and support mapping of files into user processes. The CSRG at Berkeley seems likely to make these modifications.
Provide support for the migration of kernel functions to user processes, perhaps through a mechanism similar to Dennis Ritchie's stream I/O system. Among the functions to be migrated initially would be the tty driver. The Centrum voor Wiskundig an Informatica in Amsterdam seems likely to make these changes.
Paging parts of the kernel, using techniques similar to those experimented with at National Semiconductor. Note that paging the keme! and migrating function to user processes are alternatives; they both avoid committing physical memory to unused functions.
Placing parts (or all) of the kernel in ROM.

Note that the size of device drivers depends on the intelligence of the controller, especially in error handling; techniques which make device drivers loadable on demand can be implemented without paging the whole kerne} (as for example on HP's portable UNIX box).

A.1.2. User Processes

A major contribution to the size of existing UNIX user processes is the pieces of the standard I/O library that are linked into each of them. Much larger contributions to the size of processes exploiting bitmap graphics come from the graphics and user interface libraries. If the facilities for mapping files mto user processes that have been specified were actually implemented it would be possible to map shared copies of appropriate libraries into each process.

A.2. Less Disk Space

The requirement for disk space on a personal workstation can be reduced both by reducing the size of the file system needed to support UNIX, and by sharing this file system among a number of networked workstations.

Alternatively, a combination of improved data encoding on the disk (such as 2/7RLL) and hardware assistance for on-the-fly data compression can be used to expand the effective capacity of the available media.

A.2.1. Shrink Filesystems

Shared lbraries as described above would reduce the space required for executable programs (7-8Mb).
The contents of the file system have evolved over many years. A careful audit would reveal many obsolete or redundant files. Nevertheless, much of the power of UNIX comes from ready access to a large, diverse file system. Eliminating some of these files (for example the manuals) will reduce the usefulness of the system.
The techniques used by Interactive Systems Corp. for IBM's PC/IX, and by Microsoft for Xenix, can be used to divide the filesystem into a common part and a number of functional subsets (program development, text formatting, games, etc.). Users load only those parts they actually require.

A.2.2. Share Filesystems

Most organizations working on 4.2BSD are now developing network file systems. The designs differ only in details; all potentially permit a workstation with only a small local disk to access files maintained elsewhere. Sun Microsystems has the most ambitious program; they can run diskless workstations from their file system. They license their changes (Pyramid and Gould have shown their implementations working), and may release their ker nel modifications to the UNIX community. The ITC has developed a similar system, but it uses the workstation’s local disk as a cache of recently used files to reduce the load on the file servers.

Of course, network file systems are useful only in larger organizations, and the cost of each workstation must include their part of the server and network. Thus, remote filesystems are only a supplement to reducing filesystem size. On the other hand, the use of 42BSD IP networking over the public telephone net has already been demonstrated. This would permit transparent access (albeit at reduced performance compared to a LAN) to network file systems from geographically distant machines. If the majority of file access was from the local disk even low-performance access for the occasional file might be a significant advantage. Most files are under 1K long, giving a 10-second delay at 1200 baud^[5].

A.3. More Predictable Response

Unpredictable response is caused by pre-emption and by page faults. These can be reduced by:

Changing the scheduler to permit fine-grain control over process priorities. For example, when the mouse moves into a window its process(es) should get a higher priority.
A mechanism for processes to give hints to the VM system about their paging behavior is already specified, and partly implemented. Full implementation would allow for pages to be declared “vital” for rapid response.
Implementation of shared libraries would make most processes much smaller, leading to fewer page faults and better response.
An altemate VM implementation in which processes paged within a fixed working set, rather than against the global set of processes, would reduce the effect of large compute-bound processes on interactive performance. This is apparently the approach taken in System V Release 2.1. Their approach should be extended to permit the VM system to accept advice (e.g. from the window manager) about changes in working set allocations.

A.4. Adaptation to Bitmap Display

The UNIX kemel implements, in the tty driver, a model of user interaction that derives from the Teletype Model 33, slightly extended to account for destructive backspace on CRT displays. Most “window managers” for UNIX are hamstrung by attempting to present themselves as upwards-compatible extensions to these facilities.

The kernel facilities needed to support bitmap-style user interfaces come in two parts:

Processes must be able to share access to the display and mouse in a controlled manner. The control can be either (as at the ITC) via a user-level process, or (as at Sun) via kernel bitmap support. The proposed changes to the virtual memory system should support an efficient shared memory scheme, in which case control via a user-level process will be preferable.

This sharing will be easier if the display cursor is not in the bitmap used to refresh the display (at least not while user processes are active). Both the ITC's and Sun's window managers suffer considerably from the need to interlock application rasterops with the cursor.
Many user interface styles for bitmap displays (Smalltalk is an example) can most effectively be expressed as a set of processes running in a single address space. Implementing such a Eghtweight process mechanism for UNIX is widely accepted as a priority; it will assist in the support of languages such as ADA, and in writing network applicati as well as in con structing responsive user interfaces.

They can be supported by implementing a version of fork() that creates a thread of control but not an address space. The scheduler would grant control without preemption among the threads of contro of the selected address space. An address space would be regarded as blocked only while all of its threads were blocked; scheduling priorities would apply to address spaces not threads.

Endnotes

UNIX is a Trademark of Bell Laboratories.
The fundamental reason for preferring Berkeley's 42BSD over AT&T's System V as a starting-point is that it has most of the functionality but is too big, whereas System V is the right size but lacks fimnctionality such aionality such as networking. Making something smaller is easier than adding functionality without adding size.
Earlier UNIX file systems were also too likely to be damaged in an unexpected shutdown for use in personal computers. These problems seem to be fixed in the 42BSD file system.
The figures on sizes are derived from the 4.2BSD systems running in the ITC. These systems include many device drivers, SNA support, the remote file system, and generous allocations of system tables. The figures are likely to be pessimistic for low-cost workstations.
This ignores both protocol overhead, tending to make the figure worse, and the potential for read-ahead, tending to make it better.

DSHR's Blog