MULTICS

Overview and selected implementation details of the MULTICS operating system.

1. 16.01.2013
Seminar: Origins of Operating Systems
Department of Operating Systems and Middleware
(Prof. Dr. Andreas Polze)
Hasso-Plattner-Institut Potsdam
http://www.multicians.org/mulimg/multics-frisbee.jpg

2. Lukas Pirl Multics Seminar: Origins of Operating Systems 2
http://www.dcl.hpi.uni-potsdam.de/teaching/origins/os-evolution.jpg

3. Lukas Pirl Multics Seminar: Origins of Operating Systems 3
http://graphics8.nytimes.com/images/2011/06/20/opinion/morris_email_corbato2/morris_email_corbato2-blog427.jpg
Fernando José Corbató
http://upload.wikimedia.org/wikipedia/commons/3/3d/Fernando_Corbato.jpg

4. Lukas Pirl Multics Seminar: Origins of Operating Systems 4
How it all began…
◾Design started 1965
◾Successor of CTSS (1961 - 1973)
◾Project leader: F. J. Corbató
◾Part of ProjectMAC at MIT

5. Lukas Pirl Multics Seminar: Origins of Operating Systems 5
Cooperation
◾MIT
◾Prior pioneering work
◾Bell Labs
◾Engineering
◾Business management
◾Communications
◾experienced users
◾General Electric
◾Hardware

6. Lukas Pirl Multics Seminar: Origins of Operating Systems 6
Goals (1)
◾Reliability
◾Increases acceptance and convenience
◾Continuity
◾maintain hardware during runtime (redundancy)
◾Timesharing
◾Simulate private computer for many users
◾long I/O waits
◾Selective information sharing
◾Increase effectiveness with shared facilities
between users

7. Lukas Pirl Multics Seminar: Origins of Operating Systems 7
Goals (2)
◾Security
◾Configurable access for data and programs
◾Changeable system configuration
◾Wide variety of system capacities
◾Convenient use (also remote)
“[…] the system should be sympathetic to its users. Multics provides no
direct assistance toward this goal […]” [SMS]
◾Openness “open-shop computer facility”
◾Most system modules implemented like user programs

8. Lukas Pirl Multics Seminar: Origins of Operating Systems 8
Development on CTSS on IBM 7094
http://www.columbia.edu/cu/computinghistory/7094-ibm.jpg
(probably smaller)

9. Lukas Pirl Multics Seminar: Origins of Operating Systems 9
Development Run
Development on (heavily loaded) CTSS
edit code
compile
create boot tape
boot
crash
read crash dump
yesno}
1 day!

10. Lukas Pirl Multics Seminar: Origins of Operating Systems 10
Written in PL/1
◾high level language
◾Comprehensible
◾Machine-Independent
◾Hardware might change
◾Adoptable
◾Requirements might change
◾“enthusiasm of those planning to implement the
compiler” [MVMSD]

11. Lukas Pirl Multics Seminar: Origins of Operating Systems 12
Phases
◾Subdivide work
◾Each phase defined
◾Quality targets
◾Functional benchmarks
◾No performance goals
◾A lot of research effort

12. Lukas Pirl Multics Seminar: Origins of Operating Systems 13
March 1967 – Phase 0.5
Working file system
On GE-645 simulator

13. Lukas Pirl Multics Seminar: Origins of Operating Systems 14
December 1967 – Phase 1
bootload
Warm bootable
Create process
Do terminal I/O

14. Lukas Pirl Multics Seminar: Origins of Operating Systems 16
General Electric 645
http://www.multicians.org/mulimg/martin-widrig-645.jpg
set-up 1967 @ MIT
CPU@435KIPS2x512k core memory18 MB drum storage

15. Lukas Pirl Multics Seminar: Origins of Operating Systems 17
set-up 1972 @ MIT
http://www.multicians.org/mulimg/betti-blank.jpg

