Peterson's algorithm allows us to safely lock data in shared memory so only one thread can access it at a time.
This is some simple code that implements Peterson's Algorithm as described by the Wikipedia article in Node.js.
Specifically, I've implemented the more generalized algorithm for 2 or more processes.
If you want to do some thinking about concurrency primitives, and specifically if you want see some example code for Peterson's algorithm, this is for you.
Do not use this for production code.
Why not?:
- Since Node.js is single-threaded, this code is providing safety amongst conceptual threads-of-execution (e.g. closures you've created that are responding to events Node.js is sending you) rather than real threads or processes. Given the single-threaded constraint, we could provide similar safety guarantees this in simpler and more efficient ways, e.g. by having a simple queue of functions that access the shared state.
- Processors have instructions for atomic access that you can use to implement alternate algorithms that should be much more efficient.
- While this has been tested and works, concurrency is hard and it's very possible there are bugs I haven't found.
- Other languages and libraries offer better tested, more performant, and more versatile concurrency primitives.
- If you can avoid it, just don't share mutable data across threads. Handling that properly is slow and error-prone and you're bound to shoot yourself in the foot at least once.
First, you need Node.js installed. Any recent version should do.
Then, install the npm dependencies (mainly we're just need TypeScript and some type files for TypeScript):
npm install
Then we can compile the TypeScript files:
./node_modules/.bin/tsc
Or if you already have TypeScript installed globally:
tsc
There's a standalone version of the algorithm with some hardcoded actions. You can run it with:
node fixed-data-fixed-thread-count.js
There is an equivalent program that uses the the nicer SharedMemory
API I created:
node shared-memory-example.js
I have also implemented a small test program that has a shared hit counter variable that you can increment by sending it HTTP requests. You can start the server like so:
node main.js
And then you can send it requests by running:
node tester.js
tester.js
will send a number of simultaneous requests to the server and log GOOD
or BAD
if the hit counter returns
in sequentially increasing order. If things return out of order, or we get the same value back multiple times, that
means our locking mechanism isn't working.
You can also visit http://localhost:3000 in your browser.
Main files:
shared-memory.ts
- An implementation of the algorithm with a nice API around it so you can make any value safely shared access multiple threads of execution. It copies its stored value using JSON.stringify/JSON.parse so that mutable versions of the shared data can't escape can wreak havoc. It also supports an arbitrary number of threads created at any time that you like. Since we don't have true threads or processes, attempts to gain a lock on the stored value are done via ES2017async
/await
with random short delays between locking attempts.shared-memory-example.ts
- Shows a simple usage of theSharedMemory
API created by the above file.fixed-data-fixed-thread-count.ts
- A simpler version of the algorithm, closer to what Wikipedia describes. It requires the number of threads to be specified in advance. It immediately executes some simple tests and so isn't suited for re-use anywhere in other code.main.ts
- A server that increments a hit counter using the locking mechanism provided byshared-memory.ts
. It introduces some delays to simulate the server doing actual work so that we can actually perceive whether the locking is working correctly.tester.ts
- Sends requests to the server created bymain.ts
and checks whether the responses are what we expect.
Auxillary files:
tsconfig.json
- TypeScript configuration.package.json
- NPM packages we use (just TypeScript stuff, no outside libraries)package-lock.json
- Specific versions of packages pulled whennpm install
was used on the abovepackage.json
.gitignore
- Tell Git we don't want to tracknode_modules
, compiled.js
files, and other things.README.md
- This file.