INTRODUCCIÓN

1. PROPIEDADES

1.1. VIVACIDAD Y ESTANCAMIENTO

1.1.1. Secuencia de disparo INFINITA O FINITA

1.1.1.1. (termina la secuencia? )

1.1.2. LIMITADA

1.1.2.1. cada lugar tiene un MAX finito de tokens. Es "estrucuralmente marcada" si para todo marcado inicial la RDP es limitada

1.1.3. SEGURA

1.1.3.1. Cada lugar tiene 0 o 1 toquen

1.1.4. SEUDO VIVA

1.1.4.1. PARTE DE LA RED ESTA VIVA Y OTRA MUERTA Existen transiciones que quedan vivas, y otras que se disparan o una unas veces y luego mueren

1.1.5. QUASI VIVA

1.1.5.1. Todas las transiciones de disparan al menos una vez.

1.1.6. LIBRE DEADLOCK

1.1.6.1. DEADLOCK: para una MARCA en la cual no se puede ejecutar ninguna transicion (el token no evoluciona)

1.1.7. LIVENESS

1.1.7.1. Todas las transiciones en todo momento existe una secuencia que pueden dispararse .

1.1.8. REVERSIBLE

1.1.8.1. Tiene un HOME STATE, es decir siempre puede volver al marcado inicial

1.2. CONFLICTO

1.2.1. ESTRUCTURAL

1.2.1.1. DOS TRANSICIONES con una PLAZA en comun

1.2.2. EFECTIVO

1.2.2.1. conflicto estructural donde el numero de tokens es menor al numero de transiciones del conflicto

1.2.3. MULTIPLE DISPARO

1.2.3.1. conflicto donde el numero de tokens abastece todas las transiciones (se pueden disparar paralelamente)

1.2.4. GENERAL

1.2.4.1. Cuando las transiciones de un conflicto se PUEDEN disparar simultáneamente, pero no todas en su grado de habilitación

1.3. CONCURRENTE

1.3.1. Transicion concurrente: es cuando dos transiciones independientes entre si, o unidas a un conflicto, PUEDEN dispararse simultaneamnte, o antes y despues

1.4. PERSISTENTE

1.4.1. Si por cada par de transiciones habilitadas, el disparo de una no me desactiva la otra, es decir pueden ejecutarse UNA TRANSICION HABILITADA SOLO SE DESACTIVA POR SU PORPIO DISPARO

1.5. GRADO DE HABILITACIÓN

1.5.1. Numero de disparos que se PUEDE disparar UNA transición concurrentemente

1.6. INVARIANTES

1.6.1. COMPONENTE CONSERVATIVO

1.6.1.1. INVARIANTE DE PLAZA: La suma de tokens en un conjunto de lugares (circuito) siempre es constante

1.6.1.2. RDP CONSERVADORA

1.6.1.2.1. estructuralmente acotada : invariante de plaza que abarca toda la red

1.6.2. COMPONENTE REPETITIVO

1.6.2.1. INVARIANTE DE TRANSICIÓN: existe una o mas secuencias que se ejecutan infinitamente, (un CICLO)

1.6.2.2. RDP CONSISTENTE

1.6.2.2.1. estructuralmente repetititvo: Cuando la secuencia de disparo de la red entera siempre es la misma, siempre reacciona igual infinitamente

1.7. DIAGRAMAS: buscar propiedades

1.7.1. grafo de marcado

1.7.1.1. arcos: disparos nodos/vertices: marcado

1.7.1.2. no se puede dibujar cuando el numero de marcas alcanzables es infinito

1.7.2. raiz del arbol de cobertura

1.7.2.1. sirve cuando el marcado alcanzable es infinito

1.7.2.2. remplaza a la marca mi por W (macro marca) cuando esta AUMENTA , y simboliza el conjunto de marcas posibles que puede o no ser infinito

1.7.2.3. No se puede conocer con exactitud todas las marcas alcanzables ya que están enmascaradas con W

2. GRAMATICAS Y LENGUAJE