16. Lukas Pirl Multics Seminar: Origins of Operating Systems 18
$7M *
* ≈29 Mio. € (2012)
http://www.multicians.org/mulimg/you-would-b2-2.jpg
http://www.multicians.org/mulimg/h6180-doors-open-big.jpg

17. Lukas Pirl Multics Seminar: Origins of Operating Systems 19
Honeywell 6180 Configuration
◾2x CPU
◾1 MIPS each
◾384k MOS memory
◾36-bit words
◾1MW drum storage
◾4,5 MB
◾15 150MB disks
◾2,25 GB
◾8 tape drives
◾ARPANet connection
◾Card reader & punch, printer, …

18. Lukas Pirl Multics Seminar: Origins of Operating Systems 20
File System
◾Hierarchical namespace
◾Addressing by symbolical names
◾Symbolic links
◾Working directory per process
◾In Multics: File = Segment
NEW
!
File
- bits/bytes/…Directory Entry
- name
Branch
- phy. address
- access control
- time created
- time modified
- time referenced
- state
(#r, w, …)
n1
1
1
1
◄ references
{XOR}
1
1
n

19. Lukas Pirl Multics Seminar: Origins of Operating Systems 21
Access Control Lists
◾ACL for every file
◾prepend only
◾Garbage collector
◾Evaluated LIFO
◾TRAP, READ, EXECUTE, WRITE, APPEND
File 'xyz' ACL
Garry: rx ProjMac: rw Alice: x
Garry (member of ProjectMAC) can read and execute but not write xyz.
Alice (member of ProjectMAC) can read and write but not execute xyz.

20. Lukas Pirl Multics Seminar: Origins of Operating Systems 22
“[…] speed of light, the physical sizes […] and the
speed of memories are intrinsic limitations of any
single processor, […] multiple processors and
multiple memory units are needed to provide
greater capacity.”
[IOMS]

21. Lukas Pirl Multics Seminar: Origins of Operating Systems 23
Hardware Layout
CPU CPU
memory memory memory memory
controller GIOCGIOC
drum
controller
disks
controller
tapes
system
console
reader
punch
system
console
reader
punch
terminalterminalterminalterminalterminal
terminalterminalterminalterminalterminal

22. Lukas Pirl Multics Seminar: Origins of Operating Systems 24
Old-fashioned Buffering
Process memory diskR/W
write back
load to buffer
}
manually!

23. Lukas Pirl Multics Seminar: Origins of Operating Systems 25
Buffering in Multics
memory
disk
}
automatic
buffering
12
7
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
Process
R/W

24. Lukas Pirl Multics Seminar: Origins of Operating Systems 26
Memory Hierarchy
◾Singe-level Storage
◾Multiple layers but flat view
like all files mmap'ed
◾On access, data automatically loaded into memory
◾No loss of identity
◾Operation on 'original data'
◾No manual loading/saving of files

25. Lukas Pirl Multics Seminar: Origins of Operating Systems 27
Segments
◾Symbolic name (i.e. not address in memory)
◾Attributes
◾Addressing: (name, i)
like a lot of small core memories
Name
Attributes
Name
Attributes
Name
Attributes
<unused>
i
<
2
*
*
1
8

26. Lukas Pirl Multics Seminar: Origins of Operating Systems 28
Why Segments
Programs and Data (=everything) stored in
segments
◾Unified, symbolic addressing
◾Space-efficiency
◾Re-use segments in memory
◾I/O efficiency
◾Read only required parts of file
◾Fine-grained access control
◾Per segment
NEW

27. Lukas Pirl Multics Seminar: Origins of Operating Systems 29
Segments in Memory
Memory 2 5 9
10
?
+
◾Fragmentation during runtime

28. Lukas Pirl Multics Seminar: Origins of Operating Systems 30
Paging
◾Whole core memory divided into pages
◾1024 words each ≈ 4,6kB each
◾Split segments onto pages
◾Space efficiency
◾Keep only active pages in memory
◾No defragmentation required
Memory 2 5 9
10

