peterson_solution.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Peterson's Solution is a classic algorithm used to solve the critical-section problem in concurrent programming. The critical-section problem arises when multiple processes or threads need to access a shared resource (such as shared memory or a shared data structure) concurrently. To prevent data inconsistency and ensure the correctness of the program, mutual exclusion must be enforced, meaning only one process can access the shared resource at a time.\n",
    "\n",
    "Peterson's Solution is based on the idea of using shared variables to coordinate the access to the critical section. It is primarily designed for systems with two processes that need to access a shared resource. The algorithm ensures that only one process is in its critical section at any given time, thus providing mutual exclusion.\n",
    "\n",
    "The algorithm relies on the following shared variables:\n",
    "\n",
    "- `int turn`: A variable that indicates whose turn it is to enter the critical section.\n",
    "- `bool flag[2]`: An array of flags that each process uses to indicate its intention to enter the critical section. `flag[i]` is true if process `i` wants to enter the critical section.\n",
    "\n",
    "The key idea of Peterson's Solution is that before entering the critical section, each process sets its `flag` to true and then sets `turn` to its own process number. Then it enters a loop where it checks if the other process also wants to enter the critical section. If the other process is in the critical section (indicated by its `flag` being true), and it has the turn (indicated by `turn` being equal to the other process number), the current process waits (spins) until it can enter the critical section. If not, it proceeds to enter its critical section.\n",
    "\n",
    "The pseudocode for Peterson's Solution is as follows:\n",
    "\n",
    "``` python\n",
    "# Shared variables\n",
    "int turn = 0\n",
    "bool flag[2] = {false, false}\n",
    "\n",
    "# Process 0\n",
    "flag[0] = true\n",
    "turn = 1\n",
    "while flag[1] and turn == 1:\n",
    "    # Wait\n",
    "# Critical section\n",
    "# Exit section\n",
    "flag[0] = false\n",
    "\n",
    "# Process 1\n",
    "flag[1] = true\n",
    "turn = 0\n",
    "while flag[0] and turn == 0:\n",
    "    # Wait\n",
    "# Critical section\n",
    "# Exit section\n",
    "flag[1] = false\n",
    "```\n",
    "\n",
    "The key property of Peterson's Solution is that it provides mutual exclusion, meaning only one process can be in its critical section at a time. Additionally, the algorithm guarantees progress, ensuring that a process that wants to enter the critical section will eventually do so as long as the other process does not remain indefinitely in its critical section.\n",
    "\n",
    "It's important to note that while Peterson's Solution is a simple and elegant algorithm, it is not suitable for scenarios with more than two processes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import threading\n",
    "import time\n",
    "\n",
    "cs = 0\n",
    "flag_0 = False\n",
    "flag_1 = False\n",
    "turn = 0\n",
    "\n",
    "def thread_0():\n",
    "    global cs, flag_0, flag_1, turn\n",
    "\n",
    "    flag_0 = True\n",
    "    turn = 1\n",
    "    while (flag_1 and turn == 1):\n",
    "            continue\n",
    "\n",
    "    for i in range(10):\n",
    "        cs += 1\n",
    "        print(\"Thread 0: cs =\", cs)\n",
    "        time.sleep(0.1)\n",
    "\n",
    "    flag_0 = False\n",
    "\n",
    "def thread_1():\n",
    "    global cs, flag_0, flag_1, turn\n",
    "\n",
    "    flag_1 = True\n",
    "    turn = 0\n",
    "    while (flag_0 and turn == 0):\n",
    "        continue\n",
    "\n",
    "    for i in range(10):\n",
    "        cs += 1000\n",
    "        print(\"Thread 1: cs =\", cs)\n",
    "        time.sleep(0.1)\n",
    "\n",
    "    flag_1 = False\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "\t\tt0 = threading.Thread(target=thread_0)\n",
    "\t\tt1 = threading.Thread(target=thread_1)\n",
    "\t\tt0.start()\n",
    "\t\tt1.start()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Alternative"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import threading\n",
    "import time\n",
    "\n",
    "# Shared variables\n",
    "turn = 0\n",
    "flag = [False, False]\n",
    "\n",
    "def process_0():\n",
    "    global turn, flag\n",
    "    flag[0] = True\n",
    "    turn = 1\n",
    "    while flag[1] and turn == 1:\n",
    "        # Wait\n",
    "        pass\n",
    "    # Critical section\n",
    "    print(\"Process 0 is in the critical section.\")\n",
    "    time.sleep(2)  # Simulating some work inside the critical section\n",
    "    # Exit section\n",
    "    flag[0] = False\n",
    "    print(\"Process 0 exited the critical section.\\n\")\n",
    "\n",
    "def process_1():\n",
    "    global turn, flag\n",
    "    flag[1] = True\n",
    "    turn = 0\n",
    "    while flag[0] and turn == 0:\n",
    "        # Wait\n",
    "        pass\n",
    "    # Critical section\n",
    "    print(\"Process 1 is in the critical section.\")\n",
    "    time.sleep(1)  # Simulating some work inside the critical section\n",
    "    # Exit section\n",
    "    flag[1] = False\n",
    "    print(\"Process 1 exited the critical section.\\n\")\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    thread_0 = threading.Thread(target=process_0)\n",
    "    thread_1 = threading.Thread(target=process_1)\n",
    "\n",
    "    thread_0.start()\n",
    "    thread_1.start()\n",
    "\n",
    "    thread_0.join()\n",
    "    thread_1.join()\n",
    "\n",
    "    print(\"Both processes have completed.\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Alternative"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The producer-consumer problem (or bounded buffer problem) describes two processes, the producer and the consumer, which share a common, fixed-size buffer used as a queue. Producers produce an item and put it into the buffer. If the buffer is already full then the producer will have to wait for an empty block in the buffer. Consumers consume an item from the buffer. If the buffer is already empty then the consumer will have to wait for an item in the buffer. Implement Peterson’s Algorithm for the two processes using shared memory such that there is mutual exclusion between them. The solution should have free from synchronization problems. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import time\n",
    "import threading\n",
    "import logging\n",
    "import queue\n",
    "\n",
    "BSIZE = 8  # Buffer size\n",
    "PWT = 2  # Producer wait time limit\n",
    "CWT = 10  # Consumer wait time limit\n",
    "RT = 10  # Program run-time in seconds\n",
    "\n",
    "def myrand(n):\n",
    "    return random.randint(1, n)\n",
    "\n",
    "def producer(queue, state):\n",
    "    index = 0\n",
    "    while state:\n",
    "        time.sleep(1)\n",
    "        logging.info(\"\\nProducer is ready now.\")\n",
    "        with queue.lock:\n",
    "            if not queue.full():\n",
    "                tempo = myrand(BSIZE * 3)\n",
    "                logging.info(f\"Job {tempo} has been produced\")\n",
    "                queue.put(tempo)\n",
    "                logging.info(f\"Buffer: {list(queue.queue)}\")\n",
    "            else:\n",
    "                logging.info(\"Buffer is full, nothing can be produced!!!\")\n",
    "        wait_time = myrand(PWT)\n",
    "        logging.info(f\"Producer will wait for {wait_time} seconds\")\n",
    "        time.sleep(wait_time)\n",
    "\n",
    "def consumer(queue, state):\n",
    "    time.sleep(5)\n",
    "    while state:\n",
    "        time.sleep(1)\n",
    "        logging.info(\"\\nConsumer is ready now.\")\n",
    "        with queue.lock:\n",
    "            if not queue.empty():\n",
    "                job = queue.get()\n",
    "                logging.info(f\"Job {job} has been consumed\")\n",
    "                logging.info(f\"Buffer: {list(queue.queue)}\")\n",
    "            else:\n",
    "                logging.info(\"Buffer is empty, nothing can be consumed!!!\")\n",
    "        wait_time = myrand(CWT)\n",
    "        logging.info(f\"Consumer will sleep for {wait_time} seconds\")\n",
    "        time.sleep(wait_time)\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    logging.basicConfig(level=logging.INFO, format='%(message)s')\n",
    "\n",
    "    shared_queue = queue.Queue(BSIZE)\n",
    "    shared_queue.lock = threading.Lock()\n",
    "    state = True\n",
    "\n",
    "    producer_thread = threading.Thread(target=producer, args=(shared_queue, state))\n",
    "    consumer_thread = threading.Thread(target=consumer, args=(shared_queue, state))\n",
    "\n",
    "    producer_thread.start()\n",
    "    consumer_thread.start()\n",
    "\n",
    "    time.sleep(RT)\n",
    "    state = False\n",
    "\n",
    "    producer_thread.join()\n",
    "    consumer_thread.join()\n",
    "\n",
    "    logging.info(\"\\nThe clock ran out.\")\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.0"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}