Operational Analysis L Grewe Operational Analysis Relationships that do not require any assumptions about the distribution of service times or inter arrival times Identified originally by Buzen 1976 and later extended by Denning and Buzen 1978 We touch only some techniques results In particular bottleneck Analysis More details see linked reading 2 Under the Hood An example FSM exit start arrival rate throughput until some center saturates CPU I O request File I O network Memory cache Operational Analysis Resource Demand of a Request CPU VCPU visits for SCPU units of resource time per visit Network VNet visits for SNet units of resource time per visit Disk VDisk visits for SDisk units of resource time per visit Memory VMem visits for SMem units of resource time per visit 4 Operational Quantities T observation interval Bi busy time of device i i 0 denotes system Ai arrivals to device i Ci completions at device i Ai arrival rate i T Ci Throughput X i T Bi Utilization Ui T Bi Mean service time Si C i 5 Utilization Law Bi Utilization Ui T Ci Bi T Ci X i Si The law is independent of any assumption on arrival service process Example Suppose processes 125 pks sec and each pkt takes 2 ms What is utilization 6 Forced Flow Law Assume each request visits device i Vi times Ci Throughput X i T Ci C0 C0 T Vi X 7 Bottleneck Device Utilization Ui X i Si Vi XSi XVi Si Define Di Vi Si as the total demand of a request on device i The device with the highest Di has the highest utilization and thus is called the bottleneck 8 Bottleneck vs System Throughput Utilization U i XVi Si 1 1 X Dmax 9 Example 1 A request may need 10 ms CPU execution time 1 Mbytes network bw 1 Mbytes file access where 50 hit in memory cache Suppose network bw is 100 Mbps disk I O rate is 1 ms per 8 Kbytes assuming the program reads 8 KB each time Where is the bottleneck 10 Example 1 cont CPU DCPU 10 ms e q 100 requests s Network 1 Mbytes 100 Mbps 80 ms e q 12 5 DNet Disk I O requests s 0 5 1 ms 1M 8K 62 5 ms e q 16 requests s Ddisk Disk I O and network are more likely to be bottlenecks single CPU thread can be enough 11 Example 1 cont Suppose arrival process rate is 12 requests per second what is the response time from the disk Utilization of disk 12 0 5 125 1ms 75 Using M M 1 not operational law Response time per request block 1 ms 1 0 75 4 ms If not cached request 125 disk blocks 4 ms 125 500 ms 12 Background Little s Law 1961 For any system with no or low loss Assume R R QQ mean arrival rate mean time at device R and mean number of requests at device Q Then relationship between Q and R Q R Example Yale College admits 1500 students each year and mean time student stays is 4 years how many students are enrolled 13 Q R Little s Law arrival A 3 2 1 A t R Area A t Q time Area t 14 Deriving Relationship Between R U and S Assume flow balanced arrival throughput Assume PASTA Poisson arrival memory less arrival sees time average a new request sees Q ahead of it Assume FIFO Q R XR R S QS S XRS According to utilization law U XS R S UR R S 1 U 15 Example 2 A request may need 150 ms CPU execution time e g dynamic content 1 Mbytes network bw 1 Mbytes file access where 50 hit in memory cache Suppose network bw is 100 Mbps disk I O rate is 1 ms per 8 Kbytes assuming the program reads 8 KB each time 16 Interactive Response Time Law System setup Closed system with N users Each user sends in a request after response think time and then send next request Notation Z user think time R Response time In duration T requests generated by The total cycle time of a user request is R Z each user T R Z requests 17 Interactive Response Time Law If N users and flow balanced System Throughput X Toal req T N R T Z T RN Z R NX Z 18 Bottleneck Analysis X N min 1 Dmax N D Z R N max D NDmax Z Here D is the sum of Di 19 1 X N min Dmax DN Z R Proof N max D NDmax Z We know 1 X Dmax R N D Using interactive response time law R NX Z X RN Z R NDmax Z X DN Z 20 In Practice Common Bottlenecks No more File Descriptors Sockets stuck in TIME WAIT High Memory Use swapping CPU Overload Interrupt IRQ Overload Aaron Bannert Summary Story So Far Avoid blocking so that we can reach bottleneck throughput Introduce threads Limit unlimited thread overhead Thread pool async io Coordinating data access synchronization lock synchronized Coordinating behavior avoid busy wait Wait notify FSM Extensibility robustness Language support Design for interfaces System modeling Queueing analysis operational analysis 22 Summary Architecture Architectures Multi threads Asynchronous Hybrid Assigned reading SEDA 23 Beyond Class Complete Java Concurrency Framework Executors Executor ExecutorService ScheduledExecutorService Callable Future ScheduledFuture Delayed CompletionService ThreadPoolExecutor ScheduledThreadPoolExecutor AbstractExecutorService Executors FutureTask ExecutorCompletionService Queues BlockingQueue ConcurrentLinkedQueue LinkedBlockingQueue ArrayBlockingQueue SynchronousQueue PriorityBlockingQueue DelayQueue Concurrent Collections ConcurrentMap ConcurrentHashMap CopyOnWriteArray List Set Synchronizers CountDownLatch Semaphore Exchanger CyclicBarrier Locks java util concurrent locks Lock Condition ReadWriteLock AbstractQueuedSynchronizer LockSupport ReentrantLock ReentrantReadWriteLock Atomics java util concurrent atomic Atomic Type Atomic Type Array Atomic Type FieldUpdater Atomic Markable Stampable Reference See jcf slides for a tutorial 24 Beyond Class Design Patterns We have seen Java as an example C and C can be quite similar For C and general design patterns http www cs wustl edu schmidt PDF OOCPtutorial4 pdf http www stal de Downloads ADC2004 pra03 pdf 25 Backup Slides 26 Asynchronous Multi Process Event Driven AMPED Accept Conn Read Request Find File Send Header Read File Send Data Event Dispatcher Helper 1 Helper 1 Helper 1 Like Single PED but use helper processes threads for disk I O avoid unnecessary blocking or CPU bottleneck when DCPU becomes bottleneck Should You Abandon Threads No important for high end servers e g databases But avoid threads wherever possible Use events not threads for GUIs distributed systems low end servers Only use threads where true CPU concurrency is needed Where threads needed isolate usage in threaded application kernel keep most of code single threaded Event Driven Handlers Threaded Kernel Ousterhout 1995 Another view Events obscure control flow For programmers and tools Threads thread main int sock struct session s accept conn sock s read