FinalExOpSys — Graph Algorithms & Multithreaded Servers

Operating Systems project combining classic graph algorithms with software‑engineering patterns (Strategy/Factory), client–server networking, and multithreading via Leader–Follower (thread pool) and Pipeline (Active Object) models. Includes unit tests, gcov code‑coverage, Valgrind (memcheck/helgrind/callgrind) and optional gprof profiling.

---

Table of contents

• Quick start
• Project layout
• Build targets
• Servers
  • Leader–Follower server (LF)
  • Pipeline server (Active Object)
  • Text protocol
• Algorithms
• Design & Patterns
• Extending the project
• Authors

---

Requirements: Linux/WSL, g++ (C++17), make. For analysis: valgrind, kcachegrind (optional), and gcov.

---

Quick start

make               # build servers (ServerLF, ServerPL) and random algorithm generator (run_algo)
make run_pl        # run pipeline server on port 12345
make run_lf        # run Leader-Follower server on port 12346
nc localhost 12345 # connect as a client

---

Project layout

├── Makefile
├── README.md
├── bin
│   ├── ServerLF
│   ├── ServerPL
│   ├── testLF
│   ├── testPL
│   └── testServers
├── build
│   ├── src
│   │   ├── Graph.o
│   │   ├── algorithms
│   │   │   ├── AlgorithmFactory.o
│   │   │   ├── EulerCircuit.o
│   │   │   ├── MST.o
│   │   │   ├── MaxClique.o
│   │   │   ├── MaxFlow.o
│   │   │   └── SCC.o
│   │   └── servers
│   │       ├── LF
│   │       │   ├── LFHandler.o
│   │       │   └── ServerLF.o
│   │       ├── PL
│   │       │   ├── PLHandler.o
│   │       │   └── ServerPL.o
│   │       └── serverUtils.o
│   └── tests
│       ├── ServerPL_test.o
│       └── runTests.o
├── include
│   ├── Algorithms.hpp
│   ├── Graph.hpp
│   ├── LFUtils.hpp
│   ├── PLUtils.hpp
│   ├── doctest.h
│   └── serverUtils.hpp
├── shortcuts.sh
├── src
│   ├── Graph.cpp
│   ├── RunAlgo.cpp
│   ├── algorithms
│   │   ├── AlgorithmFactory.cpp
│   │   ├── EulerCircuit.cpp
│   │   ├── MST.cpp
│   │   ├── MaxClique.cpp
│   │   ├── MaxFlow.cpp
│   │   └── SCC.cpp
│   └── servers
│       ├── LF
│       │   ├── LFHandler.cpp
│       │   └── ServerLF.cpp
│       ├── PL
│       │   ├── PLHandler.cpp
│       │   └── ServerPL.cpp
│       └── serverUtils.cpp
└── tests
    ├── fail_inject
    │   ├── fail_accept.c
    │   ├── fail_bind.c
    │   ├── fail_listen.c
    │   └── fail_socket.c
    ├── server_tests
    │   ├── log_lf.txt
    │   ├── log_pl.txt
    │   ├── testLF.cpp
    │   ├── testPL.cpp
    │   └── testServers.cpp
    ├── testAlgorithms.cpp
    ├── testGraph.cpp
    └── testRunAlgo.cpp

---

Build Targets

The provided Makefile supports both normal builds and instrumented builds (with gcov coverage). Below is a list of the most useful targets and what they do.

Core builds

• make
  Compiles the servers’ binaries (ServerLF, ServerPL) and the random algorithm generator (run_algo) into ./bin.

• make clean
  Removes all build artifacts, coverage files, and valgrind outputs.

---

Executable runners

• make run_lf
  Builds and runs the Leader–Follower server (./bin/ServerLF).
  By default it listens on port 12346.

• make run_pl
  Builds and runs the Pipeline server (./bin/ServerPL).
  By default it listens on port 12345.

• make run_algo
  Compiles the standalone algorithm runner binary (./bin/run_algo).
  To execute it, run manually:

  ./bin/run_algo <options>

  where:

  • -a <algorithm> → algorithm type (e.g. euler, mst, scc, maxflow, maxclique)
  • -s <seed> → random seed for reproducibility
  • -n <nodes> → number of nodes (if generating a random graph)
  • -m <edges> → number of edges (if generating a random graph)

---

Unit and integration tests

• make test_algo
  Builds and runs algorithm unit tests (testAlgorithms).

• make test_graph
  Builds and runs graph unit tests (testGraph).

• make test_run_algo
  Builds and runs the test harness for the standalone runner (test_run_algo).

