Question

Write a program in C++ to implement Lamport’s logical clocks. Your program should take as input a description of several process schedules (i.e., lists of send, receive or print operations). The output of your program will be a linearization of these events in the order actually performed, annotated with Lamport clock values. The input of the program will be a collection of processes, each with a list of operations to perform. The processes are named p1...pn for some n (you may assume that n is at most 9) The format of a process is: begin process p1 operation … operation end process where each line contains a basic operation. The possible basic operations are: ● send pN msg (that is, send message msg to process pN) ● recv pN msg (that is, receive message msg from process pN) ● print msg (that is, print message msg to the terminal) where msg is any alphanumeric string. The send operation simply sends a message and the process is free to continue executing the next operation. The recv operation blocks and waits to hear message msg from a given process. (This means that there can be deadlocks if all processes are waiting to receive and there are no messages in transit.). An individual print operation takes place atomically. Messages can be sent and received, and printing can take place, in any order, provided causality is respected: that is, the order of events within a process is preserved, and a message is always sent before it is received. One approach to handle send and recv operations is to maintain a pool of messages including sender, receiver and payload. When a message msg is sent from p1 to p2, we add message m = (p1, msg, p2) to the pool, and when the message is received by p2, m is removed from the pool. Here is a small example illustrating the input format: begin process p1 send p2 m1 print abc print def end process begin process p2 print x1 recv p1 m1 print x2 send p1 m2 print x3 end process p2 Note that the message sent from p2 to p1 is never received, this is fine. The output format is a single log of the events that took place during the simulation run, one per line, including Lamport clock timestamps. The possible events are: ● sent pN msg pM T (that is, pN sent message msg to pM at local time T) ● received pN msg pM T (that is, pN received message msg from pM at local time T) ● printed pN msg T (that is, pN printed message msg to the shared terminal at time T) The following is a valid output: printed p2 x1 1 sent p1 m1 p2 1 received p2 m1 p1 2 printed p1 abc 2 printed p1 def 3 printed p2 x2 3 sent p2 m2 p1 4 printed p2 x3 5 Several other outputs are also possible depending on the order in which events at different processes happen. Your program should report if a deadlock happens. For example if after the occurrence 5 events all processes are deadlock the output show those 5 events along with their clocks and then should print “system deadlocked”.

Answer 1

#ifndef LAMPORT_CLOCK_LAMPORT_CLOCK_H
#define LAMPORT_CLOCK_LAMPORT_CLOCK_H

#include <atomic>

class LamportClock {
public:
    /// Lamport timestamp
    typedef unsigned int LamportTime;

    LamportClock() : time_(0) {}

    /**
     * Get current Lamport timestamp.
     *
     * @return LamportTime value.
     */
    LamportTime get_time() const {
        return time_.load();
    }

    /**
     * Handle local event.
     * Increment timer and return the new value.
     *
     * @return LamportTime value;
     */
    LamportTime local_event() {
        return time_.fetch_add(1);
    }

    /**
     * Handle send event.
     * Increment local time and return the new value.
     *
     * @return LamportTime value;
     */
    LamportTime send_event() {
        return time_.fetch_add(1);
    }

    /**
     * Handle receive event.
     * Receive sender's time and set the local time to the maximum between received and local time plus 1.
     *
     * @param received_time Sender's time.
     * @return LamportTime value;
     */
    LamportTime receive_event(LamportTime received_time) {
        RECEIVE_EVENT:

        auto cur = get_time();

        // If received time is old, do nothing.
        if (received_time < cur) {
            return cur;
        }

        // Ensure that local timer is at least one ahead.
        if (!time_.compare_exchange_strong(cur, received_time + 1)) {
            goto RECEIVE_EVENT;
        }

        return received_time + 1;
    }

private:
    std::atomic<LamportTime> time_;
};

#endif //LAMPORT_CLOCK_LAMPORT_CLOCK_H
//lamport_clock/tests/CMakeLists.txt
project(test)


include(CTest)
enable_testing()

