• Begin to Read Chapter 13, Program Execution Time
• Quiz Today

• Early 1960's machines: Almost Bare
• Mid 1960's Machines: Early Batch Operating Systems
• Multiprogramming Systems
• Time Sharing
• Lab Computers

• Microprocessor
• PC's; Operating Systems
• Apple; Macintosh (Xerox PARC)
• Workstations
• UNIX; License Wars

• Processor Management (Multiprogramming)
  • Several virtual machines
• I/O Systems
  • Windowing Systems / GUIs
  • File Systems
  • Communications/Networking
• Memory Management
  • Sharing Memory
  • Simulating Additional Memory (Virtual Memory)
• Software Environments
  • Administration/Accounting
  • Compilers
  • Tools

• Virtual Memory
  • Simulate memory using disks
• Cache Memory
  • slow and fast memory
  • library, bookcase, desktop analogies
• Memory Hierarchies
  • Registers x1
  • Cache x10 - x100
  • Main Memory x100 - x1000
  • Disks x1,000,000
• Overhead
  • Card Catalog analogies
  • Finding stuff on your desk or bookcase
• Historically
  • Swapping in Time Sharing Systems
• Paging
  
  
  

• Protection
  • Security (write protect)
  • Confidentiality (read protect)

• Communications/Networking
  • Dealt with that before
• Graphical User Interfaces (GUI)
  • X-Windows
  • Macintosh Desktop
  • MS Windows
  • Xerox PARC; Legal Fun
• Files Systems
  • Flat
  • Hierarchical (Directories)

• True Parallel Processes vs Simulated
• Synchronization
  • Danger of shared data
    • clock process
    • race condition
  • Deadlock
    • shared resources; partial allocation
    • prevention (simple minded)
• Process Management

• Administration/Accounting
  • Security
  • Logs
• Compilers
  • C++
  • Java
  • Basic
  • Assemblers
• Tools
  • Linkers
  • Debuggers
  • Editors
• Applications
  • Word processor
  • Spreadsheet
  • Database System
  • Games

• Historical
  • One integrated (mess!)
  • 360 Job control language
• Modular
• Kernel
  • System Calls: request services
  • Processor States
    • privileged instructions(kernel)
    • user
• Shell(s)
  • command processor

1. runs too long
   • real time requirements
   • predicting yesterday's weather
2. Non-computable
3. Don't know the algorithm

• Time
• Space

• Sorting, Ordering
• Alphabetizing

• N items in an array named Data
  [ 2 | 4 | 7 | 3 | 1 | 8 | 5 ]
• Find smallest of elements 1 thru N of Data
• Interchange this with 1st element of array Data
  [ _ | _ | _ | _ | _ | _ | _ ]
• Find smallest of elements 2 thru N of Data
• Interchange this with 2nd element of array Data
  [ _ | _ | _ | _ | _ | _ | _ ]
• ...
• Find smallest of elements K thru N of Data
• Interchange this with Kth element of array Data
  [ _ | _ | _ | _ | _ | _ | _ ]
  [ _ | _ | _ | _ | _ | _ | _ ]
  [ _ | _ | _ | _ | _ | _ | _ ]
• Done when K = N
  [ _ | _ | _ | _ | _ | _ | _ ]

• Comparisons
• N-1 comparisons in first pass
• N-2 comparisons in first pass
• ...
• 1 comparisons in last pass
• N-1 + N-2 + N-3 + ... 2 + 1
• N*(N-1)/2 = N*N/2 - N/2 (Gauss)

• Examples
• Various values of N

• N	N*N/2	-N/2	comparisons
  2	2	-1	1
  3	4.5	-1.5	3
  4	8	-2	6
  6	18	-3	15
  8	32	-4	28
  10	50	-5	45
  20	200	-10	190
  40	800	-20	780
  100	5000	-50	4950
  200	20000	-100	19900
  1000	500000	-500	499500
  ________	____________	________	____________
  ________	____________	________	____________
  ________	____________	________	____________
  ________	____________	________	____________

• t = A * N * N = A * N^2

• Add elements of an array
• Single loop algorithms
• t = A * N

• matrix multiplication
• t = A * N^3

• t = A * N^K
• and in-between
• Faster machines make a lot of difference

• t = A * N * log(N)
• logarithmic behavior

• Various values of N

• N	log(N)	N * log(N)	N^2
  2	1	2	4
  4	2	8	16
  8	3	24	64
  16	4	64	256
  1 K	10	10 K	1 M
  2 K	11	22 K	4 M
  8 K	13	1 M	64 M
  1 M	20	20 M	1 T
  2 M	21	42 M	4 T
  __________	__________	__________	__________

• K = 1024; M = K * K; G = K * M; T = K * G

• Assumes Sorted
• Like Telephone Book
• Logarithmic Time
• t = A * log(N)

• Note: here N is number of moves looking ahead.
• We Have an Algorithm!
• Layers of look ahead: If I do this, then he does this, ....
• Problem Solved (?!)
• Can Represent Possibilities by Tree
• Assume 10 Possibilities Each Move
• t = A * 10^N
• !!!!
• Exponential
• Sample Numbers

• Visit N Cities in Optimal Order
• Optimal By:
  • time
  • distance
  • cost
• N factorial (N!) Possibilities
• Look at Table
• N! is roughly N^N
• Typical of some very practical problems

3	2! = 2		5	4! = 24
abc			abcde
acb 			abced
			abdce
4	3! = 6		abdec
abcd			abecd
abdc			abedc
acbd		
acdb			acbde
adbc			acbed
adcb 			acdbe
			acdeb
			acebd
			acedb
		
			adbce
			adbec
			adcbe
			adceb
			adebc
			adecb

			aebcd
			aebdc
			aecbd
			aecdb
			aedbc
			aedcb

	t = 5.49 * 10**-3 * 2**n
n	t
5	.17s
10	5.62s
15	3.00m
20	1.6h
25	2.13d
30	68.23d
35	5.98y
40	191.3y
45	6120.y
50	196K y
55	6.27M y
60	201M y
65	6.42G y
70	205G y