IoT e IoT Lab: tempo e stato nei sistemi distribuiti, Università Parthenope

IoT e IoT Lab

IoT and IoT Lab Time and state in a distributed system DİST ARTHENOPE UNIVERSITÀ DIPARTIMENTO DI SCIENZE E TECNOLOGIE loT and loT Lab - Prof. A. Ferone DEGLI STUDI UNIVERSITA' NAPOLI PARTHENOPE

Tempo e Stato

• Time and state are two key notions used in an operating system
• The OS needs to know the chronological order in which events such as resource requests occur, and it needs to know the states of resources and processes for performing resource allocation and scheduling

DİST loT and loT Lab - Prof. A. Ferone DIPARTIMENTO DI SCIENZE E TECNOLOGIE DEGLI STUDI UNIVERSITA' NAPOLI PARTHENOPE UNIVERSITÀ ARTHENOPE

Tempo e Stato nei Sistemi Convenzionali

• In a conventional computer system, presence of a single memory and a single CPU simplifies handling of time and state
• Only one event can occur at any time, so the OS knows the chronological order of events implicitly, and it knows states of all processes and resources in the system

DİST loT and loT Lab - Prof. A. Ferone DIPARTIMENTO DI SCIENZE E TECNOLOGIE DEGLI STUDI UNIVERSITA' NAPOLI PARTHENOPE UNIVERSITÀ ARTHENOPE

Tempo e Stato nei Sistemi Distribuiti

• A distributed system consists of several computer systems, each with a clock, memory, and one or more CPUs, that communicate through messages, which incur unpredictable communication delays
• Consequently, the distributed OS cannot know the chronological order in which events occur, or the states of resources and processes in all nodes of the system at the same instant of time

DİST loT and loT Lab - Prof. A. Ferone DEGLI STUDI UNIVERSITA' NAPOLI PARTHENOPE UNIVERSITÀ ARTHENOPE DIPARTIMENTO DI SCIENZE E TECNOLOGIE

Questioni Teoriche nei Sistemi Distribuiti

• The key theoretical issues in distributed systems are to evolve practical alternatives to the traditional notions of time and state
• Develop algorithms to implement these alternatives
• Show correctness of these algorithms

DİST loT and loT Lab - Prof. A. Ferone DIPARTIMENTO DI SCIENZE E TECNOLOGIE DEGLI STUDI UNIVERSITA' NAPOLI PARTHENOPE UNIVERSITÀ ARTHENOPE

Definizioni di Tempo e Stato

• Time is the fourth dimension: it indicates when an event occurred
• The state of an entity is the condition or mode of its being and depends on its features (e.g., the state of a memory cell is the value contained in it)
• If an entity is composed of other entities, its state contains the states of its component entities
• The global state of a system comprises the states of all entities in the system at a specific instant of time

DEGLI STUDI UNIVERSITA' DI NAPOLI PARTHENOPE ENOPE UNIVERSITÀ DİST loT and loT Lab - Prof. A. Ferone DIPARTIMENTO DI SCIENZE E TECNOLOGIE

Uso di Tempo e Stato in un OS

• An OS uses the notions of time and state for performing scheduling of resources and the CPU
• It uses time to know when a request event occurred, or to find the chronological order in which request events occurred, and it uses the state of a resource to decide whether it can be allocated
• A distributed OS also uses these notions in recovery to ensure that processes of a distributed computation would be in mutually consistent states after recovery from the crash of a node that contained some of the processes

DİST ARTHENOPE UNIVERSITÀ DIPARTIMENTO DI SCIENZE E TECNOLOGIE loT and loT Lab - Prof. A. Ferone DEGLI STUDI UNIVERSITA' DI NAPOLI PARTHENOPE

Gestione di Tempo e Stato in un OS Uniprocessore

• It is easy to handle time and state in a uniprocessor OS
• The system has a clock and a single CPU, so the OS can find the times at which processes made their resource requests and use this information to determine their chronological order
• However, a typical conventional operating system uses the notion of time only implicitly
• When an event occurs, it adds information about the event to a queue, so the queue shows the chronological order of events
• The OS also knows states of processes, and the states of all physical and logical resources.

DİST ARTHENOPE UNIVERSITÀ DIPARTIMENTO DI SCIENZE E TECNOLOGIE loT and loT Lab - Prof. A. Ferone DEGLI STUDI UNIVERSITA' DI NAPOLI PARTHENOPE

Gestione di Tempo e Stato in un OS Distribuito

• In a distributed system, each node is a computer system with its own clock and a local memory, and nodes are connected by communication links which have unpredictable communication delays
• Consequently, a node cannot precisely determine the time at which an event occurred in another node; its perception of the state of a remote process or resource may also be stale
• Thus, a distributed OS cannot use the notions of time and state in the same manner as a uniprocessor OS.

DEGLI STUDI UNIVERSITA' NAPOLI PARTHENOPE ARTHENOPE UNIVERSITÀ DİST loT and loT Lab - Prof. A. Ferone DIPARTIMENTO DI SCIENZE E TECNOLOGIE

Stati Locali e Globali

• Each entity in a system has its own state
• The state of a memory cell is the value contained in it
• The state of a CPU is the contents of its PSW and general- purpose registers
• The state of a process is its state tag - state of the memory allocated to it - the CPU state if it is currently scheduled on the CPU, or contents of PCB fields if it is not scheduled on the CPU - the state of its interprocess communication, which consists of information concerning the messages received and sent by it

DİST DIPARTIMENTO DI SCIENZE E TECNOLOGIE loT and loT Lab - Prof. A. Ferone DEGLI STUDI UNIVERSITA' NAPOLI PARTHENOPE UNIVERSITÀ ARTHENOPE

