1

Consider we have three thread, bool status_flag[500] array, and working situations as follow :

  1. Two threads only writing in status_flag array at different index. while third thread is only reading at any index.

  2. All three thread writing at different index. While all three threads reading at any index.

In writing operation we are just setting the flag never reset it again.

status_flag [i] = true;

In reading operation we are doing something like that :

    for(;;){  //spinning to get flag true
       if(status_flag [i] == true){
           //do_something ;
           break;
       }
    }

What happen if compiler optimize (branch prediction) code?

I have read lot about lock but still having confusion to conclude result. Please help me to conclude.

alk
  • 69,737
  • 10
  • 105
  • 255
Mohan
  • 1,871
  • 21
  • 34
  • 3
    You need synchronization. Whether you need a *mutex* is a different question. – EOF Jul 22 '15 at 06:45
  • Yes, mutex/semaphore, the operation has to be "atomic" because you read from where another thread writes. – Jeremiah Dicharry Jul 22 '15 at 06:49
  • @mohan branch prediction is a processor pipeline optimization. If you think `status_flag` will be optimized out, you can use the `volatile` keyword. – Jeremiah Dicharry Jul 22 '15 at 07:01
  • @JeremiahDicharry: See http://stackoverflow.com/questions/2484980/why-is-volatile-not-considered-useful-in-multithreaded-c-or-c-programming... – Oliver Charlesworth Jul 22 '15 at 07:12
  • I stand corrected on the `volatile` part. – Jeremiah Dicharry Jul 22 '15 at 21:45
  • @JeremiahDicharry Here I am talking about flag which is set in write part of one thread and in reading I am spinning to get true flag. I don't want do anything with false flag. actually I have implemented this without mutes/semaphore and it's working for me. Is it fail in future? – Mohan Jul 23 '15 at 05:38
  • 2
    @mohan It will fail because the operation needs to be atomic. Check out the wikipedia page - [Non-atomic](https://en.wikipedia.org/wiki/Linearizability#Non-atomic) for an example of what can happen. – Jeremiah Dicharry Jul 23 '15 at 05:48
  • @mohan: mutexes and semaphores are atomic and able to do thread control. – Jeremiah Dicharry Jul 23 '15 at 05:53
  • @EOF these are some method I know for synchronization ,Mutual Exclusion (Mutex) Locks , Condition Variables & Semaphores. Is there any other way to do synchronization? In above situation if we don't use mutex/semaphore then is there any chance to never get updated data to other thread ? – Mohan Jul 23 '15 at 05:56
  • `status_flag [i] == true` is not guaranteed to be synchronized between all threads without a method of synchronization, because it is not atomic. Another thread could be writing to `status_flag[i]` at the same time. – Jeremiah Dicharry Jul 23 '15 at 06:06
  • @mohan: I guess if you're code is working then whatever floats your boat but it's bad practice to not do some kind of locking. – Jeremiah Dicharry Jul 23 '15 at 06:08
  • You want read/write locks. (http://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_rwlock_init.html) – alk Jul 23 '15 at 08:25
  • If you have C11 support, you can use the new `_atomic` types to synchronize without any kind of lock. However, if you're waiting for a flag to change, spinning on an atomic variable is wasting CPU time. – EOF Jul 23 '15 at 13:03

2 Answers2

2

POSIX is quite clear on this:

Applications shall ensure that access to any memory location by more than one thread of control (threads or processes) is restricted such that no thread of control can read or modify a memory location while another thread of control may be modifying it.

So without locking you're not allowed to read memory that some other thread may be writing. Furthermore, that part of POSIX describes which function will synchronize the memory between the threads. Before both threads have called any of the functions listed in there, you have no guarantee that the changes made by one thread will be visible to the other thread.

Art
  • 19,807
  • 1
  • 34
  • 60
  • I got it but still having confusion in case of flag . In case if I am reading value without synchronize I will get some garbage or stale data. But what if one thread only writing (true) flag and other thread reading in for loop till it gets true. Is there no surety to get updated data to other thread without synchronization ? – Mohan Jul 23 '15 at 07:34
  • @Mohan: POSIX is clear, isn't it? If you do not believe it, try it without synchronisation. You will fail, probably not always, but sometimes. – alk Jul 23 '15 at 08:31
  • @alk it's not about believe.I am just wondering in other reading thread , it's spinning to get true flag ,still there is chance of failure why? Maybe because of cache or something else that is not allowing to reading thread to get updated value. I just want to know root causes. – Mohan Jul 23 '15 at 09:19
  • @Mohan: Because reading and/or writing not necessarly are atomic operations. See also this comment: http://stackoverflow.com/questions/31555700/do-i-really-need-mutex-lock-in-this-case/31556748?noredirect=1#comment51111970_31555700 – alk Jul 23 '15 at 09:21
  • 2
    @Mohan There is no guarantee that you will ever see the changed value. On x86 systems you will most often see the value as soon as possible, but there are situations that can be created (intentionally or by accident) where the changed value will never propagate to the other thread/CPU until you use proper memory synchronization instructions. POSIX is deliberately strict because of portability to systems where you'll never see the modified value unless you synchronize. But even on x86 the synchronization can be very much delayed. The minimum you can do it to use stdatomic.h from C11. – Art Jul 23 '15 at 09:23
  • 1
    @Mohan Btw. what do you intend to do with the flag? The flag itself is useless because other memory writes done by the flag setting thread may not be visible to the other thread that reads the flag. So a thread calculates something, writes down the result somewhere, sets the flag that the result is done, the main thread reads the flag, sees that it's set, reads the result and gets uninitialized garbage. This happens all the time. The past 10 years of performance improvements in x86 CPUs have been about how much CPU designers can get away with not synchronizing things. – Art Jul 23 '15 at 09:32
1

If all the threads are operating on different index value, then you do not need a lock. Basically it is equivalent to using different variables. In your code , the value of the variable i is not set or modified. So it is reading only a particular index of flag. And for writing you are using different index, in this case no need to use lock.

Dipanjan
  • 181
  • 3
  • 12
  • Obviously if threads were *always* writing to different indices than the one being read, the loop would be an infinite one... – Oliver Charlesworth Jul 22 '15 at 07:09
  • @Oliver Charlesworth I made sure index which being is read definitely get write. if it reading at index (e.g. 5) and write happen at same index (e.g. 5) after it start reading. So thread which reading will able to break loop or not ? or it will still read a stale data. – Mohan Jul 22 '15 at 07:50
  • @Mohan: If you are reading and writing at the same index then you need a lock. – Dipanjan Jul 22 '15 at 08:21
  • @Dipanjan ok Can't we avoid use of lock in two thread read & write case? – Mohan Jul 22 '15 at 09:34
  • @Mohan: If you do not use of lock, then you can not guarantee the sequence of execution. For example, you started two threads , one is writing(ex- incrementing a variable) and the other is reading it, now you wont be sure that the read will occur after write or before, so you will not get consistent or intended data when you are reading it. So you should use lock, if you do not use , you can not be sure of the sequence of execution. Hope this is clear. :) – Dipanjan Jul 23 '15 at 03:58
  • @Dipanjan I am talking about flag in my question not about value. So in reading part I am spinning till the point I don't get true flag .Initially I am setting flag to false. I don't want to do anything with false flag and in writing part only setting to true. so what you say? – Mohan Jul 23 '15 at 05:05
  • 1
    @Mohan: This could work without a lock, try to give some delay or sleep, so that the control goes to other thread as well. It might happen, that thread which is reading gets the control and it keep running in infinite loop and the write thread does not gets the chance to modify the flag. – Dipanjan Jul 23 '15 at 05:37