Study Guides (258,621)
CA (124,962)
McMaster (7,783)
SFWRENG (36)
Final

SFWRENG 3BB4 Final: SFWR_ENG_3BB4
Premium

10 Pages
55 Views

Department
Software Engineering
Course Code
SFWRENG 3BB4
Professor
Tom Maibaum

This preview shows pages 1-3. Sign up to view the full 10 pages of the document.
SFWR ENG 3BB4 Summary
Dr. Maibaum
Winter 2015
McMaster University
Primary Author: Kemal Ahmed
This course is about concurrency in systems.
SFWR ENG 3BB4 Summary
e.g.
Action hiding
LTSA
Synchronized
Java
Monitors
Interference
Bounded Buffer
Deadlock
Safety & Liveness property
Progress Properties
Dynamic Systems
Linda
Templates
Tuple Space Model
Timed Systems
Concurrent Sof tware:
Distributed Software:
We represent models of concurrency using finite state machines (a.k.a. FSP).
Threads
active entities because they initiate actions
Opposite of monitors
Sequential process:
Processes: units of sequential execution
Models of Processes:
Finite State Processes (FSP): model processes as sequence of actions in an
algebraic f orm
Labelled Transition Systems (LT S): analyzes, displays, animates behaviour in a
graphical f orm
Labelled Transition Systems Animator (LTSA): a cool program
FSPs follow algebraic rules, such as:
Associativity: order of which operations to perform is sometimes irrelevant
Communitivity: x || y = y || x
Associativity: x || (y || z) = (x || y) || z = (x || z) ||y
State Machine Details:
Colour coding is sometimes used
Blue generally defines arbitrary states
Red generally defines the first state
An arrow without a head is still the standard for the beginning state, like from 2FA3
Arrow is triggered by a condition and
Trace: a possible sequence of actions; there can be multiple traces for a given FSM
Maximal trace:
Action [x]:
Process [P]: processes are ALWAYS CAPITALIZED
(x -> P) : a representation of a process, engaged by an action, x, and does the process, P
e.g.
SWITCH = OFF
OFF = (on -> ON),
ON = (off -> OFF).
SWITCH = OFF,
OFF = (on -> (off -> OFF)).
SWITCH = (on -> off -> SWITCH).
One rule of precedence that allows you to remove brackets is that you execute from Right
to Left
(x -> P | y -> Q) : engages in either the first or second action, depending on the input
that selects it
Concurrency:
Parallelism:
Are there shared actions?
Labels: ( label:Process | e.g. a:P )
Prefix Labels: useful f or modelling shared resources ( {set of prefix
labels}::Process | e.g. {a1,..,ax}::P )
When youre implementing a parallel database, you need to make sure that you dont do half
the re-saving/editing processes before you allow someone else to open the file.
Equivalent: same trace
Action hiding
P = (C -juice-> J,
J -return-> P ) {return}
this hides the return function
Shared Objects
How do you allocate access to a resource among multiple processes?
Mutual Exclusion: when only one process can access a resource at a time
Semaphor
Something that enables access to a resource

Loved by over 2.2 million students

Over 90% improved by at least one letter grade.

Leah — University of Toronto

OneClass has been such a huge help in my studies at UofT especially since I am a transfer student. OneClass is the study buddy I never had before and definitely gives me the extra push to get from a B to an A!

Leah — University of Toronto
Saarim — University of Michigan

Balancing social life With academics can be difficult, that is why I'm so glad that OneClass is out there where I can find the top notes for all of my classes. Now I can be the all-star student I want to be.

Saarim — University of Michigan
Jenna — University of Wisconsin

As a college student living on a college budget, I love how easy it is to earn gift cards just by submitting my notes.

Jenna — University of Wisconsin
Anne — University of California

OneClass has allowed me to catch up with my most difficult course! #lifesaver

