mcs-queue -> ms-queue

This queue is by Michael and Scott; hence, "M&S".

diff --git a/mcs-queue/Makefile b/mcs-queue/Makefile
deleted file mode 100644 (file)
index 0f19830..0000000
--- a/mcs-queue/Makefile
+++ /dev/null
@@ -1,17 +0,0 @@
-include ../benchmarks.mk
-
-TESTNAME = main
-
-HEADERS = main.h my_queue.h
-OBJECTS = main.o my_queue.o args.o
-
-all: $(TESTNAME)
-
-$(TESTNAME): $(HEADERS) $(OBJECTS)
-       $(CC) -o $@ $^ $(CPPFLAGS) $(LDFLAGS)
-
-%.o: %.c
-       $(CC) -c -o $@ $< $(CPPFLAGS)
-
-clean:
-       rm -f $(TESTNAME) *.o

diff --git a/mcs-queue/args.c b/mcs-queue/args.c
deleted file mode 100644 (file)
index 89101e5..0000000
--- a/mcs-queue/args.c
+++ /dev/null
@@ -1,26 +0,0 @@
-#include "main.h"
-
-extern unsigned iterations;
-extern unsigned multi;
-extern unsigned initial_nodes;
-extern unsigned procs;
-extern unsigned repetitions;
-extern unsigned work;
-
-void parse_args(int argc, char **argv)
-{
-       extern char * optarg;
-       int c;
-
-       while ((c = getopt(argc, argv, "i:m:n:p:r:w:")) != EOF)
-               switch(c) {
-                       case 'i':  iterations = atoi(optarg); break;
-                       case 'm':  multi = atoi(optarg);  break;
-                       case 'n':  initial_nodes = atoi(optarg);  break;
-                       case 'p':   procs = atoi(optarg);   break;
-                       case 'r':   repetitions = atoi(optarg);   break;
-                       case 'w':   work = atoi(optarg);   break;
-                       default:
-                                   assert(0);
-               }
-}

diff --git a/mcs-queue/main.c b/mcs-queue/main.c
deleted file mode 100644 (file)
index 015fbd4..0000000
--- a/mcs-queue/main.c
+++ /dev/null
@@ -1,80 +0,0 @@
-#include "main.h"
-#include <stdlib.h>
-
-#define NUM_PROCESSORS                 12
-
-struct tms tim;
-struct tms tim1;
-
-int shmid;
-
-unsigned pid;
-char* name = "";
-unsigned procs = 1;
-unsigned multi = 1;
-unsigned iterations = 1;
-unsigned initial_nodes = 0;
-unsigned repetitions = 1;
-unsigned work = 0;
-private_t private;
-shared_mem_t *smp;
-
-void time_test()
-{
-       unsigned i,j;
-       struct tms time_val;
-       clock_t t1, t2;
-       unsigned val;
-
-       if(pid==0) {
-               init_queue();
-       }
-       init_memory();
-       init_private();
-       for(i=0;i<iterations;i++) {
-               val = private.value;
-               enqueue(val);
-               for(j=0; j<work;) j++;
-               val = dequeue();
-               for(j=0; j<work;) j++;
-               private.value++;
-       }
-}
-
-void main_task()
-{
-       unsigned processor;
-       unsigned i;
-
-       processor = (pid/multi)+1;
-       processor %= NUM_PROCESSORS;
-       for (i=0; i<repetitions; i++) {
-               time_test();
-       }
-}
-
-int user_main(int argc, char **argv)
-{
-       int i, num_threads;
-       thrd_t *t;
-
-       parse_args(argc, argv);
-       name = argv[0];
-       iterations = (iterations + ((procs*multi)>>1))/(procs*multi);
-
-       smp = (shared_mem_t *)calloc(1, sizeof(shared_mem_t));
-       assert(smp);
-
-       num_threads = procs * multi;
-       t = malloc(num_threads * sizeof(thrd_t));
-
-       for (i = 0; i < num_threads; i++)
-               thrd_create(&t[i], main_task, NULL);
-       for (i = 0; i < num_threads; i++)
-               thrd_join(t[i]);
-
-       free(t);
-       free(smp);
-
-       return 0;
-}

