Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

http://code.google.com/p/xpost/source/browse/itp.c#115

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).

share|improve this question
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). –  Ross Patterson May 28 '13 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. –  luser droog May 29 '13 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")... –  Jimmy Shelter Jun 18 '13 at 20:14
add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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. –  luser droog May 28 '13 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 –  Bart van Ingen Schenau May 28 '13 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). –  luser droog May 28 '13 at 10:54
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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