3. DIFERENCIAS

3.1. Es mas simpley rápido cambiar de un hilo a otro dentro del mismo proceso, que cambiar de un proceso a otro

3.2. •Los procesos son –generalmente– independientes, VS •Los hilos generalmente comparten otros recursos de forma directa.

3.3. • Al cambiar de un proceso a otro, el sistema operativo, (mediante el dispatcher) genera lo que se conoce como overhead, que es tiempo desperdiciado por el procesador para realizar un cambio de contexto (context switch), VS •El tiempo de espera del cambio de hilos es despreciable

3.4. Si bien los hilos son generados a partir de la creación de un proceso, podemos decir que un proceso LIVIANO es un hilo de ejecución, conocido como Monohilo. O un proceso puede tener multiples hilos en ejecución que pueden ser cooperativas o no entre sí

3.5. La comunicación entre procesos debe intervenir el núcleo para ofrecer protección de los recursos y realizar la comunicación misma, la comunicación entre hilos no requiere nucleo.

4. PROCESO

4.1. "Una unidad de actividad que se caracteriza por la ejecución de una secuencia de instrucciones, un estado actual, y un conjunto de recursos del sistema asociados“

4.2. Un proceso es un programa en ejecución

4.3. Un proceso simple TIENE un hilo de ejecución (concepto de hilo)

4.3.1. El proceso sigue en ejecución mientras al menos uno de sus hilos de ejecución siga activo.

4.4. un proceso es una ACTIVIDAD de cierto tipo que contiene: un PROGRAMA, ENTRADAS Y SALIDAS Y ESTADOS

4.5. ESTADO

4.5.1. Inactivo(memoria secundaria)

4.5.1.1. Suspendido bloqueado:

4.5.1.1.1. Es el proceso que fue suspendido en espera de un evento, sin que hayan desaparecido las causas de su bloqueo.

4.5.1.2. Suspendido programado:

4.5.1.2.1. Es el proceso que han sido suspendido, pero no tiene causa parta estar bloqueado.

4.5.2. Activo (memoria principal)

4.5.2.1. Ejecución/Running

4.5.2.1.1. Estado en el que se encuentra un proceso cuando tiene el control del procesador. En un sistema monoprocesador este estado sólo lo puede tener un proceso.

4.5.2.2. Preparado/Ready

4.5.2.2.1. Aquellos procesos que están dispuestos para ser ejecutados, pero no están en ejecución por alguna causa (Interrupción, haber entrado en cola estando otro proceso en ejecución, etc.).

4.5.2.3. Bloqueado/waiting:

4.5.2.3.1. Son los procesos que no pueden ejecutarse de momento por necesitar algún recurso no disponible (generalmente recursos de entrada/salida BLOCKING, o esperando un recuso en una cola WATING, o durmiendo SLEEPING).

4.5.3. new

4.5.3.1. el proceso esta siendo creado, no se termino de cargar en la memoria primncipal pero existe

4.5.4. Terminated

4.5.4.1. el proceso terminó, y es ZOMBIE si todavia no fue limpiado de la memoria

4.6. CONTROL

4.6.1. Es un registro especial BCP (bloque de control de procesos)donde el sistema operativo agrupa toda la información que necesita conocer respecto a un proceso particular

4.6.2. Identificador del proceso (Process Identificator -PID-, de sus siglas en Inglés).

4.6.3. Estado del proceso. Por ej. listo, en espera, bloqueado.

4.6.4. Contador de Programa: Dirección de la próxima instrucción a ejecutar.

4.6.5. Valores de registro de CPU. Se utilizan también en el cambio de contexto.

4.6.6. Espacio de direcciones de memoria.

4.6.7. Prioridad en caso de utilizarse dicho algoritmo para planificación de CPU.

4.6.8. Lista de recursos asignados (incluyendo descriptores de archivos y sockets abiertos).

4.6.9. Estadísticas del proceso.

4.6.10. Datos del propietario (owner).

4.6.11. Permisos asignados.