diff --git a/mcs-queue/main.h b/mcs-queue/main.h
deleted file mode 100644 (file)
index 7a7d2a7..0000000
--- a/mcs-queue/main.h
+++ /dev/null
@@ -1,11 +0,0 @@
-#include <stdio.h>
-#include <sys/param.h>
-#include <sys/types.h>
-#include <sys/times.h>
-#include <sys/types.h>
-#include <sys/ipc.h>
-#include <sys/shm.h>
-#include <signal.h>
-#include <assert.h>
-#include <threads.h>
-#include "my_queue.h"

diff --git a/mcs-queue/my_queue.c b/mcs-queue/my_queue.c
deleted file mode 100644 (file)
index 1f8a446..0000000
--- a/mcs-queue/my_queue.c
+++ /dev/null
@@ -1,130 +0,0 @@
-#include "main.h"
-
-extern unsigned pid;
-extern unsigned iterations;
-extern unsigned initial_nodes;
-extern private_t private;
-extern shared_mem_t* smp;
-
-void init_private()
-{
-       private.node = 2 + initial_nodes + pid;
-       private.value = 1 + initial_nodes + (pid * iterations);
-
-}
-
-void init_memory()
-{
-}
-
-static unsigned new_node()
-{
-       return private.node;
-}
-
-static void reclaim(unsigned node)
-{
-       private.node = node;
-}
-
-void init_queue()
-{
-       unsigned i;
-
-       /* initialize queue */
-       smp->head.sep.ptr = 1;
-       smp->head.sep.count = 0;
-       smp->tail.sep.ptr = 1;
-       smp->tail.sep.count = 0;
-       smp->nodes[1].next.sep.ptr = NULL;
-       smp->nodes[1].next.sep.count = 0;
-
-       /* initialize avail list */
-       for (i=2; i<MAX_NODES; i++) {
-               smp->nodes[i].next.sep.ptr = i+1;
-               smp->nodes[i].next.sep.count = 0;
-       }
-       smp->nodes[MAX_NODES].next.sep.ptr = NULL;
-       smp->nodes[MAX_NODES].next.sep.count = 0;
-
-       /* initialize queue contents */
-       if (initial_nodes > 0) {
-               for (i=2; i<initial_nodes+2; i++) {
-                       smp->nodes[i].value = i;
-                       smp->nodes[i-1].next.sep.ptr = i;
-                       smp->nodes[i].next.sep.ptr = NULL;
-               }
-               smp->head.sep.ptr = 1;
-               smp->tail.sep.ptr = 1 + initial_nodes;    
-       }
-}
-
-void enqueue(unsigned val)
-{
-       unsigned success;
-       unsigned node;
-       pointer_t tail;
-       pointer_t next;
-
-       node = new_node();
-       smp->nodes[node].value = val;
-       smp->nodes[node].next.sep.ptr = NULL;
-
-       for (success = FALSE; success == FALSE; ) {
-               tail.con = smp->tail.con;
-               next.con = smp->nodes[tail.sep.ptr].next.con;
-               if (tail.con == smp->tail.con) {
-                       if (next.sep.ptr == NULL) {
-                               success = cas(&smp->nodes[tail.sep.ptr].next, 
-                                               next.con,
-                                               MAKE_LONG(node, next.sep.count+1));
-                       }
-                       if (success == FALSE) {
-                               cas(&smp->tail,
-                                               tail.con,
-                                               MAKE_LONG(smp->nodes[tail.sep.ptr].next.sep.ptr,
-                                                       tail.sep.count+1));
-                               thrd_yield();
-                       }
-               }
-       }
-       cas(&smp->tail, 
-                       tail.con,
-                       MAKE_LONG(node, tail.sep.count+1));
-}
-
-unsigned dequeue()
-{
-       unsigned value;
-       unsigned success;
-       pointer_t head;
-       pointer_t tail;
-       pointer_t next;
-
-       for (success = FALSE; success == FALSE; ) {
-               head.con = smp->head.con;
-               tail.con = smp->tail.con;
-               next.con = smp->nodes[head.sep.ptr].next.con;
-               if (smp->head.con == head.con) {
-                       if (head.sep.ptr == tail.sep.ptr) {
-                               if (next.sep.ptr == NULL) {
-                                       return NULL;
-                               }
-                               cas(&smp->tail,
-                                               tail.con,
-                                               MAKE_LONG(next.sep.ptr, tail.sep.count+1));
-                               thrd_yield();
-                       } else {
-                               value = smp->nodes[next.sep.ptr].value;
-                               success = cas(&smp->head,
-                                               head.con,
-                                               MAKE_LONG(next.sep.ptr, head.sep.count+1));
-                               if (success == FALSE) {
-                                       thrd_yield();
-                               }
-                       }
-               }
-       }
-       reclaim(head.sep.ptr);
-       return value;
-}

