Fischer's protocol id- shared variable each process has it's own timer(for delaying) for correctness it is necessary that K2> Kl Pr rocess 1 while(true) <noncritical section> while id!=0 do i delay kl id delay k2 if (id=i <critical section> d:=0
Fischer's Protocol ◼ id — shared variable ◼ each process has it's own timer (for delaying) ◼ for correctness it is necessary that K2 > K1 Process i: while (true) { <noncritical section>; while id != 0 do {} delay K1; id := i; delay K2; if (id = i) { <critical section>; id := 0; } }
Modeling real Time systems ■ Two models of time o discrete time domain o continuous time domain
Modeling Real Time Systems ◼ Two models of time: discrete time domain continuous time domain
Discrete Time domain a clock ticks at regular interval at each tick something may happen between ticks -the system only waits
Discrete Time Domain ◼ clock ticks at regular interval ◼ at each tick something may happen ◼ between ticks — the system only waits
Discrete Time domain choose a fixed sample period 8 all events happen at multiples of e simple extension of classical models ■ main disadvantage— how to choose? obig→ too coarse model o low 8= time fragmentation, too big state space usage: particularly synchronous systems(hardware circuits
Discrete Time Domain ◼ choose a fixed sample period ε ◼ all events happen at multiples of ε ◼ simple extension of classical models ◼ main disadvantage — how to choose ε ? big ε too coarse model low ε time fragmentation, too big state space ◼ usage: particularly synchronous systems (hardware circuits)
Continuous time domain time is modeled as real numbers delays may be arbitrarily small more faithful model, suited for asynchronous systems uncountable state space = cannot be directly handled automatically by brute force
Continuous Time Domain ◼ time is modeled as real numbers ◼ delays may be arbitrarily small ◼ more faithful model, suited for asynchronous systems ◼ uncountable state space cannot be directly handled automatically by “brute force