diff options
author | Sergey Nazaryev <sergey@nazaryev.ru> | 2016-04-24 08:28:15 +0000 |
---|---|---|
committer | Sergey Nazaryev <sergey@nazaryev.ru> | 2016-04-24 08:28:15 +0000 |
commit | 51aeb1fb630713d6bbb9ac1c403f5068d22b7dc5 (patch) | |
tree | 8bf205900df8d7c9a56adb196b73af27b6da205f | |
parent | 87534aac9928ca4f6f59540b23f5e906424b13f6 (diff) | |
download | pa3-51aeb1fb630713d6bbb9ac1c403f5068d22b7dc5.zip pa3-51aeb1fb630713d6bbb9ac1c403f5068d22b7dc5.tar.gz pa3-51aeb1fb630713d6bbb9ac1c403f5068d22b7dc5.tar.bz2 |
Initial commit for PA2
-rw-r--r-- | .version | 1 | ||||
-rw-r--r-- | Makefile | 19 | ||||
-rw-r--r-- | bank_robbery.c | 20 | ||||
-rw-r--r-- | banking.h | 103 | ||||
-rw-r--r-- | child.c | 2 | ||||
-rw-r--r-- | child.h | 2 | ||||
l---------[-rw-r--r--] | common.h | 18 | ||||
-rw-r--r-- | dist.c | 23 | ||||
-rw-r--r-- | dist.h (renamed from main.h) | 13 | ||||
-rw-r--r-- | ipc.c | 17 | ||||
l---------[-rw-r--r--] | ipc.h | 116 | ||||
-rwxr-xr-x | lib32/libruntime.so | bin | 0 -> 30930 bytes | |||
-rwxr-xr-x | lib64/libruntime.so | bin | 0 -> 32587 bytes | |||
-rw-r--r-- | pa23.c (renamed from main.c) | 55 | ||||
-rw-r--r-- | pa23.h | 12 | ||||
-rw-r--r-- | pa2345.h | 56 | ||||
-rw-r--r-- | parent.c | 5 | ||||
-rw-r--r-- | parent.h | 2 | ||||
-rw-r--r-- | prepare.sh | 4 |
19 files changed, 268 insertions, 200 deletions
diff --git a/.version b/.version new file mode 100644 index 0000000..e673a57 --- /dev/null +++ b/.version @@ -0,0 +1 @@ +38f0c5ce6aa00c87b4fb0155fc3889e64d1ee93d @@ -1,22 +1,13 @@ CFLAGS = -std=c99 -Wall -Wpedantic CC = gcc -all: dist +all: pa2 -dist: main.o parent.o child.o ipc.o - $(CC) -o $@ $^ +pa2: pa23.o parent.o child.o ipc.o dist.o + $(CC) -o $@ $^ -L. -lruntime -main.o: main.c - $(CC) -c -o $@ $< $(CFLAGS) - -parent.o: parent.c - $(CC) -c -o $@ $< $(CFLAGS) - -child.o: child.c - $(CC) -c -o $@ $< $(CFLAGS) - -ipc.o: ipc.c +*.o: *.c $(CC) -c -o $@ $< $(CFLAGS) clean: - rm -f *.o dist + rm -f *.o pa2 diff --git a/bank_robbery.c b/bank_robbery.c new file mode 100644 index 0000000..03bbbbf --- /dev/null +++ b/bank_robbery.c @@ -0,0 +1,20 @@ +/** + * @file bank_robbery.c + * @Author Michael Kosyakov and Evgeniy Ivanov (ifmo.distributedclass@gmail.com) + * @date March, 2014 + * @brief Toy implementation of bank_robbery(), don't do it in real life ;) + * + * Students must not modify this file! + */ + +#include "banking.h" + +void bank_robbery(void * parent_data, local_id max_id) +{ + for (int i = 1; i < max_id; ++i) { + transfer(parent_data, i, i + 1, i); + } + if (max_id > 1) { + transfer(parent_data, max_id, 1, 1); + } +} diff --git a/banking.h b/banking.h new file mode 100644 index 0000000..d4e51b3 --- /dev/null +++ b/banking.h @@ -0,0 +1,103 @@ +/** + * @file banking.h + * @Author Michael Kosyakov and Evgeniy Ivanov (ifmo.distributedclass@gmail.com) + * @date March, 2014 + * @brief Definitions of data structures and functions related to banking + * + * Students must not modify this file! + */ + +#ifndef __IFMO_DISTRIBUTED_CLASS_BANKING__H +#define __IFMO_DISTRIBUTED_CLASS_BANKING__H + +#include "ipc.h" + +typedef int16_t balance_t; + +/** + * 1. "Main process" sends TransferOrder to process with id=s_src. + * 2. s_src decreases its balance by s_amount and sends TransferOrder to s_dst. + * 3. s_dst increases its balance by s_amount. + * 4. s_dst sends ACK to "main process". + */ +typedef struct { + local_id s_src; ///< transfer from process with this ID + local_id s_dst; ///< transfer to process with this ID + balance_t s_amount; ///< $$$ +} __attribute__((packed)) TransferOrder; + +typedef struct { + balance_t s_balance; + timestamp_t s_time; ///< physical time in PA2 or Lamport's scalar + ///< time in PA3 + balance_t s_balance_pending_in; ///< $$$ sent at t <= s_time, but + ///< received at t > s_time. PA3 only, + ///< in other labs must be 0 +} __attribute__((packed)) BalanceState; + +enum { + MAX_T = 255 ///< max possible value of timestamp returned by get_lamport_time() + ///< or get_physical_time() +}; + +/** + * Describes balance state of process with id=s_id at each time t >= 0 + * and t < s_history_len + */ +typedef struct { + local_id s_id; + uint8_t s_history_len; + BalanceState s_history[MAX_T + 1]; ///< Must be used as a buffer, unused + ///< part of array shouldn't be transfered +} __attribute__((packed)) BalanceHistory; + +/** + * Should contain balance histories of all processes in the distributed system + * except parrent process. + */ +typedef struct { + uint8_t s_history_len; ///< should be equal to the number of children + BalanceHistory s_history[MAX_PROCESS_ID + 1]; +} AllHistory; + +//------------------------------------------------------------------------------ +// Functions below must be implemented by students +//------------------------------------------------------------------------------ + +/** Transfer amount from src to dst. + * + * @param parent_data Any data structure implemented by students to perform I/O + */ +void transfer(void * parent_data, local_id src, local_id dst, balance_t amount); + +//------------------------------------------------------------------------------ +// Functions below are implemented by lector, test implementations are +// provided to students for testing purposes +//------------------------------------------------------------------------------ + +/** Perform a number of transfers between various children with ids [1;max_id] + * + * @param parent_data Any data structure implemented by students to perform I/O, + * will be passed to transfer() + * @param max_id max id of existing process, so that (max_id + 1) is the total + * number of processes + */ +void bank_robbery(void * parent_data, local_id max_id); + +/** + * Returs the value of Lamport's clock. + */ +timestamp_t get_lamport_time(); + +/** Returns physical time. + * + * Emulates physical clock (for each process). + */ +timestamp_t get_physical_time(); + +/** Pretty print for BalanceHistories. + * + */ +void print_history(const AllHistory * history); + +#endif // __IFMO_DISTRIBUTED_CLASS_BANKING__H @@ -1,7 +1,7 @@ #include <stdint.h> #include <string.h> -#include "main.h" +#include "dist.h" #include "ipc.h" #include "pa1.h" @@ -3,7 +3,7 @@ #include <stdint.h> -#include "main.h" +#include "dist.h" void child_workflow( dist_info_t *info, uint8_t id ); @@ -1,17 +1 @@ -/** - * @file common.h - * @Author Michael Kosyakov and Evgeniy Ivanov (ifmo.distributedclass@gmail.com) - * @date March, 2014 - * @brief Common definitions and constants for for programming assignments - * - * Students must not modify this file! - */ - -#ifndef __IFMO_DISTRIBUTED_CLASS_COMMON__H -#define __IFMO_DISTRIBUTED_CLASS_COMMON__H - -// Not extern for simplicity only -static const char * const events_log = "events.log"; -static const char * const pipes_log = "pipes.log"; - -#endif // __IFMO_DISTRIBUTED_CLASS_COMMON__H +../common/common.h
\ No newline at end of file @@ -0,0 +1,23 @@ +#include "dist.h" + +void close_redundant_pipes( dist_info_t *info, uint8_t id ) { + uint8_t i, j; + for(i = 0; i < info->proccnt; i++) { + uint8_t base = i * (info->proccnt-1); // base of block of pipes for this process + + if( i == id ) { + for(j = 0; j < info->proccnt - 1; j++) + close( info->pipes[base + j][0] ); // close only read descriptor of ( ID -> Y ) + } else { + uint8_t idx = ( id > i ? id - 1: id ); // index number in block of pipes for ( X -> ID ) + for(j = 0; j < info->proccnt - 1; j++) { + if( j == idx ) { + close( info->pipes[base + j][1] ); // close only write descriptor of ( X -> ID ) + } else { + close( info->pipes[base + j][0] ); // close read descriptor of ( X -> Y, where Y != ID ) + close( info->pipes[base + j][1] ); // close write descriptor of ( X -> Y, where Y != ID ) + } + } + } + } +} @@ -1,13 +1,8 @@ -#ifndef __IFMO_DISTRIBUTED_CLASS_MAIN__H -#define __IFMO_DISTRIBUTED_CLASS_MAIN__H +#ifndef __IFMO_DISTRIBUTED_CLASS_DIST__H +#define __IFMO_DISTRIBUTED_CLASS_DIST__H -#include <stdio.h> -#include <stdint.h> -#include <sys/types.h> -#include <unistd.h> +#include "pa23.h" -#define MAX_X ( 10 ) -#define MAX_PROCCNT ( MAX_X + 1 ) #define MAX_PIPES ( MAX_PROCCNT ) * ( MAX_PROCCNT - 1 ) typedef struct { @@ -27,4 +22,4 @@ typedef struct { void close_redundant_pipes( dist_info_t *info, uint8_t id ); -#endif // __IFMO_DISTRIBUTED_CLASS_MAIN__H +#endif @@ -1,10 +1,11 @@ #define _DEFAULT_SOURCE #include <stdint.h> +#include <stdlib.h> #include <unistd.h> #include <string.h> #include "ipc.h" -#include "main.h" +#include "dist.h" int send(void * self, local_id dst, const Message * msg) { if( self == NULL ) @@ -94,7 +95,7 @@ int receive_any(void * self, Message * msg) { return 1; uint8_t i, j = 0; - int descriptors[MAX_PROCCNT - 1]; + int *descriptors = (int *)malloc( sizeof(int) * (me->dist_info->proccnt - 1) ); for(i = 0; i < me->dist_info->proccnt; i++) { // don't see at pipes as ( ID -> Y ) if( me->id == i ) @@ -116,19 +117,13 @@ int receive_any(void * self, Message * msg) { for( i = 0; i < j; i++ ) { if( ( size = read( descriptors[i], buf, sizeof( buf ) ) ) > 0 ) { memcpy( msg, buf, sizeof( *msg ) ); - /*switch( msg->s_header.s_type ) { - case STARTED: - fprintf( stderr, "[ID: %d] Message STARTED received\n", me->id ); - break; - - case DONE: - fprintf( stderr, "[ID: %d] Message DONE received\n", me->id ); - break; - }*/ + free( descriptors ); return 0; } } usleep(100000); // sleep 100 ms } + + free( descriptors ); return 1; } @@ -1,115 +1 @@ -/** - * @file ipc.h - * @Author Michael Kosyakov and Evgeniy Ivanov (ifmo.distributedclass@gmail.com) - * @date March, 2014 - * @brief A simple IPC library for programming assignments - * - * Students must not modify this file! - */ - -#ifndef __IFMO_DISTRIBUTED_CLASS_IPC__H -#define __IFMO_DISTRIBUTED_CLASS_IPC__H - -#include <stddef.h> -#include <stdint.h> - -//------------------------------------------------------------------------------ - -typedef int8_t local_id; -typedef int16_t timestamp_t; - -enum { - MESSAGE_MAGIC = 0xAFAF, - MAX_MESSAGE_LEN = 4096, - PARENT_ID = 0, - MAX_PROCESS_ID = 15 -}; - -typedef enum { - STARTED = 0, ///< message with string (doesn't include trailing '\0') - DONE, ///< message with string (doesn't include trailing '\0') - ACK, ///< empty message - STOP, ///< empty message - TRANSFER, ///< message with TransferOrder - BALANCE_HISTORY, ///< message with BalanceHistory - CS_REQUEST, ///< empty message - CS_REPLY, ///< empty message - CS_RELEASE ///< empty message -} MessageType; - -typedef struct { - uint16_t s_magic; ///< magic signature, must be MESSAGE_MAGIC - uint16_t s_payload_len; ///< length of payload - int16_t s_type; ///< type of the message - timestamp_t s_local_time; ///< set by sender, depends on particular PA: - ///< physical time in PA2 or Lamport's scalar - ///< time in PA3 -} __attribute__((packed)) MessageHeader; - -enum { - MAX_PAYLOAD_LEN = MAX_MESSAGE_LEN - sizeof(MessageHeader) -}; - -typedef struct { - MessageHeader s_header; - char s_payload[MAX_PAYLOAD_LEN]; ///< Must be used as a buffer, unused "tail" - ///< shouldn't be transfered -} __attribute__((packed)) Message; - -//------------------------------------------------------------------------------ - -/** Send a message to the process specified by id. - * - * @param self Any data structure implemented by students to perform I/O - * @param dst ID of recepient - * @param msg Message to send - * - * @return 0 on success, any non-zero value on error - */ -int send(void * self, local_id dst, const Message * msg); - -//------------------------------------------------------------------------------ - -/** Send multicast message. - * - * Send msg to all other processes including parrent. - * Should stop on the first error. - * - * @param self Any data structure implemented by students to perform I/O - * @param msg Message to multicast. - * - * @return 0 on success, any non-zero value on error - */ -int send_multicast(void * self, const Message * msg); - -//------------------------------------------------------------------------------ - -/** Receive a message from the process specified by id. - * - * Might block depending on IPC settings. - * - * @param self Any data structure implemented by students to perform I/O - * @param from ID of the process to receive message from - * @param msg Message structure allocated by the caller - * - * @return 0 on success, any non-zero value on error - */ -int receive(void * self, local_id from, Message * msg); - -//------------------------------------------------------------------------------ - -/** Receive a message from any process. - * - * Receive a message from any process, in case of blocking I/O should be used - * with extra care to avoid deadlocks. - * - * @param self Any data structure implemented by students to perform I/O - * @param msg Message structure allocated by the caller - * - * @return 0 on success, any non-zero value on error - */ -int receive_any(void * self, Message * msg); - -//------------------------------------------------------------------------------ - -#endif // __IFMO_DISTRIBUTED_CLASS_IPC__H +../common/ipc.h
\ No newline at end of file diff --git a/lib32/libruntime.so b/lib32/libruntime.so Binary files differnew file mode 100755 index 0000000..8fce4aa --- /dev/null +++ b/lib32/libruntime.so diff --git a/lib64/libruntime.so b/lib64/libruntime.so Binary files differnew file mode 100755 index 0000000..2da3ac8 --- /dev/null +++ b/lib64/libruntime.so @@ -6,42 +6,20 @@ #include <stdlib.h> #include <string.h> -#include "main.h" +#include "pa23.h" + +#include "dist.h" #include "child.h" #include "parent.h" + #include "common.h" +#include "banking.h" static char* app_name; void usage( FILE* output ) { - fprintf(output, "usage: %s -p <x>\n", app_name); - fprintf(output, "`x` must be int between 1 and %d\n", MAX_X); -} - -void close_redundant_pipes( dist_info_t *info, uint8_t id ) { - uint8_t i, j; - for(i = 0; i < info->proccnt; i++) { - uint8_t base = i * (info->proccnt-1); // base of block of pipes for this process - - if( i == id ) { - for(j = 0; j < info->proccnt - 1; j++) { - // fprintf( stderr, "Read descriptor %d closed for id %d\n", info->pipes[base + j][0], id ); - close( info->pipes[base + j][0] ); // close only read descriptor of ( ID -> Y ) - } - } else { - uint8_t idx = ( id > i ? id - 1: id ); // index number in block of pipes for ( X -> ID ) - for(j = 0; j < info->proccnt - 1; j++) { - if( j == idx ) { - close( info->pipes[base + j][1] ); // close only write descriptor of ( X -> ID ) - // fprintf( stderr, "Write descriptor %d of pipe (%d -> %d) closed for id %d\n", info->pipes[base + j][1], i, id, id ); - } else { - // fprintf( stderr, "LOL\n\n\n"); - close( info->pipes[base + j][0] ); // close read descriptor of ( X -> Y, where Y != ID ) - close( info->pipes[base + j][1] ); // close write descriptor of ( X -> Y, where Y != ID ) - } - } - } - } + fprintf(output, "usage: %s -p <X> <BAL1> <BAL2> ... <BALX>\n", app_name); + fprintf(output, "`X` must be int between 1 and %d\n", MAX_X); } int main(int argc, char* argv[]) { @@ -49,7 +27,7 @@ int main(int argc, char* argv[]) { dist_info_t info; app_name = argv[0]; - if( argc != 3 || strcmp( argv[1], "-p") != 0 ) { + if( argc < 3 || strcmp( argv[1], "-p") != 0 ) { usage(stdout); return 1; } @@ -61,6 +39,15 @@ int main(int argc, char* argv[]) { return 1; } + if( argc != (3 + info.x) ) { + usage(stdout); + return 1; + } + + for( i = 1; i <= info.x; i++ ) { + int balance = atoi(argv[3 + i - 1]); + } + info.proccnt = info.x + 1; info.parent_pid = getpid(); info.events_log = fopen( events_log, "w" ); @@ -93,3 +80,11 @@ int main(int argc, char* argv[]) { parent_workflow( &info ); return 0; } + +//int main(int argc, char * argv[]) +//{ +// //bank_robbery(parent_data); +// //print_history(all); +// +// return 0; +//} @@ -0,0 +1,12 @@ +#ifndef __IFMO_DISTRIBUTED_CLASS_MAIN__H +#define __IFMO_DISTRIBUTED_CLASS_MAIN__H + +#include <stdio.h> +#include <stdint.h> +#include <sys/types.h> +#include <unistd.h> + +#define MAX_X ( 10 ) +#define MAX_PROCCNT ( MAX_X + 1 ) + +#endif // __IFMO_DISTRIBUTED_CLASS_MAIN__H diff --git a/pa2345.h b/pa2345.h new file mode 100644 index 0000000..80fdbdd --- /dev/null +++ b/pa2345.h @@ -0,0 +1,56 @@ +/** + * @file pa2345.h + * @Author Michael Kosyakov and Evgeniy Ivanov (ifmo.distributedclass@gmail.com) + * @date March, 2014 + * @brief Constants for programming assignments 2-5 + * + * Students must not modify this file! + */ + +#ifndef __IFMO_DISTRIBUTED_CLASS_PA2345__H +#define __IFMO_DISTRIBUTED_CLASS_PA2345__H + +#include "common.h" +#include "ipc.h" + +/* + * <timestamp> process <local id> (pid <PID>, paranet <PID>) has STARTED with balance $<id> + */ +static const char * const log_started_fmt = + "%d: process %1d (pid %5d, parent %5d) has STARTED with balance $%2d\n"; + +static const char * const log_received_all_started_fmt = + "%d: process %1d received all STARTED messages\n"; + +static const char * const log_done_fmt = + "%d: process %1d has DONE with balance $%2d\n"; + +static const char * const log_transfer_out_fmt = + "%d: process %1d transferred $%2d to process %1d\n"; + +static const char * const log_transfer_in_fmt = + "%d: process %1d received $%2d from process %1d\n"; + +static const char * const log_received_all_done_fmt = + "%d: process %1d received all DONE messages\n"; + +/* Iteration enumerated starting from 1, i.e. + * 1, 2, 3, 4 out of 4. + * <timestamp> process <local id> ... + */ +static const char * const log_loop_operation_fmt = + "process %1d is doing %d iteration out of %d\n"; + +//------------------------------------------------------------------------------ +// Functions below must be implemented by students +//------------------------------------------------------------------------------ + +int request_cs(const void * self); +int release_cs(const void * self); + +//------------------------------------------------------------------------------ +// Functions below are implemented by lector +//------------------------------------------------------------------------------ +void print(const char * s); + +#endif // __IFMO_DISTRIBUTED_CLASS_PA2345__H @@ -2,8 +2,9 @@ #include <sys/wait.h> #include <stdlib.h> -#include "main.h" +#include "dist.h" #include "ipc.h" +#include "banking.h" void parent_workflow( dist_info_t *info ) { Message msg; @@ -29,6 +30,8 @@ void parent_workflow( dist_info_t *info ) { } } } + + //bank_robbery(); // PARENT PHASE 2: Receive all DONE messages for( i = 1; i <= info->x; i++ ) { @@ -1,7 +1,7 @@ #ifndef __IFMO_DISTRIBUTED_CLASS_PARENT__H #define __IFMO_DISTRIBUTED_CLASS_PARENT__H -#include "main.h" +#include "dist.h" void parent_workflow( dist_info_t *info ); diff --git a/prepare.sh b/prepare.sh new file mode 100644 index 0000000..6a15558 --- /dev/null +++ b/prepare.sh @@ -0,0 +1,4 @@ +#!/bin/sh + +LD_LIBRARY_PATH="`pwd`/lib64/:$LD_LIBRARY_PATH" +LIBRARY_PATH="`pwd`/lib64/:$LD_LIBRARY_PATH" |