Anne — University of California
Description
SFWR ENG 3BB4 Summary Dr. Maibaum Winter 2015 McMasterUniversity Primary Author: KemalAhmed This course is about concurrency insystems. SFWRENG3BB4 Summary e.g. Actionhiding LTSA Synchronized Java Monitors Interference BoundedBuffer Deadlock Safety & Liveness property Progress Properties Dynamic Systems Linda Templates Tuple Space Model TimedSystems Concurrent Software: Distributed Software: We represent models of concurrency using finite state machines (a.k.a. FSP). Threads active entities because they initiate actions Opposite of monitors Sequentialprocess: Processes: units of sequentialexecution Models of Processes: Finite State Processes (FSP): modelprocesses as sequence of actions inan algebraic form Labelled Transition Systems (LTS): analyzes, displays, animates behaviourina graphicalform Labelled Transition Systems Animator (LTSA): a coolprogram FSPs follow algebraic rules, such as: Associativity: orderof which operations to perform is sometimes irrelevant Communitivity: x || y = y || x Associativityx || (y || z) = (x || y) || z = (x || z) ||y State Machine Details: Colourcoding is sometimes used Blue generally defines arbitrary states Redgenerally defines the first state Anarrow without a headis stillthe standardforthe beginning state, like from 2FA3 Arrow is triggeredby a conditionand Trace: a possible sequence of actions; there canbe multiple traces fora givenFSM Maximaltrace: Action [x]: Process [P]: processes are ALWAYS CAPITALIZED (x -> P) : a representationof a process, engagedby anaction, x, anddoes the process, P e.g. SWITCH = OFF OFF = (on -> ON), ON = (off -> OFF). SWITCH = OFF, OFF = (on -> (off -> OFF)). SWITCH = (on -> off -> SWITCH). One rule of precedence that allows you to remove brackets is that you execute from Right to Left (x -> P | y -> Q) : engages ineitherthe first orsecondaction, depending onthe input that selects it Concurrency: Parallelism: Arethereshared actions? Labels: (label:Process |e.g. a:P ) Prefix Labels: usefulformodelling sharedresources ( {set of prefix labels}::Process |e.g. {a1,..,ax}::P ) When you’reimplementing a parallel database, you need to makesurethat you don’t do half there-saving/editing processes beforeyou allow someoneelseto open thefile. Equivalent: same trace Action hiding P = (C -juice-> J, J-return-> P ){return} this hides the returnfunction Shared Objects How do you allocateaccess to a resourceamong multipleprocesses? MutualExclusion: whenonly one process canaccess a resource at a time Semaphor Something that enables access to a resource You canimplement a handshakeusing multiple semaphors that allows you to toggle executionwhensharing a resource Race Conditions: the process that gets to the resource the fastest goes first If you have multiple processes that needto be executedfrom a givenprocessorthat are waiting to be executedona sharedresource, you canpush the processes onto a stackand wait, untilthe resource is free. Using this inconjunctionwith the semaphores willbe nice. Semaphors also count the numberof processes waiting to use the resource Whena resource is unavailable, the process caneitherwait ordo a non-criticalprocess. Binary Semaphor: enables anddisables?? LTSA Labelled Transition System Analyser ERROR : predefinedprocess to identify…error acquire release livelock: whenprocesses are waiting fora process to stopusing a resource that they are lockedinto using Synchronized synchronized : synchronized : only one personcanaccess a methodat a time Java synchronized : uses a lockonthe object Monitors passive entities which respondto actions (a.k.a. humans) Opposite of a thread The early conceptionof anobject Canbe implementedinobject-orientedlanguages, where its use makes it a monitor Guarded Actions: modelling by defining the range of the system monitors, identifiedby when wait() : sleeps thread, untilnotificationfrom anotherthread notify() : only runs one thread notifyAll() : wakes upallwaiting threads andthe ones that don’t get access get put to sleep overkill, so notify() if you know you only have one thread operating system deals with the orderinwhich threads are executed Interference Interactions betweenprocesses trying to share a resource. It canbe good Controlledby monitors Feature interaction: unwantedinterference BoundedBuffer A process queue forwhenthere are multiple resources Deadlock When multipleprocesses need multipleresources simultaneously to continuebut it’s not working Thinkif there is one chopstickonthe left andone onthe right of each personona table, but you need2 andeveryone takes the right chopstick, nobody caneat because you need2 Safety & Liveness property Termination: every prog
More Less
Unlock Document

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

Unlock Document
You're Reading a Preview

Unlock to view full version

Unlock Document

Log In


OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit