Atomicity

I am working on a primitive project ported on AIX Unix Box. Earlier this system used to run on VMS VAX and DEC Alpha system. The major source code files are written in FROTRAN.

Across process data are exchanged through FROTRAN COMMONS and a specific locking mechanism is implemented for resource synchronization. Data for exchange are stored in FROTRAN Array in COMMONS. During addition to the bottom of the array and removal from the top, a specific position of the array is marked as 1 or 0 meaning that array can be accessed or cannot. Based upon these values the action on arrays would be taken. I hope that I am clear.

They used LIB$BBSSI() system call to lock the list and LIB$BBCCI() system call to release the list from lock state in VMS. I presume that this would be atomic cause of which process where in synchronization.

During porting of the same software in Tru64 they swapped the same routines with C subroutines _TESTBITSSI() and _TESTBITCCI() calls.

The problem came when they ported it to AIX. Due to lack of technology specifications we are unable to have atomic locking mechanism. Hence the issue is that two or more process is able to detect that they can act on a same array resulting on an unpredictable behavior.

We need a solution for the problem. I though of a solution but I don't know that in multi-process environment whether the solution would work or not. Please provide your necessary input and ensure that the code does leads to a DEADLOCK.
:

During the process startup we would store the required address our interest. Say for example we have 3-array list and list lock index is 1. So if the arrays are named as A, B, D then we will store the address of A (1), B (1) and D (1) in �C' array of pointers *list_arr[3] (list_arr[0], list_arr[1], list_arr[2]).
Now LOCK() and REL() subroutine would be called across process running in different address space.

LOCK(int bit_pos, int address)
{
.......
.......
/ For One specific address /
RERUN:
if ( address == list_arr[0] )
{
if ( shared_variable_One == 0 ) / Variable Shared Across Processes /
{
shared_variable_One = getpid ( ) ;
}
if (shared_variable_One == getpid ( ) )
{
if ( ++ shared_variable_two > 1 ) / Variable Shared Across Processes Initially initialized as 0/
goto RERUN:
/* Set the bit value */
shared_variable_One = 0 ;
shared_variable_two = 0 ;
}
else
goto RERUN;
}

.......................
.......................
}
The same can be implemented for REL(int *bit_pos, int *address).

These subroutines would then be called through FROTANS subroutines.

I have had thought about using SEMAPHORES but then we had to use 3 semaphores (as in this example) such that operation on one address by one process does not blocks operation on other address which is being accessed by multiple process.

Thanks in advance.

First of all I would like to state that the pseudo-code I have written in my initial post needs modification. Instead of writing LOCK () and REL() as two separate functions, it would be only one subroutine LOCK_REL() implementing the pseudo-code.

Yes. This concept is already implemented in the project. All I need to is add up the required variables.

I studied the pseudo-code but that's what exactly we do not want. For example there are 10 process. Assume 2 different process would like to implement LOCK on the array and while 3 different process tries to REL the LOCK on the same array. Only one of the process should succeed for a specific array operation.

Further more of the remaining 5, 3 different process are trying to implement LOCK on 3 different arrays and 2 are REL two separate arrays, then they very well should. I mean they should not wait other wise timing would become a major issue i.e. time to process one transaction would increase.

Here's a sample view of what I would like to implement atomically:

Process'xx'1'xxxxx'2'xxxxx'3'xxxx'4'xxxxx'5'xxxxx'6'
Array'xxxx'A'xxxxx'B'xxxxx'C'xxxx'D'xxxxx'E'xxxxx'F'

xxxxxxxx ..... xxxx..... xx..... xxxx..... xxx......xxx.........
xxxxxxxxL(D)xxxxL(D)xxR(D)xxxxL(E)xxxR(F)xxxL(A)
xxxxxxxx ..... xxxx..... xx..... xxxx..... xxx......xxx.........

Where L stands for LOCK and R stands for REL the lock on array passed as arguments and value at array index 1 states whether array is locked ( value 1 ) or unlock ( value 0 ) . Please ignore the x's as I have put it for alignment purpose

I hope that I am clear in my requirement.

Thanks in advance.

First of all I would thank Driver for all the technical support and aid that he has provided.

Driver as you have stated that:

We have more than 10 process and in each process it has to LOCK or REL the LOCK for a specific array. One specific process cannot lock or release for more than one resource at a time. As per your pseudo-code then we need to have as many number of SEMAPHORES as there are number of arrays and LOCK / REL piece of code should be injected where locking and releasing of the resource comes into picture within the process. That would include a lot of re-work in the project. Will it be time efficient?

That is what I have posted the same in initial post.

Yes your pseudo-code would work fine if through out the processes we make a check that for a specific array the mapped SEMAPHORE key would lock or unlock the resource.

Thanks Driver, your solution is definitely a valuable one. I will build up a set of test executables implementing your pseudo-code.

Also please let me know if the pseudo-code I posted in my initial post is ok or not?

Thanks in advance.