Definizione di Stati Locali e Globali

• The state of an entity is called a local state
• The global state of a system at time instant t is the collection of local states of all entities in it at time t
• Considering multiple processes: - Local state of a process Pk at time t: Stk - Global state of a system at time t: St - For a system with n processes P1, ... , Pn: St={st1, ... , stn}

DİST UNIVERSITÀ ARTHENOPE DIPARTIMENTO DI SCIENZE E TECNOLOGIE loT and loT Lab - Prof. A. Ferone DEGLI STUDI UNIVERSITA' NAPOLI PARTHENOPE

Eventi

• An event could be the sending or receiving of a message over a channel, which is an interprocess communication path, or some other happening that does not involve a message
• The state of a process changes when an event occurs in it
• We represent an event as follows: (process id, old state, new state, event description, channel, message)
• Es .: e ;= (Pk , s, s', send, c, m)
• The event is the sending of a message m over a channel c. When this event occurs, process Pk enters the new state s' Event ei Old state of Pk s s' New state of Pk

DİST loT and loT Lab - Prof. A. Ferone DEGLI STUDI UNIVERSITA NAPOLI PARTHENOPE UNIVERSITÀ ARTHENOPE DIPARTIMENTO DI SCIENZE E TECNOLOGIE

Orologio Globale

• Let a global clock be an abstract clock that can be accessed from different sites of a distributed system with identical results
• If processes in two nodes of a distributed system perform the system call "give current time" at the same time instant, they would obtain identical time values
• If they perform these system calls 6 time units apart, they would obtain time values that differ by exactly 8 time units
• A global clock cannot be implemented in practice because of communication delays
• Requests for current time made in two different nodes at the same time instant would face different communication delays to reach the site where the clock is maintained

DİST UNIVERSITÀ PARTHENOPE DIPARTIMENTO DI SCIENZE E TECNOLOGIE loT and loT Lab - Prof. A. Ferone DEGLI STUDI UNIVERSITA' I NAPOLI PARTHENOPE

Precedenza degli Eventi

• Let two events e1 and e2, the notation e1 > e2 is used to indicate that event e1 precedes event e2 in time
• Considering the precedes relation: - A total order w.r.t. - all events that can occur in a system can be ordered - A partial order w.r.t. - at least two events exist that cannot be ordered

DEGLI STUDI UNIVERSITA' NAPOLI PARTHENOPE UNIVERSITÀ DIPARTIMENTO DI SCIENZE E TECNOLOGIE loT and loT Lab - Prof. A. Ferone DİST ARTHENOPE

Ordinamento degli Eventi

• Category Description of rule

• Events within a process The OS performs event handling, so it knows the order in which events occur within a process.

• Events in different processes In a causal relationship, i.e., a cause-and-effect relationship, an event that corresponds to the cause precedes an event in another process that corresponds to the effect.

• Transitive precedence The precedes relation is transitive; i.e., e1 -> e2 and e2 -> e3 implies e1 -> e3.

UNIVERSITÀ DİST ARTHENOPE DIPARTIMENTO DI SCIENZE E TECNOLOGIE loT and loT Lab - Prof. A. Ferone DEGLI STUDI UNIVERSITA' NAPOLI PARTHENOPE

Relazione tra Eventi

• Es .:
• event e : P2 executes "send P3, <message m;>"
• event e2: P3 "receives message m;"
• e1 > e2
• e1 and e2 have a causal relationship
• Es .:
• event eo: P2 "receives message mi"
• e0 e 1
• e1 e2
• eo e2 (transitive precedence)

PARTHENOPE DİST DIPARTIMENTO DI SCIENZE E TECNOLOGIE loT and loT Lab - Prof. A. Ferone DEGLI STUDI UNIVERSITA' NAPOLI PARTHENOPE

Classificazione della Precedenza tra Eventi

• Precedence between any two events (e), e;) can be classified as follows:
• e; precedes e; if events ek and e; exist such that - ex > e - e; ekoe =ek - e| Dejo el Fej
• e; follows e; if events eg and en exist such that - eg 2 en - ej Degoejeg - en Dejo en =ei
• e; and e; are concurrents if e; neither precedes nor follows e;

DİST PARTHENOPE DIPARTIMENTO DI SCIENZE E TECNOLOGIE loT and loT Lab - Prof. A. Ferone DEGLI STUDI UNIVERSITA I NAPOLI PARTHENOPE

Diagramma di Temporizzazione

• A timing diagram is a plot of the activities of different processes against time
• Processes are marked along the vertical axis in the plot, and time is marked along the horizontal axis
• The notation ekn identifies event en in the process Pk e 11 € 12 e 13 P1 m1 P2 e 21 e 22 €23 e 24

DEGLI STUDI UNIVERSITA' NAPOLI PARTHENOPE UNIVERSITÀ ARTHENOPE DİST DIPARTIMENTO DI SCIENZE E TECNOLOGIE loT and loT Lab - Prof. A. Ferone

Esempio di Diagramma di Temporizzazione

• The previous image shows event that occur in two processes P1 and P2
• Event e23 is a "send" event of message m1
• Event e 12 is a "receive" event for message m1

• e 23 e 12

• For the transitivity - e 22 e 12 - e21 e 12 - @ 22 e 13 - e 21 e 13
• Event e 11 is concurrent with events e 21 e 22 € 23 € 24

DEGLI STUDI UNIVERSITA' NAPOLI PARTHENOPE UNIVERSITÀ ARTHENOPE DİST loT and loT Lab - Prof. A. Ferone DIPARTIMENTO DI SCIENZE E TECNOLOGIE