Wiki de Sistemas Operativos - Contribuciones del usuario [es]

Página con listado de personas que han contribuido

2012-01-28T17:56:20Z

Sertrimur:

A continuación, la lista de usuarios/as de la Universidad de Sevilla que han contribuido a la wiki. Si ponéis tu usuario/a estás solicitando al profesor que evalúe tus contribuciones a la wiki para la subida de notas de hasta 2 puntos posible:

* luigarhor
* rafperper
* sergaralo
* josalgrod1
* felgaroje
* luimunlei
* [https://1984.lsi.us.es/wiki-ssoo/index.php/Usuario:Lorruimor Lorruimor]
* albsolnog
* framorexp
* javgarang
* FerGuaTol
* jesgonbel
* fraperdom
* antdomflo
* antmorzam
* migoligon
* danplaseg
* peducemar
* danescsan
* sertrimur

Índices de evaluación

2012-01-28T17:51:23Z

Sertrimur: /* ¿Cómo se evalúa un criterio de planificación? */

= ¿Cómo se evalúa un criterio de planificación? =

En base a los siguientes parámetros:

* '''Throughput''' (tasa de transferencia, en castellano), indica la cantidad de procesos en estado activo por unidad de tiempo. Un throughput alto es un indicador de un buen planificador (se mide en nºprocesos/segundo).
* '''Latencia''', indica el tiempo que tarda un planificador de procesos en seleccionar qué proceso pasa a estado activo. Si el planificador toma mucho tiempo en decidir qué proceso pasa a estado activo, se dice que la latencia será alta (se mide en segundos).

Un buen planificador ofrecerá un throughput alto y una latencia baja.

Además, existen otros índices que nos permiten evaluar el planificador:

* '''Tiempo de ejecución''' (tejecución): Unidades de tiempo que requiere el proceso para finalizar su ejecución.
* '''Tiempo de terminación''' (Tterminación): Diferencia entre el instante de lanzamiento y el instante de terminación.
* '''Tiempo perdido''': T-t . Es el tiempo durante el cual un proceso no está asignado al procesador.
* '''Tiempo de inactividad''': Tiempo durante el cual el procesador está ocioso (''idle'', en inglés), es decir, que no tienen ningún proceso asignado.
* '''Tiempo del sistema''': Tiempo empleado por el [[planificador de procesos|planificador]] para la conmutación de procesos.
* '''Tiempo de espera''': Tiempo desde el instante de lanzamiento hasta que el proceso pasa a estado preparado (se suele despreciar).
* '''Índice de penalización''': <math>\frac{T}{t} = \frac{H_f-H_0}{t} = x</math>. Indica que un proceso ha tardado x-1 veces más en ejecutarse que si hubiera tenido el procesador en exclusividad y sin que se hubiese producido ningún bloqueo. Nótese que el índice de penalización crece rápidamente para procesos cuyo tiempo de ejecución es pequeño, mientras que para procesos con tiempo de ejecución mayores, lo hace de manera más suave.

Suponga el siguiente ejemplo, en el que hay dos procesos <math>P_x</math> y <math>P_y</math>, para ilustrar los índices definidos:

< indica que el proceso está preparado
> indica que el proceso ha finalizado su ejecución
$ indica que al proceso se le ha retirado el procesador
X indica la ejecución del planificador para la conmutación

| | | | | | |
Px <---|---$ |---> | |
Py | | <---> | | |
planificador | | X X | | |
|___|___|___|___|___|___|___
0 1 2 3 4 5 6

tiempo ->

Para el proceso Px:

* t = 3 : Indica que el proceso Px requiere 3 unidades de tiempo para ejecutarse.
* T = 4 : unidades de tiempo desde que se lanza hasta que se finaliza el proceso Px
* T-t = 1 : unidades de tiempo durante la cual el proceso Px no está asignado al procesador, por tanto, no progresa en su actividad.
* x = 4/3 = 1.34 : el proceso Px ha tardado un 34% de tiempo más en ejecutarse que si lo hubiera tenido en exclusividad (al tener que haber que compartido el procesador con Py).

En el ejemplo anterior, los tiempos de espera y del sistema se suponen despreciables (en la práctica no lo son, aunque son muy pequeños con respecto a los ilustrados).

Ejercicios fundamentos Sistemas Operativos

2012-01-28T17:49:42Z

Sertrimur: /* Ejercicio 1 */ entre

== Ejercicio 1 ==
''[Este ejercicio fue parte del Primer Control de Evaluación Contínua en el curso 2010/11, del 23 de marzo de 2011]''

Indique la diferencia fundamental de diseño entre un sistema operativo monolítico y otro micronúcleo.

(''[[Solución de los ejercicios de fundamentos#Ejercicio 1|Ver solución]]'')

== Ejercicio 2 ==
''[Este ejercicio fue parte del Primer Control de Evaluación Contínua en el curso 2011/12, del 24 de Noviembre de 2011]''

Enumere y detalle brevemente los cuatro componentes básicos de un Sistema Operativo, así como las interfaces que este ofrece para interactuar con él.

(''[[Solución de los ejercicios de fundamentos#Ejercicio 2|Ver solución]]'')

Mensajería

2011-11-26T16:42:07Z

Sertrimur:

Un mensaje es un contenedor que se emplear para intercambiar información entre dos o más procesos. Los mensajes tienen un cierto formato generalmente compuesto por una cabecera, que contiene información sobre la fuente y el destinatario, y un cuerpo, que contiene información específica.

Los mecanismos de mensajería se refiere al conjunto de funcionalidades que permiten al sistema operativo realizar la entrega de un mensaje a uno o varios procesos. Mediante dicho mecanismo también es posible resolver problemas de concurrencia.

Los sistemas operativos generalmente ofrecen dos llamadas al sistema para que un proceso pueda enviar y recibir mensajes:

* '''send(mensaje, destino)''': Para enviar un mensaje
* '''recv(mensaje)'''': Para recibir un mensaje

Cualquier proceso que necesita comprobar si tiene mensajes para ser procesados por él debe invocar la llamada al sistema '''recv'''.

== Formas de identificación ==

Para identificar la fuente y el destino de nuestro mensaje se pueden emplear dos estrategias.

=== Denominación Directa ===

En este caso se emplea un ID que permite identificar a la fuente y al destinatario de manera unívoca en el sistemas, por ejemplo, el PID de un proceso. La denominación directa permite tres configuraciones:

* ''Unicast'', de manera que la comunicación sucede entre una fuente y un destinatario.
* ''Broadcast'', el emisor envía un mensaje a '''todos''' los procesos existentes en el sistema.
* ''Multicast'', el emisor envía un mensaje a un grupo de procesos, siendo un grupo un subconjunto de procesos existentes en el sistema. El sistema operativo debe ofrecer llamadas al sistema que permitan a los procesos crear grupos y suscribirse a ellos. Un proceso puede suscribirse a tantos grupos como le sea necesario.

El principal inconveniente de la denominación directa es que se pierde el mensaje si el destino no se encuentra.

=== Denominación Indirecta ===

Se emplea un elemento intermediario denominado ''buzón''. El sistema operativo ofrece llamadas al sistema que permiten la creación y destrucción de buzones, por ejemplo, '''CreateMailbox''' y '''DestroyMailbox'''. Una vez creado el buzón, se emplea éste para realizar la comunicación entre procesos.

El sistema operativo debe de comprobar que la identidad de la fuente de un mensaje es correcta, de lo contrario un proceso podría suplantar la identidad de otro.

== Formas de transmisión ==

Distinguimos tres formas de transmisión: Transmisión por copia, transmisión por referencia y transmisión por copia en caso de escritura.

=== Transmisión por copia ===

Si se emplea ''denominación directa'', al invocar el receptor la llamada ''recv'', el mensaje se copia de espacio de memoria del emisor al espacio de receptor. Esta forma de implementar la transmisión tiene un coste de orden lineal <math>O(n)</math>.

Si se emplea ''denominación indirecta'', al invocar ''send'' el emisor, el mensaje se copia del espacio de emisor al espacio del buzón, que se encuentra en el espacio de memoria del sistema operativo. Una vez que el receptor invoca ''receive'', se copia el mensaje al espacio de memoria que el receptor ha habilitado para almacenar el mensaje.

=== Transmisión por referencia ===

Es una mejora frente al mecanismo de transmisión por copia. Básicamente, en lugar de copiar el mensaje, lo que supone un coste de <math>O(n)</math>, se le devuelve al receptor una dirección de memoria en la que se encuentra el mensaje, lo que supone únicamente 4 u 8 bytes dependiendo del tamaño de palabra del procesador (si es de 32-bits o 64-bits).

Si se emplea junto a la '''denominación directa''', el sistema operativo le devuelve al receptor un puntero a la dirección en la que se encuentra el mensaje. Si el mensaje está en el espacio del emisor, son necesarios mecanismos explícitos de compartición de memoria entre procesos, ya que dos procesos cualquiera no comparten memoria. Si el mensaje está en el espacio del sistema operativo, éste debe ofrecer a los procesos mecanismos para acceder a su espacio de memoria-

Si se emplea junto a la '''denominación indirecta''', el emisor crea un mensaje en el espacio del sistema operativo y se le ofrece un puntero al receptor.

=== Transmisión por copia de escritura ===

El mensaje sólo se copia si se modifica por emisor o receptor.

== Formas de comunicación ==

* Comportamiento del emisor, '''send()'''
** ''Síncrona'': el proceso emisor que realiza el send() queda bloqueado hasta que el receptor llama a recv()
** ''Asíncrona'': suponemos una estructura de datos con capacidad de almacenamiento limitada, dependiente del proceso destinatario o en el buzón del SO. Al ser enviados, los mensajes irán encolándose para que el proceso receptor pueda gestionarlos cuando pueda. De esta manera se aumenta el rendimiento pero se requiere de políticas adicionales de tratamiento de los mensajes si la capacidad de almacenamiento de la estructura de datos se ve sobrepasada(PE, eliminación de mensajes, realocalización de memoria, etc..)

* Comportamiento del receptor, '''recv()'''
** ''Bloqueante'': una llamada a recv() sin mensajes a procesar pasa el proceso llamante a estado bloqueado. Un send() de otro proceso que añada un mensaje a la cola del proceso bloqueado hace que éste pase a estado preparado.
** ''No bloqueante'': una llamada a recv() sin mensajes a procesar devuelve un mensaje de error, pero la ejecución del proceso llamante continúa.

Entendemos por proceso llamante a aquel que hace uso de las llamadas send() y recv().

== Formato de los mensajes ==

=== Fijo ===

Los procesos acuerdan emplear un formato fijo para sus mensajes.

'''Ejemplo''': Simple Network Time Protocol.<ref> Véase http://tools.ietf.org/html/rfc4330, sección 4, Message Format.</ref>

1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|LI | VN |Mode | Stratum | Poll | Precision |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Root Delay |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Root Dispersion |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reference Identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Reference Timestamp (64) |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Originate Timestamp (64) |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Receive Timestamp (64) |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Transmit Timestamp (64) |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Key Identifier (optional) (32) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| |
| Message Digest (optional) (128) |
| |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

=== Variable ===

* Type-Length-Value

'''Ejemplo''': Usado en Netlink para la codificación de atributos de un mensaje.<ref>Ver Communicating between the kernel and user-space in Linux using Netlink Sockets (http://1984.lsi.us.es/~pablo/docs/spae.pdf)</ref>
{| border="2" cellpadding="4" cellspacing="0" style="margin: 1em 1em 1em 0; background: #f9f9f9; border: 1px #aaa solid; border-collapse: collapse; font-size: 95%;"
|+ align="center" style="background:DarkSlateBlue; color:white"|'''Type-Length-Value'''
! width="15 px" style="background:#efefef;" | 0
! width="15 px" style="background:#efefef;" | 1
! width="15 px" style="background:#efefef;" | 2
! width="15 px" style="background:#efefef;" | 3
! width="15 px" style="background:#efefef;" | 4
! width="15 px" style="background:#efefef;" | 5
! width="15 px" style="background:#efefef;" | 6
! width="15 px" style="background:#efefef;" | 7
! width="15 px" style="background:#efefef;" | 8
! width="15 px" style="background:#efefef;" | 9
! width="15 px" style="background:#efefef;" | 10
! width="15 px" style="background:#efefef;" | 11
! width="15 px" style="background:#efefef;" | 12
! width="15 px" style="background:#efefef;" | 13
! width="15 px" style="background:#efefef;" | 14
! width="15 px" style="background:#efefef;" | 15
! width="15 px" style="background:#efefef;" | 16
! width="15 px" style="background:#efefef;" | 17
! width="15 px" style="background:#efefef;" | 18
! width="15 px" style="background:#efefef;" | 19
! width="15 px" style="background:#efefef;" | 20
! width="15 px" style="background:#efefef;" | 21
! width="15 px" style="background:#efefef;" | 22
! width="15 px" style="background:#efefef;" | 23
! width="15 px" style="background:#efefef;" | 24
! width="15 px" style="background:#efefef;" | 25
! width="15 px" style="background:#efefef;" | 26
! width="15 px" style="background:#efefef;" | 27
! width="15 px" style="background:#efefef;" | 28
! width="15 px" style="background:#efefef;" | 29
! width="15 px" style="background:#efefef;" | 30
! width="15 px" style="background:#efefef;" | 31

|-
| colspan=16, align="center"| Length
| colspan=16, align="center"| Type
|-
| colspan=32, align="center"| Value
|}

* Text-based human-readable.

#Comma-Separated Value (CSV). http://en.wikipedia.org/wiki/Comma-separated_values
#Extensible Markup Language (XML). http://en.wikipedia.org/wiki/XML
#JavaScript Object Notation (JSON). http://en.wikipedia.org/wiki/JSON

=== Mixto ===

Los procesos acuerdan emplear mensaje con partes cuyo formato es fijo, como por ejemplo una cabecera inicial, seguido de partes de tamaño variable.

'''Ejemplo''': Internet Protocol (IPv4).<ref>Ver http://www.ietf.org/rfc/rfc791.txt, sección 3.1.</ref>

0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Version| IHL |Type of Service| Total Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Identification |Flags| Fragment Offset |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Time to Live | Protocol | Header Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Options | Padding |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
/ /
/ Payload /
/ /
/////////////////////////////////////////////////////////////////

== Mensajería a través de la red ==

* Unicidad del destinatario
* Fiabilidad en la transmisión
* Formato de los datos (http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Data/endian.html): Enviar un entero a través de la red puede ser un problema debido a la forma en el que se representan los datos en la memoria dependiente de la arquitectura. Por ejemplo, un PC con arquitectura Intel x86 emplea formato little-endian, mientras que un SPARC de Sun Microsystems (ahora Oracle) emplea big-endian.

** Little Endian: Bytes menos significativo al principio.

<source lang="c">
int main(void)
{
int a = 10, i;
char *p = &a;

for (i=0; i<sizeof(a); i++) {
printf("posición %d: %.2x\n", i, p[i]);
}
}
</source>

Muestra el siguiente resultado en un PC:

posición 0: 0a (n+3)
posición 1: 00 (n+2)
posición 2: 00 (n+1)
posición 3: 00 (n)

** Big Endian: Bytes menos significativo al final.

posición 0: 00 (n)
posición 1: 00 (n+1)
posición 2: 00 (n+2)
posición 3: 0a (n+3)

En Internet se sigue la convención de expresar datos en Big Endian, habría que hacer la conversión. Habría que usar '''ntohl''' (network to host long).

En little-endian, la implementación de ntohl es la siguiente:

#define __constant_ntohl(x) ___constant_swab32((__be32)(x)

Ver /usr/include/linux/byteorder/little_endian.h

mientras que en big-endian es:

#define __constant_ntohl(x) ((__u32)(__be32)(x))

Si empleamos formato textuales, como CSV, XML o JSON, que codifican la información en bytes, no tenemos este problema.

==Referencias==
<references/>

Monitores

2011-11-26T16:35:44Z

Sertrimur: /* Ejemplo del funcionamiento de una clase monitor */ faltaban algunos procesos

Idea desarrollada en los años 70 Brinch-Hansen y Hoare <ref>http://java.sun.com/developer/Books/performance2/chap4.pdf</ref>que notaron los siguientes problemas con respecto al uso de los semáforos:

* Los semáforos son difíciles de usar. Es frecuente que el programador cometa errores al emplearlos.
* El compilador no asiste al programador en el desarrollo de programas concurrentes mediante semáforos, pues no ofrece ningún tipo de validación en tiempo de compilación.
* No hay nada que obligue a usarlos. Puede suceder que el programador los necesite y lo desconozca
* Son independientes del recurso compartido

Los monitores tienen que estar integrados en el lenguaje de programación.

== Definición ==
Un monitor es una estructura del lenguaje cuyas principales características son:

* Los datos son privados.
* Ofrecen una serie de métodos públicos para acceder a dichos datos.
* En cada momento sólo puede haber un proceso activo en algún método del monitor, es decir, ejecutando código de esos métodos públicos del monitor. Seria equivalente a decir que el recurso que queremos compartir se declara como monitor. Los procesos que usan el monitor son independientes unos de otros y cuando deseen usar el recurso, llamarán a los métodos del monitor que implementen la operación que se desea ejecutar.

Permiten organizar procesos en espera mediante:

* Variables de condición: lista de procesos inicialmente vacía.
* Primitivas: ''wait(c)'', añade el proceso p invocante a c y proceso p bloquea; ''signal(c)'', selecciona a uno de los procesos en c y lo pone en preparado.

<source lang="java">

class recursoCompartido {

public int get(void);
public void set(int valor);
private int recursoCompartido;
private Semaforo s = 1;

public int get(void){
int ret; #1
down(s); #2
ret = recursoCompartido; #3
up(s); #4
return ret; #5
}

public void set(int valor){
down(s); #1
recursoCompartido = valor; #2
up(s); #3
}
}
</source>

Como vemos, los monitores se implementan con semáforos, son una abstracción de los mismos.

== Ejemplo del funcionamiento de una clase monitor ==

Dado un cierto recurso compartido protegido por una clase monitor denominada ''RecursoCompartido'' con los siguientes métodos:

* '''get''', permite obtener el valor del recurso compartido, devuelve un entero.
* '''set''', permite establecer el valor del recurso compartido.

Suponga ya creada un objeto RecursoCompartido para dos hilos h1 y h2:

<source lang="java">
RecursoCompartido r = new RecursoCompartido();
</source>

Dichos hilos tienen el siguiente código:

* Lector (h1):

<source lang="java">
int valor;
for(int j=0; j<2; j++) { #1
valor=r.get(); #2
print(valor); #3
}
</source>

* Escritor (h2):

<source lang="java">
int i=0;
for(int j=0; j<2; j++) { #1
r.set(); #2
i++; #3
}
</source>

Suponiendo turno rotatorio estricto con quantum de 4 unidades de tiempo y que el planificador da paso en primer lugar al hilo h1. El cronograma con la representación de la ejecución sería el siguiente:

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento.
B = el proceso pasa a estado bloqueado
P = el proceso pasa a estado preparado

Asignación del recurso procesador

| 1 |2.1|2.2|2.3| | |2.4|2.5| 3 | 1 | | | | |2.1|2.2|2.3|2.4| | | | |2.5| 3 | 1 | |
h1 <---|---|---|---P | |---|---|---|---P | | | |---|---|---|---| | | | |---|---|---> |
| | | | | 1 |2.1| | | | |2.2|2.3| 3 | 1 | | | | |2.1|2.2|2.3| 3 | | | | 1 |
h2 | | | | <---|---B P | | |---|---|---|---P | | | |---|---|---|---| | | |--->
----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Nota: Los números de la parte superior a los guiones, indican el número de instrucción que
se está ejecutando en dicho momento. En el caso de los 2.1, 2.2 y sucesivos se
refieren al número de instrucción qué internamente se ejecutan en el get() y set()
del monitor (Ver la implementación de la clase monitor de RecursoCompartido vista en clase).

En la página de [https://1984.lsi.us.es/wiki-ssoo/index.php/Discusi%C3%B3n:Monitores discusión] hay un ejemplo en java.

== Fuentes ==
<references/>

Semáforos

2011-11-26T16:03:20Z

Sertrimur: /* Semáforos */ Semáforo contador

= Planificador de procesos: Diagrama de estados simplicado =

Para comprender apropiadamente cómo funcionan los semáforos vamos a recordar el diagrama de estados simplificado que emplea el planificador de procesos del sistema operativo.

|---------------|
pendiente | | recibido
evento ---------> | bloqueado |----------- evento
externo | | | | externo
| |---------------| |
| |
| planificador \/
|--------------| retira CPU |---------------|
| | -------------------> | |
| activo | | preparado |
| | <------------------- | |
|--------------| |---------------|
planificador
asigna CPU

La vida de un proceso pasa por tres estados:

* Activo: el proceso está empleando la CPU, por tanto, está ejecutándose. Hay tantos procesos activos como recurso de procesamiento disponible. Por tanto, si el sistema dispone de un único procesador, únicamente puede haber un proceso activo a la vez.
* Preparado: el proceso no está ejecutándose pero es candidato a pasar a estado activo. Es el planificador el que, en base a un criterio de planificación, decide qué proceso selecciona de la lista de procesos preparados para pasar a estado activo.
* Bloqueado: el proceso está pendiente de un evento externo, tales como la espera de finalización de un proceso hijo, una señal, una operación sobre un semáforo o una operación de lectura/escritura.

La transición de activo a preparado y viceversa depende de decisiones tomadas por el planificador del sistema operativo (que emplea algún criterio visto en clases teóricas, tales como el turno rotatorio), el programador no puede interferir en estas decisiones. Mientras que la transición de activo a bloqueado, y de bloqueado a preparado pueden ser controladas por el programador mediante llamadas al sistema.

= Semáforos =

Los semáforos son un mecanismo de sincronización de procesos inventados por [http://es.wikipedia.org/wiki/Edsger_Dijkstra Edsger Dijkstra] en 1965. Los semáforos permiten al programador '''asistir al planificador del sistema operativo en su toma de decisiones''' de manera que permiten sincronizar la ejecución de dos o más procesos. A diferencia de los [[cerrojos]], los semáforos nos ofrecen un mecanismo de espera no ocupada.

Los semáforos son un tipo de datos que están compuestos por dos atributos:

* Un contador, que siempre vale >= 0.
* Una lista de procesos(lista formada por el PCB de cada proceso), inicialmente vacía.

Y disponen de dos operaciones básicas que pasamos a describir en pseudocódigo:

<source lang="c">
down(semáforo s)
{
si s.contador == 0:
añade proceso a s.lista
proceso a estado bloqueado
sino:
s.contador--
}
</source>

Nótese que siempre que queramos forzar una transición de un proceso a estado bloqueado, tenemos que hacer que dicho proceso realice una operación ''down'' sobre un semáforo cuyo contador vale cero.

<source lang="c">
up(semáforo s)
{
si hay procesos en s.lista
retira proceso de s.lista
proceso a estado preparado
sino:
s.contador++
}
</source>

Nótese que una operación ''up'' sobre un semáforo en el que hay procesos en su lista resulta en que se retire uno de los procesos (el que más tiempo lleva en la lista), realizando éste la transición a estado preparado. Es un error frecuente pensar que una operación ''up'' resulte en que el proceso retirado de la lista pase a estado activo. Recuerde que las transiciones de estado activo a preparado y viceversa son siempre controladas por el planificador del sistema operativo.

Además, se disponen de un constructor y un destructor que permiten la creación y la liberación de un semáforo.

=== Ejemplo de uso de semáforos ===

Suponga el siguiente ejemplo en el que se quieren sincronizar dos hilos de un proceso, de manera que se dé la siguiente secuencia de ejecución: A, B, A, B, ... y así sucesivamente. El siguiente código resolvería el problema:

<source lang="c">
semaforo a = semaforo.create(1);
semaforo b = semaforo.create(0);

/* código del hilo A */
while (1) {
a.down();
printf("hilo A\n");
b.up();
}

/* código del hilo B */
while (1) {
b.down();
printf("hilo B\n");
a.up();
}
</source>

=== Tipos de semáforos ===

Dependiendo de la función que cumple el semáforo, vamos a diferenciar los siguientes tipos:

* Semáforo de exclusión mutua, inicialmente su contador vale 1 y permite que haya un único proceso simultáneamente dentro de la sección crítica.
* Semáforo contador, permiten llevar la cuenta del número de unidades de recurso compartido disponible, que va desde 0 hasta N.
* Semáforo de espera, generalmente se emplea para forzar que un proceso pase a estado bloqueado hasta que se cumpla la condición que le permite ejecutarse. Por lo general, el contador vale 0 inicialmente, no obstante, podría tener un valor distinto de cero.

=== Ventajas e inconvenientes ===

La principal ventaja de los semáforos frente a los [[cerrojos]] es que permiten sincronizar dos o más procesos de manera que no se desperdician recursos de CPU realizando comprobaciones continuadas de la condición que permite progresar al proceso.

Los inconvenientes asociados al uso de semáforos son los siguientes:

* Los programadores tienden a usarlos incorrectamente, de manera que no resuelven de manera adecuada el problema de concurrencia o dan lugar a interbloqueos.
* No hay nada que obligue a los programadores a usarlos.
* Los compiladores no ofrecen ningún mecanismo de comprobación sobre el correcto uso de los semáforos.
* Son independientes del recurso compartido al que se asocian.

Debido a estos inconvenientes, se desarrollaron los [[Monitores|monitores]].

Solución de los ejercicios de concurrencia

2011-11-22T18:15:46Z

Sertrimur: /* Ejercicio 2 */ corregido el error del tiempo 21-24

== Ejercicio 1==

| #1| #2| #3| | | | #4| #1| #2| | | | #3| #4| #1| | | | | | | | |
H1 |<--|---|---| | | |---|---|---| | | |---|---|-->| | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | |
| | | | #1| #2| #2| | | | #2| #2| #2| | | | #2| #3| #4| #1| #2| #3| #4| #1|
H2 | | | |<--|---|---| | | |---|---|---| | | |---|---|---|---|---|---|---|-->|
| | | | | | | | | | | | | | | | | | | | | | | |
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Algunas observaciones:
* Los hilos '''no''' comparten la variable ''i''. Esta variable se trata de una variable local, por tanto, no es una variable que ambos hilos compartan. Únicamente las variables globales son compartidas por dos o más hilos.
* Al ser los cerrojos un control de concurrencia de espera activa, se comprueba continuamente la condición que nos permite acceder a la sección crítica.

--[[Usuario:Pneira|Pneira]] 07:33 10 may 2011 (UTC)

== Ejercicio 2==

| #1| #2| #3| | | | #4| #5| #1| | | | #2| #2| #2| | | | #2| #3| #4| | | | #5| #1| | | | | |
H1 |<--|---|---| | | |---|---|---| | | |---|---|-->| | | |---|---|---| | | |---|-->| | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | #1| #2| #2| | | | #2| #3| #4| | | | #5| #1| #2| | | | #2| #2| #2| | | #2| #3| #4| #5| #1|
H2 | | | |<--|---|---| | | |---|---|---| | | |---|---|---| | | |---|---|---| | |---|---|---|---|-->|
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

'''Nota:'''
En este ejercicio los cerrojos no resuelven la concurrencia (véase a partir del instante 18).

== Ejercicio 3==
Al tener un quantum de únicamente dos unidades, el planificador cambia de proceso antes de actualizar el valor del cerrojo, lo que provoca que se produzca una situación de concurrencia.

Usuario:Sertrimur

2011-11-06T18:30:22Z

Sertrimur: Página creada con 'Sergio Trigos Muriel'

Sergio Trigos Muriel

Sol-ejer2-2-otros-aspectos

2011-11-06T15:30:44Z

Sertrimur: error

____|_PA_|_PB_|_PC_| Prioridad C<B<A
Datos del ___H0_|_0__|_1__|_2__| PA bloquea cada 1 u.t.
problema ___t__|_3__|_5__|_6__| PB bloquea cada 3 u.t.
_plazo|_6__|_15_|_15_| tiempo de bloqueo=2 u.t.

< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
X = se ejecuta el código del planificador
# = el proceso se bloquea
--- = proceso ejecutándose
* = el proceso aborta

| | | | | | | | | | | | | | | |
Pa <---# | < |---# * | | | | | | | | |
Pb | <---|---|---# | <---|---> | | | | | | |
Pc | | < | | |---| | |---|---|---|---|---> | |
Planificador X X X X X | X X | | | | | | | |
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

'''OBSERVACIONES:'''

*Este ejercicio (de momento) no ha sido corregido por Pablo Neira, es por ello que si alguien tiene una duda sobre él debería indicarlo para discutirlo hasta que dicho profesor lo revise.

-Creo que hay un error en el instante de tiempo 3 debería comenzar Pa porque tiene prioridad sobre Pb y en el instante de tiempo 4 empezar Pb y ser bloqueada en el instante de tiempo 5 con lo que en el momento 5 empieza Pc hasta el momento 7 que es el tiempo de bloqueo de Pb.
--[[Usuario:Sertrimur|Sertrimur]] 17:23 5 nov 2011 (UTC)==Por prioridades apropiativo en tiempo real==

Sol-ejer2-2-otros-aspectos

2011-11-05T17:23:44Z

Sertrimur:

--[[Usuario:Sertrimur|Sertrimur]] 17:23 5 nov 2011 (UTC)==Por prioridades apropiativo en tiempo real==

____|_PA_|_PB_|_PC_| Prioridad C<B<A
Datos del ___H0_|_0__|_1__|_2__| PA bloquea cada 1 u.t.
problema ___t__|_3__|_5__|_6__| PB bloquea cada 3 u.t.
_plazo|_6__|_15_|_15_| tiempo de bloqueo=2 u.t.

< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
X = se ejecuta el código del planificador
# = el proceso se bloquea
--- = proceso ejecutándose
* = el proceso aborta

| | | | | | | | | | | | | | | |
Pa <---# | < |---# * | | | | | | | | |
Pb | <---|---|---# | <---|---> | | | | | | |
Pc | | < | | |---| | |---|---|---|---|---> | |
Planificador X X X X X | X X | | | | | | | |
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

'''OBSERVACIONES:'''

*Este ejercicio (de momento) no ha sido corregido por Pablo Neira, es por ello que si alguien tiene una duda sobre él debería indicarlo para discutirlo hasta que dicho profesor lo revise.

-En el instante de tiempo 3 debería comenzar Pa porque tiene prioridad sobre Pb y en el instante de tiempo 4 empezar Pb y ser bloqueada en el instante de tiempo 5 con lo que en el momento 5 empieza Pc hasta el momento 7 que es el tiempo de bloqueo de Pb.

Planificación en sistemas multiprocesadores

2011-11-04T14:08:50Z

Sertrimur:

En este tipo de sistemas disponemos de n (n>=2) procesadores, siendo los criterios de planificación los mismos seguidos hasta ahora pero contando con más de un procesador.
Hay que considerar que la asignación del proceso a un procesador puede ser
* '''Estática''': en la que el proceso es asignado siempre a dicho procesador mientras este no haya terminado su ejecución.
* '''Dinámica''': en la que se permite la migración del procesador o balanceo de carga.

Se utiliza principalmente la estática debido al principio de localidad espacio y temporal, cuando un proceso se carga en un procesador se carga en caché los datos más frecuentes accedidos por el proceso. Si cambiamos de procesador a dicho proceso habría que cargar de nuevo los datos en la caché del otro procesador.

Ejemplo de planificación en sistemas multiprocesadores con dos CPU:

[[Archivo:Ejemplo de multiprocesador.png]]

Archivo:Ejemplo de multiprocesador.png

2011-11-01T10:39:26Z

Sertrimur: subió una nueva versión de «Archivo:Ejemplo de multiprocesador.png»: texto descriptivo

Archivo:Ejemplo de multiprocesador.png

2011-11-01T07:50:59Z

Sertrimur:

Planificación en sistemas multiprocesadores

2011-11-01T07:48:54Z

Sertrimur: