RustySpigot
software solutions
Computer Science » Computer Design
Computer Design
CISC & RICS
CISC tried to make the semantic gap between high level language and assembler smaller, but this resulted in large, slow instruction sets.
RISC makes the common case fast.
Register Files
A register file is an array of registers. It is used to localise intermediate results for speed gains.
ARM has 15 registers r0-r14. r15 is the program counter. There is also the cspr (current program status register) which contains 4 conditional bit fields. Conditional branches check these values.
The accumulator is a special register in that it can be used implicitly (it doesn't have to be stated) e.g.
ADD memoryaddress
will add the accumulator to the memory address.
Load and Store
STR R0, [Rbase] Store R0 at Rbase.
STR R0, [Rbase, Rindex] Store R0 at Rbase + Rindex.
STR R0, [Rbase, #index] Store R0 at Rbase + index.
Index is an immediate value.
STR R0, [R1, #16] would load R0
from R1+16.
STR R0, [Rbase, Rindex]! Store R0 at Rbase + Rindex, &
write back new address to Rbase.
STR R0, [Rbase, #index]! Store R0 at Rbase + index, &
write back new address to Rbase.
STR R0, [Rbase], Rindex Store R0 at Rbase, & write back
Rbase + Rindex to Rbase.
STR R0, [Rbase, Rindex, LSL #2] will store R0 at the address
Rbase + (Rindex * 4)
STR R0, place Will generate a PC-relative offset
to 'place', and store R0 there.
The multiple data transfer instructions (LDM and STM) are used to load and store multiple words of data from/to main memory.
The main use of LDM/STM is to dump registers that need to be preserved onto the stack. We've all seen STMFD R13!, {R0-R12, R14}.
Example: Iterative Fibonacci in ARM
;assume x is held in r0 at start
mov r1,#1 ;initialisation
mov r2,#1
mov r3,#2
loop: cmp r3,r0 ;if i>x
bgt finish ;then jump to finish
add r1,r1,r2 ;a:=a+b
sub r2,r1,r2 ;b:=a-b
add r3,r3,#1 ; i:=i+1
b loop
finish: mov r0,r1 ;return result in r0
Where x is held in register r0, a is held in register r1, b is held in register r2, i is held in register r3
Virtual Addresses
As computers became more complex, it became difficult for programs to keep track of the different types of memory in different locations. To solve this problem, the operating system fabricates a "virtual memory space".
With a multiple address space scheme, each application resides in its own virtual memory space and can't accesses any other memory. UNIX uses this ,but it makes sharing libraries difficult.
With the single address space scheme, all applications share the same memory space. This is simple, and means there is only one virtual address for each physical address.
A 32-bit machine can reference 4GB or memory, though it may only have say 16M of real physical memory- but with virtual addressing it can use the secondary memory(hard disk) to pretend it has the full 4GB. This 4GB virtual address space is split up into chunks, commonly 4K in size, called pages. The physical memory is also split up into chunks, also commonly 4K in size, called frames. A program's text segment might start at the virtual address 0x00000004 - page number 0x0, and offset 0x4, but in reality, this may correspond to the physical address 0xff0e0004 - frame number 0xff0e, and offset 0x4. What the virtual memory system does is convert virtual addresses into physical addresses, essentially, mappings between pages and frames. The page table is used for this purpose.
When an application attempts to use a page which has been swapped to disk an exception is raised and the OS swaps an existing page with the required one.
Translation Lookaside Buffers (TLBs)
A TLB is a cache in the CPU used to improve the speed of virtual address translation.
Many architectures also have direct hardware support for virtual memory, providing what is known as a translation lookaside buffer (TLB), which is filled with page-frame mappings initially, and instead of having the virtual memory system entirely in software, when the hardware looks up a memory address and does the page-frame translation, virtual address to page-frame mapping is cached in the TLB, which gains us a performance increase.
However, the TLB can only hold a fixed number of page-frame mappings. It is the job of the virtual memory system to extend this into software, and to hold extra page-frame mappings. The virtual memory system does so by means of a page table.
The TLB contains not only translation information, but also the protection data. A permission fault is raised if an application attempts to access a page it doesn't have the right to access.
If a TLB hit takes 1 clock cycle, a miss takes 30 clock cycles, and the miss rate is 1%, the effective memory cycle rate is an average of 
clock cycles per memory access.
 |
Translating Virtual Addresses to Physical Addresses
The page table
Say a program is running and it tries to access memory in the virtual address 0xd09fbabe. The virtual address is broken up into two: 0xd09f is the page number and 0xbabe is the offset, within the page 0xd09f.
With hardware support for virtual memory, the address is looked up within the TLB. The TLB is specifically designed to perform this lookup in parallel, so this process is extremely fast. If there is a match for page 0xd09f within the TLB (a TLB hit), the physical frame number is retrieved, the offset replaced, and the memory access can continue. However, if there is no match (called a TLB miss), the second port-of-call is the page table.
When the hardware is unable to find a physical frame for a virtual page, it will generate a processor interrupt called a page fault. Hardware architectures offer the chance for an interrupt handler to be installed by the operating system to deal with such page faults. The handler can look up the address mapping in the page table, and can see whether a mapping exists in the page table. If one exists, it is written back to the TLB, as the hardware accesses memory through the TLB in a virtual memory system, and the faulting instruction is restarted, with the consequence that the hardware will look in the TLB again, find the mapping, and the translation will succeed.
However, the page table lookup may not be successful for two reasons:
· there is no translation available for that address - the memory access to that virtual address is thus bad or invalid, or
· the page is not resident in physical memory (it is full).
In the first case, the memory access is invalid, and the operating system must take some action to deal with the problem. On modern operating systems, it will send a segmentation fault to the offending program. In the second case, the page is normally stored elsewhere, such as on a disk. To handle this case, the page needs to be taken from disk and put into physical memory. When physical memory is not full, this is quite simple, one simply needs to write the page into physical memory, modify the entry in the page table to say that it is present in physical memory (see the next section), write the mapping into the TLB and restart the instruction.
However, when physical memory is full, and there are no free frames available, pages in physical memory may need to be swapped with the page that needs to be written to physical memory. The page table needs to be updated to mark that the pages that were previously in physical memory are no longer so, and to mark that the page that was on disk is no longer so also (and to of course write the mapping into the TLB and restart the instruction). This process of swapping pages between physical memory and disk is known sometimes as, obviously, swapping (though the term is sometimes used to describe swapping entire processes). This process however is extremely slow in comparison to memory access via the TLB or even the page table, which lies in physical memory.
Safety
One of the most important benefits of virtual addressing is that each process can write only to the physical memory for which the operating system has created page table entries. This prevents one process from overwriting another process's data. The OS often splits up the memory into text (instructions), data (constants) and stack regions to reduce the chances of the stack overwriting the text area etc.
Thrashing is when the OS is constantly moving data between primary and secondary storage.
Real and Protected Mode
The physical address is generated by multiplying the segment register by 16, then adding a 16-bit offset. Using 16-bit offsets implicitly limits the CPU to 64k segment sizes.
In protected mode, memory segmentation is defined by a set of tables (called descriptor tables) and the segment registers contain pointers into these tables.
The Java Virtual Machine (JVM)
Virtual machines allow portability and numerous at run time performance improvements.
The JVM has 4 special registers (Pc, base address of local memory, address of top of operand stack, base of current frame). A frame contains local variables, operand stack and run time data.
Memory Hierarchy
● register file (~128 bytes), multiported SRAM,multiple read/writes per cycle
● 1st level cache (~64 kbytes), SRAM, 1 or 2 read/writes per cycle
● 2nd level cache (~1Mbytes), SRAM, 0.75 read/write per cycle
● main memory (~2GBytes), DRAM 50 cycles for first read/write, then 5 (burst mode)
● hard disk for virtual memory (~200 GBytes), slow but has cache
Main memory can be built from the fast SRAM (5 transistors/bit) or the cheaper DRAM (1 transistor/bit).
Cache Principles
● Temporal locality: then it is likely to be accessed again
● If a word is accessed then its neighbours are likely to be accessed soon
Cache lines take advantage of spatial locality: rather than storing words randomly in memory they are stored next to each other in lines of 4 or 8 words and area all read at once from DRAM in a burst.
Direct Mapped Cache
A direct-mapped cache scheme makes picking the slot very simple. It treats the slot as a large array, and the index of the array is picked from bits of the address (which is why we need the number of slots to be a power of 2---otherwise we can't select bits from the address)
The scheme can suffer from many addresses "colliding" to the same slot, thus causing the cache line to be repeatedly evicted, even though there may be empty slots that aren't being used, or being used with less frequency.
("Slot" is normally called Index)
Suppose you have address B31-0.
l Use bits B11-5 to find the slot.
l See if bits B31-12 match the tag of the slot.
l If so, get the byte at offset B4-0.
l If not, fetch the 32 bytes from memory, and place it in the slot, updating valid bit, dirty bit, and tag as needed.
Car Park analogy: "Your parking spot is the first 3 digits of your student Id number,"
Set Associative Cache
Direct mapped cache have a set of cache lines at each location used to indicate which element to read from.
Car park analogy: "Your parking spot is based on the first 2 digits of your student ID number. In this case, you use the first 2 digits of your student ID, and have up to 10 different parking spots you can park at. "
Victim Cache
A victim cache is a cache used to hold blocks evicted from a CPU cache due to a conflict or capacity miss. The victim cache lies between the main cache and its refill path, and only holds blocks that were evicted from that cache on a miss. This technique is used to reduce the penalty incurred by a cache on a miss.
Cache Line Replacement Policies
Least Recently Used, Not Last Used, Random
Write Back and Write Through
Write through: Data is written to both cache and lower level memory
Write back: Data is written to the cache only, then written to lower level memory when cache line is replaced.
Dyadic (2 part) Instruction Encoding
● Fetch instruction from memory at address PC, increase PC (word increment so PC:=PC +4)
● Decode opcode
● Check conditionals
● Execution: Fetch operands 1+2
● Shift operand 2 is required
● Perform operation (ALU)
● Write result to destination register
● If S bit is set then set condition codes
Monadic instructions are the same except operand 1 doesn't need to be fetched.
ARM Thumb Code
The thumb instruction set uses 16-bit instructions, so requiring less memory but generally more instructions.
MIPS (Microprocessor without Interlocked Pipeline Stages)
One major barrier to pipelining was that it required interlocks to be set up to ensure that instructions that took multiple clock cycles to complete would stop the pipeline from loading more data -- basically to pause while it completed. A major design aspect of the MIPS design was to demand that all instructions take only one cycle to complete, thereby removing any needs for interlocking.
Pipelines
Pipe lining, as opposed to sequential execution, allows numerous instructions to be processed at once.
Many designs include pipelines as long as 31 stages (like in the Intel Pentium 4).The downside of a long pipeline is when a program branches, the entire pipeline must be flushed, a problem that branch predicting helps to alleviate. ARM uses the cleared stages in the pipeline to save the corrected version of the PC to R14 and to write the branch address to the PC.
A pipelined system typically requires more resources (circuit elements, processing units, computer memory, etc.) than one that executes one batch at a time, because its stages cannot reuse the resources of a previous stage. Moreover, pipelining may increase the time it takes for an instruction to finish.
The pipeline controller would take a typical instruction like ADD A, B, C
and translate it into something like:
LOAD A, R1
LOAD B, R2
ADD R1, R2, R3
STORE R3, C
LOAD next instruction
And then execute the instructions on the pipeline.
The following diagram has four pipelines (in this pipeline execute and write back are separate stages):
In this example, the purple instruction gets delayed at the fetch stage, stalling all further instructions by one clock cycle.
The ARM710 pipeline has 3 stages: fetch, decode and execute. The pipelines throughput is limited by the worst case performance of a particular stage. The ARM's execute stage includes register reads, a shift, an ALU operation and register write back- so it takes a long time. Adding extra stages improves performance, at the cost of power consumption and transistor count.
We could speed up the pipeline by taking "register fetch" and "register write back" out of the execution stage:
| instruction fetch | decode | register fetch | execute | register write back |
But this creates a problem when the result of the next instruction depends on the prior:
add R1,R1,R3
add R1,R1,R3
There are two options here: either stall the execution until the write back has occurred, or feedforward/bypass the output of the execution stage straight back to its input. The second option is faster but consumes more transistors.
Note: In practice, register write back and read are performed in the same cycle as they don't take long.
The Classic RISC Pipeline
| instruction fetch | register fetch | execute | memory access | register write back
|
Load Delay Slots
The data from a load has to be bypassed two pipeline stages. If there is a data dependency, the next instruction will have to be stalled at the register fetch/decode stage.
nop instructions can be put in by the assembler, so the hardware doesn't have to worry. Alternatively, the hardware can use a method such as scoreboarding (every register has a flag to indicate whether its value is available, or will be made available via a bypass).
Exception Handling in Pipelines
Precise exceptions are hardware intensive and allow the OS to know exactly what happened, and the PC is saved.
Instruction Replays
You tend to find out about a cache miss late, so replay the instructions.
Parallel Communication
This doesn't work well for high clock frequencies over long distances due to timing skew.
Serial Communication
The clock is recovered from the data stream, and data is coded.
RS232
Designed for dumb devices, many non standard devices. Asynchronous serial line.
USB
Devices can be chained together. A twisted data pair (bidirectional differential signalling).
Plug and play (devices hold vendor, class information).
Up to page 25 in Comp Design 2
Concurrent Systems and Applications
Syllabus
Aims
The aims of this course are (a) to introduce the modular design of application software, using the facilities of the Java and C# programming language as running examples, (b) to explore the need for and implementation of concurrency control and communication in inter-process and intra-process contexts and (c) to introduce the concept of transactions and their implementation and uses.
Lectures
· Programming with objects. Revision overview of the Java programming language. Structuring programs using encapsulation and inheritance. Design patterns. [4 lectures]
· Further Java topics. Graphical user interfaces. Reflection and serialization. Finalizers. Class loaders. Software testing. [8 lectures]
· Concurrent systems. Reasons for multi-threaded programming. Correctness criteria. Mutual exclusion locks and condition variables. Alternative concurrency-control primitives. [5 lectures]
· Distributed systems & transactions. General problems in distributed systems. Naming. Access control. IDLs. Message passing and the use of sockets in Java. Remote method invocation. Compound operations & correctness criteria. Crash recovery. Isolation. [5 lectures]
· Generics in Java. Single-compilation templated classes. Type specialisation and typing constraints. Interactions with reflection, serialisation, and the class loader. Advanced implementation techniques using Generics. [2 lectures]
Objectives
At the end of the course students should
· understand the terminology of object oriented programming and be able to use it with precision
· be able to illustrate the use of object oriented techniques through examples of the kind seen in the Java standard libraries
· understand the need for and implementation of concurrency control
· understand different mechanisms for communication within or between applications and evaluate their trade-offs in different scenarios
· understand the concept of transactions and their application in a range of systems
· understand why software testing is not always easy and the techniques used to achieve thorough testing
Recommended reading
* Bacon, J. & Harris, T. (2003). Operating systems or Bacon, J. (1997) Concurrent systems (2nd ed.). Addison-Wesley.
Myers, G.J. (2004). The art of software testing. Wiley (2nd ed.).
Lea, D. (1999). Concurrent programming in Java. Addison-Wesley (2nd ed.).
Bracha, G., Gosling, J., Joy, B. & Steele, G. (2000). The Java language specification. Addison-Wesley (2nd ed.). http://java.sun.com/docs/books/jls/
Gamma, E., Helm, R., Johnson, R. & Vlissides, J. (1994). Design patterns. Addison-Wesley.
Java Revision
| x <
x > x <= x >= |
More than x
Less than x More than/= to x Less than/= to x |
==
!= |
Equal to
Not equal to |
|
| Any numeric comparison returns 0 if either number is a NaN | ||||
| +,-,*,/ | Obvious | x % y | r where x=qy+r | |
| byte
short int long float double char boolean |
Represents -128 to 127
-215 to 215 -1 -231 to 231 -1 -263 to 263 -1 32 bit floating point value 64 bit floating point value A single character |
|||
| \n
\r \u[Hex number] |
New line
Carriage return Unicode character |
\"
\' \\ |
"
' \ |
|
| <<
>> >>> |
Shift every bit left
Shift every bit right Same,fills with 0's |
(type)x
Final type name
|
Casts x
Makes a constant
|
|
| ~x
& ^ | |
-x
And Exclusive Or Inclusive Or |
While (case) {}
do {} while(); break continue |
Continue while case
Condition at end Exit loop Jump to next cycle |
|
| Switch (var) {
case x: ...; break; default: ...; |
Compare var
If var =x then ... Exit switch If no case found |
Throw x
try { catch (Arg) {..} finally
|
Raise Exception X
Precedes catch If exception arg ..
Do at end of try
|
|
| assert x
import [class] extends x
implements x |
If x and -ea flag at command line then raise exception
Allows you to directly reference members of [class] Creates a subclass of x, ie the new class begins as x and can then be extended The new class adheres to x, the name,number and type of arguments in the class must match the interface/inherited class |
|||
| This.x
abstract
final
static
super.method(); strictfp |
Refers to the main x in top class
Class is abstract if declared or contains abstract method. Can't be instantiated buy can make object references. When a method is final it cant be overridden by any derived class. A final class can't be sub-classed. Also constants. Associated with class, not instantiations: A single global class variable meaning it can be referred to globally just as Class.ItemName Calls method() from the class that the current class extended The method/class will be executed using IEE754 floating point |
|||
| Private
Package protected public
|
A method or variable declared as private can only be referenced from within the class in which it is defined.
Any class in the same package can reference a value (default). Visible in derived classes even if they are in other packages. Names available regardless of packages and inheritance |
|||
| synchronized
volatile
transient native |
Ensures that several threads in a multi-threaded applications do not access the same class/method at the same time
Rather than caching the JVM will re-read variables each time they're accessed Transient fields aren't serialized Non-java code |
|||
|
|
|
|||
| Printf("...
%i$ %< %d |
Prints argument i Re-use argument Prints an integer |
%s
%n %tD %c |
Anything to string
Newline Date Prints a character |
|
Reference types are class types, interface types and array types .
The substitution principle states that sub-types must be substitutable for supertypes. This is true so
long as for each method in the super type, the sub type must have a corresponding method.
The instanceof operator requires an object as its left operand and the name of a reference type as its
right operand. It evaluates to true if the object is an instance of the specified type.
If B extends A...
If B extends A, then an array of type A[] can hold objects of type A or B, but an array of type B can only hold objects of type B.
A field in the sub-class B is said to hide a field in the super-class if it has the same name. The hidden field can be accessed by casting the object reference to the type on which the field is defined, or by writing super.name (ie A.name) to get to the immediate super-class.
The sub-class B can overload the methods in its superclass A by making additional definitions with different signatures (ie taking different arguments).
It can override them by supplying new definitions with the
same signature.
Abstract methods
It is not permitted to instantiate an abstract class, but we can use object references of the type of the abstract class.
Static modifier
A static field/method is associated with the class rather than objects.
Interfaces
An interface definition declares method signatures and static final fields (constants).
A class that implements an interface must either supply definitions for all declared methods or be declared abstract.
Nested classes/interfaces
There are four cases:
● inner classes in which the enclosed class is an ordinary class (i.e. non-static)
● static nested classes in which the enclosed definition is declared static
● nested interfaces in which an interface is declared within an enclosing class or interface
● anonymous inner classes
Each inner class is said to be "enclosed" by the class that it is in. Inner classes can access fields in the outer class, and the outer class itself can be accessed using [outer-class].this
Static nested classes are often used as "helper" functions.
Anonymous inner classes are declared with just "{ }"
Design patterns
The observer design pattern
One or more observers/listeners watch for events raised by the observed object.
Subect class has a list of observers and the following functions:
The Attatch() itself to list of observers on the object. Also Detach(). Notify() calls the update function in each observer.
The abstract observer class has it's Update() function overridden by subclasses.
The singleton pattern
Ensures that a class can be instantiated at most once. Private constructor ensures external classes cannot instantiate the class by calling new. A static method creates an instance when first called and subsequently returns an object reference to the same instance.
class Singleton {
static Singleton theInstance = null;
private Singleton() {...}
static Singleton getInstance() {
if (theInstance == null)
return (theInstance = new Singleton());
return theInstance;
}
void method1() {...}
void method2() {...}
void method3() {...}
}
The abstract factory pattern
An example of this would be an abstract factory class DocumentCreator that provides interfaces to create a number of products (eg. createLetter() and createResume()). The system would have any number of derived concrete versions of the DocumentCreator class like FancyDocumentCreator or ModernDocumentCreator, each with a different implementation of createLetter() and createResume() that would create a corresponding object like FancyLetter or ModernResume.
/*
* GUIFactory example
*/
abstract class GUIFactory
{
public static GUIFactory getFactory()
{
int sys = readFromConfigFile("OS_TYPE");
if (sys == 0)
{
return new WinFactory();
}
else
{
return new OSXFactory();
}
}
public abstract Button createButton();
}
class WinFactory extends GUIFactory
{
public Button createButton()
{
return new WinButton();
}
}
class OSXFactory extends GUIFactory
{
public Button createButton()
{
return new OSXButton();
}
}
abstract class Button
{
public abstract void paint();
}
class WinButton extends Button
{
public void paint()
{
System.out.println("I'm a WinButton: ");
}
}
class OSXButton extends Button
{
public override void paint()
{
System.out.println("I'm a OSXButton: ");
}
}
public class Application
{
public static void main(String[] args)
{
GUIFactory factory = GUIFactory.getFactory();
Button button = factory.createButton();
button.paint();
}
// Output is either:
// "I'm a WinButton:"
// or:
// "I'm a OSXButton:"
}
The adapter pattern
The adapter design pattern 'adapts' one interface for a class into one that a client expects. An adapter allows classes to work together that normally could not because of incompatible interfaces by wrapping its own interface around that of an already existing class. The adapter is also responsible for handling any logic necessary to transform data into a form that is useful for the consumer. For instance, if multiple boolean values are stored as a single integer but your consumer requires a 'true'/'false', the adapter would be responsible for extracting the appropriate values from the integer value.
Visitor Pattern
Use a hierarchy of classes to represent the nodes in a data structure, e.g. a tree.
A concrete sub-class of Visitor is constructed for each kind of operation on the data structure:
abstract class Visitor {
abstract void apply(Object o);
}
class VisitorCountNulls extends Visitor {
int count=0;
void apply(Object o) {if (o == null) ++count;}
}
class VisitorSumIntegers extends Visitor {
int sum=0;
void apply(Object o) {
if (o instanceof Integer) {
sum += ((Integer) o).intValue();
}
}
}
Reflection
Reflection is provided by a number of classes in the java.lang and java.lang.reflect packages.
Can get errors eg java.lang.ClassNotFoundException and java.lang.SecurityException.
You can access public fields with getFields();
public class ReflExample3 {
public static int field1 = 10;
public static int field2 = 11;
public static void main(String [] args) {
try {
Class c = Class.forName(args[0]);
java.lang.reflect.Field f;
f = c.getField(args[1]);
int value = f.getInt(null);
System.out.println(value);
} catch (Exception e) {
System.out.println(e);
}
}
}
You can invoke methods, eg;
Object parameters[] = new Object [2];
parameters[0] = ref1;
parameters[1] = ref2;
m.invoke(target,parameters);
The parameters must be wrapped, eg rather than just 42 you have to write new Integer(42).
Serialization
You could use reflection to get the contents of fields at run time, then save them.
ObjectInputStream and ObjectOutputStream classes automate this procedure e.g;
FileOutputStream s = new FileOutputStream("file");
ObjectOutputStream o = new ObjectOutputStream(s);
o.writeObject(drawing);
o.close();
Classes must implement the java.io.Serializable interface to indicate that the programmer believes this is a suitable way of loading or saving instance state.
A 0-argument constructor must be accessible to the sub-classes being serialized: it is used to initialize fields of the non-serializable super-classes.
Swing follows a model-view-controller
Components and Containers
Containers implement an add method to place components within them.
Components represent the building blocks of the interface: for example, buttons, check-boxes, text boxes, etc.
A JFrame has a root pane which contains the main content pane and the menu bar.
Methods which extend java.awt.event and java.awt.event are invoked on a listener for input.
Anonymous inner classes can be used to handle input eg;
addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
...
}
});
Another way is to define inner classes that extend adapter classes from the java.awt.event package.
javax.accessibility
Swing components implement Accessible, defining a single method getAccessibleContext().
Garbage Collection
Reclaiming Space
The JVM guarantees that storage space will not be reclaimed while an object remains reachable, defined as being if it:
· is referred to by a static field in a class;
· is referred to by a local variable in a running thread;
· still needs to be finalized; or
· is referred to by another reachable object.
Methods of collection
Generational collection: "most objects die young" ->
keep a small young generation which can be collected
quickly and frequently.
Parallel collection: multiple processors work on GC at the
same time -> application pauses for less time.
Concurrent collection: GC occurs at the same time as
application execution.
Incremental collection: GC occurs in small bursts, e.g.
each time an object is allocated: -Xincgc.
Finalizers
When the GC detects that an object is otherwise unreachable (e.g. D and E two slides previous) then it can run a finalizer method on it. These are ordinary methods that override a default version defined on java.lang.Object.
The finalizer method can be used for cleaning up eg; closing network connections.
The JVM gives few guarantees about finalizer methods: they will be run at most once and will not be run on an object before it becomes unreachable.
System.runFinalization() will cause the JVM to try to complete any outstanding finalizations.
Reference Objects
The referant is selected at instantiation and can be subsequently obtained using the get() method.
A weak reference object acts as a normal object, except that it requires explicit calls to get(). Once the object becomes unreachable, subsequent calls to get() return null.
A reference queue supports three operations:
poll() attempts to remove a reference object from the queue, returning null if none is available;
remove(x) attempts to remove a reference object, blocking up to x milliseconds; and
remove() attempts to remove a reference object, blocking indefinitely.
A reference can be associated with a reference queue rq at declaration:
Reference ref = new WeakReference(obj,rq);
After clearing reference objects the garbage collector will (possibly some time later) append those associated with reference queues to the appropriate queue.
It is the reference object (ref), not the referent (obj), that is appended to the queue.
This prevents the problem of `resurrected' objects.
There are three kinds of reference object, in decreasing strength they are:
A SoftReference can be cleared by the GC when memory is tight, so long as the referent isn't reachable by ordinary references. Useful for memory-sensitive caches.
A WeakReference can be cleared by the GC once the referant isn't reachable by ordinary or soft references. Useful for hashtables where data can be discarded once no longer in use.
A PhantomReference is enqueued once the referent isn't reachable through ordinary, soft or weak references and once it has been finalized. get() always returns null. Useful to be sub-classed and used with reference queues as a more flexible alternative to finalizers.
Java Native Interface
Useful to access hardware, old libraries or to optimize code. The native side of the code, and objects passed to it, aren''t garbage collected.
1 class HelloWorld {
2 public native void displayHelloWorld();
3
4 static {
5 System.loadLibrary("hello");
6 }
7
8 public static void main(String args[]) {
9 new HelloWorld().displayHelloWorld();
10 }
11 }
Line 2 defines the signature of a native method.
Lines 4-6 are a static initializer, executed by the JVM
when the class is loaded.
Line 9 instantiates the class and calls the native method.
Compile the Java and create the C function signatures:
$ javac HelloWorld.java
$ javah -jni HelloWorld
Creates HelloWorld.class and HelloWorld.h
The native, eg C, side of the code will look something like:
JNIEXPORT void JNICALL Java_ClassName_MethodName
(JNIEnv *env, jobject obj)
{
//Implement Native Method Here
}
The JNIEnv parameter refers to an environment structure containing the function pointers for these operations, eg GetSuperClass.
Class Loaders
Class loaders can be used to dynamically load classes at run time, eg from across a network or classes that have been dynamically generated.
Class loaders are Java objects extending java.lang.ClassLoader.
c.loadClass(name) requests that c loads the named class, returning a java.lang.Class object.
Within the JVM, classes are identified by the pair of their fully-qualified name and the class loader that created them.
Concurrency
Threads
Threads are controlled by the scheduler- they are associated with a thread control block (TCB) which contains the thread state, context information and priority etc.
You can create a thread by sub-classing java.lang.Thread and overriding the run() method- run contains the code that will be executed by the thread. You can then create a new instance of you're subclass and call start() on it, eg;
Thread t1 = new MyThread();
t1.start();
The second way of creating a thread is to define a class that implements the java.lang.Runnable interface. The implementation is slightly more complex, but doesn't take away the ability to sub-class a parent:
class MyCode implements Runnable { public void run() { } }
MyCode mt = new MyCode();
Thread t_a = new Thread(mt);
t_a.start();
Threads can be interrupted with thread.interrupt(),try to change thread with thread.yield(), pause with thread.sleep(). Methods that deal with threads should throw InterruptedException.
The join method on java.lang.Thread causes the currently running thread to wait until the target thread dies. setPriority and getPriority cannot be relied upon to control data access as different JVMs implement thread control differently.
Non-preemptive schedulers (which only switch when the running thread yields, becomes blocked, or exits) are commonly used by the JVM. The OS typically uses preemption.
When a thread reads or writes a field declared volatile it must actually access the memory location in which that field's value is held. This is an alternative to mutexes.
Safety
Invariants are things that must remain true. In consistent object states all invariants are satisfied
Liveness
"Something good eventually happens"
Deadlock--a circular dependency between processes holding resources and processes requiring them. Typically the `resources' are exclusive access to locks.
Livelock--a thread keeps executing instructions but makes no useful progress, e.g. busy-waiting on a condition that will never become true.
Missed wake-up (wake-up waiting)--a thread misses a notification that it should continue with some operation and instead remains blocked.
Starvation--a thread is waiting for some resource but never receives it--e.g. a thread with a very low scheduling priority may never receive the CPU.
Distribution failures--of nodes or network connections in a distributed system.
Shared data
Most field acesses in Java are atomic, however this is not true for long and double types. So you could read the first part, then another thread writes to it, and read a different second half- giving an incorrect value. This is an example of a race condition.
Mutual Exclusion Locks
The JVM associates a separate mutex with each object.
Synchronized
The synchronized keyword can be used in two ways--either applied to a method or applied to a block of code.
Locks are re-entrant, meaning that the thread may call one synchronized method from another.
If a static synchronized method is called then the thread must acquire a lock associated with the class rather than with an individual object.
Eg; synchronized (x) { System.out.println("1"); }
The synchronized region locks the mutex associated with the object to which x refers, performs the println operation, and then releases the lock.
When an exception is thrown in a synchronized block the mutex is released before entering the catch code -to prevent deadlock, but you have to be careful you don't access sensitive data in the catch code.
See http://www.cs.duke.edu/~chase/cps210-archive/slides/sync6.pdf for more on mutexes.
Deadlock
Suppose that a and b refer to two different shared objects,
| Thread P
synchronized (a) synchronized (b) { ... } |
Thread Q
synchronized (b) synchronized (a) { ... } |
If P locks both a and b then it can complete its operation and release both locks, thereby allowing Q to acquire them.
Similarly, Q might acquire both locks, then release them and thus allow P to continue.
But, if P locks a and Q locks b then neither thread can continue: they are each deadlocked waiting for the resources that the other has.
If all of the following conditions are true then deadlock exists:
1. A resource request can be refused--e.g. a thread cannot acquire a mutual-exclusion lock because it is already held by another thread.
2. Resources are held while waiting--e.g. while a thread blocks waiting for a lock it does not have to release any others that it holds.
3. No pre-emption of resources is permitted--e.g. once a thread acquires a lock then it is up to that thread to choose when to release it, it cannot be taken away from the thread.
4. Circular wait--a cycle of threads exists such that each holds a lock requested by the next process in the cycle, and that request has been refused.
In the case of mutual exclusion locks in Java, 1-3 are always true (they are static properties of the language), and so the existence of a circular wait leads to deadlock.
 |
In the following diagram, a is held by thread P and P is requesting object b:
Deadlock Detection
You can avoid deadlock by working out all the resources that every process could possibly want, then if there are no overlaps then the execution is safe. However, this is slow and there may be no safe states.
You can also use schemes that allow more concurrency, eg multiple reader single writer, or make processes acquire all resources at one time rather than waiting with held resources or pre-emption can be used.
Alternatively you can combine locks so just one lock is used for many/all resources, or enforce a locking order.
Another problem is that a low priority process can get stuck holding a resource that a high priority task requires. The solution is to boost the holder of every locks priority to that of the greatest priority thread requiring the object.
Condition Variables
In general, condition variables support cv.CVWait(m) which causes the current thread to atomically release a lock on mutex m and to blox itself on condition variable cv, reacquiring the lock on m before it completes; and a cv.CVNotify(m) operation that wakes up threads blocked on cv.
Eg;
public synchronized int removeValue() {
while (!full) cv.CVWait(this);
full = false;
cv.CVNotify();
return value;
}
Internally each condvar has private fields that hold a queue of threads that are waiting on the condition variable and an additional mutex cvLock that is used to give the atomicity required by CVWait().
cv.CVWait(m) proceeds by:
1 Acquire mutex cv.cvLock
2 Add the current thread to cv.queue
3 Release mutex m
4 Release mutex cv.cvLock
5 Suspend current thread
6 Re-acquire mutex m
cv.CVNotify() proceeds by:
1 Acquire mutex cv.cvLock
2 Remove one thread from cv.queue
3 Resume that thread
4 Release mutex cv.cvLock
However, Java doesn't provide individual condition variables in this way. Instead, each object o has an associated condition variable which is accessed by:
o.wait() is the equivalent of cv.CVWait(o) on the condition variable associated with o.
o.notify() unblocks exactly one thread (if any are any waiting)
o.notifyAll() unblocks all waiting threads.
Eg;
public synchronized int removeValue()
throws InterruptedException
{
while (!full) wait();
full = false;
notifyAll();
return value;
}
With notifyAll() the programmer must ensure that every thread blocked on the condition variable can continue safely.
notify() selects arbitrarily between the waiting threads: the programmer must therefore be sure that the exact choice does not matter.
The suspend() and resume() methods defined on java.lang.Thread allow one thread to temporarily stop and start the execution of another (or to suspend itself), however they are depreceated and shouldnt be used as they can lead to deadlocks.
Multiple Reader, Single Writer example
class MRSWImpl1 implements MRSW {
private int numReaders = 0;
private int numWriters = 0;
//A reader must wait until numWriters is zero. A writer must wait until both fields are zero.
synchronized void enterReader()
throws InterruptedException
{
while (numWriters > 0) wait();
numReaders++;
}
synchronized void enterWriter()
throws InterruptedException
{
while ((numWriters > 0) ||
(numReaders > 0)) wait();
numWriters++;
}
synchronized void exitReader() {
numReaders--;
notifyAll();
}
synchronized void exitWriter() {
numWriters--;
notifyAll();
}
}
Advantages:
Simple design: Create a class containing fields, write entry protocols and write exit protocols.
Disadvantages:
notifyAll() is safe but inefficient.
First Come First Server example
class FCFSImpl implements CCInterface {
private int currentTurn = 0;
private int nextTicket = 0;
//Threads take a ticket and wait until it becomes their turn:
synchronized void enter()
throws InterruptedException
{
int myTicket = nextTicket++;
while (currentTurn < myTicket)
wait();
}
synchronized void exit() {
currentTurn++;
notifyAll();
}
}
Advantages:
Simple
Disadvantages:
If a thread is interrupted during wait() then its ticket is lost.
Compare and Swap (CAS)
The compare-and-swap instruction is a special instruction that atomically compares the contents of a memory location to a given value and, if they are the same, modifies the contents of that memory location to a given new value.
class Mutex {
int lockField = 0;
void lock() {
while (CAS(&lockfield,0,1) != 0) {
/* someone else has the lock */
}
}
void unlock() {
lockField = 0;
}
}
The problem with this is that the lock operation uses CPU time whilst waiting.
Semaphores
In Pseudocode:
class CountingSemaphore {
CountingSemaphore (int x) {
...
}
native void P();
native void V();
}
P (sometimes called wait) decrements the value and then blocks if the result is less than
zero. V (sometimes called signal) increments the value and then, if the result is zero or
less, selects a blocked thread and unblocks it. Using semaphores directly is intricate--the
programmer must ensure P() / V() are paired correctly.
The mutex is considered unlocked when the value of the counting semaphore is 1 (it is
initialized unlocked) and is locked when the value is 0 or less.
Event Counts and Primitives
An event count is represented by an integer, initilialized to 0, supporting the atomic
operations:
● advance() - Increment by one, return value
● read() - Return current value
● await(i) - Wait until value is greater or equal to i
A sequencer is represented by an integer, initialised to 0, supporting
● ticket() - Increment value by one, return old value
Mutual exclusion is simple: A thread takes a ticket entering a critical region and invokes
await() to receive its turn.
The values returned by await() can be used directly in implementing a single-producer
single-consumer N-slot buer: they give the modulo-N indices to read/write.
Monitors
Monitors are abstract data types, and so have the advantages associated with oop.
if busy wait(free)
busy=true;
// do stuff
busy=false;
notify(free);
-Busy is a boolean, free is a condition variable
Active Objects
Active objects have a dedicated thread that performs operations.; using conditional
ACCEPT statements.
Threads Communicating between different Machines and Address Spaces may have different low level data representations and different file-name locations.
The sender needs to agree marshalling and the receiver marshalling.
Distributed Systems
Problems include different machine performances, communication delay, failure and
different clocks.
Naming
A directory service can be used to look up eg "the closest server providing xyz". Unique
ID's can be simply assigned as successive integers- simply but centralized and can run
out of UID's. Hierarchical namespaces are generally better for allow local allocation.
A pure name, eg 113, contains no information about the object.
An impure name, eg mrf34@cam.ac.uk gives information about the object.
A namespace is a collection of names recognised by a name service. A naming domain is
a section of a namespace operated under a single administrative authority.
Namespaces can be replicated for availability, distributed and allow caching.
Using a name service at run-time to resolve names, rather than embedding addresses
directly in a program is considered good practice.
Security
Use a security manager class (java.lang.SecurityManager) to limit what the JVM is
able to do.
● e.g. limiting the IP addresses to which it can connect or whether it is permitted to
write to your files.
● If using network sockets directly, then make the program robust to unexpected
input.
Eg;
checkPermission(
new RuntimePermission(
"loadLibrary."+lib));
UDP
UDP sockets provide unreliable datagram-based communication that is subject to:
● Loss: datagrams that are sent might never be received.
● Duplication: the same datagram might be received several times.
● Re-ordering: datagrams are forwarded separately within the network and might
arrive out of order.
With UDP you have to re-invent the wheel, including flow & congestion control.
marshalling, loss detection.
What is provided:
● A checksum is used to guard against corruption (corrupt data is discarded by the
protocol implementation and the application perceives it as packet loss).
● The framing within datagrams is preserved|a UDP datagram might be fragmented
into separate packets within the network but these are reassembled by the receiver.
Communication is between an ip and a port number.
You can use multicast to broadcast to an entire group.
In Java
UDP sockets are represented by instances of java.net.DatagramSocket.
Datagrams are represented in Java as instances of java.net.DatagramPacket eg;
DatagramPacket(byte buf[], int length, InetAddress address, int port)
MulticastSocket defines a UDP socket capable of receiving multicast packets.
Example
import java.net.*;
public class Send {
public static void main(String args[]) {
try {
DatagramSocket s = new DatagramSocket();
byte[] b = new byte[1024];
int i;
for (i=0;i<args.length-2;++i)
b[i] = Byte.parseByte(args[2+i]);
DatagramPacket p = new DatagramPacket (
b, i,
InetAddress.getByName(args[0]),
Integer.parseInt(args[1]));
s.send(p);
} catch (Exception e) {
System.out.println("Caught " + e);
}}}
TCP
TCP provides a reliable bi-directional connection-based byte-stream with flow control and
congestion control.
● Unlike UDP framing must be provided explicitly.
● Marshalling must still be done explicitly|but serialization may help here.
● Communication is always one-to-one.
● Used for HTTP.
In Java
java.net.Socket represents a connection over which data can be sent and received.
java.net.ServerSocket represents a socket awaiting incoming connections. ServerSocket
provides an accept() operation that blocks the caller until an incoming connection is
received (or the wait is interrupted).
Example
import java.net.*;
import java.io.*;
public class TCPSend {
public static void main(String args[]) {
try {
Socket s = new Socket (
InetAddress.getByName(args[0]),
Integer.parseInt(args[1]));
OutputStream os = s.getOutputStream();
while (true) {
int i = System.in.read();
os.write(i);
}
} catch (Exception e) {
System.out.println("Caught " + e);
}}}
RMI
● Similar code to local calls
● Uses TCP and UDP, so is simple but doesn't provide much functionality
● The provider and user of the network service agree on how to access data using
interfaces
● It is better to use a name service at run time than embedding addressees directly
into a program
Java RMI is rather unusual in using ordinary language facilities to dene remote interfaces.
Usually a separate interface denition language (IDL) is used.
How it works
A server registers a reference to a remote object with the registry (a basic name service)
and deposits associated .class files in a shared location, the RMI codebase.
2. A client queries the registry to obtain a reference to a remote object.
3. If they are not directly available, the client obtains the .class files needed to access the
remote object.
4. The client makes an RMI call to the remote object.
The registry acts as a name service, with names being of the form
rmi://linux2.pwf.cl.cam.ac.uk/jkf21/example-1.2
Parameters and results are generally passed by making
deep copies when passed or returned over RMI.
Remote objects are passed by reference and so both caller and callee will interact with the
same remote object if a reference to it is passed or returned.
Note that Java only supports remote method invocation|changes to fields must be made
use get/set methods.
Implementations
1 package remifc;
2
3 import java.rmi.*;
4
5 public interface FishFinder extends Remote
6 {
7 public static final String NAME
8 = "rmi://magic.voidstar.org.uk/jkf/fishfinder";
9
10 public FishLocation
11 getFish(FishLocation me)
12 throws RemoteException;
13 }
All RMI invocations are made across remote interfaces extending java.rmi.Remote. All
remote methods must throw RemoteException.
Instead of defining a separate IDL and per-language bindings, the Microsoft .NET platform
denes a common language subset and programming conventions for making denitions
that conform to it.
Transactions
We say that a transaction commits atomically (if it completes successfully) or it aborts (if it
fails for some reason). Aborted transactions leave the state wholly unchanged.
In more detail we would like committed transactions to satisfy four ACID properties:
● Atomicity: Either all of the tasks of a transaction are performed or none of them are. The transfer of funds can be completed or it can fail for a multitude of reasons, but atomicity guarantees that one account won't be debited if the other is not credited as well. It must be ensured that no partial transactions are performed (atomicity) and also that apparently-committed transactions aren't lost (durability)
● Consistency: Invariants must be preserved across accounts, eg; totals across
accounts. If an integrity constraint states that all accounts must have a positive balance, then any transaction violating this rule will be aborted.
● Isolation: refers to the ability of the application to make operations in a transaction
appear isolated from all other operations. Isolation means the transaction history is
serializable. Eg. another transaction shouldn't read the source and destination amounts midtransfer and then commit.
● Durability: refers to the guarantee that once the user has been notified of success, the transaction will persist, and not be undone. This means it will survive system failure, and that the system has checked the integrity constraints and won't need to abort the transaction. Typically, all transactions are written into a log that can be played back to recreate the system to its state right before the failure. A transaction can only be deemed committed after it is safely in the log.
Eg; If there was a system failure and something was undone the transaction would
fail durability.
These histories show non-serializable executions in which one read sees an old value and
the other sees a new value:
In general, "cycles" are caused by three kinds of problem:
● Lost updates (e.g. by another transaction overwriting them before they are
committed)
● Dirty reads (e.g. of updates before they are committed)
● Unrepeatable reads (e.g. before an update by another transaction overwrites it)
A concurrent execution is serializable if there is some serial execution of the same
transactions that gives the same result|the programmer cannot distinguish between
parallel execution and the simple one-at-a-time scheme.
Strict isolation: actually ensure that transactions are isolated during their execution|prohibit all three problems.
● Non-strict isolation: ensure that a transaction was isolated before it's allowed to
commit.
● Non-strict isolation may permit more concurrency but can lead to delays on commit
(e.g. a transaction that performed a dirty read cannot commit until the writer has)
and cascading aborts (if the writer actually aborts).
Two Phase Locking 2PL
In two-phase locking (2PL) each transaction is divided into:
a phase of acquiring locks; and a phase of releasing locks.
1 transaction {
2 if (server.getBalance(src) >= amount) {
3 server.credit(dest, amount);
4 server.debit (src, amount);
5 return true;
6 } else
7 return false;
8 }
Could require explicit invocations by the programmer, e.g.
● expose lock() and unlock() operations on the server:
● acquire a read lock on src before 2, release if the else clause is taken;
● upgrade to a write lock on src before 3;
● acquire a write lock on dest before 4;
● release the lock on src any time after acquiring both locks; and
● release the lock on dest after 4.
Some problems can be addressed by Strict 2PL, in which all locks are held until commit/abort:
transactions never see partial updates made by others. Strict 2PL prevents transactions reading
uncommitted data, overwriting uncommitted data, and unrepeatable reads. Thus, it prevents
cascading aborts, since exclusive locks (for write privileges) must be held until a transaction
commits.
Strict 2PL has two rules:
1. If a transaction T wants to read/write an object, it must request a shared/exclusive lock on the object.
2. All exclusive locks held by transaction T are released when T commits (and not before).
The rules for non-strict 2PL are similar to those of Strict 2PL:
1. If a transaction T wants to read/write an object, it must request a shared/exclusive lock on the object.
2. A transaction cannot request additional locks on any object once it releases any lock, and it can release locks at any time (not only at commit time as in Strict 2PL).
Advantages:
● Ensures serializable execution if implemented correctly.
● Allows other transactions to access objects as soon as they have been unlocked increases concurrency.
Disadvantages:
● Complexity of programming
● Would be nice to provide startTransaction and endTransaction rather than individual lock operations.
● Risk of deadlock.
● If Tb locks an object just released by Ta then isolation requires that:
- Tb cannot commit until Ta has done so; and
-Tb must abort if Ta does (a cascading abort).
Time Stamp Ordering
Each transaction has a timestamp, eg. of its start time, which are subject to a total ordering. Every object in the database has a read timestamp, which is updated whenever the object's data is read, and a write timestamp, which is updated whenever the object's data is changed.
● The ordering between the timestamps is used to give a serializable order for the transactions.
● Transactions must access objects in the order of their timestamps
If a transaction wants to read an object:
● but the transaction started before the object's write timestamp it means that something changed the object's data after the transaction started. In this case, the transaction is cancelled and must be restarted.
● and the transaction started after the object's write timestamp, it means that it is safe to read the
● object. In this case, if the transaction timestamp is after the object's read timestamp, it is set to the transaction timestamp. If a transaction wants to write to an object,
● but the transaction started before the object's read timestamp it means that something has had a look at the object, and we assume it took a copy of the object's data. So we can't write to the object as that would make any copied data invalid so the transaction is aborted and must be restarted.
● and the transaction started before the object's write timestamp it means that something has changed the object since we started our transaction. In this case we simply cancel our transaction and continue as normal; it does not have to be restarted.
● otherwise, the transaction writes to the object, and the object's write timestamp is set to the transaction's timestamp.
Advantages:
● The decision of whether to admit a particular operation is based on information local to the object
● Simple to implement, e.g. by interposing checks on each invocation at the server (contrast with non-strict 2PL).
● Avoiding locking might increase concurrency.
● Deadlock is not possible ( as there are no locks)
Disadvantages:
● Needs a roll-back mechanism.
● Cascading aborts are possible
Eg; if T1,2 had updated A then it would need to be undone and T2 would have to abort because it might have been influenced by T1. You could delay T2,2 until T1 either commits or aborts (stilln avoiding deadlock)....
● -Serializable executions might be rejected if they do not agree with the transactions' timestamps. (e.g. executing T2 in its entirety, then T1).
● Generally: the low overheads and simplicity make TSO good when conflicts are rare.
Optimistic Concurrency Control
OCC is an optimistic schemes assume transactions rarely conflict. Rather than ensuring isolation during execution a transaction proceeds directly and serializability is checked at commit-time.
Transactions use shadow copies of each object it uses (made on first access) so changes remain local/isolated from other transactions.
There are three phases in an OCC transaction:
1 Read
A transaction proceeds by taking shadow copies of each object it uses (when it accesses it
for the first time). It works on these shadows so changes remain local--isolated from other
transactions.
2 Validation
Validation is required to show that the shadows were consistent and that no other
transaction has updated the object in the meantime in a way that conflicts.
If the validation returns ok then the updates are committed to their permanent objects, if
not then the transaction is aborted and retried. Until commit, updates are made locally.
Validation is the complex part of OCC, one way is giving transactions timestamps. During
validation there is a check to see if transactions are in a correct order; if they are then the
transactions cotinue, otherwise the transaction is aborted.
3 Write
If there is no possibility of conflict then the transaction commits.
Persistent Storage- Logging
● Write details of the proposed update to a write-ahead log|e.g. in a simple case
giving the old and new values of the data, or giving a list of smaller updates as a set
of (address,old,new) tuples.
● Proceed through the log making the updates. More generally we can record details
of multiple transactions in the log by associating each with a transaction ID.
Complete records, held in an append-only log, are of the form:
After a transaction has aborted or become deadlocked:
If deadlocked is detected using a deadlock detection algorithm then the transaction can be
aborted and restarted.
Once a transaction has been aborted an algorithm like the following can be used:
The recovery manager keeps UNDO (initialized to set of transactions active at the last
checkpoint) and REDO (initially empty). Search forwards from the (most recent)
checkpoint record:
· Add transactions that start to the UNDO list.
· Move transactions that commit from the UNDO list to the REDO list.
Then work backwards through the log from the end to the checkpoint record:
· UNDOing the effects of transactions on the UNDO list.
Then work forwards through the log from the checkpoint record:
· REDOing the effects of transactions in the REDO list.
Generics
http://java.sun.com/j2se/1.5/pdf/generics-tutorial.pdf
The cast to Integer in this code snippet is typical of Java code pre-1.5, and is annoying.
The programmer knows that the list contains Integers because (s)he put them there. The
type system is getting in the way (and adding run-time overhead).
List listOfInts = new LinkedList();
listOfInts.add(new Integer(42));
Integer i = (Integer) listOfInts.iterator().next();
● The problem is that the compiler can only guarantee that the iterator's next item will be an
instance of java.lang.Object so the cast is needed to perform a run-time check on the type
of the object returned by next().
● Generics allow us to encode sufficient extra information in the source code that the
compiler can relax the requirement for the programmer to cast to the subtype.
With generics:
List<Integer> gil = new LinkedList<Integer> ();
gil.add(new Integer(42));
Integer i = gil.iterator().next(); // whohoo!
How do we write parametrically polymorphic definitions?
public interface List<T> {
void add(T item);
Iterator<T> iterator();
}
public interface Iterator<S> {
S next();
boolean hasNext();
}
We can use T and S as if they were the names of declared types.
Relations
List<String> ls = new ArrayList<String>();
List<Object> lo = ls; // error!
This gives a compile-time error.
In general, List<A> is not a supertype of List<B> (and List<B> is not a subtype of
List<A>).
Wildcards
Because Collection<Object> is not the superclass of other Collections, we cannot write a
method that is able to operate on a collection of \anythings". The type of the argument
supplied to the method would not match that declared type of the parameter.
Instead, we can use wildcards:
void printThemAll(Collection<?> c) {
for (Object e : c) System.out.println(e);
}
The solution to the problem of not being able to insert into collections of unknowns is to
use generic methods.