29. Lukas Pirl Multics Seminar: Origins of Operating Systems 31
Page Lookup
DBR
LP
PT of DS
s
p
DBR = descriptor base register DS = descriptor segment PT = page table L = length P = pointer
LP
Page “s
p
”of DS
LP
LPLP ACL
i
p
PT of Segment “s”
LPfaultP
fault
i
w
Page “i
p
” of
Segment “s”
Word[s,i]
s
w

30. Lukas Pirl Multics Seminar: Origins of Operating Systems 32
Address spaces
◾Address space per process
◾Already accessed addresses
◾Set of (segment number, word number) tuples
◾Supervisor has no dedicated memory area
◾Protected through access control
◾Can be paged
◾Easy sharing of supervisory procedures
N
E
W

31. Lukas Pirl Multics Seminar: Origins of Operating Systems 33
Supervisory Data per Process
◾Stack segment
◾Data of process
◾Concealed stack segment
◾Various Supervisory data (charging information, …)
◾descriptor segment
◾Maps segment addresses to core memory addresses
◾Known Segment Table
◾Maps symbolic segment names to segment numbers
◾Further segments dynamically, as needed

32. Lukas Pirl Multics Seminar: Origins of Operating Systems 34
Dynamic Linking
◾Compiler retains symbolic names
◾Segment lookup and linking on first access
◾Get most recent shared procedure / data
◾For long execution times: explicit unlinking possible
◾Access to data of other segments via (linked) code
in other segments
◾Inter-process communication
N
E
W

33. Lukas Pirl Multics Seminar: Origins of Operating Systems 35
Sharing through Linking
Procedure
Segment
'Trade'
in execution
call ship
Procedure
Segment
'Warehouse'
as daemon
Data
Segment
'Purchases'
Data
Segment
'Sales'
Data
Segment
'Items'
Data
Segment
'Shipments'
access
no access
linking
as
◾Access to segments of linked segments
◾configurable

34. Lukas Pirl Multics Seminar: Origins of Operating Systems 36
Process Life Cycle
◾Creation
◾Spawned from other process
◾With segments to copy, segments to hide, start pointer
◾States
◾Running
◾Blocked
◾Maximum blocked time
◾Access violation, I/O wait, wait for lock, wait for 21.12.2012, …
◾Ready
◾Termination
◾Done XOR gets killed by other process

35. Lukas Pirl Multics Seminar: Origins of Operating Systems 37
Load
◾Hard to predict load in multiprogrammed system
◾Load rarely matches system capacity
◾Perform well under light overload
◾Switching processes often when load is light
◾Provide responsive system when possible
◾Frequency of switches indirect proportional to load
◾Access occasional overload
◾For economical reasons

36. Lukas Pirl Multics Seminar: Origins of Operating Systems 38
Scheduling - Aims
◾Symmetry in CPU responsibilities
◾Good service to all customers
◾Good service at reasonable cost
◾Differentiate between urgencies
◾Delays of results differ in resulting costs
◾Human-determined
◾As efficient as possible

37. Lukas Pirl Multics Seminar: Origins of Operating Systems 39
1
st
Scheduler – Priority Queuing
CPU
Queue priority 0
Queue priority 1
Queue priority 2
Queue blocked
Dispatcher
done
new

38. Lukas Pirl Multics Seminar: Origins of Operating Systems 40
1
st
Scheduler – Priority Queuing
◾Descended from scheduler in CTSS
◾N queues reflecting different priorities
◾Exponential quantum length
◾Highest priority (0), shortest quantumx
◾Lowest priority (n), longest quantumx*2**n
◾Rules for lowering and raising priorities
◾Run first job from non-empty queue with highest priority
◾Lower priority when job misses quantum end
◾(Move all jobs to highest priority queue periodically)
◾Enhancement: Grant %age of CPU time to groups
◾Priority queuing within groups