What you're trying to do is code a mutex using only shared memory. And for n processes, not just 2 processes. I'm not qualified to pass judgement on your algorithm, but I wouldn't be surprised if there is a problem with it.

This is like encryption or compression... what you should do is use one of the well known and carefully researched algorithms.

See this page for example.

Thanks Perderabo.

Currently I am going through the algorithms as provided by you in a link.

I would like to put forward my observations in this post. As earlier mentioned the code was ported from VMS to Tru64 to AIX. Now as a part of unit integration, I copied the existing LOCK() and REL() functions in AIX box to that in Tru64 and re-compiled the executables. Surprisingly I did not receive any errors in Tru64. I wonder why ?

And will Shared libraries help us to our problem. We can resist only one copy of functions in the memory and validate which address is getting locked or release and take action accordingly.

Thanks in advance.

To add I just learnt that the AIX system we have runs on dual CPU while that of Tru64 has a single CPU.

Will that make a difference on performance or code behavior?

Thanks for the information, Driver.

The second if takes care such that only one process has the right to execute code:

I hope that I am clear.

Shared libraries (also called dynamic libraries) are linked into the program in two stages. First, during compile time, the linker verifies that all the symbols (again, functions, variables and the like) required by the program, are either linked into the program, or in one of its shared libraries. However, the object files from the dynamic library are not inserted into the executable file. Instead, when the program is started, a program in the system (called a dynamic loader) checks out which shared libraries were linked with the program, loads them to memory, and attaches them to the copy of the program in memory.

The complex phase of dynamic loading makes launching the program slightly slower, but this is a very insignificant drawback, that is out-weighted by a great advantage - if a second program linked with the same shared library is executed, it can use the same copy of the shared library, thus saving a lot of memory. Only one copy of the library is stored in memory at any given time. This means we can use far less memory to run our programs, and the executable files are much smaller, thus saving a lot of disk space as well.

Hence if I write LOCK() and REL() subroutines as a part of Shared Library and link it to the executable, will not aid me to make the operations atomic. I can easily validate in the subroutines which address is requested for locking and which for release.

Thanks in advance.

I personally thank Driver and Perderabo for their interest shown to solve the issue. Please continue aiding me till we conclude to a unanimous decision.

You're right that's a race condition. But the next line is...

if (shared_variable_One == getpid ( ) )
{

which is (I think) intended to check for the race condition. But there is still a race condition here. Both processes hit the first test and see the variable as zero. Then one process proceeds all the way past the second test. Then the second process picks up right after the first test and rolls right through the code.

This kind of thing is why I'd be afraid to design my own algorithm. You've gotta go with one of the algorithms that were designed by the pros and have been peer reviewed.

As I am not confident about a topic and it may sound to be silly, so forgive me for my query.

My question is 'is if atomic' i.e. suppose if I have the following lines of code in a 'C' program:

......;
......;
x=0;
y=8;
u=1;
z=9;
...... ;
.......;

if ( x == 0 && y ==8 && ++u || z = user_func ( ) && ...... )
{
/* Statements to be executed */
}
..........;
..........;

Does atomicity regarding 'if' is implied in 'C'.

Thanks in advance.

If you mean 'will the entire if statement be evaluated atomically'
-- the answer is No. It cannot be guaranteed.

Once the quantum expires (your timeslice is used up), some other process can pre-empt the processor. Assuming I understood your question correctly.

Please visit the link within this post.

_check_lock and _clear_lock on AIX

I tested the code implementing the routines and the code behaves fine in Unit testing.

Also if someone can explain me in detail "The word variable must be aligned on a full word boundary." as stated in the page. Please correct me if I am worng - "A group of related bytes that are treated as a single addressable unit or entity in memory is called as a WORD. Hence size of a word varies from one computer to another, depending on the CPU. For computers with a 16-bit CPU, a word is 16 bits (2 bytes)."

Single Word = Single addressable unit by CPU
Word Boundary = Address completely divisible by number of bytes that represents a single addressable unit.

Example Single Word length = 16 bits then a word boundary is any address that is completely divisible by 16, which would mean that the variable referenced here should begin at 0,16,32,48,64 ... and so on memory locations and the variable should consume 16 bits of memory.

Am I correct? What extra care should I take into account during coding?

Please let me know whether these are a proven set of standard 'C' routines. Please let me know your honest opinions before I put it into the production system and have a go.

Thanks in advance

I agree to the modification of the definition of 'Single Word'.

Please provide me arguments as to why you say 'No, divisible by two' with regards to �word boundary'. Is it that word boundary depends upon the type of data we are referring to i.e. depends upon the sizeof of the data type. Hence for a four-byte-sized integer the word boundary will be of multiples of 4 and for two-byte-sized integer the word boundary will be multiples of 2 respectively.

Thanks in advance.

Oh ! After reading your reply I realized that I have confused myself regarding 'word boundary' memory alignment. It happens to me at times.

Thanks Driver for your replies.