I'm designing and implementing a multiprocessing postscript interpreter ("lightweight" processes simulated by a single OS-thread), and I need to generate a unique identifier for each process in the system, as well as maintain ids for any dead processes which still have live references. (Reference: Adobe PLRM, 2ed, Ch. 7 Display PostScript, http://partners.adobe.com/public/developer/en/ps/psrefman.pdf‎)

I've started with a simple increment, which arithmetically maps to the table index for the per-process data.


unsigned nextid = 0;  // global (file-static) counter

unsigned initctxid(void) {  // generate a new cid
    while ( ctxcid(++nextid)->state != 0 )  // .state == 0 means free
    return nextid; 

context *ctxcid(unsigned cid) {  // get context data from cid
    return &itpdata.ctab[ (cid-1) % MAXCONTEXT ];

But there's gonna be a big problem if (when) the unsigned wraps around. Perhaps not scary for a game or an application, but this thing is supposed to be a server. Eventually. I'd like to avoid writing (in earnest) the disclaimer, "warning: will start having strange problems after running for a long time".

So, it should be easy enough to detect when it wraps, but what then? Bail out?

So the situation/scenario so far is: you're a multitasking postscript server with a handful of processes with cids allocated during one epoch of the generator, and the epoch has just turned. My thought (not impossible, just seems really hard) is to compact these existing IDs down to the 0..N range (rewriting all references, scanning all memory if necessary) and reset nextid to N.

But that's gonna be a pain-in-the-butt. Is there a different way to generate these IDs so I don't have to do a big garbage-collect on them, and have it work, you know, perpetually?

Edit: A fact I neglected to mention was that the Display PostScript reference says IDs are not re-used during a running instance of the system. But since these IDs are not exposed, they cannot be saved in any form other than the context object. So re-use should be just fine as long as no running process can know about it (contains an old context object in accessible memory).

  • 2
    "With enough [bits] all [value exhaustion problems] are shallow." Just use a 128-bit processid - everyone else seems to think that's enough (e.g., GUIDs). May 28, 2013 at 11:05
  • Certainly something I'll think about. But it doesn't fit with my current design which uses 64bit objects (at least some of which is devoted to metadata (type tag and flags)). The cid value is the payload of a contexttype object. Currently it's 32bits, but there's room in the design to stretch it to 48. May 29, 2013 at 0:03
  • I think your assumption about it being OK to reuse dead process ids is unsafe. You're just looking at the external side of the interface, but are you quite certain that something internal is not going to cause you trouble? Or that it will cleanly survive the next upgrade of the Display Postscript software (customers generally don't like being locked into specific versions of software on account of things like this)? Reminds me of the old "reserved bits" bomb ("these bits are currently not being used so it's OK to stuff my own data into them")... Jun 18, 2013 at 20:14

1 Answer 1


It doesn't matter if nextid wraps (as long as you don't have any overflow checking enabled).

What will happen is that the id is just passed into the function ctxcid which limits it to the range [0..MAXCONTEXT) (using the mod %). So the wrapping around happens way before the nextid wraps around.

So actually the worse case for you is the array filling up, which will cause an infinite loop because that while loop won't exit.

  • Ok. Yeah. I suppose it still couldn't reuse them, because the contexts would be marked dead not free. As for the loop filling-up, you're right. It's already in the TODO. I guess it's as simple as copying the initial nextid and check if nextid == initialnextid + MAXCONTEXT. May 28, 2013 at 9:59
  • 1
    @luserdroog: Then you need a mechanism to mark those entries that refer to dead processes without references as free. That is also roughly how the linux kernel allocates process-ids May 28, 2013 at 10:19
  • @Bart You're right. That one I'll have to think about. I suppose it's either reference counting, or I'll have to make a new global pass for the garbage collector (so far it just works on individual process memories). May 28, 2013 at 10:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.