2

I'm working on an assignment in operating system course on Xv6. I need to implement a data status structure for a process for its creation time, termination time, sleep time, etc...

As of now I decided to use the ticks variable directly without using the tickslock because it seems not a good idea to use a lock and slow down the system for such a low priority objective.

Since the ticks variable only used like so: ticks++, is there a way where I will try to retrieve the current number of ticks and get a wrong number?

I don't mind getting a wrong number by +-10 ticks but is there a way where it will be really off. Like when the number 01111111111111111 will increment it will need to change 2 bytes. So my question is this, is it possible that the CPU storing data in stages and another CPU will be able to fetch the data in that memory location between the start and complete of the store operation?

So as I see it, if the compiler will create a mov instruction or an inc instruction, what I want to know is if the store operation can be seen between the start and end of it.

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
Adam Jensen
  • 49
  • 1
  • 5
  • 1
    Beware of caching too. – Fred Larson Mar 25 '19 at 20:29
  • When an interrupt occurs, it is activated at the *end* of the currently executing instruction, and before the next one begins. – Weather Vane Mar 25 '19 at 20:31
  • 2
    Are you asking about *assembler* or about *c*? C semantics are not specified in terms of assembler instructions – Antti Haapala -- Слава Україні Mar 25 '19 at 20:36
  • @AnttiHaapala dosen't matter really, because what matter to me is just the storing of the data. i don't mind if the compiler separate the fetching and the storing. i want to be sure that the storing can't be seeing by another process before it completes. as i see it there will be one instruction for storing, i don't think the compiler will separate storing to a number of instructions so i'm ok at assuming that even if its not specified. – Adam Jensen Mar 25 '19 at 20:46
  • Using `tick` in a loop in C will let the compiler read it once and keep using the same value repeatedly. You need a `READ_ONCE` macro like the Linux kernel uses, e.g. `*(volatile int*)&tick`. But yes, for a variable narrow enough to fit in one integer register, it's generally safe to assume that a sane compiler will write it with a single dword store. With one writer and multiple readers, yes the readers can simply read it without any need for any kind of locking. – Peter Cordes Mar 25 '19 at 21:37
  • (working on an answer, but probably you just want to make `ticks` into `volatile unsigned ticks`. Related links: [Why is integer assignment on a naturally aligned variable atomic on x86?](//stackoverflow.com/q/36624881) / [MCU programming - C++ O2 optimization breaks while loop](//electronics.stackexchange.com/q/387181). With a single writer, you're right that you don't need atomic `inc`, just for the store part of it to be atomic. But see [Can num++ be atomic for 'int num'?](//stackoverflow.com/q/39393850) in case you're curious. – Peter Cordes Mar 26 '19 at 12:55
  • @PeterCordes thx, was very helpful – Adam Jensen Mar 26 '19 at 13:44

2 Answers2

1

There's no problem in asm: aligned loads/stores done with a single instruction on x86 are atomic up to qword (8-byte) width. Why is integer assignment on a naturally aligned variable atomic on x86?

(On 486, the guarantee is only for 4-byte aligned values, and maybe not even that for 386, so possibly this is why Xv6 uses locking? I'm not sure if it's supposed to be multi-core safe on 386; my understanding is that the rare 386 SMP machines didn't exactly implement the modern x86 memory model (memory ordering and so on).)

But C is not asm. Using a plain non-atomic variable from multiple "threads" at once is undefined behaviour, unless all threads are only reading. This means compilers can assume that a normal C variable isn't changed asynchronously by other threads.

Using ticks in a loop in C will let the compiler read it once and keep using the same value repeatedly. You need a READ_ONCE macro like the Linux kernel uses, e.g. *(volatile int*)&ticks. Or simply declare it as volatile unsigned ticks;

For a variable narrow enough to fit in one integer register, it's probably safe to assume that a sane compiler will write it with a single dword store, whether that's a mov or a memory-destination inc or add dword [mem], 1. (You can't assume that a compiler will use a memory-destination inc/add, though, so you can't depend on an increment being single-core-atomic with respect to interrupts.)

With one writer and multiple readers, yes the readers can simply read it without any need for any kind of locking, as long as they use volatile.

Even in portable ISO C, volatile sig_atomic_t has some very limited guarantees of working safely when written by a signal handler and read by the thread that ran the signal handler. (Not necessarily by other threads, though: in ISO C volatile doesn't avoid data-race UB. But in practice on x86 with non-hostile compilers it's fine.)

(POSIX signals are the user-space equivalent of interrupts.)

See also Can num++ be atomic for 'int num'?

For one thread to publish a wider counter in two halves, you'd usually use a SeqLock. With 1 writer and multiple readers, there's no actual locking, just retry by the readers if a write overlapped with their read. See Implementing 64 bit atomic counter with 32 bit atomics

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
0

First, using locks or not isn't a matter of whether your objective is low priority or not, but a matter of solving a race condition.

Second, in the specific case you describe, it will be safe to read ticks variable without any locks as this is not a race condition case because RAM access to the same region (even same address here) cannot be made by 2 separate CPUs simultaneously (read more) and because ticks writing only increments the value by 1 and not doing any major changes that you really miss.

Omer Efrat
  • 295
  • 1
  • 5
  • yea, you're right but i wanted to make sure i'm not resorting to locks because i fear there is a race condition. i prefer not to implement such a low priority objective with locks if there is a race condition. – Adam Jensen Mar 26 '19 at 21:33
  • Your reasoning that `++` would be safe without atomicity is wrong: *if* there was tearing between bytes of `ticks`, a reader could see big jumps and non-monotonic clock behaviour. e.g. during increment from `0x0001ffff` to `0x00020000`, a reader that reads the low half first could see `0x0002ffff`. Then soon after, see `0x00020001`, so time goes backwards. This is why both store by the producer and load by the consumer must be atomic. (Which it is on x86). The reason locking is used here is to work around C data-race undefined behaviour, but yes this is not a real race condition. – Peter Cordes Mar 26 '19 at 22:11
  • Or maybe the code uses locking to work correctly even with no guarantee of atomicity for `volatile unsigned int`. Not until C11 do we have language support for `atomic_load_explicit(&ticks, memory_order_relaxed);`. (You wouldn't want to use `ticks++` on `_Atomic unsigned ticks`, an atomic RMW is unneeded in a single-producer case.) – Peter Cordes Mar 26 '19 at 22:17