Mercurial > hg > Members > shoshi > distributedalgorithm
changeset 2:8e1f63faa2fd default tip
added Franklin's Algorithm
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/main/java/suikwasha/distributedalgorithm/algorithms/franklin/Franklin.java Tue Oct 23 16:49:26 2012 +0900 @@ -0,0 +1,33 @@ +package suikwasha.distributedalgorithm.algorithms.franklin; + +import java.util.LinkedList; + +import suikwasha.distributedalgorithm.framework.Algorithm; +import suikwasha.distributedalgorithm.link.ReliableLinkBuilder; +import suikwasha.distributedalgorithm.machines.SimpleMachineBuilder; +import suikwasha.distributedalgorithm.simulator.Simulator; +import suikwasha.distributedalgorithm.simulator.Summary; +import suikwasha.distributedalgorithm.topologies.RingTopologyBuilder; + +public class Franklin +{ + public static void main(String _args[]) throws InterruptedException + { + LinkedList<Algorithm> algoList = new LinkedList<Algorithm>(); + + long num = 0; + + for(num = 0;num < 3;num ++){ + algoList.add(new FranklinAlgorithm(num)); + } + + ReliableLinkBuilder linkBuilder = new ReliableLinkBuilder(); + SimpleMachineBuilder machineBuilder = new SimpleMachineBuilder(); + RingTopologyBuilder ringBuilder = new RingTopologyBuilder(); + + Simulator sim = new Simulator(algoList,linkBuilder,machineBuilder,ringBuilder); + Summary sum = sim.startSimulation(); + sum.print(); + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/main/java/suikwasha/distributedalgorithm/algorithms/franklin/FranklinAlgorithm.java Tue Oct 23 16:49:26 2012 +0900 @@ -0,0 +1,87 @@ +package suikwasha.distributedalgorithm.algorithms.franklin; + +import java.nio.ByteBuffer; +import java.util.Iterator; + +import fj.P2; + +import suikwasha.distributedalgorithm.framework.Algorithm; +import suikwasha.distributedalgorithm.framework.Context; +import suikwasha.distributedalgorithm.framework.Message; +import suikwasha.distributedalgorithm.framework.Port; +import suikwasha.distributedalgorithm.util.Commons; + +public class FranklinAlgorithm implements Algorithm +{ + private final long num; + private long max; + private static final int MESSAGE_SIZE = 9; + + public FranklinAlgorithm(long _num) + { + num = _num; + max = 0; + } + + /* + * message format. + * flag | long value + * 0xFF | 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF + */ + public static ByteBuffer s(boolean _flagMax,long _value) + { + ByteBuffer b = ByteBuffer.allocate(MESSAGE_SIZE); + b.put((_flagMax) ? (byte)1 : (byte)0); + b.putLong(_value); + b.rewind(); + return b; + } + + public void execute(Context _c) throws Exception + { + Iterator<Port> portItr = _c.getPorts().iterator(); + Port left = portItr.next(); + Port right = portItr.next(); + + Message receivedMessage; + + long a,b; + do{ + right.send(new Message(s(false,num))); + left.send(new Message(s(false,num))); + + Message mesA = right.blockingReceive(); + Message mesB = left.blockingReceive(); + + a = mesA.getMessage().getLong(1); + b = mesB.getMessage().getLong(1); + + receivedMessage = (mesA.getMessageChain().getMessageCount() < mesB.getMessageChain().getMessageCount()) ? + mesA : mesB; + + if(num < a || num < b){ + // passive + while(true){ + P2<Message,Port> ret = Commons.RECV(right,left); + Message m = ret._1(); + Port p = (ret._2() == right) ? left : right; + + if(m.getMessage().get() == (byte)1){ + max = m.getMessage().getLong(1); + p.send(m.newMessage(s(true,max))); + + //stop + return; + } + } + } + }while(!(num == a || num == b)); + + max = num; + right.send(receivedMessage.newMessage(s(true,max))); + + //stop + return; + } + +}
--- a/src/main/java/suikwasha/distributedalgorithm/algorithms/krs/KorachRotemSantoroAlgorithm.java Fri Oct 19 23:48:11 2012 +0900 +++ b/src/main/java/suikwasha/distributedalgorithm/algorithms/krs/KorachRotemSantoroAlgorithm.java Tue Oct 23 16:49:26 2012 +0900 @@ -50,14 +50,8 @@ if(message != null){ return P.p(message,p); } - try{ - Thread.sleep(1); - }catch(Exception _e){ - _e.printStackTrace(); - } } } - } public void execute(Context _c)
--- a/src/main/java/suikwasha/distributedalgorithm/framework/Algorithm.java Fri Oct 19 23:48:11 2012 +0900 +++ b/src/main/java/suikwasha/distributedalgorithm/framework/Algorithm.java Tue Oct 23 16:49:26 2012 +0900 @@ -2,5 +2,5 @@ public interface Algorithm { - public void execute(Context _c); + public void execute(Context _c) throws Exception; }
--- a/src/main/java/suikwasha/distributedalgorithm/framework/Port.java Fri Oct 19 23:48:11 2012 +0900 +++ b/src/main/java/suikwasha/distributedalgorithm/framework/Port.java Tue Oct 23 16:49:26 2012 +0900 @@ -6,6 +6,4 @@ public boolean isReady(); public Message blockingReceive() throws InterruptedException; public Message tryReceive(); - - public void register(Selector _s); }
--- a/src/main/java/suikwasha/distributedalgorithm/link/ReliableLinkBuilder.java Fri Oct 19 23:48:11 2012 +0900 +++ b/src/main/java/suikwasha/distributedalgorithm/link/ReliableLinkBuilder.java Tue Oct 23 16:49:26 2012 +0900 @@ -63,5 +63,10 @@ { return in.poll(); } + + public boolean isReady() + { + return !in.isEmpty(); + } } }
--- a/src/main/java/suikwasha/distributedalgorithm/machines/SimpleMachineBuilder.java Fri Oct 19 23:48:11 2012 +0900 +++ b/src/main/java/suikwasha/distributedalgorithm/machines/SimpleMachineBuilder.java Tue Oct 23 16:49:26 2012 +0900 @@ -33,7 +33,11 @@ public void run() { - algo.execute(new ContextImpl(ports)); + try{ + algo.execute(new ContextImpl(ports)); + }catch(Exception _e){ + _e.printStackTrace(); + } } }
--- a/src/main/java/suikwasha/distributedalgorithm/simulator/LoggingMessageLinkBuilder.java Fri Oct 19 23:48:11 2012 +0900 +++ b/src/main/java/suikwasha/distributedalgorithm/simulator/LoggingMessageLinkBuilder.java Tue Oct 23 16:49:26 2012 +0900 @@ -73,5 +73,10 @@ { return port.tryReceive(); } + + public boolean isReady() + { + return port.isReady(); + } } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/main/java/suikwasha/distributedalgorithm/util/Commons.java Tue Oct 23 16:49:26 2012 +0900 @@ -0,0 +1,22 @@ +package suikwasha.distributedalgorithm.util; + +import suikwasha.distributedalgorithm.framework.Message; +import suikwasha.distributedalgorithm.framework.Port; +import fj.P; +import fj.P2; + +public class Commons +{ + public static P2<Message,Port> RECV(Port... ports) + { + while(true){ + for(Port p : ports){ + Message message = p.tryReceive(); + if(message != null){ + return P.p(message,p); + } + } + } + } + +}
--- a/target/classes/META-INF/MANIFEST.MF Fri Oct 19 23:48:11 2012 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,5 +0,0 @@ -Manifest-Version: 1.0 -Built-By: shoshi -Build-Jdk: 1.6.0_35 -Created-By: Maven Integration for Eclipse -
--- a/target/classes/META-INF/maven/suikwasha/distributedalgorithm/pom.properties Fri Oct 19 23:48:11 2012 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,7 +0,0 @@ -#Generated by Maven Integration for Eclipse -#Fri Oct 19 23:47:17 JST 2012 -version=0.0.1-SNAPSHOT -groupId=suikwasha -m2e.projectName=distributedalgorithm -m2e.projectLocation=/Users/shoshi/Documents/old/distributedalgorithm -artifactId=distributedalgorithm
--- a/target/classes/META-INF/maven/suikwasha/distributedalgorithm/pom.xml Fri Oct 19 23:48:11 2012 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,30 +0,0 @@ -<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" - xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd"> - <modelVersion>4.0.0</modelVersion> - - <groupId>suikwasha</groupId> - <artifactId>distributedalgorithm</artifactId> - <version>0.0.1-SNAPSHOT</version> - <packaging>jar</packaging> - - <name>distributedalgorithm</name> - <url>http://maven.apache.org</url> - - <properties> - <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding> - </properties> - - <dependencies> - <dependency> - <groupId>junit</groupId> - <artifactId>junit</artifactId> - <version>3.8.1</version> - <scope>test</scope> - </dependency> - <dependency> - <groupId>org.functionaljava</groupId> - <artifactId>functionaljava</artifactId> - <version>3.0</version> - </dependency> - </dependencies> -</project>