4.6.12. Signals pendientes de ser servidos. (Almacenados en un mapa de bits)

5. Dijikstra

5.1. "No hay que apresurarse a codificar, eso lo vuelve muy costoso, primero hay que pensar"

5.2. Software= Producto abstracto

5.3. (ALGOL60), escribió el primer compilador

5.4. 1965 introdujo el "problema de la exclusión mutua" Y "La sección crítica"

5.5. diseñaron e implementaron el sistema operativo THE, que estaba organizado en capas claramente identificadas.

5.6. 1968 Dijkstra publicó su famoso artículo "Procesos secuenciales de cooperación"

5.7. Propuso el semáforo

5.8. • Identificó el "problema del dead-lock" y propuso un elegante "algoritmo de Banker"

5.9. Ilustro el problema del dead-lock con el problema de los filósofos que Condujo al concepto del monitor

5.10. • Dio origen a uno de los principales enfoques de la computación tolerante a las fallas "Sistemas autoestabilizadores a pesar del control distribuido

5.11. En 1976 publicó A Discipline of Programming (Una disciplina de programación), que presentaba su método de desarrollo sistemático de programas junto con sus pruebas de corrección

6. SISTEMAS

6.1. TIPOS

6.1.1. SISTEMAS REACTIVOS

6.1.1.1. Interactúan con el ambiente en el tiempo

6.1.1.2. En muchos casos, éstos no computan resultados, y suele no requerirse que terminen. O Ejemplos de sistemas reactivos son: sistemas operativos, software de control, hardware, etc.

6.1.2. SISTEMAS FUNCIONALES O TRANSORMACIONALES

6.1.2.1. no interactúan con el ambiente

6.2. MODELOS

6.2.1. MAQUINA DE ESTADOS

6.2.1.1. • Hay que notar que la representación gráfica de las máquinas de estado, limita seriamente la complejidad de los problemas que se pueden abordar.

6.2.2. REDES DE PETRI

6.3. Testing y Simulación

6.3.1. “El testing puede confirmar la presencia de errores pero nunca garantizar su ausencia”

6.3.2. VERIFICACIÓN SEMI AUTOMÁTICA

6.3.2.1. Existen serias limitaciones en lo que respecta a la verificación automática de software.

6.3.2.1.1. Por ejemplo, el problema de decidir si un programa dado termina o no o no es computable.

6.3.2.2. Sin embargo, si imponemos algunas restricciones sobre las propiedades que queremos verificar, algunas tareas podrán verificarse automáticamente sobre el sistema

6.3.2.2.1. eJ: MODELCHEKING

6.4. Semantica

6.4.1. sistemas de transición de estados

6.4.1.1. Un sistema de transición de estados es un grafo dirigido (S,S0,->)

6.4.1.2. 𝑆 𝑒𝑠 𝑒𝑙 𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑒 𝑒𝑠𝑡𝑎𝑑𝑜𝑠/nodos • 𝑠0 𝑒𝑠 𝑒𝑙 𝑒𝑠𝑡𝑎𝑑𝑜/nodo 𝑖𝑛𝑖𝑐𝑖𝑎𝑙 • 𝑅𝑒𝑙𝑎𝑐𝑖𝑜𝑛 𝑑𝑒 𝑇𝑟𝑎𝑛𝑠𝑖𝑐𝑖ó/ aristas

6.5. SISTEMAS CRÍTICOS

6.5.1. Son sistemas, cuyas fallas pueden ocasionar daños de gran importancia, incluyendo pérdida de vidas humanas, catástrofes ecológicas, grandes pérdidas financieras, etc.

7. PROGRAMAS CONCURRENTES

7.1. Los programas concurrentes deben, en general, colaborar para llegar a un objetivo común, para lo cual la sincronización entre procesos es crucial.

7.2. problemas comunes

7.2.1. Violación de propiedades universales (invariantes)

7.2.2. Starvation (inanición): Uno o más procesos quedan esperando por mas tiempo del debido por un mensaje o la liberación de un recurso

