round-robin.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "\n",
    "import warnings\n",
    "warnings.filterwarnings('ignore')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# test case 0\n",
    "processes = [ \"A\", \"B\", \"C\", \"D\"]\n",
    "arrival_time = [0, 0, 0, 0]\n",
    "burst_time = [5, 4, 2, 1]\n",
    "waiting_time = [7, 7, 4, 6]\n",
    "turnaround_time = [12, 11, 6, 7]\n",
    "complete_time = [12, 11, 6, 7]\n",
    "quanta = 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# test case 1\n",
    "processes = ['P0', 'P1', 'P2','P3','P4']\n",
    "arrival_time = [0,1,2,3,7]\n",
    "burst_time = [3,2,1,1,1]\n",
    "waiting_time = [3,1,2,3,0]\n",
    "turnaround_time = [6,3,3,4,1]\n",
    "complete_time = [6,4,5,7,8]\n",
    "quanta = 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test case 2\n",
    "processes = ['P0', 'P1', 'P2','P3']\n",
    "arrival_time = [0,1,2,4]\n",
    "burst_time = [10,5,8,2]\n",
    "waiting_time = [15,11,13,4]\n",
    "turnaround_time = [25,16,21,6]\n",
    "complete_time = [25,17,23,10]\n",
    "quanta = 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# test case 3 \n",
    "processes = ['A', 'B', 'C','D','E']\n",
    "arrival_time = [0,0,2,3,1]\n",
    "burst_time = [3,2,1,4,3]\n",
    "waiting_time = [0,3,6,6,4]\n",
    "turnaround_time = [3,5,7,10,7]\n",
    "complete_time = [3,5,9,13,8]\n",
    "quanta = 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# test case 4\n",
    "processes = ['P1','P2','P3','P4','P5','P6']\n",
    "arrival_time = [0,25,30,60,100,105]\n",
    "burst_time = [20,25,25,15,10,10]\n",
    "waiting_time = [0,20,30,15,0,5]\n",
    "turnaround_time = [20,45,55,30,10,15]\n",
    "complete_time = [20,70,85,90,110,120]\n",
    "quanta = 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# test case 5\n",
    "processes = ['P1','P2','P3','P4','P5','P6']\n",
    "arrival_time = [0,1,2,3,4,5]\n",
    "burst_time = [8,4,2,1,3,2]\n",
    "waiting_time = [10,3,6,7,7,13]\n",
    "turnaround_time = [18,7,8,8,10,15]\n",
    "complete_time = [18,8,10,11,14,20]\n",
    "quanta = 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# test case 6 - to be checked\n",
    "processes = [\"A\", \"B\", \"C\", \"D\"]\n",
    "arrival_time = [0,1,2,3]\n",
    "burst_time = [10,5,8,2]\n",
    "waiting_time = [10,3,6,7]\n",
    "turnaround_time = [18,7,8,8]\n",
    "complete_time = [18,8,10,11]\n",
    "quanta = 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "expected_answer = pd.DataFrame({'Process':processes, 'Arrival Time':arrival_time, 'Burst Time':burst_time, \n",
    "                               'Waiting Time':waiting_time, 'Turn Around Time':turnaround_time, 'Completion Time':complete_time})\n",
    "expected_answer.sort_values(by=['Arrival Time', 'Burst Time'], ignore_index=True, inplace=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# generate a sorted timeline for the round robin algorithm\n",
    "\n",
    "def sort_process_rr(processes, arrival_time, burst_time, quanta):\n",
    "    end_time = sum(burst_time)\n",
    "    current_time = 0\n",
    "    rem_time = burst_time.copy()\n",
    "    processes_list = [ list(tup) for tup in list(zip(arrival_time, burst_time, processes, rem_time)) ]\n",
    "    processes_list.sort(key=lambda x: x[0])\n",
    "    sorted_process_list = []\n",
    "    queue = []\n",
    "    \n",
    "    while current_time < end_time or processes_list or queue:\n",
    "        available_processes_list = [process for process in processes_list if process[0] <= current_time]\n",
    "        \n",
    "        for process in available_processes_list:\n",
    "            if process not in queue:\n",
    "                queue.append(process)\n",
    "                processes_list.remove(process)\n",
    "        \n",
    "        if queue:\n",
    "            process_sel = queue.pop(0)\n",
    "            print(\"Process selected\", process_sel)\n",
    "            \n",
    "            if process_sel[3] > quanta:\n",
    "                process_sel[3] -= quanta\n",
    "                \n",
    "                for i in range(quanta):\n",
    "                    current_time += 1\n",
    "                    available_processes_list = [process for process in processes_list if process[0] <= current_time]\n",
    "                    for process in available_processes_list:\n",
    "                        if process not in queue:\n",
    "                            queue.append(process)   \n",
    "                            processes_list.remove(process)\n",
    "             \n",
    "                queue.append(process_sel)\n",
    "                sorted_process_list.append([current_time - quanta, quanta, process_sel[2]])\n",
    "                \n",
    "            else:\n",
    "                \n",
    "                for i in range(process_sel[3]):\n",
    "                    current_time += 1\n",
    "                    available_processes_list = [process for process in processes_list if process[0] <= current_time]\n",
    "                    for process in available_processes_list:\n",
    "                        if process not in queue:\n",
    "                            queue.append(process)\n",
    "                            processes_list.remove(process)\n",
    "                \n",
    "                sorted_process_list.append([current_time - process_sel[3], process_sel[3], process_sel[2]])\n",
    "                \n",
    "            \n",
    "        else:\n",
    "            process_sel = processes_list.pop(0)\n",
    "            print(\"Process selected\", process_sel)\n",
    "            current_time = process_sel[0]\n",
    "            \n",
    "            if process_sel[3] > quanta:\n",
    "                process_sel[3] -= quanta\n",
    "                for i in range(quanta):\n",
    "                    current_time += 1\n",
    "                    available_processes_list = [process for process in processes_list if process[0] <= current_time]\n",
    "                    for process in available_processes_list:\n",
    "                        if process not in queue:\n",
    "                            queue.append(process)   \n",
    "                            processes_list.remove(process)\n",
    "                \n",
    "                queue.append(process_sel)\n",
    "                sorted_process_list.append([current_time - quanta , quanta, process_sel[2]])\n",
    "            else:\n",
    "                for i in range(process_sel[3]):\n",
    "                    current_time += 1\n",
    "                    available_processes_list = [process for process in processes_list if process[0] <= current_time]\n",
    "                    for process in available_processes_list:\n",
    "                        if process not in queue:\n",
    "                            queue.append(process)\n",
    "                            processes_list.remove(process)\n",
    "                            \n",
    "                sorted_process_list.append([current_time - process_sel[3], process_sel[3], process_sel[2]])\n",
    "    \n",
    "    print(\"\\nSorted Processed List\", sorted_process_list)\n",
    "    return sorted_process_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_gantt_chart(timeline):\n",
    "    end_at_prev = 0\n",
    "    for i in timeline:\n",
    "        start_at = i[0]\n",
    "        end_at = i[1] + start_at\n",
    "        \n",
    "        if start_at != end_at_prev:\n",
    "            print(f\"{end_at_prev}-{start_at} : Idle | \", end=\"\")\n",
    "    \n",
    "        print(f\"{start_at}-{end_at} : Process {i[2]} | \", end=\"\")\n",
    "        \n",
    "        end_at_prev = end_at"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# writing a program for shortest job first scheduling algorithm with arrival times to return\n",
    "# waiting time and turn around time for each process and average waiting time and average turn around time\n",
    "# for all processes\n",
    "\n",
    "\n",
    "def rr(process, arrival_time, burst_time, quanta):    \n",
    "    # for preemptive algorithms\n",
    "    \n",
    "    timeline = sort_process_rr(processes, arrival_time, burst_time, quanta)\n",
    "    processes_list = [ list(tup) for tup in list(zip( process, arrival_time, burst_time )) ]\n",
    "    df = pd.DataFrame(processes_list, columns=['Process', 'Arrival Time', 'Burst Time' ])\n",
    "    timeline_df = pd.DataFrame(timeline, columns=['Start Time', 'Duration', 'Process'])\n",
    "    \n",
    "    list_of_processes = df['Process'].tolist()\n",
    "    for i in list_of_processes:\n",
    "        temp = timeline_df.loc[timeline_df['Process'] == i, 'Start Time'] + timeline_df.loc[timeline_df['Process'] == i, 'Duration']\n",
    "        df.loc[df['Process'] == i, 'Completion Time'] = temp.iloc[-1]\n",
    "\n",
    "    df['Turn Around Time'] = df['Completion Time'] - df['Arrival Time']\n",
    "    df['Waiting Time'] = df['Turn Around Time'] - df['Burst Time']    \n",
    "    \n",
    "    df = df[['Process', 'Arrival Time', 'Burst Time', 'Waiting Time', 'Turn Around Time', 'Completion Time']]\n",
    "        \n",
    "    print(\"\\nProcess Details:\")\n",
    "    for i in range(len(df)):\n",
    "        print(f\"Process: {df['Process'].iloc[i]}, Wait Time: {df['Waiting Time'].iloc[i]}, Turn Around Time: {df['Turn Around Time'].iloc[i]}, Completion Time: {df['Completion Time'].iloc[i]}\")\n",
    "        \n",
    "    print(f\"\\nAverage Waiting Time: {df['Waiting Time'].mean():.2f} \")\n",
    "    print(f\"Average Turn Around Time:  {df['Turn Around Time'].mean():.2f} \")\n",
    "    return df.reset_index(drop=True) , timeline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Process selected [0, 10, 'A', 10]\n",
      "Process selected [1, 5, 'B', 5]\n",
      "Process selected [2, 8, 'C', 8]\n",
      "Process selected [0, 10, 'A', 8]\n",
      "Process selected [3, 2, 'D', 2]\n",
      "Process selected [1, 5, 'B', 3]\n",
      "Process selected [2, 8, 'C', 6]\n",
      "Process selected [0, 10, 'A', 6]\n",
      "Process selected [1, 5, 'B', 1]\n",
      "Process selected [2, 8, 'C', 4]\n",
      "Process selected [0, 10, 'A', 4]\n",
      "Process selected [2, 8, 'C', 2]\n",
      "Process selected [0, 10, 'A', 2]\n",
      "\n",
      "Sorted Processed List [[0, 2, 'A'], [2, 2, 'B'], [4, 2, 'C'], [6, 2, 'A'], [8, 2, 'D'], [10, 2, 'B'], [12, 2, 'C'], [14, 2, 'A'], [16, 1, 'B'], [17, 2, 'C'], [19, 2, 'A'], [21, 2, 'C'], [23, 2, 'A']]\n",
      "\n",
      "Process Details:\n",
      "Process: A, Wait Time: 15.0, Turn Around Time: 25.0, Completion Time: 25.0\n",
      "Process: B, Wait Time: 11.0, Turn Around Time: 16.0, Completion Time: 17.0\n",
      "Process: C, Wait Time: 13.0, Turn Around Time: 21.0, Completion Time: 23.0\n",
      "Process: D, Wait Time: 5.0, Turn Around Time: 7.0, Completion Time: 10.0\n",
      "\n",
      "Average Waiting Time: 11.00 \n",
      "Average Turn Around Time:  17.25 \n"
     ]
    }
   ],
   "source": [
    "actual_answer, timeline = rr(processes, arrival_time, burst_time, quanta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Quanta: 2\n",
      "\n",
      "0-2 : Process A | 2-4 : Process B | 4-6 : Process C | 6-8 : Process A | 8-10 : Process D | 10-12 : Process B | 12-14 : Process C | 14-16 : Process A | 16-17 : Process B | 17-19 : Process C | 19-21 : Process A | 21-23 : Process C | 23-25 : Process A | "
     ]
    }
   ],
   "source": [
    "print(\"Quanta:\", quanta, end=\"\\n\\n\")\n",
    "generate_gantt_chart(timeline)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Process</th>\n",
       "      <th>Arrival Time</th>\n",
       "      <th>Burst Time</th>\n",
       "      <th>Waiting Time</th>\n",
       "      <th>Turn Around Time</th>\n",
       "      <th>Completion Time</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>A</td>\n",
       "      <td>0</td>\n",
       "      <td>10</td>\n",
       "      <td>15.0</td>\n",
       "      <td>25.0</td>\n",
       "      <td>25.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>B</td>\n",
       "      <td>1</td>\n",
       "      <td>5</td>\n",
       "      <td>11.0</td>\n",
       "      <td>16.0</td>\n",
       "      <td>17.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>C</td>\n",
       "      <td>2</td>\n",
       "      <td>8</td>\n",
       "      <td>13.0</td>\n",
       "      <td>21.0</td>\n",
       "      <td>23.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>D</td>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "      <td>5.0</td>\n",
       "      <td>7.0</td>\n",
       "      <td>10.0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "  Process  Arrival Time  Burst Time  Waiting Time  Turn Around Time  \\\n",
       "0       A             0          10          15.0              25.0   \n",
       "1       B             1           5          11.0              16.0   \n",
       "2       C             2           8          13.0              21.0   \n",
       "3       D             3           2           5.0               7.0   \n",
       "\n",
       "   Completion Time  \n",
       "0             25.0  \n",
       "1             17.0  \n",
       "2             23.0  \n",
       "3             10.0  "
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "actual_answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Process</th>\n",
       "      <th>Arrival Time</th>\n",
       "      <th>Burst Time</th>\n",
       "      <th>Waiting Time</th>\n",
       "      <th>Turn Around Time</th>\n",
       "      <th>Completion Time</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>A</td>\n",
       "      <td>0</td>\n",
       "      <td>10</td>\n",
       "      <td>10</td>\n",
       "      <td>18</td>\n",
       "      <td>18</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>B</td>\n",
       "      <td>1</td>\n",
       "      <td>5</td>\n",
       "      <td>3</td>\n",
       "      <td>7</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>C</td>\n",
       "      <td>2</td>\n",
       "      <td>8</td>\n",
       "      <td>6</td>\n",
       "      <td>8</td>\n",
       "      <td>10</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>D</td>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "      <td>7</td>\n",
       "      <td>8</td>\n",
       "      <td>11</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "  Process  Arrival Time  Burst Time  Waiting Time  Turn Around Time  \\\n",
       "0       A             0          10            10                18   \n",
       "1       B             1           5             3                 7   \n",
       "2       C             2           8             6                 8   \n",
       "3       D             3           2             7                 8   \n",
       "\n",
       "   Completion Time  \n",
       "0               18  \n",
       "1                8  \n",
       "2               10  \n",
       "3               11  "
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "expected_answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "check_actual_answer = actual_answer.sort_values(by=['Arrival Time', 'Burst Time'], ignore_index=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Your answer is incorrect\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead tr th {\n",
       "        text-align: left;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr>\n",
       "      <th></th>\n",
       "      <th colspan=\"2\" halign=\"left\">Waiting Time</th>\n",
       "      <th colspan=\"2\" halign=\"left\">Turn Around Time</th>\n",
       "      <th colspan=\"2\" halign=\"left\">Completion Time</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th></th>\n",
       "      <th>self</th>\n",
       "      <th>other</th>\n",
       "      <th>self</th>\n",
       "      <th>other</th>\n",
       "      <th>self</th>\n",
       "      <th>other</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>15.0</td>\n",
       "      <td>10</td>\n",
       "      <td>25.0</td>\n",
       "      <td>18</td>\n",
       "      <td>25.0</td>\n",
       "      <td>18</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>11.0</td>\n",
       "      <td>3</td>\n",
       "      <td>16.0</td>\n",
       "      <td>7</td>\n",
       "      <td>17.0</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>13.0</td>\n",
       "      <td>6</td>\n",
       "      <td>21.0</td>\n",
       "      <td>8</td>\n",
       "      <td>23.0</td>\n",
       "      <td>10</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>5.0</td>\n",
       "      <td>7</td>\n",
       "      <td>7.0</td>\n",
       "      <td>8</td>\n",
       "      <td>10.0</td>\n",
       "      <td>11</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "  Waiting Time       Turn Around Time       Completion Time      \n",
       "          self other             self other            self other\n",
       "0         15.0    10             25.0    18            25.0    18\n",
       "1         11.0     3             16.0     7            17.0     8\n",
       "2         13.0     6             21.0     8            23.0    10\n",
       "3          5.0     7              7.0     8            10.0    11"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "diff = check_actual_answer.compare(expected_answer)\n",
    "\n",
    "if diff.empty:\n",
    "    print(\"Your answer is correct\")\n",
    "else:\n",
    "    print(\"Your answer is incorrect\")\n",
    "    \n",
    "diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "# # insert this line in rr() function before uncommenting this cell and running it\n",
    "# # df = df.astype({'Completion Time': 'int64', 'Turn Around Time': 'int64', 'Waiting Time': 'int64'})\n",
    "\n",
    "# from pandas.testing import assert_frame_equal\n",
    "# assert_frame_equal(check_actual_answer, expected_answer)"
   ]
  }
 ],
 "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.5"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}