diff --git a/mcs-queue/my_queue.h b/mcs-queue/my_queue.h
deleted file mode 100644 (file)
index 3e3f435..0000000
--- a/mcs-queue/my_queue.h
+++ /dev/null
@@ -1,43 +0,0 @@
-#include <stdatomic.h>
-
-#define TRUE                           1
-#define FALSE                          0
-
-#define MAX_NODES                      0xff
-#define MAX_SERIAL                     10000
-
-#define MAKE_LONG(lo, hi)              ((hi)<<16)+(lo)
-
-typedef union pointer {
-       struct {
-               volatile unsigned short count;
-               volatile unsigned short ptr;
-       } sep;
-       atomic_ulong con;
-} pointer_t;
-
-typedef struct node {
-       unsigned value;
-       pointer_t next;
-       unsigned foo[30];
-} node_t;
-
-typedef struct private {
-       unsigned node;
-       unsigned value;
-       unsigned serial[MAX_SERIAL];
-} private_t;
-
-typedef struct shared_mem {
-       pointer_t head;
-       unsigned foo1[31];
-       pointer_t tail;
-       unsigned foo2[31];
-       node_t nodes[MAX_NODES+1];
-       unsigned serial;
-} shared_mem_t;
-
-void init_private();
-void init_memory();
-void init_queue();
-unsigned dequeue();

diff --git a/ms-queue/Makefile b/ms-queue/Makefile
new file mode 100644 (file)
index 0000000..0f19830
--- /dev/null
+++ b/ms-queue/Makefile
@@ -0,0 +1,17 @@
+include ../benchmarks.mk
+
+TESTNAME = main
+
+HEADERS = main.h my_queue.h
+OBJECTS = main.o my_queue.o args.o
+
+all: $(TESTNAME)
+
+$(TESTNAME): $(HEADERS) $(OBJECTS)
+       $(CC) -o $@ $^ $(CPPFLAGS) $(LDFLAGS)
+
+%.o: %.c
+       $(CC) -c -o $@ $< $(CPPFLAGS)
+
+clean:
+       rm -f $(TESTNAME) *.o

diff --git a/ms-queue/args.c b/ms-queue/args.c
new file mode 100644 (file)
index 0000000..89101e5
--- /dev/null
+++ b/ms-queue/args.c
@@ -0,0 +1,26 @@
+#include "main.h"
+
+extern unsigned iterations;
+extern unsigned multi;
+extern unsigned initial_nodes;
+extern unsigned procs;
+extern unsigned repetitions;
+extern unsigned work;
+
+void parse_args(int argc, char **argv)
+{
+       extern char * optarg;
+       int c;
+
+       while ((c = getopt(argc, argv, "i:m:n:p:r:w:")) != EOF)
+               switch(c) {
+                       case 'i':  iterations = atoi(optarg); break;
+                       case 'm':  multi = atoi(optarg);  break;
+                       case 'n':  initial_nodes = atoi(optarg);  break;
+                       case 'p':   procs = atoi(optarg);   break;
+                       case 'r':   repetitions = atoi(optarg);   break;
+                       case 'w':   work = atoi(optarg);   break;
+                       default:
+                                   assert(0);
+               }
+}