7.2.3. Deadlock: dos o más procesos esperan mutuamente el avance del otro

7.2.4. Problemas de uso no exclusivo de recursos compartidos

7.2.5. Livelock: Dos o más procesos no pueden avanzar en su ejecución porque continuamente responden a los cambios en el estado de otros procesos

7.3. INTERLEAVING

7.3.1. ¿COMO SE EJECUTAN LOS PROCESOS CONCURRENTES? Los procesos concurrentes se ejecutan intercalando las acciones atómicas que los componen.

7.3.1.1. (A,1)-> (A,2) ó (B,1) -> (B,2)

7.3.1.2. El orden en que se ejecutan las acciones atómicas no puede decidirse en general, y un mismo par de procesos puede tener diferentes ejecuciones

7.3.1.3. Por cada sentencia atómica tenemos una transición.

7.3.1.4. El espacio de estados crece exponencialmente con el número de componentes y variables.

7.3.2. El número de interleavings posibles, por su parte, es en general muy grande POR LO QUE ES AVECES ES IMPOSIBLE DE TEATEAR Y LLEGAR AL OVERFLOW

8. HILOS

8.1. COMPARTEN

8.1.1. Si un mismo proceso compartan los recursos hace que cualquiera de sus hilos pueda modificarlos

8.1.2. Los hilos de ejecución que comparten los mismos recursos, y estos recursos, son en conjunto conocidos como un proceso

8.1.2.1. El proceso sigue en ejecución mientras al menos uno de sus hilos de ejecución siga activo.

8.2. Permite a una aplicación realizar varias tareas a la vez(concurrentemente).

8.3. PROPIO

8.3.1. contador de programa

8.3.2. la pila de ejecución

8.3.3. el estado de la CPU ->

8.3.4. -> (incluyendo el valor de los registros) Espacio de almacenamiento estático donde almacenará las variables

8.4. ESTADOS

8.4.1. Creación

8.4.1.1. Cuando se crea un proceso se crea un hilo para ese proceso.

8.4.1.2. Luego, este hilo puede crear otros hilos dentro del mismo proceso.

8.4.1.3. El hilo tendrá su propio contador, registros, espacio de pila, y pasara a la cola de listos.

8.4.2. Bloqueo

8.4.2.1. Cuando un hilo necesita esperar por un suceso, se bloquea (salvando sus registros de usuario, contador de programa y punteros de pila).

8.4.2.2. Ahora el procesador podrá pasar a ejecutar otro hilo que esté en la cola de Listos mientras el anterior permanece bloqueado.

8.4.3. Desbloqueo

8.4.3.1. Cuando el suceso por el que el hilo se bloqueó se produce, el mismo pasa a la cola de Listos.

8.4.4. Terminación

8.4.4.1. Cuando un hilo finaliza se liberan tanto su contexto como sus pilas.

9. Programas: Paralelismo y Concurrencia

10. redes de pretri

10.1. Es un modelo eficaz para visualizar los comoportamientos de l paralelismo y concurrecia

10.2. COMPONENTES

10.2.1. plazas

10.2.2. transiciones

10.2.3. arcos (pre T y pos T)

10.2.4. tokens (forman el marcado)

10.3. MARCADO: es el conjunto de tokens asociados a una una plaza en un momento dado

10.4. DISPARO: es la transicion de un estado a otro, este es ATOMICO, es decir o esta completo o no se ejecuta

10.5. CONCEPTOS MODELADOS

10.5.1. CONFLICTO

10.5.1.1. SIMPLE

10.5.1.2. SIMETRICO

10.5.1.3. ASIMETRICO (potencial)

10.5.2. CONCURRENCIA

10.5.3. SINCRIONIZACIÓN (->1T)

10.5.4. FUSION (->1P)

10.5.5. LECTOR Y ESCRITOR EN EXCLUSIÓN MUTUA

10.5.6. PRIORIDAD (con arco inhibidor)

