day 70 - deadlock.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "from time import sleep\n",
    "from threading import Thread, Lock"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class SharedState:\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self._lock = Lock()\n",
    "        self._state = defaultdict(int)\n",
    "        self._resources = [Lock() for _ in range(n)]\n",
    "\n",
    "    def atomic(self, key, value=0):\n",
    "        with self._lock:\n",
    "            self._state[key] += value\n",
    "            return self._state[key]\n",
    "\n",
    "    def resource(self, i):\n",
    "        return self._resources[i]\n",
    "\n",
    "    def kill(self):\n",
    "        resources = self._resources\n",
    "        self._resources = None\n",
    "        for i in resources:\n",
    "            i.release()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def worker(pid, state):\n",
    "    try:\n",
    "        while True:\n",
    "            state.atomic('waiting', 1)\n",
    "            with state.resource(pid):\n",
    "                state.atomic('waiting', 1)\n",
    "                with state.resource(pid - 1):\n",
    "                    state.atomic('waiting', -2)\n",
    "                    state.atomic('tasks', 1)\n",
    "\n",
    "    except RuntimeError:\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def deadlock(n):\n",
    "    state = SharedState(n)\n",
    "\n",
    "    for i in range(n):\n",
    "        Thread(target=worker, args=(i, state)).start()\n",
    "\n",
    "    while state.atomic('waiting') < 2 * n:\n",
    "        sleep(1)\n",
    "\n",
    "    print(n, 'workers; deadlock after', state.atomic('tasks'), 'tasks')\n",
    "    state.kill()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## run"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 workers; deadlock after 19935 tasks\n",
      "20 workers; deadlock after 36262 tasks\n",
      "30 workers; deadlock after 77059 tasks\n",
      "40 workers; deadlock after 15107 tasks\n",
      "50 workers; deadlock after 43405 tasks\n",
      "60 workers; deadlock after 9465 tasks\n",
      "70 workers; deadlock after 78949 tasks\n",
      "80 workers; deadlock after 10051 tasks\n",
      "90 workers; deadlock after 14169 tasks\n"
     ]
    }
   ],
   "source": [
    "for i in range(1, 10):\n",
    "    deadlock(10 * i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}