• make test_lf
  Builds and runs Leader–Follower server tests (testLF).
  Notes: certain error outputs like

  connect failed: Connection refused
  socket failed: Too many open files
  

  are expected and filtered automatically.

• make test_pl
  Builds and runs Pipeline server tests (testPL).

• make test_servers
  Builds and runs the combined server integration tests (testServers) which exercise both LF and PL servers, in parallel.

---

Coverage builds

These run the corresponding tests, and then run gcov on the relevant sources:

• make gcov_graph → Coverage report for Graph.cpp.
• make gcov_algorithms → Coverage report for all files in src/algorithms/.
• make gcov_serverlf → Coverage report for ServerLF.cpp, LFHandler.cpp, and serverUtils.cpp.
• make gcov_serverpl → Coverage report for ServerPL.cpp, PLHandler.cpp, and serverUtils.cpp.

Coverage reports (.gcov files) are collected into ./coverage_gcov/.

---

Valgrind analysis

• make valgrind
  Runs all tests under Valgrind (--leak-check=full).

• make valgrind_callgraph
  Runs all tests under valgrind --tool=callgrind for performance/call graph analysis.

---

Servers

Two text‑protocol servers expose the algorithms to clients.

Leader–Follower server (LF)

• Binary: ./bin/ServerLF
• Default port: 12346
• Model: thread pool in a Leader–Follower pattern using a shared accept(); a thread becomes leader, accepts a connection, promotes a new leader, and handles the client.
• Signals: SIGINT/SIGTERM trigger a graceful shutdown (shutdown(server_fd, SHUT_RDWR)).

Pipeline server (Active Object)

• Binary: ./bin/ServerPL
• Default port: 12345
• Model: Pipeline based on Active Object stages. Each algorithm runs in its own stage (eulerStage, sccStage, mstStage, cliqueStage, maxFlowStage) and results are serialized through an outputStage.

Text protocol

Both servers speak the same simple, lowercase, line‑based protocol.

Client:  new
Server:  Input mode? [Manual(m)/Random(r)]:

# Manual mode
Client:  m
Server:  Enter number of vertices:
Client:  5
Server:  Is the graph directed? [Yes(y)/No(n)]:
Client:  y
Server:  Number of edges:
Client:  2
Server:  Enter edge (u v w):
Client:  0 1 2
Server:  Enter edge (u v w):
Client:  1 4 3
Server:  Graph:\n...printed adjacency...
Server:  Choose algorithm [Euler(e)/SCC(s)/MST(m)/Max Clique(c)/Max Flow(f)] or type 'new' to restart:
Client:  e
Server:  <algorithm result>\n
# Random mode
Client:  new
Client:  r
Server:  Enter number of vertices:
Client:  10
Server:  Number of edges:
Client:  18
Server:  Seed:
Client:  42
...

• You may type new at any prompt to restart input.
• Empty lines are ignored. Unknown choices yield Invalid input. Try again.

---

Algorithms

Implemented algorithms live under src/algorithms/ and are constructed via the AlgorithmFactory using a string key:

• euler — Euler circuit detection / construction (or a proof it does not exist)
• scc — Strongly Connected Components
• mst — Minimum Spanning Tree weight (for undirected graphs)
• maxclique — Maximum Clique size (and/or set depending on build)
• maxflow — Maximum flow from source 0 to sink n‑1

Implementation details and complexity notes are documented in the source files.

---

Design & Patterns

• Graph — adjacency list with weights; supports directed/undirected creation, random generation (Graph(v, e, seed)), validation and pretty printing.
• Strategy — common Algorithm interface with run(Graph&) -> std::string.
• Factory — AlgorithmFactory::create(name) maps string keys to concrete strategies (EulerCircuit, SCC, MST, MaxFlow, MaxClique).
• Leader–Follower — shared listening socket guarded by mutex/condvar; threads rotate the leader role around accept().
• Active Object / Pipeline — lock‑free client IO at the edge; algorithm work is submitted to dedicated stages and results are funneled through an output stage.
• Signals & Shutdown — SIGPIPE ignored; SIGTERM/SIGINT flip an atomic shutdown_requested and break blocking accept().

---

Extending the project

1. Add a new algorithm under src/algorithms/ implementing the Algorithm interface.
2. Register it in AlgorithmFactory.cpp, e.g., register_("hamilton", []{ return std::make_unique<Hamilton>(); });
3. Expose it to the servers: add a choice key in the prompt and route to the factory name.
4. Add tests in tests/ and, if needed, an e2e scenario in tests/server_tests/.

---

Authors

• Aviv Neeman
• Gal Maymon
• Noa Shalom