效绵鼎 Fischer's Protocol id -shared variable each process has it's own timer (for delaying) for correctness it is necessary that K2 >KI Process i: while (true){ <noncritical section>; while id !=0 do delay K1; id :i; delay K2; if (id =i){ <critical section>; id=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: 0 discrete time domain continuous time domain
Modeling Real Time Systems ◼ Two models of time: discrete time domain continuous time domain
效绵鼎 Discrete Time Domain 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 s all events happen at multiples of s simple extension of classical models main disadvantage -how to choose s bige→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