39. Lukas Pirl Multics Seminar: Origins of Operating Systems 41
Percentage Scheduler - Challenges
◾Unused CPU time
◾? idle OR sum for later use OR split to others
◾! add up a little (with maximum), split the rest
◾Interval in which CPU time will be 'accounted'
◾? daily, hourly, secondly, …
◾! 4 * length(quantum)
◾Scheduler should consider (very) near future
◾Will the job use the whole quantum?
◾! Account CPU time as credits per group
◾Per default, discount credits for whole quantum
◾Add back credits accordingly (if process finishes earlier)

40. Lukas Pirl Multics Seminar: Origins of Operating Systems 42
Percentage Scheduler – Multilevel Q
◾Percentage scheduler degrades response time
◾Process that caused interaction consumed CPU time
◾Queuing Theory
◾Introduced interactive queue
◾For processes that recently interacted
◾FIFO
◾Good response time for simple commands
◾cp. boost of priority after I/O in Windows

41. Lukas Pirl Multics Seminar: Origins of Operating Systems 43
Deadline Scheduling
◾Assign deadlines to groups
◾Virtual deadlines
◾Used to sort processes of all groups in one queue
–No attempt to meet deadline
◾Different deadlines and quanta length after interaction
–Retain good average response time
◾Realtime deadlines
◾Used to sort process into a realtime queue
◾Deadline for start of work
◾Execution on deadline
◾Other scheduling similar to a process with virtual deadline
N
E
W

42. Lukas Pirl Multics Seminar: Origins of Operating Systems 44
Traps
◾System Traps
◾Failures, I/O termination, …
◾Process Traps
◾Overflows, access violation, …
◾Trap handling
◾Routine per system trap
◾With intercept points for custom trap handling
◾Default or custom trap routine for all traps
◾Custom overflow handling, custom page-fault handling, …

43. Lukas Pirl Multics Seminar: Origins of Operating Systems 45
Hardware Failures
◾Essential for dependability
◾On-line reconfiguration
◾Core memory
◾Unwritten data will be lost
◾Attached I/O devices
◾CPU's
◾Affected process will be damaged
◾Unsolved: misbehaving hardware
◾“We have no very useful techniques for protecting the
system from software bugs” [M]
NEW
!

44. Lukas Pirl Multics Seminar: Origins of Operating Systems 47
Accounting
◾Pay-per-use
◾CPU time in milliseconds
◾Number of pages in Memory
◾every millisecond
◾Number of pages on disk
◾every millisecond
◾Quotas
◾Dollar-limits

45. Lukas Pirl Multics Seminar: Origins of Operating Systems 48
Security
◾Access Control
◾Single concept for whole addressable
memory
◾Ring layout
◾Access relative to ring of execution
◾8 rings in hardware, 64 simulated in software
◾Supervisor in ring 0
◾Now, standard architecture on Intel and of Microsoft
◾“No back door was ever discovered in any 6180
Multics” [M]
N
E
W
!
http://www.multicians.org/mulimg/slider-you-would-b2.jpg

46. Lukas Pirl Multics Seminar: Origins of Operating Systems 50
http://www.multicians.org/mulimg/outgrow-sm.jpg

47. Lukas Pirl Multics Seminar: Origins of Operating Systems 51
*'s
◾[IOMS]: F. J. Corbato, and V. A. Vyssotsky, "Introduction and Overview of
the Multics System", Fall Joint Computer Conference, 1965
◾[SMS]: V. A. Vyssotsky, F. J. Corbato, and R. M. Graham, "Structure of the
Multics Supervisor", Fall Joint Computer Conference, 1965
◾[MVMSD]: F. J. Corbató, and C. T. Clingen, “A Managerial View of the
Multics System Development”, M.I.T. Press, 1979
◾R. C. Daley, and P. G. Neumann, "A general-purpose file system for
secondary storage", Fall Joint Computer Conference, 1965
◾J. F. Ossanna, L. Mikus, and S. D. Dunten, "Communications and input-
output switching in a multiplexed computing system", Fall Joint
Computer Conference, 1965
◾[M] http://www.multicians.org/, accessed 15 January 2013
◾All slides under