include(DownloadProject.cmake)
download_project(
        PROJ    googletest
        GIT_REPOSITORY  https://github.com/google/googletest.git
        GIT_TAG master
        UPDATE_DISCONNECTED 1
)

add_subdirectory(${googletest_SOURCE_DIR} ${googletest_BINARY_DIR} EXCLUDE_FROM_ALL)

add_executable(runUnitTests gtest.cpp lamport_clock_tests/lamport_clock_tests.cpp)
target_link_libraries(runUnitTests gtest

#include <gtest/gtest.h>
#include "../../include/lamport_clock.h"

TEST(LamportClock_Test, InitWithZero) {
    LamportClock clock;
    ASSERT_EQ(clock.get_time(), 0);
}

TEST(LamportClock_Test, LocalEvent) {
    LamportClock clock;
    clock.local_event();
    ASSERT_EQ(clock.get_time(), 1);
}

TEST(LamportClock_Test, SendEvent) {
    LamportClock clock;
    clock.send_event();
    ASSERT_EQ(clock.get_time(), 1);
}

TEST(LamportClock_Test, ReceiveEvent) {
    LamportClock clock;

    clock.receive_event(3);
    ASSERT_EQ(clock.get_time(), 4);

    clock.receive_event(2);
    ASSERT_EQ(clock.get_time(), 4);
}
lamport_clock/tests/DownloadProject.CMakeLists.cmake.in
cmake_minimum_required(VERSION 2.8.2)

project(${DL_ARGS_PROJ}-download NONE)

include(ExternalProject)
ExternalProject_Add(${DL_ARGS_PROJ}-download
                    ${DL_ARGS_UNPARSED_ARGUMENTS}
                    SOURCE_DIR          "${DL_ARGS_SOURCE_DIR}"
                    BINARY_DIR          "${DL_ARGS_BINARY_DIR}"
                    CONFIGURE_COMMAND   ""
                    BUILD_COMMAND       ""
                    INSTALL_COMMAND     ""
                    TEST_COMMAND        ""
)

# MODULE:   DownloadProject
#
# PROVIDES:
#   download_project( PROJ projectName
#                    [PREFIX prefixDir]
#                    [DOWNLOAD_DIR downloadDir]
#                    [SOURCE_DIR srcDir]
#                    [BINARY_DIR binDir]
#                    [QUIET]
#                    ...
#   )
//lamport_clock/tests/DownloadProject.cmake
#
#       Provides the ability to download and unpack a tarball, zip file, git repository,
#       etc. at configure time (i.e. when the cmake command is run). How the downloaded
#       and unpacked contents are used is up to the caller, but the motivating case is
#       to download source code which can then be included directly in the build with
#       add_subdirectory() after the call to download_project(). Source and build
#       directories are set up with this in mind.
#
#       The PROJ argument is required. The projectName value will be used to construct
#       the following variables upon exit (obviously replace projectName with its actual
#       value):
#
#           projectName_SOURCE_DIR
#           projectName_BINARY_DIR
#
#       The SOURCE_DIR and BINARY_DIR arguments are optional and would not typically
#       need to be provided. They can be specified if you want the downloaded source
#       and build directories to be located in a specific place. The contents of
#       projectName_SOURCE_DIR and projectName_BINARY_DIR will be populated with the
#       locations used whether you provide SOURCE_DIR/BINARY_DIR or not.
#
#       The DOWNLOAD_DIR argument does not normally need to be set. It controls the
#       location of the temporary CMake build used to perform the download.
#
#       The PREFIX argument can be provided to change the base location of the default
#       values of DOWNLOAD_DIR, SOURCE_DIR and BINARY_DIR. If all of those three arguments
#       are provided, then PREFIX will have no effect. The default value for PREFIX is
#       CMAKE_BINARY_DIR.
#
#       The QUIET option can be given if you do not want to show the output associated
#       with downloading the specified project.
#
#       In addition to the above, any other options are passed through unmodified to
#       ExternalProject_Add() to perform the actual download, patch and update steps.
#       The following ExternalProject_Add() options are explicitly prohibited (they
#       are reserved for use by the download_project() command):
#
#           CONFIGURE_COMMAND
#           BUILD_COMMAND
#           INSTALL_COMMAND
#           TEST_COMMAND
#
#       Only those ExternalProject_Add() arguments which relate to downloading, patching
#       and updating of the project sources are intended to be used. Also note that at
#       least one set of download-related arguments are required.
#
#       If using CMake 3.2 or later, the UPDATE_DISCONNECTED option can be used to
#       prevent a check at the remote end for changes every time CMake is run
#       after the first successful download. See the documentation of the ExternalProject
#       module for more information. It is likely you will want to use this option if it
#       is available to you.
#
# EXAMPLE USAGE:
#
#   include(download_project.cmake)
#   download_project(PROJ                googletest
#                    GIT_REPOSITORY      https://github.com/google/googletest.git
#                    GIT_TAG             master
#                    UPDATE_DISCONNECTED 1
#                    QUIET
#   )
#
#   add_subdirectory(${googletest_SOURCE_DIR} ${googletest_BINARY_DIR})
#
#========================================================================================


set(_DownloadProjectDir "${CMAKE_CURRENT_LIST_DIR}")

include(CMakeParseArguments)

function(download_project)

    set(options QUIET)
    set(oneValueArgs
            PROJ
            PREFIX
            DOWNLOAD_DIR
            SOURCE_DIR
            BINARY_DIR
            # Prevent the following from being passed through
            CONFIGURE_COMMAND
            BUILD_COMMAND
            INSTALL_COMMAND
            TEST_COMMAND
            )
    set(multiValueArgs "")

    cmake_parse_arguments(DL_ARGS "${options}" "${oneValueArgs}" "${multiValueArgs}" ${ARGN})

    # Hide output if requested
    if (DL_ARGS_QUIET)
        set(OUTPUT_QUIET "OUTPUT_QUIET")
    else()
        unset(OUTPUT_QUIET)
        message(STATUS "Downloading/updating ${DL_ARGS_PROJ}")
    endif()

    # Set up where we will put our temporary CMakeLists.txt file and also
    # the base point below which the default source and binary dirs will be
    if (NOT DL_ARGS_PREFIX)
        set(DL_ARGS_PREFIX "${CMAKE_BINARY_DIR}")
    endif()
    if (NOT DL_ARGS_DOWNLOAD_DIR)
        set(DL_ARGS_DOWNLOAD_DIR "${DL_ARGS_PREFIX}/${DL_ARGS_PROJ}-download")
    endif()

    # Ensure the caller can know where to find the source and build directories
    if (NOT DL_ARGS_SOURCE_DIR)
        set(DL_ARGS_SOURCE_DIR "${DL_ARGS_PREFIX}/${DL_ARGS_PROJ}-src")
    endif()
    if (NOT DL_ARGS_BINARY_DIR)
        set(DL_ARGS_BINARY_DIR "${DL_ARGS_PREFIX}/${DL_ARGS_PROJ}-build")
    endif()
    set(${DL_ARGS_PROJ}_SOURCE_DIR "${DL_ARGS_SOURCE_DIR}" PARENT_SCOPE)
    set(${DL_ARGS_PROJ}_BINARY_DIR "${DL_ARGS_BINARY_DIR}" PARENT_SCOPE)

    # Create and build a separate CMake project to carry out the download.
    # If we've already previously done these steps, they will not cause
    # anything to be updated, so extra rebuilds of the project won't occur.
    configure_file("${_DownloadProjectDir}/DownloadProject.CMakeLists.cmake.in"
            "${DL_ARGS_DOWNLOAD_DIR}/CMakeLists.txt")
    execute_process(COMMAND ${CMAKE_COMMAND} -G "${CMAKE_GENERATOR}" .
            ${OUTPUT_QUIET}
            WORKING_DIRECTORY "${DL_ARGS_DOWNLOAD_DIR}"
            )
    execute_process(COMMAND ${CMAKE_COMMAND} --build .
            ${OUTPUT_QUIET}
            WORKING_DIRECTORY "${DL_ARGS_DOWNLOAD_DIR}"
            )

endfunction()