changeset 2:8e1f63faa2fd default tip

added Franklin's Algorithm
author suikwasha
date Tue, 23 Oct 2012 16:49:26 +0900
parents d24bcb819032
children
files src/main/java/suikwasha/distributedalgorithm/algorithms/franklin/Franklin.java src/main/java/suikwasha/distributedalgorithm/algorithms/franklin/FranklinAlgorithm.java src/main/java/suikwasha/distributedalgorithm/algorithms/krs/KorachRotemSantoroAlgorithm.java src/main/java/suikwasha/distributedalgorithm/framework/Algorithm.java src/main/java/suikwasha/distributedalgorithm/framework/Port.java src/main/java/suikwasha/distributedalgorithm/link/ReliableLinkBuilder.java src/main/java/suikwasha/distributedalgorithm/machines/SimpleMachineBuilder.java src/main/java/suikwasha/distributedalgorithm/simulator/LoggingMessageLinkBuilder.java src/main/java/suikwasha/distributedalgorithm/util/Commons.java target/classes/META-INF/MANIFEST.MF target/classes/META-INF/maven/suikwasha/distributedalgorithm/pom.properties target/classes/META-INF/maven/suikwasha/distributedalgorithm/pom.xml
diffstat 12 files changed, 158 insertions(+), 52 deletions(-) [+]
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>