10.5.7. RECURSO COMPARTIDO Y EXCLUSIÓN MUTUA

10.5.8. BUFFER O MEMORIA DE DISPARO

10.5.9. PRECENCIA

10.5.10. CAPACIDAD LIMITADA

10.6. EXTENSIONES

10.6.1. con capacidad finita de plaza

10.6.2. con prioridad en transiciones de conflictos

10.6.3. extensión de arcos

10.6.3.1. inhibidor

10.6.3.1.1. se sensibiliza si NO hay tokens

10.6.3.2. lector

10.6.3.2.1. se sensibiliza si hay tokens pero no se consumen

10.6.3.3. reset

10.6.3.3.1. consume todos los tokens al disparar

10.6.4. No automatas

10.6.4.1. es decir que la condición de sensibilizado de la transición puede estar ligada a un evento externo como el tiempo

10.6.4.1.1. GUARDAS

10.6.4.1.2. EVENTO

10.6.4.1.3. TIEMPO

10.6.5. continuas

10.6.5.1. en vez de tener un numero entero positivo en la cantidad de tokens tenemos un FLUJO, es decir va a ser un numero REAL positivo

10.6.6. HIBRIDAS

10.6.6.1. combinación de continuas y discretas en una misma red

10.7. TIPOS-CARACTERÍSTICAS

10.7.1. ORDINARIA

10.7.1.1. es la red original sin nada extra, los pesos de los arcos es 1, es automata , discreta, sin prioridad ni nada.

10.7.2. ESPECIALES

10.7.2.1. SIMPLE

10.7.2.1.1. cada TRANSICIÓN puede verse afectada para UN ÚNICO CONFLICTO

10.7.2.2. LIBRE ELECCIÓN

10.7.2.2.1. Para todas las transiciones de un conflicto poceen unicamente 1/+ lugar de entrada que es el mismo.

10.7.2.3. MAQUINA DE ESTADO

10.7.2.3.1. por CADA TRANSICION tiene una unico Lugar entrada y salida (equivalente a un automata) (no hay concurrencia, si puede haber conflicto)

10.7.2.4. LIBRE DE CONFLICTO

10.7.2.4.1. Para cara plaza puede haber una sola transicion de salida

10.7.2.5. GRAFO DE EVENTO

10.7.2.5.1. por cada LUGAR/PLAZA tiene una unica Transicion de entrada y salida (NO HAY CONFLICTO pero puede haber concurrencia)

10.7.2.6. PURA

10.7.2.6.1. si no tiene un AUTO LOOP

10.8. ALGEBRA

10.8.1. Matriz de Incidencia

10.8.1.1. W= (W+) - (W-)

10.8.1.1.1. Matriz de pesos de entrada a Transiciones menos pesos de salida de Transiciones

10.8.2. ECUACIÓN fundamental

10.8.2.1. mo = mi+W*s

10.8.2.1.1. mi=marcado en instante i s=vector de disparos W=Matriz de incidencia mo=marcado despues de "s"

10.8.3. Invariante de Plaza

10.8.3.1. Xt*W=0

