Transcript 11. Threads

11. Threads
• A way to support several parallel activities in a
program
• Execute asynchronously and ”simultaneously” e.g.
timeslicing
• If two threads are dependent on each other
synchronization may be necessary
• If they depend on a shared resource then deadlock,
livelock or race conditions can occur.
• One solution to synchronization is the semaphore
11.1 Example: Web browser
Problem: fetching images, files, sound etc
takes time. Don’t want to lock up screen while
waiting, e.g. can’t scroll down screen or abort
fetch.
Solution: create separate thread for page fetch
and start this on each new fetch.
11.2 Threads in Java
•
•
•
•
•
•
Interface Runnable with method run()
classes Thread, Write run() yourself
To start a thread start()
start() calls run() immediately
To stop a thread interrupt()
Try to avoid stop(), suspend(), resume()
11.3 Thread
Safety/Management
• Problem: threads running methods on the
same object may corrupt that object. E.g.
internal bank transfer.
acc[i] = acc[i]+x
acc[j] = acc[j]-x
acc[i] = acc[i]+y
acc[j] = acc[j]-y
Problem: keep the bank total constant!
•
•
•
•
Solution: synchronization on objects
Aka Monitors
Give each object a lock.
Thread gets a lock by calling a
synchronized object method.
• When one thread has the lock on an object
no other thread may get the lock.
• Lock is on the object, not its methods
• Unsynchronized methods can still be called.
• Lock a method with synchronized
public synchronized void transfer (int from, int to)
{
acc[from] -= amount;
acc[to] += amount;
num_transactions++;
}
Looks fine, but what if an account mustn’t go
negative (no credit facility)??
• Problem: what happens if we get the lock
and can’t proceed?
• Another thread which had the lock could
allow us to proceed!
• Thread calls wait() method
• Gives up the lock temporarily,
• Enters queue of waiting threads on the
object.
• notify() reawakens one thread in queue
• notifyAll() reawakens all threads in queue
public synchronized void transfer (int from, int to)
{
while ( acc[from] < amount )
{ wait(); } // inactive wait!
acc[to] += amount;
num_transactions++;
notifyAll();
}
Try to avoid deadlocks, livelocks and races!!
11.4 Rules (for the WC!)
1. If 2 or more threads modify an object,
declare them as synchronized. Read-only
methods which are affected must also be
synchronized. (Decency Rule 1)
2. If a thread must wait for a change, wait
inside the object by entering a
synchronized method and doing a wait.
(Decency Rule 2)
3. Don’t spend a long time in a synchronized
method. If you can’t complete, perform a
wait(). (Fairness Rule 1)
4. Whenever a method changes the state of
the object, execute a notifyAll(). (Fairness
Rule 2)
5. wait() and notifyAll()/notify() are methods
of the Object class, not the Thread class.
make sure waits are matched by notifies
on the same object. (Fairness Rule 3)
11.5 Real-Time Issues
• Real-time systems are not necessarily fast
• Programmer gives guarantees for execution
time, etc
• Operating system must handle time, parallel
activities, scheduling and priority of
processes, as well as interrupts
• Program uses synchronization
(semaphores), conditional execution (event
variables) e.g. using monitors (ADT)
11.6 Timers
• Class Timer
• Constructor Timer(int delay, ActionListener l)
• void start() : starts the timer
• void stop(): stops the timer sending events
• actionPerformed() of l is called whenever
a timer interval has elapsed.
11.7 Real-Time Example
When we burn a CD the hardware must not
pause but write continuously. The data buffer
may therefore not become empty. In
Windows or Unix there is no guarantee for
this under heavy loading. In a real-time OS
such loading is dealt with by lowered priorities
(burn has highest).
12. Data Structures
• What kind of problem is to be solved?
– Queue (FIFO)
– Stack (LIFO)
– Random Access (sorted or unsorted)
• Table with lookup using keys
• Set , 1 copy of each
• List many copies
12.1 Collections
• Collection Interfaces
– JList
– JTree
– Vector, LinkedList
– Set (1 copy of each object)
– HashSet, TreeSet
– Map (lookup key + value in a table)
– AbstractMap, HashMap, TreeMap
12.2 Pattern Iterator
• For each data structure we need a method to
traverse it, a so called iterator
• Example: Trees, breadth-first, depth-first
• Method will affect run-time performance,
but end-user shouldn’t see this, only see
iterator interface.
Iterator (Cont.)
•
•
•
•
•
Data Structure
Start of traversal
Increment traversal
Get i-th element
Finished traversal?
Vector
i = 0;
i++;
myVector.get(i);
i < myVector.size();
12.3 Trees
•
•
•
•
•
•
Need a node called root
A node can have several child nodes
A childless node is called a leaf
Example: DefaultMutableTreeNode
parent.add(child); adds a child to a node
See also DirTree.java in Lab ex. 4.
TreeModel model = … ;
Jtree tree = new Jtree(model);
• Make a class that implements TreeModel
interface. DefaultTreeModel already does this.
TreeNode root = …;
DefaultTreeModel model = new
DefaultTreeModel(root);
• TreeNode is another interface.
• DefaultMutableTreeNode already
implements MutableTreeNode a
subinterface of TreeNode.
DefaultMutableTreeNode node = new
DefaultMutableTreeNode(“Stockholm”);
or
node.setUserObject(“Göteborg”)
Now to construct a tree!
DefaultMutableTreeNode root = new
DefaultMutableTreeNode(“World”);
DefaultMutableTreeNode country = new
DefaultMutableTreeNode(“Sverige”);
DefaultMutableTreeNode town = new
DefaultMutableTreeNode(“Stockholm”);
root.add(country);
country.add(town);
DefaultTreeModel model = new
DefaultTreeModel(root);
JTree tree = new JTree(model);
Container contentPane = getContentPane();
contentPane.add(new JScrollPane(tree));
• What about the iterators?
enumeration e =
root.breadthFirstEnumeration();
while (e.hasMoreElements()) {
DefaultMutableTree node =
(DefaultMutableTree)e.nextElement();
/* do something with node … e.g. */
if (node.getUserObject().equals(obj) )
return node;
}
13. Java and Operating
Systems
• Java is OS independent
• Class Runtime gives an interface to the OS
• Applets execute in a sandbox where a
security manager controls access to file
system, network connections, devices, etc.
• Applications can be given a security
manager.
13.1 Execution of Java
• Class file is not binary and isn’t executed
directly in hardware.
• Java byte code executes on a virtual java
machine jvm … slow??
• Applets execute in an appletviewer or a
web-browser with a jvm
• Beans execute in a BeanBox
13.2 Execution of Java (Cont.)
• Can connect Java code to other code (C,
C++, Fortran etc.) vis JNI java native
interface
• 3rd party suppliers have compilers to
binary code. Increases speed but loses
platform independence.
• Write-once, debug everywhere!! ?? (NM!)
14. BNF Grammars
• Standard format to define new context-free
grammars, Backus-Naur-Form BNF.
• Example:
Proposition ::= Subject Predicate
Subject ::= “I” | “you”
Predicate ::= “know” | “think”
Gives strings
I know, I think,
you know, you think
14.1 BNF Example
Statement ::= Proposition |
Proposition Conjunction
Statement
Conjunction ::= “and” | “that”
Gives
I know that you think that I
think and you know
14.2 Parse Trees
I know that you think that I think
sub
pred
prop
conj
sub
pred
prop
conj
sub
statement
statement
statement
pred
14.3 Ambiguity
This language is unambiguous.
i.e. every string in the language has a
unique parse tree.
Tip: use recursive descent in lab ex. 4 and a
method for each symbol in the grammar.
I know that you think that I think
sub
pred
conj
sub
pred
statement
prop
statement
statement
conj
sub
pred
prop/statement
14.4 Language Analysis
• Skaldic (old Icelandic) poetry – kennings
man ::= “man” | “tree of the” battle |
“thrower of the” sword | “giver of the”
gold
gold ::= “gold” | “fire of the” war
war ::= “war” | “storm of the” spear
spear ::= “spears” | “witch of the”
shield
shield ::= “shield” | “moon of the ship”
Giver of the fire of the storm of the
witch of the moon of the ship
Construct a parse tree for this kenning to
understand its structure. Are kennings simply
metaphors? Only a great poet was allowed to
introduce a new kenning rule! Add some rules!
M. I. Steblin-Kamenskii, Icelandic Culture, 1967.
“As a rule, any kenning for a warrior was no richer
in content than the pronoun “he” ”
14.5 XML
• Not related to UML!!!
• XML = eXtensible Markup Language
• An internet standard for data interchange,
e.g. between databases.
• Defines a data interface.
• Originates from SGML and is related to
HTML
14.6 XML Methodology
•
•
•
•
Tagged data
e.g. <flower>rose</flower>
<color>rose</color>
Data marked up with its identity e.g.
<?xml version=”1.0” encoding=”UTF-8”?>
<!DOCTYPE configuration …>
<configuration>
<title>
<font>
<name>Helvetica</name>
<size unit=”pt”>36</size>
</font>
<author>
Karl Meinke
<phone>6337</phone>
</author>
</title>
</configuration>
• Optional (recommended) header
<?xml version=”1.0”?>
• Optional document type declaration (DTD)
<!DOCTYPE configuration SYSTEM
”http://myserver.com/config.dtd”>
• Finally the root element
<configuration> … <configuration>
• An element can contain child elements, text or
both (but both makes a messy DTD!)
• Use attributes to modify data interpretation,
and not to specify values
Parsing an XML document
• Document Object Model (DOM) parser
reads an XML document into a tree
structure
• Simple API for XML (SAX) pareser
generates events as it reads an XML
document.
• Sun provides its own DOM parser
• Be careful with whitespace around tags!
import javax.xml.parsers.*;
import javax.swing.tree.*;
…
DocumentBuilderFactory factory =
DocumentBuilderFactory.newInstance();
DocumentBuilder builder =
factory.newDocumentBuilder();
File f = …
Document doc = builder.parse(f); /*tree structure of the
document*/
Element root = doc.getDocumentElement();
NodeList children = root.getChildNodes();
Node firstchild = children.item(1);
14.7 DTD
• Usually an external file (small DTDs can
be internal)
• Specifies the format of tagged data.
• An XML document is valid (wrt a DTD) if
it satisfies the format of the DTD
• Can build XML validators – prevent data
corruption, more efficient parse, etc.
• factory.setValidating(true);
• e.g. A font element consists of a name
element followed by a size element
<!ELEMENT font (name,size)>
• e.g. A kenning
<!ELEMENT man ( manText |
treeText, battle |throwerText,
sword | giverText, gold )>
<!ELEMENT manText #PCDATA >
• DTDs define regular expressions
• XML assumes grammar is unambiguous!!
Rule
E*
E+
E?
E1 | … | En
E1 , … , En
Meaning
0 or more occurrences of E
1 or more occurrences of E
0 or 1 occurrences of E
E1 or E2 …. or En
E1 followed by E2 followed
by … followed by En
#PCDATA Text
Any
Any children allowed
Empty
No children allowed
• Can also specify attributes of elements
<!ATTLIST font style (plain|bold|italic) plain>
• Style attribute can be plain, bold or italic, but
default is plain.
<!ATTLIST size unit CDATA #IMPLIED>
• Unit attribute of size is a character sequence
and optional
<!ATTLIST size unit CDATA #REQUIRED>
• Now unit is not optional!
<!DOCTYPE Date [
<!ELEMENT Date (Name*, Moon?)>
<!ATTLIST Date year CDATA #REQUIRED>
<!ATTLIST Date month #REQUIRED>
<!ATTLIST Date day #REQUIRED>
<!ATTLIST Date weekday #IMPLIED>
<!ATTLIST Date CDATA #REQUIRED>
<!ELEMENT Name(#PCDATA)>
<!ELEMENT Moon EMPTY>
<!ATTLIST Moon phase (new|between|full)
“between”>
]>