diff --git a/ms-queue/main.c b/ms-queue/main.c
new file mode 100644 (file)
index 0000000..015fbd4
--- /dev/null
+++ b/ms-queue/main.c
@@ -0,0 +1,80 @@
+#include "main.h"
+#include <stdlib.h>
+
+#define NUM_PROCESSORS                 12
+
+struct tms tim;
+struct tms tim1;
+
+int shmid;
+
+unsigned pid;
+char* name = "";
+unsigned procs = 1;
+unsigned multi = 1;
+unsigned iterations = 1;
+unsigned initial_nodes = 0;
+unsigned repetitions = 1;
+unsigned work = 0;
+private_t private;
+shared_mem_t *smp;
+
+void time_test()
+{
+       unsigned i,j;
+       struct tms time_val;
+       clock_t t1, t2;
+       unsigned val;
+
+       if(pid==0) {
+               init_queue();
+       }
+       init_memory();
+       init_private();
+       for(i=0;i<iterations;i++) {
+               val = private.value;
+               enqueue(val);
+               for(j=0; j<work;) j++;
+               val = dequeue();
+               for(j=0; j<work;) j++;
+               private.value++;
+       }
+}
+
+void main_task()
+{
+       unsigned processor;
+       unsigned i;
+
+       processor = (pid/multi)+1;
+       processor %= NUM_PROCESSORS;
+       for (i=0; i<repetitions; i++) {
+               time_test();
+       }
+}
+
+int user_main(int argc, char **argv)
+{
+       int i, num_threads;
+       thrd_t *t;
+
+       parse_args(argc, argv);
+       name = argv[0];
+       iterations = (iterations + ((procs*multi)>>1))/(procs*multi);
+
+       smp = (shared_mem_t *)calloc(1, sizeof(shared_mem_t));
+       assert(smp);
+
+       num_threads = procs * multi;
+       t = malloc(num_threads * sizeof(thrd_t));
+
+       for (i = 0; i < num_threads; i++)
+               thrd_create(&t[i], main_task, NULL);
+       for (i = 0; i < num_threads; i++)
+               thrd_join(t[i]);
+
+       free(t);
+       free(smp);
+
+       return 0;
+}

diff --git a/ms-queue/main.h b/ms-queue/main.h
new file mode 100644 (file)
index 0000000..7a7d2a7
--- /dev/null
+++ b/ms-queue/main.h
@@ -0,0 +1,11 @@
+#include <stdio.h>
+#include <sys/param.h>
+#include <sys/types.h>
+#include <sys/times.h>
+#include <sys/types.h>
+#include <sys/ipc.h>
+#include <sys/shm.h>
+#include <signal.h>
+#include <assert.h>
+#include <threads.h>
+#include "my_queue.h"

