Semaphore rules/Efficiency using semaphores in list objects

[Jose]

Does the use of semaphores has to be organized in the structure like the example they have on the RKM Libs ? Like:

Code: [Select]

struct SharedList {
 struct SignalSemaphore sl_Semaphore;
 struct MinList sl_List;
},
or can the semaphore be anywhere in a structure (or even somewhere else ? Maybe there's some AmigaOS internal code that relies on a certain organization (the RKM doesn't mention it though, but I want to be sure).

Last but not least, to protect more efficiently, in terms of multitasking, a list's elements from getting currupt because of multiple writes of different tasks, wouldn't it make more sense to have each of the list's elements have a Semaphore and then ObtainSemaphore() the two nodes between wich you want to insert a new one, or just a certain node's Semaphore if you just want to change some fields in the structure that contains it (rather than blocking the whole list everytime you want to do something to one of it's elements). This way other tasks accesing nodes that aren't being changed could continue to access them.

:pint:

[Piru]

@Jose

Does the use of semaphores has to be organized in the structure like the example they have on the RKM Libs ?

No.

or can the semaphore be anywhere in a structure (or even somewhere else ? Maybe there's some AmigaOS internal code that relies on a certain organization (the RKM doesn't mention it though, but I want to be sure).

Yes.

Last but not least, to protect more efficiently, in terms of multitasking, a list's elements from getting currupt because of multiple writes of different tasks, wouldn't it make more sense to have each of the list's elements have a Semaphore and then ObtainSemaphore() the two nodes between wich you want to insert a new one, or just a certain node's Semaphore if you just want to change some fields in the structure that contains it (rather than blocking the whole list everytime you want to do something to one of it's elements). This way other tasks accesing nodes that aren't being changed could continue to access them.

No. It would be horribly wasteful, and leave room for massive deadlocks (multiple semaphores must always be obtained in the same order, or a master semaphore lock must be used to arbitrate the sub-locking. Read the exec.doc ObtainSemaphoreList stuff, it's described there).

Also, the actual removal/insertation is very very fast, so the actual lock is only kept for a very short period. Since this is the case it doesn't really help at all to add any more complexcity layers from additional semaphores. In fact, it could be argued that Forbid/Permit protection would be even faster (if only insert/remove is used). If some very slow and complex operations are made while keeping the list "locked" then semaphore does pay off.

Since list iteration again involves locking the whole list (all the nodes, and they usually must not change inbetween), it doesn't really pay off to have any lower level granularity semaphores.

Also, doubly linked list Insert/Remove involves changing ptrs in 2 to 3 elements, in fact. For reference, see dlist for doubly linked list implementation.

I hope I made some sense here.

[Jose]

@Piru
Yeah, that made sense. I now have a buch of lines of code to change cause I had already started puting Semaphores in each node and writing code that would use them doh!! :-x  :lol:
Better now than after finishing I guess...

:pint:

[Jose]

Another question: I guess the exception where it would be usefull and safe would be if the operations made on each node took a long time and code only needed to lock one semaphore for each node (not a Semaphore list). This is the case of the code I'm writing now, though the operations take a very short time (checking/setting a boolean only :-)(for now))

[Cymric]

No, it wouldn't. The reason is that list operations (finding nodes, removing nodes, adding nodes) need the node structure to begin with; if parts of them are locked, then the list operations cannot continue. Therefore locking separate nodes still implies a master lock on the list itself, albeit a read-only one. The idea of semaphores, mutexes and spin locks is that you provide synchronised access to a data set: as long as a task is busy with data, all others must wait. You could attempt to read a locked data structure, but since the contents are by definition uncertain, you cannot do anything useful with it. Not even print the contents. The only solution is not to link the separate data structures into a list.

For a very good introduction to this fascinating topic, I recommend this site.

[Jose]

@Cymric
"No, it wouldn't. The reason is that list operations (finding nodes, removing nodes, adding nodes) need the node structure to begin with; if parts of them are locked, then the list operations cannot continue. Therefore locking separate nodes still implies a master lock on the list itself, albeit a read-only one."

Ok, but that's only if I was messing with the Node structure right? If I was only changing other user data (in the structure in wich I embeded the struct Node to be able to create a linked list), the ln_Succ and ln_Pred fields would still be valid and other tasks could traverse the list (e.g. My Semaphore in each node protects only the user data in the node).
 For taking off/adding/resorting nodes I have another Semaphore that pertains to the whole list.

P.S.
That's a very cool link but if I start reading that I won't take advantage of the time I have now to updtate my program.

[Jose]

Hi. I guess I messed up my initial explanation (I had forgot how my own code works!!). I actually have a Semaphore in each node, but it's allways only used to access the data after the Node structure. In my last reply to Cymric I was only thinking "if I had it working like that would it be feasible?" but my code actually works like that after all (been a few moths since I stopped updating it :oops: ).

So I guess it's ok then ?