10.8.3.1.1. Xt= vector traspuesto donde vale 1 en las plazas del invariate. (Se puede obtener reducinedo la matriz W -> I*W

10.8.4. Invariante de Transicion

10.8.4.1. W*s=0

10.8.4.1.1. s= invariante de transicion

10.8.5. T. SENSIBILIZADA

10.8.5.1. Mi+Wn >=0

10.8.5.1.1. arco normal

10.8.5.2. C*Wi>0

10.8.5.2.1. arco inhibidor

10.8.5.3. U*Wl>0

10.8.5.3.1. arco lector

10.8.5.4. G*Wg>0

10.8.5.4.1. guarda

10.8.5.5. E*We>0

10.8.5.5.1. eventos

10.8.5.6. T*Wt>0

10.8.5.6.1. tiempo

10.8.5.7. R*Wr>0

10.8.5.7.1. reset

10.8.6. MARCADO

10.8.6.1. Mi+1=Mi+W*(disp*Ex)#A,

10.8.6.1.1. con # multiplicacion elemento a elemento

10.8.6.1.2. Ex = multiplicacion de todas las opciones de sencibilizado (indicadas arriba)

10.8.6.1.3. A=numero de disparos por el reset= Marca(Wr*Mi)

10.9. RDP TEMPORAL

10.9.1. Tipos

10.9.1.1. RDP con delay

10.9.1.2. RDP con tiempo

10.9.2. SEMANTICA DE TIEMPO

10.9.2.1. DÉBIL

10.9.2.1.1. Una transición PUEDE o no dispararse, y si se dispara deberá ser en un [INTERVALO] de tiempo dado

10.9.2.2. FUERTE

10.9.2.2.1. (ininterrumpible) Cuando la transicion se secibiliza por tokens, estos son absorvidos y luego de pasar "X tiempo " se disparan

10.9.3. tipos de transiciones

10.9.3.1. CODE

10.9.3.1.1. ejecuta un codigo al sencibilizarce, [alfa,beta]

10.9.3.2. TIME

10.9.3.2.1. transicion asociada a una actividad temporal, (timeOut, act periodica, etc) [alfa, beta]

10.9.3.3. SYCO

10.9.3.3.1. disparo inmediato [0,0]

10.9.4. Sub Clases

10.9.4.1. Time Environmet Relationship nets

10.9.4.1.1. los tokens guardan valores, como la de CHRONOS: que funcona como "time stamp". El disparo de la transicion esta condicionado al valor de chronos

10.9.4.2. Time basic nets

10.9.4.2.1. Caso aprticular de los TER, donde la unca variable que puede almacenar los tokes es la de chronos

11. INDEPENDIENTE

12. DEPENDIENTE

13. MONITORES

13.1. Es un mecanismo de software (instancia de una clase) que permite el acceso seguro a múltiples thread de recursos compartidos

13.2. CLASIFICACIÓN

13.2.1. SEÑALES (signal/resume)

13.2.1.1. IMPLICITA

13.2.1.1.1. Es un monitor de señal automática, que no tiene ninguna declaración: NO HAY COLAS DE CONDICIÓN, es una sola cola de espera ademas de la cola de entrada, la cual se chequea, cuando un proceso sale del monitor. pero LAS AFIRMACIONES SON CODIFICADAS DE FORMA EXPLICITA

13.2.1.2. EXPLICITA

13.2.1.2.1. Es un monitor con una declaración explícita de la variable señal

13.2.2. PRIORIDAD

13.2.2.1. prioridad a la cola de cortesía

13.2.2.2. prioridad a la cola de condición

13.2.2.3. prioridad a la cola de entrada

13.3. ELEMENTOS

13.3.1. VARIABLES LOCALES

13.3.1.1. variables que almacenan el estado interno del recurso

13.3.1.2. variables de condición(colas)

13.3.1.2.1. operaciones

13.3.2. CONSTRUCTOR

13.3.2.1. código de inicialización

13.3.3. MÉTODOS

13.3.3.1. deben ejecutarse en exclusión mutua

13.4. política

13.4.1. Resume-and-Exit (RE)

13.4.1.1. el proceso reactivador sale del monitor y entra el reactivado (RESUME se ejecuta antes de salir, al último)

13.4.2. Resume-and-Wait (RW)

13.4.2.1. El proceso reactivador ejecuta la funcion resume al principio y si hay hilos esperando, me voy a la cola de ENTRDA, y doy prioridad al proceso despertado

13.4.3. Resume-and-Urgent-Wait (RUW)

13.4.3.1. El proceso reactivador ejecuta el RESUME cuando entra y le da prioridad a al proceso despertado y me voy a una cola ESPECIAL (con mayor prioridad que la cola de entrada)

13.4.4. Resume-and-Continue (RC)

13.4.4.1. El proceso reactivador ejecuta el RESUME al principio y sigue ejecutando el monitor y el despertado se va a la cola de entrada