diff --git a/ms-queue/my_queue.c b/ms-queue/my_queue.c
new file mode 100644 (file)
index 0000000..1f8a446
--- /dev/null
+++ b/ms-queue/my_queue.c
@@ -0,0 +1,130 @@
+#include "main.h"
+
+extern unsigned pid;
+extern unsigned iterations;
+extern unsigned initial_nodes;
+extern private_t private;
+extern shared_mem_t* smp;
+
+void init_private()
+{
+       private.node = 2 + initial_nodes + pid;
+       private.value = 1 + initial_nodes + (pid * iterations);
+
+}
+
+void init_memory()
+{
+}
+
+static unsigned new_node()
+{
+       return private.node;
+}
+
+static void reclaim(unsigned node)
+{
+       private.node = node;
+}
+
+void init_queue()
+{
+       unsigned i;
+
+       /* initialize queue */
+       smp->head.sep.ptr = 1;
+       smp->head.sep.count = 0;
+       smp->tail.sep.ptr = 1;
+       smp->tail.sep.count = 0;
+       smp->nodes[1].next.sep.ptr = NULL;
+       smp->nodes[1].next.sep.count = 0;
+
+       /* initialize avail list */
+       for (i=2; i<MAX_NODES; i++) {
+               smp->nodes[i].next.sep.ptr = i+1;
+               smp->nodes[i].next.sep.count = 0;
+       }
+       smp->nodes[MAX_NODES].next.sep.ptr = NULL;
+       smp->nodes[MAX_NODES].next.sep.count = 0;
+
+       /* initialize queue contents */
+       if (initial_nodes > 0) {
+               for (i=2; i<initial_nodes+2; i++) {
+                       smp->nodes[i].value = i;
+                       smp->nodes[i-1].next.sep.ptr = i;
+                       smp->nodes[i].next.sep.ptr = NULL;
+               }
+               smp->head.sep.ptr = 1;
+               smp->tail.sep.ptr = 1 + initial_nodes;    
+       }
+}
+
+void enqueue(unsigned val)
+{
+       unsigned success;
+       unsigned node;
+       pointer_t tail;
+       pointer_t next;
+
+       node = new_node();
+       smp->nodes[node].value = val;
+       smp->nodes[node].next.sep.ptr = NULL;
+
+       for (success = FALSE; success == FALSE; ) {
+               tail.con = smp->tail.con;
+               next.con = smp->nodes[tail.sep.ptr].next.con;
+               if (tail.con == smp->tail.con) {
+                       if (next.sep.ptr == NULL) {
+                               success = cas(&smp->nodes[tail.sep.ptr].next, 
+                                               next.con,
+                                               MAKE_LONG(node, next.sep.count+1));
+                       }
+                       if (success == FALSE) {
+                               cas(&smp->tail,
+                                               tail.con,
+                                               MAKE_LONG(smp->nodes[tail.sep.ptr].next.sep.ptr,
+                                                       tail.sep.count+1));
+                               thrd_yield();
+                       }
+               }
+       }
+       cas(&smp->tail, 
+                       tail.con,
+                       MAKE_LONG(node, tail.sep.count+1));
+}
+
+unsigned dequeue()
+{
+       unsigned value;
+       unsigned success;
+       pointer_t head;
+       pointer_t tail;
+       pointer_t next;
+
+       for (success = FALSE; success == FALSE; ) {
+               head.con = smp->head.con;
+               tail.con = smp->tail.con;
+               next.con = smp->nodes[head.sep.ptr].next.con;
+               if (smp->head.con == head.con) {
+                       if (head.sep.ptr == tail.sep.ptr) {
+                               if (next.sep.ptr == NULL) {
+                                       return NULL;
+                               }
+                               cas(&smp->tail,
+                                               tail.con,
+                                               MAKE_LONG(next.sep.ptr, tail.sep.count+1));
+                               thrd_yield();
+                       } else {
+                               value = smp->nodes[next.sep.ptr].value;
+                               success = cas(&smp->head,
+                                               head.con,
+                                               MAKE_LONG(next.sep.ptr, head.sep.count+1));
+                               if (success == FALSE) {
+                                       thrd_yield();
+                               }
+                       }
+               }
+       }
+       reclaim(head.sep.ptr);
+       return value;
+}

diff --git a/ms-queue/my_queue.h b/ms-queue/my_queue.h
new file mode 100644 (file)
index 0000000..3e3f435
--- /dev/null
+++ b/ms-queue/my_queue.h
@@ -0,0 +1,43 @@
+#include <stdatomic.h>
+
+#define TRUE                           1
+#define FALSE                          0
+
+#define MAX_NODES                      0xff
+#define MAX_SERIAL                     10000
+
+#define MAKE_LONG(lo, hi)              ((hi)<<16)+(lo)
+
+typedef union pointer {
+       struct {
+               volatile unsigned short count;
+               volatile unsigned short ptr;
+       } sep;
+       atomic_ulong con;
+} pointer_t;
+
+typedef struct node {
+       unsigned value;
+       pointer_t next;
+       unsigned foo[30];
+} node_t;
+
+typedef struct private {
+       unsigned node;
+       unsigned value;
+       unsigned serial[MAX_SERIAL];
+} private_t;
+
+typedef struct shared_mem {
+       pointer_t head;
+       unsigned foo1[31];
+       pointer_t tail;
+       unsigned foo2[31];
+       node_t nodes[MAX_NODES+1];
+       unsigned serial;
+} shared_mem_t;
+
+void init_private();
+void init_memory();
+void init_queue();
+unsigned dequeue();