Transcript CSC 552.201 - Advanced Unix Programming, Fall, 2008

A State Machine Language for the
Undergraduate Operating Systems Course
CSC Research & Teaching Talk
Dale E. Parson
Tuesday, April 28, 2015
http://faculty.kutztown.edu/parson
Motivation
• Low-level projects such as modifying and
extending real O.S. modules -- scheduling,
paging, I/O drivers, etc. -- entail a lot of inertia
and incidental work.
• A theoretical / mathematical approach such as
queuing theory does not provide the
constructivist experience of a building system.
• Kutztown’s dual software development / IT
tracks have diverging prerequisite paths.
2
Why UML State Diagrams?
• Unified Modeling Language State Diagrams
are among the few UML diagram types
capable of fully specifying executable code.
• Network protocol handlers.
• I had a need for a MIDI controller protocol handler.
• Operating systems textbooks specify many
standard algorithms using state machines.
• CPU scheduling, page replacement, disk I/O scheduling.
• Tools might have been available.
3
CPU Scheduler from Silberschatz, Galvin
and Gagne's Operating System Concepts
4
UML State Diagram Constructs
• State bubbles include normal states, a unique start
state, and one or more accept states.
• Transitions between states S1  S2.
• An event triggers a transition.
• Optional data arguments may accompany event arrival.
• An optional, boolean guard expression determines
whether to cross a transition when its event arrives.
• An optional activity produces output actions and
updates to state variables that are available to
subsequent guards and activities.
5
UML State Diagram Constructs
6
UML State Diagram Tools?
• Most open source tools over-couple a front
end to a back end code generator.
• Commercial tools such as MathWorks®
Simulink® are too expensive.
• Most of the diagram elements are textual.
• Parsing a state-transition language is easy.
• Generating run-time code for a simulation
framework is the hard part, anyway.
7
Python for the compiler &
simulation run-time framework
• Regular expression module (re) for scanning.
• PLY framework for Python, similar to YACC.
• Python provides eval and exec for run-time
interpretation of source code in a
parameterized scope.
• Provides cooperative multithreading for
manageable scheduling of active state
machine objects in an event-driven simulation
framework.
8
Assignment 1 Specification
9
Assignment 1 code for
Silberschatz’s CPU state machine
• machine thread {
•
enteredRunning = 0 ;
•
start init, state ready, state running, accept terminated ;
•
init -> ready init()[]/@sleep(50)@,
•
ready -> running sleep()[@enteredRunning == 0@]/
•
@enteredRunning += 1 ; cpu(10)@,
•
ready -> running sleep()[@enteredRunning == 1@]/
•
@enteredRunning += 1 ; io(-1)@,
•
ready -> running sleep()[@enteredRunning > 1@]/
•
@trigger(1, "exit")@,
•
running -> ready cpu()[]/@sleep(50)@,
•
running -> ready io()[]/@sleep(50)@,
•
running -> terminated exit()[]/@sleep(0)@;
• }
10
Generated assignment 1 code (1)
•1
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
while True: # processor runs until return.
if self.__sleepResult__:
stime, event, args = self.__sleepResult__
self.logger.log(self)
else:
stime = self.scheduler.time
event = None
args = None
# generates custom run() code here.
if self.state == 'init':
if event == 'init':
self.logger.log(self, tag="DEPART")
self.state = 'afterstart'
self.logger.log(self, tag="ARRIVE")
exec('fork()',globals,locals)
continue
11
Generated assignment 1 code (2)
•
•
•
•
•
•
•
•
•
•
•
17
18
19
20
21
22
23
24
25
26
27
elif self.state == 'afterstart':
if event == 'fork':
locals["pid"] = args[0]
locals["tid"] = args[1]
self.logger.log(self, tag="DEPART")
self.state = 'alldone'
self.logger.log(self, tag="ARRIVE")
exec('idle(0)',globals,locals)
continue
elif self.state == 'alldone':
return
12
Statistical analysis of log files
•
•
•
•
•
•
•
•
•
•
•
•
000000000000,LOG,processor 0,init,ARRIVE
000000000000,LOG,processor 0,init,init
000000000000,LOG,processor 0,init,DEPART
000000000000,LOG,processor 0,afterstart,ARRIVE
000000000000,LOG,processor 0,afterstart,fork
000000000001,LOG,thread 0 process 0,init,ARRIVE
000000000001,LOG,thread 0 process 0,init,init
000000000001,LOG,processor 0,afterstart,DEPART
000000000001,LOG,thread 0 process 0,init,DEPART
000000000001,LOG,processor 0,alldone,ARRIVE
000000000001,LOG,thread 0 process 0,ready,ARRIVE
000000000001,LOG,processor 0,alldone,idle
13
More sophisticated simulation –
queues and sampling
Uniform, Gaussian, Exponential & Reverse Exponential lib functions
14
Queues & Sampling
•
•
•
•
FIFO Queue / Priority Queue class
Priority value to enqueue operation
Additional operations for reordering queue
Sampling function includes exponential,
reverse exponential, uniform & Gaussian
• Processor, Thread and IOUnit state machine
classes simulate hardware contexts and I/O
mechanical & queuing delays
15
Graphviz tools extract PNG graphs
– round robin scheduling example
16
Summary from First Year
• State machine diagrams provide a good intermediate
level of abstraction between real O.S. modules &
mathematical models
• Implement & run entire algorithm at a high level
• Assignments included CPU scheduler, page
replacement algorithms & I/O scheduling
• Instructor hands out 1 solution, students adapt it
• Like solving a puzzle or a proof
• Enhancements for Fall 2014 include macros to avoid
repeated code, pure functions, and push-down
automata for subroutine-style reuse
17
Updates for Fall 2014
• Added macros to avoid copy & paste code.
• Added subgraphs to model kernel libraries.
http://acad.kutztown.edu/~parson/rr_lrupage_dirty_global_subgraph.jpg
18
Plans for Fall 2015
• Increase the emphasis on analysis.
– The coding part if relatively small and “easy.”
– Small changes create massive statistical changes.
– Add more analysis into student workload.
• Increase the amount of data analyzed by increasing
simulation speed and hence throughput.
– Switch from Python threads to Python generators.
– How will we deal with massive student data sets?
19
Python threads emulate coroutines
• One thread at a time makes projects manageable.
• Thread locking slows execution down severely.
20
Python generators are only 1 frame
deep, but …
• The compiler knows all the blocking library functions.
• Make each store the state of its STM & return.
• Run method is now a fast Python generator that
yields its STM object. No threads, locks, preemption.
21
Fast == generate much data
•
•
•
•
•
•
Overrun student accounts, /tmp not solution.
Run it through a compressor on the way out.
Student inspects log via a decompressor.
Make them learn to use Unix less etc.
Statistical cruncher temporary decompresses.
The statistical diffs are based on the statistical
analysis, not on the big raw data set.
• Maybe data mining tools (e.g., Weka)!
22
Other benefits for students
• They learn how to write statistical, discretetime, discrete-event simulations.
• These could be applied to other domains.
• They could apply this to load analysis, etc. in
their upcoming careers.
• With slightly more robust & sophisticated
tools, they could take these tools with them.
• I may work on a debugger. 
23