Descarga la aplicación para disfrutar aún más
Lea materiales sin conexión, sin usar Internet. Además de muchas otras características!
UCM _ Grado en Ingeniería a Informática _ Sistemas operativos _ ejercicios
Materiales Generales
Esta es una vista previa del archivo. Inicie sesión para ver el archivo original
ejercicios SO/2.2-FicherosProblemasSoluciones.pdf
1
Sistemas Operativos UCM 2012/2013
Módulo 2 Gestión de Archivos y Directorios
1. Considerar un sistema donde el espacio libre se especifica en una lista de espacios libres.
a) Suponer que se pierde el puntero a la lista. ¿Puede el sistema reconstruirla?
b) Sugerir un esquema que asegure que el puntero nunca se pierda como resultado de un fallo de
memoria.
SOLUCIÓN
a) Habría que recorrer todos los ficheros del sistema y guardar un registro de sus posiciones, para
seguidamente asignar los que faltan a la lista enlazada (válido para 1 solo error).
b) Lista doblemente enlazada? Duplicidad? En general, redundancia de información.
2. Calcular el número de accesos a disco necesarios (para el caso peor y para el caso mejor) para leer 20
bloques lógicos consecutivos (no necesariamente los 20 primeros) de un fichero en un sistema con:
a) Asignación contigua
b) Asignación no contigua mediante índice enlazado (FAT)
c) Asignación no contigua indexada directa
Nota: Asumir que no hay ningún dato relacionado con el sistema de ficheros en memoria RAM y que el
fichero se encuentra en el directorio actual.
SOLUCIÓN
a) 20 (datos) + encontrar el fichero en el directorio actual (entre 1 y N accesos dependiendo del
tamaño del directorio y la posición del fichero)
b) 20 (datos) + 1‐N (directorio actual) + seguir la FAT (entre 1 (mínimo) e Y+20 (maximo))
c) 20 (datos) + 1‐N (directorio actual) + 1 (i‐nodo) + buscar las tablas de índices adecuadas (hasta 3
niveles)
3. Un dispositivo de memoria flash de 64 MB de capacidad y bloques de 1KB, contiene un sistema de
ficheros FAT. ¿Cuántos bytes son necesarios para almacenar la tabla FAT?
a. 64 KB
b. 128 KB
c. 1 MB
d. 512 KB
e. Ninguna de las respuestas anteriores es correcta
¿Es posible realizar enlaces rígidos en un sistema de ficheros tipo FAT? ¿Por qué no se puede establecer
enlaces rígidos a ficheros de volúmenes distintos en sistemas de ficheros tipo EXT2?
SOLUCIÓN
Número de bloques de datos direccionables: 64 MB/1KB = 64K bloques
La FAT debe poder contener 64K direcciones
Cada dirección ocupa como mínimo: log2 64K bits = 16 bits = 16/8 bytes = 2 bytes
Luego, la FAT ocupa: 64K direcciones * 2 bytes/dirección = 128KB (respuesta b)
Apartado b)
No es posible – porque en FAT cada nombre de fichero dentro de un volumen tiene una entrada de
atributos distinta y mantenerlas exactamente iguales representaría un problema de coherencia desorbitado
PORQUE los enlaces rígidos están asociados a un inodo de un volumen específico, y los inodos no se pueden
compartir entre volúmenes (cada volumen es un “espacio” de inodos independiente.
4. En la siguiente figura se representa una tabla FAT. Al borde de sus entradas se ha escrito, como ayuda de
referencia, el número correspondiente al bloque en cuestión. También se ha representado la entrada de
cierto directorio. Como simplificación del ejemplo, suponemos que en cada entrada del directorio se
almacena: Nombre de archivo/directorio, el tipo (F=archivo, D=directorio), la fecha de creación y el número
del bloque inicial.
2
#Bloque Índice #Bloque Índice
1 10
2 11
3 15 12
4 13
5 14
6 15 <EOF>
7 16
8 17
9 18
Nombre Tipo Fecha Nº Bloque
DATOS F 8‐2‐05 3
Rellene la figura para representar lo siguiente (Nota: supóngase tamaño de bloque 512 Bytes y que siempre
se elige el primer bloque vacío como política de asignación):
a) Creación del archivo DATOS1 con fecha 1‐3‐90, y tamaño de 10 Bytes.
b) Creación del archivo DATOS2 con fecha 2‐3‐90, y tamaño 1200 Bytes.
c) El archivo DATOS aumenta de tamaño, necesitando 2 bloques más.
d) Creación del directorio D, con fecha 3‐3‐90, y tamaño 1 bloque.
e) Creación del archivo CARTAS con fecha 13‐3‐90 y tamaño 2 KBytes.
Si usamos un Mapa de Bits para la gestión del espacio libre, especifique la sucesión de bits que contendría
respecto a los 18 bloques de la tabla anterior.
SOLUCIÓN
#Bloque Índice #Bloque Índice
1 <EOF> 10 11
2 4 11 12
3 15 12 <EOF>
4 5 13
5 <EOF> 14
6 7 15 <EOF>/6
7 <EOF> 16
8 <EOF> 17
9 10 18
Nombre Tipo Fecha Nº Bloque
DATOS F 8‐2‐05 3
DATOS1 F 1‐3‐90 1
DATOS2 F 2‐3‐90 2
D D 3‐3‐90 8
CARTAS F 13‐3‐90 9
5. Considerar un fichero que consta de 100 bloques. ¿Cuántas operaciones de disco son necesarias para
cada una de las tres estrategias de asignación (contigua, enlazada e indexada) al realizar las siguientes
operaciones?:
a) Añadir un bloque de información al comienzo
b) Añadirlo a la mitad
c) Añadirlo al final
d) Suprimirlo del principio
e) Suprimirlo de la mitad
f) Suprimirlo del final.
SOLUCIÓN
Añadir Mirar si hay hueco al principio o final. Si lo hay, marcarlo como ocupado y mover la porción de
datos necesaria (modificar la posición inicial del fichero si hace falta). Si no hay hueco, buscar uno lo
suficientemente grande y copiar el contenido completo, actualizando la posición inicial del fichero (liberar y
reservar huecos). Actualizar siempre el tamaño del fichero y atributos en el directorio.
Eliminar Mover la porción de datos necesaria (modificar la posición inicial del fichero si hace falta),
marcar el espacio como libre. Actualizar siempre el tamaño del fichero y atributos en el directorio.
3
Añadir Buscar un hueco en la FAT, enlazarlo en la posición deseada (modificando si es necesario el
bloque inicial en el directorio). Actualizar el tamaño y atributos en el directorio.
Eliminar Marcar el bloque correspondiente como libre, quitarlo de la lista enlazada (modificando si es
necesario el bloque inicial en el directorio). Actualizar el tamaño y atributos en el directorio.
Añadir Buscar un hueco en el mapa de bits y marcarlo como ocupado. Indexar el nuevo hueco en la
posición correcta, desplazando los siguientes índices. Actualizar los atributos en el i‐nodo.
Eliminar Buscar un hueco en el mapa de bits y marcarlo como libre. Eliminar el índice y desplazar los
siguientes índices. Actualizar los atributos en el i‐nodo.
6. Un sistema de ficheros UNIX utiliza bloques de 1024 bytes y direcciones de disco de 16 bits. Los i‐nodos
(entradas en una tabla que contiene la información descriptiva de los ficheros) contienen 8 direcciones de
disco para bloques de datos, una dirección de bloque índice indirecto simple y una dirección de bloque
índice indirecto doble. ¿Cuál es el tamaño máximo de un fichero en este sistema? ¿Y el de la partición?
SOLUCIÓN
El tamaño máximo de un fichero será el número de bloques accesible, directa o indirectamente, desde un i‐
nodo:
Directamente se puede acceder a 8 bloques
Indirectamente se puede acceder a:
Simple: 1024[Bytes]/2[Bytes/Bloque] 512 [Bloques].
Doble: 512 [Índices/Bloque] • 512 [Bloque/Índice] = 512^2 [Bloques]
Recuento final:
8 + 512 + 512•512 = 262 664 bloques = 268.967.936Bytes = 256’5MB
Pero el tamaño del disco es como máximo 216 = 64 MB!!!!
7. Dar 5 nombres de ruta diferentes para el fichero /etc/passwd. (Sugerencia: considerar las entradas de
directorio . y . .)
SOLUCIÓN
Si consideramos que un fichero en UNIX sólo está representado unívocamente por su número de inodo y no
por su nombre simbólico, podría haber muchos nombres distintos que designaran al mismo fichero: todos
los que hubieran sido declarados enlaces al mismo inodo mediante la orden.
Pero si se nos pide acceder al mismo nombre simbólico expresando con distintos nombres de rutas una
solución podría ser:
/etc/passwd , nombre de ruta absoluto
passwd , suponiendo que el directorio actual es /etc
./passwd
././passwd
../etc/passwd
, suponiendo que el directorio actual es /usr
8. ¿Cuántos accesos a disco son necesarios para abrir el fichero games/chess en UNIX?
SOLUCIÓN
Para abrir al fichero games/chess son necesarias como mínimo 4 referencias a disco (entendiendo que
algunas de las referencias a disco pueden ser evitadas porque la información precisada ya se encuentra en
la cache de buffers):
1. Acceso al directorio actual para buscar el nombre games
2. Acceso al inodo correspondiente al directorio games
3. Acceso al directorio games para buscar el nombre chess
4. Acceso al inodo correspondiente al fichero chess
5. (No es preciso acceder a los datos del fichero chess durante la apertura)
9. Un programa UNIX crea un fichero e inmediatamente se posiciona (con lseek) en el byte 55 millones.
Luego escribe un byte. ¿Cuántos bloques de disco ocupa ahora el fichero (incluyendo bloques indirectos)?
Asúmase que los i‐nodos contienen 10 índices directos, 1 índice indirecto simple, 1 índice indirecto doble y
4
1 índice indirecto triple, los bloques tienen un tamaño de 2 Kbytes y el tamaño de los índices (direcciones
de bloques de disco) es de 32 bits. ¿Qué sucesión de índices lógicos nos lleva al byte posicionado por lseek?
SOLUCIÓN
Cada bloque contiene 2048 bytes y que cada índice ocupa 4 bytes un bloque de índices apunta a 512
bloques.
Con los 10 índices directos se accede a los primeros 10 x 2048 = 20.480 bytes
Con el índice indirecto simple se accede a los siguientes (2048 / 4) x 2048 = 1.048.576 bytes
Con el índice indirecto doble se accede a los siguientes (2048 / 4)2 x 2048 = 536.870.912 bytes
Luego el bloque de datos que contiene el byte 55 millones se alcanza mediante el índice indirecto doble, y
en consecuencia el número de bloques que ocupa un fichero que sólo tiene escrito el byte 55 millones es de
3:
1. El bloque de índices al que apunta el índice indirecto doble (índices indirectos). (Tiene escrito el
índice 51) floor( (55e6‐10*2048‐1024^2) / 1024^2 ) = 51
2. El bloque de índices al que apunta uno de los índices del bloque anterior (índices directos). (Tiene
escrito el índice 221) floor( (55e6‐10*2048‐1024^2‐51*1024^2) / 2048 ) = 221
3. El bloque de datos que contiene el byte 55 millones. (Tiene escrito el byte 960)
4. 55e6‐10*2048‐1024^2‐51*1024^2‐221*2048 = 960
La cuenta total es: 20.480 + 1.048.576 + 51 x 1.048576 + 221 x 2048 + 960 = 55.000.000
10. Juan crea un fichero de nombre JFichero. María crea un enlace físico a JFichero y le da el nombre
MFichero. Juan elimina JFichero. Luego Juan crea un nuevo fichero y también le llama JFichero. ¿Cuántos
ficheros diferentes existen después de las acciones anteriores? ¿Sería diferente la respuesta si el enlace que
ha creado María fuese un enlace simbólico de nombre MFichero que apuntara a JFichero?
SOLUCIÓN
a. Dos ficheros diferentes
b. Un fichero y un enlace simbólico
11. Sugerir una razón por la cuál alguien pudiera desear construir un directorio sobre los cuales los demás
usuarios tuvieran permiso de ejecución pero no de lectura, en un sistema de ficheros de tipo UNIX.
SOLUCIÓN
The execute permission, which grants the ability to execute a file. This permission must be set for
executable binaries or shell scripts in order to allow the operating system to run them. When set for a
directory, this permission grants the ability to traverse its tree in order to access files or subdirectories, but
not see the content of files inside the directory (unless read is set).
Por ejemplo, en /home para poder entrar en tu directorio pero no saber el nombre de los demás
12. Dos estudiantes de informática, Estudiante1 y Estudiante2, sostienen una discusión respecto a los i‐
nodos. Estudiante1 argumenta que, dado que las memorias son cada vez más grandes y baratas, cuando se
abre un fichero es más sencillo y rápido obtener una nueva copia del i‐nodo para llevarla a la tabla de i‐
nodos en memoria, que buscar en la tabla entera para comprobar si ya está allí. Estudiante2 discrepa.
¿Quién tiene razón?
SOLUCIÓN
El estudiante 2. Sólo se debe de tener una copia válida del inodo, ya que contiene absolutamente toda la
información del fichero (menos los datos en si), que deberá de ser actualizada para hacerla visible a otras
tareas por consistencia.
13. Un sistema de ficheros basado en i‐nodos y mapa de bits contiene la siguiente información:
Mapa de bits: 1 0 0 1 0 1 1 1 0 0 0 0 1 0 0 1 0 0 …………. 0
i‐nodo 2 i‐nodo 3 i‐nodo 4 i‐nodo 5 i‐nodo 9
Tamaño 1
#Enlaces NA
Tipo F/D D
Directo 3
Tamaño 2
#Enlaces 1
Tipo F/D F
Directo 6
Tamaño 1
#Enlaces
Tipo F/D F
Directo 12
Tamaño
#Enlaces NA
Tipo F/D D
Directo 0
Tamaño 1
#Enlaces NA
Tipo F/D D
Directo
5
Indirecto Null
Indirecto 7
Indirecto Null Indirecto Null Indirecto Null
Bloque 0 Bloque 3 Bloque 5 Bloque 6 Bloque 7 Bloque 12 Bloque 15
. 5
.. 2
C 9
D 4
. 2
..
A 3
B 5
E 4
. 9
.. 5
Datos sin
formato
Datos sin
formato
a) Rellene los huecos para que el sistema sea consistente. Asuma para ello que el tamaño se expresa
en bloques.
b) Dibuje el árbol del directorio empleando óvalos para los directorios, rectángulos para los ficheros y
triángulos para los datos
SOLUCIÓN
Apartado a)
Mapa de bits: 1 0 0 1 0 1 1 1 0 0 0 0 1 0 0 1 0 0 …………. 0
i‐nodo 2 i‐nodo 3 i‐nodo 4 i‐nodo 5 i‐nodo 9
Tamaño 1
#Enlaces NA
Tipo F/D D
Directo 3
Indirecto Null
Tamaño 2
#Enlaces 1
Tipo F/D F
Directo 6
Indirecto 7
Tamaño 1
#Enlaces 2
Tipo F/D F
Directo 12
Indirecto Null
Tamaño 1
#Enlaces NA
Tipo F/D D
Directo 0
Indirecto Null
Tamaño 1
#Enlaces NA
Tipo F/D D
Directo 5
Indirecto Null
Bloque 0 Bloque 3 Bloque 5 Bloque 6 Bloque 7 Bloque 12 Bloque 15
. 5
.. 2
C 9
D 4
. 2
.. 2
A 3
B 5
E 4
. 9
.. 5
Datos sin
formato
15
Datos sin
formato
Datos sin
formato
Apartado b)
14. Un sistema de ficheros UNIX utiliza bloques de 512 bytes y direcciones de disco de 16 bits. Los nodos‐i
contienen 10 direcciones de disco para bloques de datos, una dirección de bloque índice indirecto simple y
una dirección de bloque índice indirecto doble. Conteste de manera razonada a las siguientes cuestiones:
a) ¿Cuál es el tamaño máximo de un fichero en este sistema?
b) Un programa UNIX crea un fichero en este sistema e inmediatamente después escribe un byte de
datos en la posición 1.000 y otro en la posición 10.000. ¿Cuántos bloques de datos ocupa este
nuevo fichero en disco?
SOLUCIÓN
Bloques 512B, direcciones 2B ‐> 252 direcciones por bloque
a) Tam. máximo:
Por organización: 10+256+(256)^2 ‐> 10+2^8+2^16 Bloques ~ 32’13MB
6
Por tamaño de índice: 2^16Bloques ‐> 32MB
b) Pos 1000 ‐> 1000/512=1’95 ‐> está en el bloque directo 1 (empezando en 0)
Pos 10000 ‐> 10000/512=19’5 ‐> está en el bloque directo simple 9
15. El sistema de ficheros de un SO diseñado a partir de UNIX utiliza bloques de disco de 1024 bytes de
capacidad. Para el direccionamiento de estos bloques se utilizan punteros de 16 bits. Para indicar el tamaño
del fichero y el desplazamiento (offset) de la posición en bytes en las operaciones read y write, se utilizan
números de 64 bits. Cada i‐nodo tiene 8 punteros de direccionamiento directo, 1 puntero indirecto simple y
1 puntero indirecto doble.
a) ¿Cuál será el tamaño máximo de un fichero suponiendo despreciable el espacio ocupado por el
superbloque y la tabla de i‐nodos?
b) Si se modifica el tamaño de puntero pasándolo a 32 bits, ¿cuál será el nuevo tamaño máximo?
c) Dada la siguiente estructura de directorio, en el que Jesús
comparte el fichero proyect de Mario
mediante un enlace rígido de nombre mem, indicar los contenidos de los directorios e i‐nodos que
se encontrará el sistema (y el orden en que se los encontrará) al hacer la búsqueda del fichero
memoria desde el directorio raíz.
Nota: los directorios se muestran como rectángulos y los ficheros como óvalos.
SOLUCIÓN
a) Tamaño
por offset : 264 bytes = 254 bloques 16Peta Bloques
por organización: 8 + 1024/2 + (1024/2)2 = 262644 bloques ~256K5 Bloques
por longitud de puntero: 216 bloques 64K Bloques
Resultado: 216 bloques ~64MB
b) Tamaño
por offset : 264 bytes = 254 bloques
por organización: 8 + 1024/4 + (1024/4)2 = 65800 bloques ~64K256 Bloques
por longitud de puntero: 232 bloques
Resultado: 65800 bloques ~64MB256
Sólo cálculo a través de i‐nodo: 0.5
c) Inodo1 (raíz) Bloque 4:
“.” 1
“ ..” 1
“mario” 2
“jesus” 3
“tfno” 4
7
Inodo 3 (jesus) Bloque 6
“.” 3
“ ..” 1
“notas” 7
“auxiliar” 8
Inodo7 (notas) Bloque 9
“.” 7
“ ..” 3
“memoria” 10
“fichas” 12
Inodo 10 (memoria) Bloque 12 ‐‐ datos del fichero memoria
Sin “.” y “..” ‐0.25
Sin contenido de bloques ‐0.25
16. Dado un sistema de ficheros tipo UNIX, en el que los directorios son relativamente pequeños (caben en
un bloque de disco) y únicamente tiene una partición; razona qué operaciones de disco se necesitan para
abrir el archivo “/usr/curso3/SO/alumnos.txt”. Suponer que el i‐nodo del directorio raíz está ya en
memoria y que no se ha cargado en memoria anteriormente ningún otro elemento de la ruta.
SOLUCIÓN
1. Lectura del bloque correspondiente al directorio raíz para encontrar la entrada usr y su número
de i‐nodo.
2. Lectura del i‐nodo correspondiente a la entrada usr para encontrar el bloque correspondiente al
directorio usr.
3. Lectura del bloque correspondiente al directorio usr para encontrar la entrada curso3 y su
número de i‐nodo.
4. Lectura del i‐nodo correspondiente a la entrada curso3 para encontrar el bloque
correspondiente al directorio curso3.
5. Lectura del bloque correspondiente al directorio curso3 para encontrar la entrada SO y su
número de i‐nodo.
6. Lectura del i‐nodo correspondiente a la entrada SO para encontrar el bloque correspondiente al
directorio SO.
7. Lectura del bloque correspondiente al directorio SO para encontrar la entrada alumnos.txt y su
número de i‐nodo.
8. Lectura del i‐nodo correspondiente a la entrada alumnos.txt
ejercicios SO/3.2.1-ProcesosProblemasSoluciones.pdf
Sistemas Operativos UCM 2011/2012
Soluciones Módulo 2.1 Procesos
1. Dado el siguiente programa …
a. Dibuje el esquema jerárquico de procesos que se genera para argc = 3
P2 P3
P1 P3
P0 P2 P3
P3
b. ¿Cuántos procesos se crean para argc = n? 2n
2. Use las llamadas fork(), exec(), exit() y wait() de UNIX …
P0:
pidP1 = fork(); exec(“P1”)
wait(pidP1);
pidP2 = fork() exec(“P2”)
pidP5 = fork() exec(“P5”)
pidP7 = fork(); exec(“P7”)
wait(pidP2);
pidP3 = fork() exec(“P3”)
pidP4 = fork(); exec(“P4”)
wait(pidP4, pidP5);
pidP6 = fork() exec(“P6”)
wait(pidP3, pidP6, pidP7)
exec(“P8”)
P1:
Código de P1
exit()
P2:
Código de P2
exit()
P3:
Código de P3
exit()
etc…
Alternativamente …
// programa problema2
void T0(){
{tarea P1}
envia_señal(S1,S2);
{tarea P5}
espera_señal(S3);
{tarea P6}
espera_señal(S4,S5);
{tarea P8}
}
void T1(){
espera_señal(S2);
{tarea P7}
envia_señal(S5);
}
void T2(){
espera_señal(S1);
{tarea P2}
envia_señal(S6);
{tarea P4}
envia_señal(S3);
}
void T3(){
espera_señal(S6);
{tarea P3}
envia_señal(S4);
}
main() {
{inicialización}
cobegin {
T0;T1;T2;T3
}
}
3. Podemos describir gran parte de la gestión del procesador …
a) Eventos:
1. Liberación de la UCP y paso a ejecutar un nuevo proceso
2. Fin del cuanto de ejecución o expropiación por prioridad.
3. Llamada a E/S, espera por sincronización o por retardo.
4. Fin de operación de E/S, o de fin de plazo, o señalización.
b) Siempre que exista al menos un proceso en la cola de preparados.
c) 2 1: Siempre que existan procesos preparados
3 2: Nunca. En ejecución sólo hay un proceso, que puede realizar una sóla transición.
4 1: Sólo si ambas transiciones las realiza el mismo proceso, para lo cual la UCP debería estar desocupada o
ese proceso debería expropiar al que actualmente está en uso de la UCP (lo cual supone una transición 2
adicional). O bien, si la política de planificación empleada recalcula las prioridades (pej.: política HPRN con
expropiación) y determina que hay un proceso preparado más prioritario
d) No hay transición:
1. Si la UCP está desocupada (es condición previa)
2. Nunca
3. Si solicita E/S y no hay procesos preparados para usar la UCP. En realidad en muchos sistemas operativos
suele haber un proceso ficticio de mínima prioridad, expropiable por cualquiera y siempre preparado, que
se emplea para tratar esta situación, ya que en realidad la UCP no puede estar sin operar (a no ser que se
desconecte el sistema) por lo cual esta transición siempre provocaría una transición 1.
4. Si acaba una operación de E/S y hay un proceso en ejecución no expropiable.
4. Suponga que los siguientes trabajos llegan a procesarse en los instantes indicados
P1 P2 P3 P4 Medias
FCFS 0 2,5 4 1,5 Tesp = 2
8 6,5 6 7,5 Prod = 0,381
SPN 0 3,5 3 0,5 Tesp = 1,75
8 7,5 5 6,5 Prod = 0,421
RR (q=1) 4,5 1,0 2,5 2,5 Tesp = 2,65
12,5 5,0 4,5 8,5 Prod = 0,32
SPN retardado 5 1,5 0,5 0,5 Tesp = 1,875
13 6 2,5 6,5 Prod = 0,308
FCF
S
SPN
RR
SPN retardado
0 5 10
La primera fila de cada entrada muestra el tiempo de espera de cada trabajo para la estrategia considerada y el tiempo
medio de espera al final. La segunda fila muestra el tiempo de retorno de cada trabajo y la productividad para la
estrategia considerada.
5. Cinco trabajos de lotes, de A a E, llegan a un centro de cálculo …
a) Inicialmente el tiempo se reparte entre los 5 procesos equitativamente hasta que termina de ejecutarse el más
corto, C, trás disponer de sus 2 unidades de tiempo de CPU. En ello se emplean 2 x 5 = 10 unidades de tiempo.
Todos los procesos restantes también han consumido 2 unidades de su tiempo de ejecución.
A continuación, se reparte el tiempo entre los 4 procesos restantes, hasta que el siguiente proceso más corto, D,
disponga de las 4 -2 = 2 unidades que le restan para terminar. Se emplean en ello 2 x 4 = 8 unidades más.
Razonando de este modo los tiempos de retorno de los diferentes procesos son:
C - 2 x 5 = 10
D - 10 + 2 x 4 = 18
B - 18 + 2 x 3 = 24
E - 24 + 2 x 2 = 28
A - 28 + 2 x 1 = 30
Y el tiempo medio de retorno es
(10 + 18 + 24 + 28 + 30) / 5 = 22
b) (b) Aplicando la estrategia de prioridad estricta el orden de atención a los procesos y sus tiempos de retorno
son:
B - 6
E - 14
A - 24
C - 26
D - 30
Y el tiempo medio de retorno es
(6 + 14 + 24 + 26 + 30) / 5 = 20
c) (c) Aplicando la estrategia de primero-en-llegar/primero-en-ser-atendido el orden de atención a los procesos y
sus tiempos de retorno son:
A - 10
B - 16
C - 18
D - 22
E - 30
Y el tiempo medio de retorno es
(10 + 16 + 18 + 22 + 30) / 5 = 19,2
d) (d) Aplicando la estrategia de primero-el- trabajo-más-corto el orden de atención a los procesos y sus tiempos
de retorno son:
C - 2
D - 6
B - 12
E - 20
A - 30
Y el tiempo medio de retorno es
(2 + 6 + 12 + 20 + 30) / 5 = 14
6. Considere un sistema con una política de planificación de procesos …
P2
P3
P3
P1 P1
P2
P2
P3
P3
P2
P1 P1
P1
P2 P2
P2
P2
Nivel A
Nivel B
Nivel C
10 20 30
P1
P2
P3
Uso de CPU: 100%
Tiempo de espera de P1: ((12-8) + (10-8) + (12-8))/3 = 3.33
Tiempo de espera de P2: (24-13) = 11
Tiempo de espera de P3: ((19-10) + (10-10)) / 2 = 4.5
7. Considere un sistema con una planificación MLF …
8. Repita el ejercicio anterior pero suponiendo que Ti = 2 · q …
9. En un sistema UNIX se quiere programar un proceso que lea de un archivo …
Ejercicio 2.19 de “Problemas de Sistemas Operativos” [Pérez Costoya et al.]
10. Se tiene un proceso productor y otro consumidor…
Ejercicio 2.22 de “Problemas de Sistemas Operativos” [Pérez Costoya et al.]
11. Sea un sistema operativo que sigue el modelo cliente-servidor …
Ejercicio 3.11
DISCO DISCO
Proceso A
Proceso B
Sistema_Ficheros
Controlador_Disco
12. Determinar el rendimiento (%uso de CPU y %sobrecarga del S.O.)…
1
1
1
1
2
2
2
2
1
1
2
3
2
1'
3
2'
4
3
3
1'
1'
4
2'
2'
5
3'
3'
3'
1'
4'
2'
5' 6'
4'
4'
Tiempo Total: 520
Tiempo CPU (SO) : 120
Tiempo inactividad CPU: 50
% Uso CPU = (520-50)/520 = 90,38%
% Recargo SO = 120/520 = 23,1%
o = 120/(520-50) = 25,53%
5 10 15 20 25 30
35 40 45 50
PA, H1 [30/110/40]
PA, H2 [50]
PA, H3 [30]
PA, H4 [20/60/40]
SO(C. Contexto)
PB, H1 [20/50/60]
PB, H2 [40/110/20]
PA, H1 (cont.)
PA, H2 (cont.)
PA, H3 (cont.)
PA, H4 (cont.)
SO (cont.)
PB, H1 (cont.)
PB, H2 (cont.)
11
6
5
5
+6
Inactividad
ejercicios SO/3.3.1-ComSincroProblemas.pdf
Sistemas Operativos UCM 2012/2013
Módulo 3.2 Comunicación y Sincronización
1. Escriba un programa que cree tres procesos que se conecten entre ellos utilizando una tubería tal y
como se muestra en la Figura
Modifique el programa anterior de forma que el proceso 1 genere 1000 números pares y el proceso
2 otros 1000 números impares. Tanto el proceso 1 como el proceso 2 introducen estos números en la
tubería de forma que el proceso 3 los extrae e imprime por pantalla. El programa desarrollado debe
asegurar que en la tubería nunca se insertan dos números pares seguidos o dos números impares
seguidos. Implementar dicha sincronización (entre el proceso 1 y el proceso 2)
a. Usando tuberías
b. Usando semáforos y memoria compartida
2. Implemente las operaciones de semáforos POSIX (sem_init, sem_destroy, sem_wait y
sem_port) utilizando tuberías.
3. El algoritmo de la panadería de Lamport es un algoritmo de computación creado por el científico
en computación Dr Leslie Lamport, para implementar la exclusión mutua de N procesos o hilos de
ejecución sin necesidad de ningún soporte HW específico. Se inspira en el funcionamiento normal de
cualquier comercio con un tendero y múltiples clientes (ej. una panadería). En este escenario, un cliente
que llega a la panadería coge un número con su turno y espera pacientemente a ser atendido. Sin
embargo, como se ha ilustrado en otros ejemplos, obtener el número para el turno no es trivial en un
computador debido a la posibilidad de que varios procesos reciban el mismo. El siguiente pseudo-
código (wikipedia) ilustra la solución de Lamport a dicho problema:
//
Variables
globales
Num[N]
=
{0,
0,
0,
...,
0};
Eligiendo[N]
=
{falso,
falso,
falso,
...,
falso};
//Código
del
hilo
i‐ésimo
Hilo(i)
{
loop
{
//Calcula
el
número
de
turno
Eligiendo[i]
=
cierto;
Num[i]
=
1
+
max(Num[1],...,
Nun[N]);
Eligiendo[i]
=
falso;
//Compara
con
todos
los
hilos
for
j
in
1..N
{
//Si
el
hilo
j
está
calculando
su
número,
espera
a
que
termine
while(
Eligiendo[j]
)
{yield()}
while(
Num[j]!=0
&&
(Num[j]<Num[i]||(Num[j]==Num[i]
&&
i<j))
)
{yield()}
}
Proces1
Proces2
Proces3 tubería
//
Sección
crítica
...
//
Fin
de
sección
crítica
Número[i]
=
0;
//
Código
restante
}
}
Discutir la validez de la solución de Lamport (seguridad, interbloqueo, inanición).
4. Utilizando la instrucción XCHG(a,b) (exchange) de intercambio de dos variables en una
operación indivisible:
a. Discutir la corrección (seguridad, interbloqueo, inanición) de la siguiente solución al problema de la
exclusión mutua.
b. Generalizar a n hilos
c. ¿Qué ocurriría si XCHG no fuera indivisible?
int c; //Compartida entre hilos
main() {
c=1;
Hilo1(); Hilo2(); // Crea 2 nuevos hilos
}
Hilo1() {
int d;
d = 0;
while (1) {
Secc_no_crítica();
do{
XCHG(c,d)}
while(d==0);
Secc_crítica();
XCHG(c,d);
}
}
Hilo2() {
int e;
e = 0;
while (1) {
Secc_no_crítica();
do{
XCHG(c,e)}
while(e==0);
Secc_crítica();
XCHG(c,e)
}
}
5. Codificar el problema de los lectores/escritores de forma que sean los escritores los que tengan
prioridad de acceso (conocido como “Segundo Problema de los Lectores/Escritores”). Emplear como
método de comunicación/sincronización únicamente semáforos.
6. En el problema de los lectores/escritores, si se prioriza a un colectivo, ya sea lectores o escritores,
es posible que los procesos priorizados nieguen el acceso al recurso compartido al otro colectivo y que,
por lo tanto, se produzca inanición (starvation). Codificar una solución para el problema de los
lectores/escritores en la cual se otorgue acceso en función del orden de solicitud (conocido como
“Tercer Problema de los Lectores/Escritores”). Emplear para ello semáforos.
7. El Barbero Dormilón: una barbería está compuesta por una sala de espera, con n sillas, y la sala
del barbero, que tiene un sillón para el cliente que está siendo atendido. Las condiciones de atención a
los clientes son las siguientes:
a. Si no hay ningún cliente, el barbero se va a dormir
b. Si entra un cliente en la barbería y todas las sillas están ocupadas, el cliente abandona la barbería
c. Si hay sitio y el barbero está ocupado, se sienta en una silla libre
d. Si el barbero estaba dormido, el cliente le despierta
e. Una vez que el cliente va a ser atendido, el barbero invocará cortarPelo() y el cliente
recibirCortePelo()
Escriba un programa que coordine al barbero y a los clientes utilizando mutex y semáforos POSIX
para la sincronización entre procesos.
8. Un monitor lo podemos entender como un objeto cuyos métodos son ejecutados con exclusión
mutua, por lo que un hilo/proceso que invoque un método del monitor se puede bloquear a la espera de
un evento generado por otro hilo/proceso a través del mismo monitor. Dicha exclusión mutua y espera
selectiva, se suele implementar mediante cerrojos y variables condicionales.
Resolver el problema de la cena de los filósofos codificando un monitor (mutex y variables
condicionales) basándose en el siguiente ejemplo de filósofo situado en la posición i-ésima de la
mesa:
Filósofo(int
i){
while(1){
pensar();
//Solicitamos
al
monitor
la
necesidad
de
coger
los
palillos
cogerPalillosMonitor(i);
comer();
//Solicitud
al
monitor
que
queremos
dejar
los
palillos
dejarPalillosMonitor(i);
}
}
9. Considerar las siguientes primitivas de sincronización:
a. ADVANCE(A): incrementa el valor de la variable A en 1.
b. AWAIT(A,C): bloquea el proceso que ejecuta esta instrucción hasta que A > C
Usando estas primitivas, desarrollar una solución para el problema productor/consumidor para un
único productor y consumidor con tamaño del almacén circular n > 1
10. El Problema de los Fumadores [Suhas Patil]: considerar un sistema con tres procesos fumadores
y un proceso agente. Continuamente cada fumador se prepara un cigarrillo y lo fuma. Para hacer un
cigarrillo se necesitan tres ingredientes: tabaco, papel y cerillas. Uno de los procesos tiene infinito
papel, otro tabaco y el tercero cerillas. El agente tiene provisión infinita de los tres
ingredientes.
El agente coloca dos ingredientes distintos y de forma aleatoria en la mesa. El fumador que tiene el
ingrediente que falta puede proceder a preparar y fumar un cigarrillo, haciendo una señal al agente
cuando acaba, el agente en este instante repite la operación, pone otros dos de los tres ingredientes en la
mesa. La operación se repite indefinidamente.
Escribir un programa que sincronice al agente y los fumadores mediante semáforos o mutexes y
variables condicionales. Asúmase que el agente no tiene forma de consultar los ingredientes que posee
cada fumador.
11. Una tribu de salvajes se sirven comida de un caldero con M raciones de estofado de misionero.
Cuando un salvaje desea comer, se sirve una ración del caldero a menos que esté vacío. Si está vacío
deberá avisar al cocinero para que reponga otras M raciones de estofado, y entonces se podrá servir su
ración. Un número arbitrario de salvajes se comportan del siguiente modo:
while
(True){
getServingFromPot()
eat()
}
Y el concinero se compora de la siguiente forma:
while
(True){
putServingsInPot(M)
}
Se deben cumplir las siguientes restricciones:
1. Los salvajes no pueden invocar getServingFromPot()
si el caldero está vacío
2. El cocinero sólo puede invocar putServingsInPot(M) si el caldero está vacío
a. Añada el código necesario para garantizar la correcta sincronización, usando semáforos POSIX
y variables de tipo entero, booleano…
b. Añada el código necesario para garantizar la correcta sincronización, usando cerrojos y
variables condicionales
12. El problema de la montaña rusa [Andrews’s Concurrent Programming]: suponga que hay un
hilo por cada pasajero, haciendo un total de n, y un hilo para el coche. Los pasajeros están
constantemente esperando y subiéndose a la montaña rusa, que puede llevar C pasajeros (C<n). El
coche sólo puede comenzar un viaje cuando está lleno. Se deben cumplir las siguientes restricciones:
1. Los pasajeros deben invocar board() y unboard()
2. El coche debe invocar load(),
run()
y unload()
3. Los pasajeros no pueden hacer board() hasta que el coche haya invocado load()
4. El coche no puede partir (run())
hasta que no haya C pasajeros en él.
5. Los pasajeros no se pueden bajar hasta que el coche invoque unload()
a. Escriba el código necesario usando semáforos POSIX generales (y variables enteras,
booleanas…)
b. Escriba el código necesairio usando cerrojos y variables condicionales (y variables enteras,
booleanas…)
13. El problema del sushi bar [Kenneth Reek]: supóngase un restaurante japonés con 5 asientos, si
un cliente llega cuando hay un asiento libre puede sentarse inmediatamente. Sin embargo, si un cliente
llega y encuentra los 5 asientos ocupados, supondrá que todos los clientes están cenando juntos y
esperará hasta que todos ellos se levanten antes de tomar asiento. Además, los clientes son atendidos
por orden. Codifique un programa que se comporte como un cliente según las especificaciones
anteriores usando semáforos generales.
14. El problema del cuidado de niños [Max Hailperin]: en cierta guardería se debe de cumplir que
por cada tres niños debe de estar presente al menos un adulto. Codificar (con semáforos generales) el
código correspondiente a los adultos de manera que se cumpla esta restricción y suponiendo que el
número de niños se mantiene constante.
ejercicios SO/3.3.2-ComSincroProblemasSoluciones.pdf
Sistemas Operativos UCM 2011/2012
Soluciones Módulo 3.2 Comunicación y Sincronización
1. Escriba un programa que cree tres procesos que se conecten entre ellos …
a. Usando tuberías
#define PROD 1000
int fds[2] , fdPar, fdImpar;
main(){
int i, dato;
char c;
pipe(fdPar); pipe(fdImpar);
//Damos el turno a Par()
write(fdPar[1], &c, sizeof(char));
pipe(fds)
if(!fork()){
//Cerrar fds[0],fdImpar[0],fdPar[1]
Pares();
}
if(!fork()){
//Cerrar fds[0],fdImpar[1],fdPar[0]
Impares();
}
//Cerrar fdPar[0-1],fdImpar[0-1],fds[1]
for(i=0; i<PROD*2; i++){
read(fds[0], &dato, sizeof(ind));
print(“Dato: %d”, dato);
//Esperamos a los hijos
wait(NULL);wait(NULL);
}
Pares(){
char c;
int i;
for(i=0; i<PROD*2; i+=2){
read(fdPar[0], &c, sizeof(char));
write(fds[1], &i, sizeof(ind));
write(fdImpar[1], &c, sizeof(char));
}
exit(0); //Cierra el resto de FD’s
}
Impares(){
char c;
int i;
for(i=0; i<PROD*2; i+=2){
read(fdImpar[0], &c, sizeof(char));
write(fds[1], &i, sizeof(ind));
write(fdPar[1], &c, sizeof(char));
}
exit(0); //Cierra el resto de FD’s
}
Proces1
Proces2
Proces3 tubería
b. Usando semáforos y memoria compartida
#define PROD 1000
main(){
int fds[2];
sem_t * sems;
sem_t * semPar;
sem_t * semImpar;
sems = mmap(NULL, 2*sizeof(sem_t),
PROT_READ|PROT_WRITE,
MAP_SHARED|MAP_ANON,-1,0);
semPar=sems [0]; semImpar=sems [1];
//Damos el turno a Par()
sem_init(semPar, 1, 1);
sem_init(semImpar, 1, 0);
pipe(fds)
if(!fork()){
//Cerrar fds[0];
Pares(fdIn, semPar, semImpar);
}
else if(!fork()){
//Cerrar fds[0];
Impares(fdIn, semPar, semImpar);
}
else{
//Cerrar fds[1];
Consumidor(fds[0]);
sem_destroy(semPar);
sem_destroy(semImpar);
}
exit(0); //Cierra FDs y hace unmap
}
Pares(fdIn, semPar, semImpar){
int i;
for(i=0; i<PROD*2; i+=2){
sem_wait(&semPar);
write(fdIn, &i, sizeof(int));
sem_post(&semImpar);
}
exit(0); //Cierra FDs y hace unmap
}
Impares(fdIn, semPar, semImpar){
int i;
for(i=0; i<PROD*2; i+=2){
sem_wait(&semImpar);
write(fdIn, &i, sizeof(int));
sem_post(&semPar);
}
exit(0); //Cierra FDs y hace unmap
}
Consumidor(fdOut){
int i, dato;
for(i=0; i<PROD*2; i++){
read(fdOut, &dato, sizeof(int));
print(“Dato: %d”, dato);
}
}
2. Implemente las operaciones de semáforos POSIX (init, wait y signal) utilizando tuberías.
semaphore CreateSem(int count){
int *fd, i;
/*Space for two file-descriptors*/
fd = malloc(2*sizeof(int));
pipe(fd);
for(i=0; i<count; i++)
write(fd[1], "x", sizeof(char));
return(fd);
}
void Post(semaphore s){
char c;
read(s[0], &c, sizeof(char));
}
void Wait(semaphore s){
char c;
write(s[1], &c, sizeof(char));
}
int DelSem(semaphore s){
close(s[0]);
close(s[1]);
free(s);
}
3. El algoritmo de la panadería de Lamport es un algoritmo …
Supongamos los tickets de la siguiente manera:
Id 1 2 3 4 5 6 7 8 9
Número 1 5 0 3 2 4 5 3 0
Eligiendo false false false false false false true false true
Si elegimos ejecutar Id1, hay que esperar (1er bucle while) a que elijan Id7 e Id9. Una vez que esto
haya ocurrido, tendrán un número entero asignado (ojo, este valor puede ser 1-6). El segundo bucle
esperará si encuentra algún hilo con ticket y que sea menor de 1 o igual y con Id menor. Esto no
ocurre.
Id2 esperará a Id7 e Id9 en el primer while y a todos los que tienen ticket menor de 5 o igual a 5 y
con Id menor. Eespera a Id1, (no a si mismo, no a Id3), a Id4 (Id5-6 ya habrán terminado, si Id7
recibe un 5 no por que 2<7), a Id8 y dependerá a Id9.
Id3 no tiene ticket
Id4 …
4. Utilizando la instrucción XCHG(a,b) de intercambio de dos variables en …
a) Es segura, sin interbloqueo, y con posible aplazamiento indefinido.
Basta para ello advertir que inicialmente los valores de las variables c (global), d de p1 (local)
y e de p2 (local) que
intervienen en la negociación del acceso a la sección crítica forman la tripleta (1,0,0) y que las únicas operaciones
que se efectúan son intercambios indivisibles sin modificación de valores. Por tanto los valores que se pueden
alcanzar son:
(1,0,0) ==> p1 y p2 están fuera de sus Secciones Críticas
(0,1,0) ==> p1 está en su Sección Crítica, y p2 está fuera de la suya
(0,0,1) ==> p1 está fuera de su Sección Crítica y p2 dentro de la suya
Luego la exclusión mutua es segura.
Para producirse interbloqueo deberían alcanzarse los valores (0,0,0): ambos procesos fuera y sin posibilidad de
entrar, lo cual no es posible.
El aplazamiento indefinido es posible puesto que no hay ningún mecanismo que impida que los valores estén
oscilando entre (1,0,0) y (0,1,0), por ejemplo, sin dar opción a p2 a pasar a su sección crítica.
b) La generalización a n procesos es inmediata. Sólo hay que repetir el esquema de cualquiera de los procesos p1 o
p2 el número de veces que haga falta, para negociar la exclusión mutua con un (n+1)-tuple de valores de los cuales
uno vale 1 y el resto 0.
c) Si XCHG no fuera indivisible ya no se aseguraría la existencia invariante de uno y sólo un 1, y ello podría
ocasionar fallos de exclusión mutua (ej. (0,1,1)) e interbloqueos (ej.(0,0,0)).
5. Codificar el problema de los lectores/escritores de forma que sean los escritores …
semáforo mtxLect, mtxEscr; // inicializados a 1
semáforo lectores, escritores; // inicializados a 1
integer n_lectores, n_escritores; // #lect/escr en SC=0
//Múltiples instancias
Lector() {
while(1)
wait(lectores);
wait(mtxLect);
n_lectores++;
if(n_lectores==1)
wait(escritores)
post(mtxLect)
post(lectores);
----- Leer -----
wait(mtxLect);
n_lectores--;
if(n_lectores==0)
post(escritores);
post(mtxLect);
//Múltiples instancias
Escritor() {
while(1){
wait(mtxEscr);
n_escritores++;
if(n_escritores==1)
wait(lectores);
post(mtxEscr);
wait(escritores);
----- Escribir -----
post(escritores);
wait(mtxEscr);
n_escritores--;
if (n_escritores==0)
post(lectores);
post(mtxEscr);
}
}
}
}
mtxLect, mtxEscr se utilizan únicamente para asegurar acceso exclusivo a n_lectores y n_escritores.
El semáforo lectores lo usan los escritores para denegar el acceso a los lectores. Cuando un escritor quiere acceder
a la sección crítica, si es el primero en intentarlo, deniega futuros accesos a los lectores haciendo un
wait(lectores). Hasta que no haya ningún escritor intentando acceder a la sección crítica (n_escritores=0)
no se hace un post(lectores).
Si un lector intenta acceder a la sección crítica y es capaz de hacerse con el semáforo lectores, es porque no hay
escritores. Si hay un número arbitrario de lectores accediendo a la región compartida y un escritor solicita acceso, éste
bloquea a futuros lectores (como se ha indicado anteriormente) y sólo tiene que esperar a que todos los lectores que
están accediendo a la sección crítica terminen.
6. En el problema de los lectores/escritores, si se prioriza a un colectivo, …
semáforo mtxOrder, mtxAccess; // inicializados a 1
semáforo mtxCount; // inicializado a 1
integer n_lectores; // #lect en SC=0
//Múltiples instancias
Lector(){
while(1)
wait(mtxOrder);
wait(mtxCount);
contador++;
if(n_lectores==1)
wait(mtxAccess);
post(mtxCount)
post(mtxOrder);
----- Leer -----
wait(mtxCount);
n_lectores--;
if(n_lectores==0)
post(mtxAccess);
post(mtxCount);
}
}
//Múltiples instancias
Escritor(){
while(1){
wait(mtxOrder);
wait(mtxAccess);
post(mtxOrder);
----- Escribir -----
post(mtxAccess);
}
}
NOTA: Esta solución sólo asegura la ausencia de inanición sí y sólo sí los semáforos emplean la política FIFO cuando
se producen bloqueos y desbloqueos
7. Codificar el problema del Barbero Dormilón usando mutex y semáforos.
sem_t sillon, afeitado; //Inicializados a 0
mutex_t mutex;
int sillas=0;
boolean esperando=FALSE;
const int MAX = 5;
//Una instancia
Barbero (){
while (TRUE) {
lock(mutex);
if (sillas == 0) {
esperando = TRUE;
unlock(mutex);
wait(sillon);
lock(mutex);
esperando = FALSE
}
sillas = sillas-1;
unlock(mutex);
post(afeitado);
cortarPelo();
}
}
//Múltiples instancias
Cliente(){
lock(mutex);
if (sillas < MAX) {
sillas = sillas+1;
if (esperando)
post(sillon);
unlock(mutex);
wait(afeitado);
recibirCortePelo();
} else
unlock(mutex);
}
Con esta solución, ¿es posible que un cliente que solicite el corte de pelo a través de la cola Clientes después que
otro reciba su corte de pelo antes? Sí, el primero que haga wait(afeitado) es el que primero se pone en cola de
verdad si los semáforos se comportan de manera FIFO, primero en bloquearse, primero en desbloquearse.
8. Un monitor lo podemos entender como un objeto cuyos métodos son ejecutados …
Solución Silberschatz:
//Interfaz pública del monitor:
cogerPalillosMonitor(int i);
dejarPalillosMonitor(i);
//Variables privadas
int estado[N] {PENSANDO, PENSANDO, ..., PENSANDO};
condición espera[N];
cogerPalillosMonitor(int i){
lock(mutex);
estado[i]=HAMBRIENTO;
test(i);
if(estado[i]!= EATING)
cond_wait(espera[i], mutex);
unlock(mutex);
}
dejarPalillosMonitor(i){
lock(mutex);
estado[i]=PENSANDO;
test((i-1)%N);
test((i+1)%N);
unlock(mutex);
}
test(int i){
if( estado[(i-1)%N] != COMIENDO &&
estado[i] == HAMBRIENTO &&
estado[(i+1)%N] != COMIENDO ){
estado[i]=COMIENDO;
cond_signal(espera[i]);
}
}
9. Considerar las siguientes primitivas de sincronización …
int prod=0, cons=0;
elementos deposito[N];
//Una instancia
void Productor(){
while(TRUE) {
AWAIT(cons, prod - N);
deposito[prod % N] = producir();
ADVANCE(prod);
}
}
//Una instancia
void Consumidor(){
while(TRUE) {
AWAIT(prod, cons);
consumir(deposito[cons % N]);
ADVANCE(cons);
}
}
10. El Problema de los Fumadores [Suhas Patil]: …
// Program Fumadores;
int ingr[3]= {FALSE,FALSE,FALSE}; // tabaco, cerillas, papel
mutex_t ingr_mutex;
cond_t ingr_cond;
Agente() {
int i, j;
while (TRUE) {
i = random()%3;
do{j=random()%3;} while (j == i);
lock (ingr_mutex)
while (tabaco || cerillas || papel)
wait(ingr_cond, ingr_mutex)
// tabaco?
ingr[0] = (i==0) || (j==0);
// cerillas?
ingr[1] = (i==1) || (j==1);
// papel?
ingr[2] = (i==2) || (j==2);
broadcast(ingr_cond1);
unlock (ingr_mutex)
}
}
void FumadorTabacoCerillas() {
while (TRUE) {
lock(ingr_mutex);
//tabaco && cerillas
while(!ingr[0] || !ingr[1])
wait(ingr_cond, ingr_mutex);
// tabaco
ingr[0] = FALSE;
// cerillas
ingr[1] = FALSE;
signal(ingr_cond);
unlock(ingr_mutex);
fumar();
}
}
11. Una tribu de salvajes se sirven comida de un caldero …
a) Semáforos
servings = 0
mutex = Semaphore(1)
emptyPot = Semaphore(0)
fullPot = Semaphore(0)
Savaje{
while (True){
mutex.wait()
if (servings == 0) {
emptyPot.signal()
fullPot.wait()
servings = M
}
servings -= 1
getServingFromPot()
mutex.signal()
eat()
}
}
Cocinero(){
while True{
emptyPot.wait()
putServingsInPot(M)
fullPot.signal()
}
}
b) Cerrojos
servings = 0
lock_t mutex;
var_cond emptyPot;
var_cond fullPot;
Savaje{
while (True){
lock(mutex);
while (servings == 0) {
cond_signal(emptyPot);
cond_wait(fullPot,mutex);
}
servings -= 1
getServingFromPot()
mutex.signal()
eat()
}
}
Cocinero(){
while True{
lock(mutex);
while (servings>0) {
cond_wait(emptyPot,mutex);
servings=M;
}
cond_broadcast(fullPot);
unlock(mutex);
}
}
Esta codificación no es del todo estilosa porque:
- Cuando esté vacía la olla, llegará un salvaje y hará un “signal” al cocinero. Luego, se duerme
dejando el mutex abierto. Luego PUEDE llegar otro(s) salvaje (antes de que el cocinero despierte)
y volverá a hacer otro signal y quedará en el wait. Finalmente, el cocinero se despertará, servirá M
raciones, despertará a todos (eso está bien) y se volverá a dormir….. salvo que “cond_signal”
tenga un efecto “acumulativo”, pero no lo tiene: si se hace un signal a una variable cond. en la que
nadie espera, no hay efecto
- La diferencia con semáforos es que aquí no se garantiza el orden de los salvajes: podría ocurrir (en
función de la planificación que se haga tras el broadcast) que el salvaje que avisó al cocinero no
sea el primero en coger su ración (o cualquier variación en el orden entre los salvajes que hayan
llegado a la cola tras ese aviso).
12. El problema de la montaña rusa [Andrews’s Concurrent Programming]: …
mutex1 = Semaphore(1) //Protección para boarders
mutex2 = Semaphore(1) //Protección para unboarders
boarders = 0 //Pasajeros en el coche
unboarders = 0 //Pasajeros que han bajado del coche
boardQueue = Semaphore(0) //Los pasajeros esperan aquí antes se subir
unboardQueue = Semaphore(0) //Los pasajeros esperan aquí para bajar
allAboard = Semaphore(0) //Coche lleno
allAshore = Semaphore(0) //Coche vacío
//Coche
while(1){
load()
boardQueue.signal(C) // NO POSIX
allAboard.wait()
run()
unload()
unboardQueue.signal(C)
allAshore.wait()
}
//Viajero
while True{
boardQueue.wait()
board()
mutex1.wait()
boarders += 1
if boarders == C{
allAboard.signal()
boarders = 0
}
mutex1.signal()
unboardQueue.wait()
unboard()
mutex2.wait()
unboarders += 1
if unboarders == C {
allAshore.signal()
unboarders = 0
}
mutex2.signal()
}
13. El problema del sushi bar [Kenneth Reek]: …
SOLUCION ERRONEA:
eating = waiting = 0 //# número de hilos sentados y esperando
mutex = Semaphore(1) //Exclusión mutual par alas variables anteriores
must_wait = False //Bar lleno o vaciándose después de lleno
block = Semaphore(0) //Cola de clients en espera
mutex.wait()
if (must_wait) {
waiting += 1
mutex.signal()
block.wait()
mutex.wait() # reacquire mutex POSIBLE ERROR
waiting -= 1
}
eating += 1
must_wait = (eating == 5)
mutex.signal()
eatSushi();
mutex.wait()
eating -= 1
if (eating == 0) {
n = min(5, waiting)
block.signal(n) // ESTO NO EXISTE EN POSIX. Sería como un bucle
must_wait = False //NACHO CUIDADO: y si n==5???
}
mutex.signal()
If a customer arrives while the bar is full, he has to give up the mutex
while he waits so that other customers can leave. When the last customer leaves,
she signals block, which wakes up at least some of the waiting customers, and
clears must wait.
But when the customers wake up, they have to get the mutex back, and that
means they have to compete with incoming new threads. If new threads arrive and
get the mutex first, they could take all the seats before the waiting threads.
This is not just a question of injustice; it is possible for more than 5
threads to be in the critical section concurrently, which violates the
synchronization constraints.
The only reason a waiting customer has to reacquire the mutex is to update
the state of eating and waiting, so one way to solve the problem is to make the
departing customer, who already has the mutex, do the updating.
eating = waiting = 0 //# número de hilos sentados y esperando
mutex = Semaphore(1) //Exclusión mutual par alas variables anteriores
must_wait = False //Bar lleno o vaciándose después de lleno
block = Semaphore(0) //Cola de clients en espera
mutex.wait()
if (must_wait){
waiting += 1
mutex.signal()
block.wait()
}
else{
eating += 1
must_wait = (eating == 5)
mutex.signal()
}
eatSushi();
mutex.wait()
eating -= 1
if eating == 0:
n = min(5, waiting)
waiting -= n
eating += n
must_wait = (eating == 5)
block.signal(n)
}
mutex.signal()
When the last departing customer releases the mutex, eating has already been
updated, so newly arriving customers see the right state and block if necessary.
Reek calls this pattern “I’ll do it for you,” because the departing thread is
doing work that seems, logically, to belong to the waiting threads.
SOLUCION POCO ELEGANTE (Y POCO DIDACTICA…)
Reek’s alternative solution is based on the counterintuitive notion that we
can transfer a mutex from one thread to another! In other words, one thread can
acquire a lock and then another thread can release it. As long as both threads
understand that the lock has been transferred, there is nothing wrong with this.
eating = waiting = 0 //# número de hilos sentados y esperando
mutex = Semaphore(1) //Exclusión mutual par alas variables anteriores
must_wait = False //Bar lleno o vaciándose después de lleno
block = Semaphore(0) //Cola de clients en espera
mutex.wait()
if must_wait{
waiting += 1
mutex.signal()
block.wait() //when we resume, we have the mutex
waiting -= 1
}
eating += 1
must_wait = (eating == 5)
if (waiting and not must_wait)
block.signal() // and pass the mutex
else
mutex.signal()
eatSushi();
mutex.wait()
eating -= 1
if eating == 0
must_wait = False
if (waiting and not must_wait)
block.signal() //and pass the mutex
else
mutex.signal()
If there are fewer than 5 customers at the bar and no one waiting, an
entering customer just increments eating and releases the mutex. The fifth
customer sets must wait.
If must wait is set, entering customers block until the last customer at the
bar clears must_wait and signals block. It is understood that the signaling
thread gives up the mutex and the waiting thread receives it. Keep in mind,
though, that this is an invariant understood by the programmer, and documented
in the comments, but not enforced by the semantics of semaphores. It is up to us
to get it right.
When the waiting thread resumes, we understand that it has the mutex. If
there are other threads waiting, it signals block which, again, passes the mutex
to a waiting thread. This process continues, with each thread passing the mutex
to the next until there are no more chairs or no more waiting threads. In either
case, the last thread releases the mutex and goes to sit down.
14. El problema del cuidado de niños [Max Hailperin]: en cierta guardería se debe de cumplir que por
cada tres niños debe de estar presente al menos un adulto. Codificar el código correspondiente a los
adultos de manera que se cumpla esta restricción y suponiendo que el número de niños se mantiene
constante.
Hailperin suggests that you can almost solve this problem with one semaphore.
Listing 7.5: Child care hint
multiplex = Semaphore(0)
Adulto{
mutiplex.signal(3)
# Atender a los niños
multiplex.wait()
multiplex.wait()
multiplex.wait()
# Salir de la sala
}
Multiplex counts the number of tokens available, where each token allows a
child thread to enter. As adults enter, they signal multiplex three times; as
they leave, they wait three times. But there is a problem with this solution.
Puzzle: what is the problem?
Adulto{
mutiplex.signal(3)
# Atender a los niños
mutex.wait()
multiplex.wait()
multiplex.wait()
multiplex.wait()
mutex.signal()
# Salir de la sala
}
Amplíe la solución anterior para que tenga en cuenta la posible variación de la cantidad de niños.
Codifique el hilo correspondiente a los niños:
Solución página 199 de Allen B. Downey “The Little Book of Semaphores”
Version 2.1.5
ejercicios SO/4.2-EntradaSalidaProblemas.pdf
Facultad de Informática
Universidad Complutense de Madrid
Problemas de Sistemas Operativos Módulo 4 / pág. 1
PROBLEMAS DE SISTEMAS OPERATIVOS
MÓDULO 4 – GESTIÓN DE ENTRADA/SALIDA
1. Un disco tiene 305 cilindros, 4 cabezas, y 17 sectores de 512 bytes cada uno. El disco
gira a 3000 rpm y tiene un mecanismo de cabezas móviles con un tiempo medio de
posicionamiento de 30 ms (90 ms para el caso peor).
a. Calcular los tiempos en el mejor y el peor caso necesarios para transferir 20
bloques consecutivos y 20 bloques aleatoriamente distribuidos.
b. Indicar cuáles son los factores determinantes para el cálculo de los tiempos de
transferencia y la variabilidad entre las cifras del mejor y peor caso.
c. Especificar claramente las consideraciones de ambas situaciones.
2. Supóngase un disco de 256 cilindros, 4 cabezas, 100 sectores por pista y 2KB por
sector. El disco gira a 6000rpm y el tiempo de desplazamiento o posicionamiento del
brazo de cabezas de lectura/escritura es de 0.5ms por cilindro. El disco gira en
dirección ascendente desde el sector 0 al 99 e inicialmente se encuentra en CPS
(Cilindro, Pista y Sector)= (25, 3, 12).
a. Determinar el tiempo de posicionamiento del brazo de disco hasta alcanzar
CPS=(15,2,15).
b. Calcular el tiempo necesario para la lectura de 900KB físicamente consecutivos
a partir de la posición CPS del apartado anterior
c. Y la posición CPS de la cabeza tras la lectura.
3. Supongamos un disco flexible con 40 cilindros, en el que un posicionamiento tarda
6ms por cilindro. Si no se intenta colocar los bloques de un fichero cercanos unos a
otros, dos bloques lógicamente consecutivos (es decir, que se siguen el uno al otro
dentro del fichero) se encontrarán separados 13 cilindros por término medio. Sin
embargo, si se intenta agrupar los bloques relacionados, la distancia media entre
bloques puede reducirse a 2 cilindros. ¿Cuánto tiempo llevaría leer un fichero de 100
bloques en ambos casos, si la latencia rotacional es de 10ms y el tiempo necesario para
realizar la lectura de un bloque son 20ms?
4. El espacio libre del disco puede contabilizarse mediante una lista o mediante un
mapa de bits. Las direcciones de disco requieren D bits. Para un disco con B bloques
totales, F de los cuales están libres, establecer la condición para la cuál la lista de
bloques libres ocupa menos espacio que el mapa de bits. Para D igual a 16 bits,
expresar la respuesta como porcentaje del espacio de disco que debe estar libre.
5. Admitamos las siguientes simplificaciones: un computador tiene instrucciones que
requieren dos ciclos de bus, uno para acceder a la instrucción y otro para acceder al
dato. Cada ciclo de bus tarda 250ns y cada instrucción tarda 500ns (es decir, el tiempo
de procesamiento interno es despreciable). El computador dispone además de un disco
en el que cada pista contiene 16 sectores de 512 bytes. El tiempo de rotación del disco
es de 8,092ms.
a. ¿Cuál es el rendimiento del computador expresado en MIPS?
b. ¿Cuál es el porcentaje de reducción del rendimiento que sufre el computador
durante una transferencia de DMA si cada una consume un ciclo de bus?
Facultad de Informática
Universidad Complutense de Madrid
Problemas de Sistemas Operativos Módulo 4 / pág. 2
Considerar dos casos: transferencias de 8 bits y transferencias de 16 bits.
6. El rendimiento de un sistema de ficheros depende críticamente de la tasa de aciertos
de la cache de disco (fracción de bloques encontrados en la cache). Si se tarda 1ms en
satisfacer una petición desde la cache, pero 40ms más en satisfacerla si se necesita una
lectura de disco, obtener una fórmula para el tiempo medio necesario para satisfacer
una petición si la tasa de acierto es h. Trazar la gráfica de la función para valores de h
entre 0 y 1.
7. Comparar las políticas de planificación de discos FCFS, SSF, SCAN y C-SCAN
simulando la siguiente lista de peticiones:
Tiempo [ms] 0 23 25 29 35 45 57 83 88 95
Pista 45 132 20 23 198 170 180 78 73 150
Para cada política, calcular la media y la desviación estándar del tiempo necesario para
atender a las peticiones. Suponer que el disco está posicionado inicialmente en la pista
1, que hay 200 pistas, que una búsqueda tarda (20 + 0’1 · P)ms, siendo P el número de
pistas que se recorre, que la latencia rotacional es de 8ms, y que el cumplimiento
estricto de la petición lleva 2ms.
8. Considerar un disco con c cilindros, p pistas por cilindro y s sectores por pista y una
longitud de sector de ls bytes. Un fichero L está almacenado de forma contigua en el
disco a partir de la posición (cL, pL, sL), donde cL, pL y sL son números de cilindro,
pista y sector, respectivamente. Deducir una fórmula para calcular la dirección de disco
(es decir, cilindro, pista y sector) de un byte situado en la posición n del fichero.
9. Un disco tiene un factor de intercalado de 2. Dispone de 8 sectores de 512 bytes por
pista y su velocidad de rotación es de 3000 rpm. ¿Cuánto tarda en leer todos los
sectores de una pista en orden, suponiendo que la cabeza ya está correctamente
posicionada en la pista y que se necesita 1/2 rotación para que el sector 0 se halle justo
debajo de la cabeza? ¿Cuál es la velocidad de transferencia? Repetir el problema para
un disco de las mismas características con factor de intercalado 1. ¿Cuánto se degrada
la velocidad de transferencia debido a la diferencia de intercalado?
ejercicios SO/4.2-EntradaSalidaProblemasSoluciones.pdf
Facultad de Informática
Universidad Complutense de Madrid
Problemas de Sistemas Operativos Módulo 4 / pág. 1
PROBLEMAS DE SISTEMAS OPERATIVOS
MÓDULO 4 – GESTIÓN DE ENTRADA/SALIDA
1. Un disco tiene 305 cilindros, 4 cabezas, y 17 sectores de 512 bytes cada uno. El disco
gira a 3000 rpm y tiene un mecanismo de cabezas móviles con un tiempo medio de
posicionamiento de 30 ms (90 ms para el caso peor).
a. Calcular los tiempos en el mejor y el peor caso necesarios para transferir 20
bloques consecutivos y 20 bloques aleatoriamente distribuidos.
b. Indicar cuáles son los factores determinantes para el cálculo de los tiempos de
transferencia y la variabilidad entre las cifras del mejor y peor caso.
c. Especificar claramente las consideraciones de ambas situaciones.
Solución
El tiempo que tarda en dar una vuelta el disco (la latencia rotacional) se calcula como:
3000 rpm = 50 rps Trot = 20 ms/vuelta
Por tanto el tiempo de lectura de un sector es:
Tsector = 20 / 17 = 1.176 ms
La velocidad máxima de transferencia en bits/segundo para una sola cabeza es:
Vmax = (17 · 512 · 8) bits / 20 ms = 3.481.600 bps = 3.32 Mb/s
(a1) Transferencia de 20 bloques consecutivos
CASO MEJOR: Las cabezas ya están posicionadas en el primero de los 20 sectores y los 20
sectores forman parte de un mismo cilindro:
20 · Tsector = 20 · 1.176 = 23.53 ms
CASO PEOR: Las cabezas están posicionadas al otro extremo de donde se encuentran los 20
bloques, al alcanzar el cilindro adecuado se hace necesario esperar una rotación completa
para alcanzar el primer sector.
Tseek-extremo + Trot + 20 · Tsector =
90 + 20 + 20 x 1.176 = 133.53 ms unas 6 veces más lento
suponiendo que
Tseek-medio = Tseek1 · (305 / 3) Tiempo medio es el correspondiente a mover la cabeza
1/3 del total
Tseek1 = (3 · 30ms) / 305 = 0.3 ms Tiempo de posicionamiento en el sector contiguo
Tseek-extremo = 3 · Tseek-medio = 90 ms Full Stroke Seek = 3 · Average seek distance
(Hemos considerado que el tiempo de seek sólo depende de la distancia recorrida, desechando
el componente de puesta en movimiento inicial de las cabezas)
(a2) Transferencia de 20 bloques aleatoriamente distribuidos
CASO MEJOR: Coincide con el anterior
CASO MEDIO: Por cada sector tener que hacer un recorrido de cabezas medio, y una vuelta
de rotación media antes de acceder al sector
20 x (Tseek-medio + Trot-media + Tsector ) =
20 x (30 + 20/2 + 1.176 ) = 823.53 mseg unas 35 veces más lento
CASO PEOR: Por cada sector tener que hacer un recorrido de cabezas extremo, y una vuelta
de rotación completa antes de acceder al sector
20 x (Tseek-extremo + Trot + Tsector ) =
20 x (90 + 20 + 1.176 ) = 2223.53 mseg unas 95 veces más lento
2. Supóngase un disco de 256 cilindros, 4 cabezas, 100 sectores por pista y 2KB por
sector. El disco gira a 6000rpm y el tiempo de desplazamiento o posicionamiento del
brazo de cabezas de lectura/escritura es de 0.5ms por cilindro. El disco gira en
dirección ascendente desde el sector 0 al 99 e inicialmente se encuentra en CPS
(Cilindro, Pista y Sector)= (25, 3, 12).
a. Determinar el tiempo de posicionamiento del brazo de disco hasta alcanzar
CPS=(15,2,15).
b. Calcular el tiempo necesario para la lectura de 900KB físicamente consecutivos
Facultad de Informática
Universidad Complutense de Madrid
Problemas de Sistemas Operativos Módulo 4 / pág. 2
a partir de la posición CPS del apartado anterior
c. Y la posición CPS de la cabeza tras la lectura.
Solución:
(a) 256 cilindros, 4 cabezas, tiempo de desplazamiento 0.5ms por cilindro.
CPS (25, 4, 12) -> CPS=(15,2,15)
-El disco gira a 6000rpm -> 60[s/min]/6000[rev/min] · 1000[ms/s]-> 10ms/rev
-Un sector tarda en leerse 10/100=0.1ms/sector
-Nos movemos 10 cilindros -> 0.5·10=5ms, lo que supone avanzar 50 sectores (media pista),
así que estaremos en el 12+50=62, si queremos ir al 15 son 38 hasta el 0 mas 15 lo que hace
53 sectores -> 5ms + 5.3ms = 10.3ms
(b) 100 sectores de 2KB por pista -> 200KB por pista, 800KB por cilindro
Si queremos leer 900KB, son 1 cilindro más 100KB, o sea, media pista más -> CHS=(16,2,65)
El tiempo de lectura son 10ms·(4+0.5) de lectura de datos, más un cambio de cilindro, pero en
el cambio de cilindro dejamos de estar en la posición 0, así que hay que esperar a la vuelta
siguiente.
Total=10ms·(4+0.5)+10ms=50.5ms.
(c) CHS=(16,2,65)
3. Supongamos un disco flexible con 40 cilindros, en el que un posicionamiento tarda
6ms por cilindro. Si no se intenta colocar los bloques de un fichero cercanos unos a
otros, dos bloques lógicamente consecutivos (es decir, que se siguen el uno al otro
dentro del fichero) se encontrarán separados 13 cilindros por término medio. Sin
embargo, si se intenta agrupar los bloques relacionados, la distancia media entre
bloques puede reducirse a 2 cilindros. ¿Cuánto tiempo llevaría leer un fichero de 100
bloques en ambos casos, si la latencia rotacional es de 10ms y el tiempo necesario para
realizar la lectura de un bloque son 20ms?
Solución
Primer caso: separación media 13 pistas
Tacceso = (6 · 13 + 10 + 20) · 100 = 10800 = 10,8 seg
Segundo caso: separación media 2 pistas
Tacceso = (6 * 2 + 10 + 20 ) · 100 = 4200 = 4,2 seg (2,57 veces más rápido)
4. El espacio libre del disco puede contabilizarse mediante una lista o mediante un
mapa de bits. Las direcciones de disco requieren D bits. Para un disco con B bloques
totales, F de los cuales están libres, establecer la condición para la cuál la lista de
bloques libres ocupa menos espacio que el mapa de bits. Para D igual a 16 bits,
expresar la respuesta como porcentaje del espacio de disco que debe estar libre.
Solución:
F · D < B, o sea F < B/16 osea, el 6.25% o menos del total deberá estar libre
Si el disco tiene libre menos del 6.25% ocupa menos espacio la lista que el mapa de bits
5. Admitamos las siguientes simplificaciones: un computador tiene instrucciones que
requieren dos ciclos de bus, uno para acceder a la instrucción y otro para acceder al
dato. Cada ciclo de bus tarda 250ns y cada instrucción tarda 500ns (es decir, el tiempo
de procesamiento interno es despreciable). El computador dispone además de un disco
en el que cada pista contiene 16 sectores de 512 bytes. El tiempo de rotación del disco
es de 8,092ms.
a. ¿Cuál es el rendimiento del computador expresado en MIPS?
b. ¿Cuál es el porcentaje de reducción del rendimiento que sufre el computador
durante una transferencia de DMA si cada una consume un ciclo de bus?
Facultad de Informática
Universidad Complutense de Madrid
Problemas de Sistemas Operativos Módulo 4 / pág. 3
Considerar dos casos: transferencias de 8 bits y transferencias de 16 bits.
Solución:
(a) 1/(500 · 10-9) = 1/5 107 instrs/seg = 2 MIPS (1M = 106)
(b) (512 · 16 bytes) /(8’092 x 10-3 seg) = 1 012 357’8 bytes/seg
1.- 1 012 357’8 transf/seg de 1 byte necesita el DMA para atender al disco
(4 000 000 ciclos/s - 1 012 357’8ciclos/s) / 2ciclos/instr = 2 987 642,2 /2 = 1 493 821,1
instr/seg
1,494MIPS / 2MIPS · 100 = 74,7 % => reducción 25,3 %
2.- 1 012 357’8 / 2 = 506 178’9 transf/seg de 2 bytes necesita el DMA
(4 000 000 – 506 178’9) / 2 = 3 493 821’1 /2 = 1 746910’5 instr/seg
1’747 / 2 x 100 = 87,35% => reducción 12,65%
6. El rendimiento de un sistema de ficheros depende críticamente de la tasa de aciertos
de la cache de disco (fracción de bloques encontrados en la cache). Si se tarda 1ms en
satisfacer una petición desde la cache, pero 40ms más en satisfacerla si se necesita una
lectura de disco, obtener una fórmula para el tiempo medio necesario para satisfacer
una petición si la tasa de acierto es h. Trazar la gráfica de la función para valores de h
entre 0 y 1.
Solución:
Latencia: 1 * h + (40+1) * (1 – h) = 41 – 40 * h
plot([0:0.01:1], 41-40*[0:0.01:1]) ;xlabel('Tasa de aciertos');ylabel('Latencia[ms]')
7. Comparar las políticas de planificación de discos FCFS, SSF, SCAN y C-SCAN
simulando la siguiente lista de peticiones:
Tiempo [ms] 0 23 25 29 35 45 57 83 88 95
Pista 45 132 20 23 198 170 180 78 73 150
Para cada política, calcular la media y la desviación estándar del tiempo necesario para
atender a las peticiones. Suponer que el disco está posicionado inicialmente en la pista
1, que hay 200 pistas, que una búsqueda tarda (20 + 0’1 · P)ms, siendo P el número de
pistas que se recorre, que la latencia rotacional es de 8ms, y que el cumplimiento
estricto de la petición lleva 2ms.
Solución:
media
desv.
t0 0 23 25 29 35 45 57 83 88 95
pista 45 132 20 23 198 170 180 78 73 150
FCFS 1 2 3 4 5 6 7 8 9 10
tfinal 34.4 73.1 114.3 144.6 192.1 224.9 255.9 296.1 326.6 364.3
tret 34.4 50.1 89.3 115.6 157.1 179.9 198.9 213.1 238.6 269.3 154.6
79.9
SSTF 1 6 3 2 10 8 9 5 4 7
tfinal 34.4 198.1 96.9 66.6 324.7 261.9 292.9 162.7 132.2 229.9
tret 34.4 175.1 71.9 37.6 289.7 216.9 235.9 79.7 44.2 134.9 132.0
92.6
SCAN 1 2 10 9 5 3 4 7 8 6
tfinal 34.4 73.1 337.5 307.2 169.7 106.9 137.9 241.7 272.2 204.5
tret 34.4 50.1 312.5 278.2 134.7 61.9 80.9 158.7 184.2 109.5 140.5
94.8
CSCAN 1 2 6 7 5 3 4 9 8 10
tfinal 34.4 73.1 217.5 247.8 169.7 106.9 137.9 313.3 282.8 350.5
tret 34.4 50.1 192.5 218.8 134.7 61.9 80.9 230.3 194.8 255.5 145.4
83.0
Facultad de Informática
Universidad Complutense de Madrid
Problemas de Sistemas Operativos Módulo 4 / pág. 4
8. Considerar un disco con c cilindros, p pistas por cilindro y s sectores por pista y una
longitud de sector de ls bytes. Un fichero L está almacenado de forma contigua en el
disco a partir de la posición (cL, pL, sL), donde
cL, pL y sL son números de cilindro,
pista y sector, respectivamente. Deducir una fórmula para calcular la dirección de disco
(es decir, cilindro, pista y sector) de un byte situado en la posición n del fichero.
Solución
El número de sector del byte n será:
nSect=floor(n/ls)
El número de sectores en un cilindro es p*s, luego el número de cilindros de desplazamiento
sobre el inicial será:
cD = floor( (nSect + pL*s + sL) / [p*s] )
El desplazamiento de pista será
pD = floor( (nSect + pL*s + sL - cD*[p*s]) / s )
El desplazamiento en sector:
sD = nSect + pL*s + sL - cD*[p*s] - pD*s
Posición de n: (cL+cD, pL+pD, sL+sD)
9. Un disco tiene un factor de intercalado de 2. Dispone de 8 sectores de 512 bytes por
pista y su velocidad de rotación es de 3000 rpm. ¿Cuánto tarda en leer todos los
sectores de una pista en orden, suponiendo que la cabeza ya está correctamente
posicionada en la pista y que se necesita 1/2 rotación para que el sector 0 se halle justo
debajo de la cabeza? ¿Cuál es la velocidad de transferencia? Repetir el problema para
un disco de las mismas características con factor de intercalado 1. ¿Cuánto se degrada
la velocidad de transferencia debido a la diferencia de intercalado?
Solución
3000 rpm => 20 ms por rotación
Intercalado = 0: una rotación y media => 30 ms para leer 8 * 512 bytes => 133 KBs
Intercalado = 1: dos rotaciones y media => 50 ms para leer 4096 bytes => 80 KBs
Intercalado = 2: tres y un cuarto => 65 ms para leer 4096 bytes => 61’5 KBs
ejercicios SO/5.2-MemoriaProblemas.pdf
Sistemas Operativos UCM 2012/2013
Módulo 5 Gestión de Memoria
1. Un sistema informático tiene sitio suficiente en memoria principal para contener cuatro programas.
Los programas están inactivos esperando E/S la mitad del tiempo. ¿Qué fracción del tiempo de CPU se
desaprovecha?
2. Encontrar una expresión que permita predecir el aumento de productividad de un sistema en
función del grado de multiprogramación y de la probabilidad p de que los programas se hallen
esperando E/S. Suponer que un computador tiene 2M de memoria principal, de las cuales el sistema
operativo ocupa 512K (una cuarta parte) y cada programa de usuario también ocupa 512K. Si todos los
programas tienen un 60% de espera por E/S, ¿en qué porcentaje aumentará la productividad si se añade
1M más de memoria?
3. Considerar un sistema de tiempo compartido con swapping, un disco para swap y tres particiones
fijas de memoria. El tiempo de latencia promedio para el disco es de 4 ms; el tiempo de transferencia
de una partición es de 6 ms. La idea es intercambiar una partición mientras se ejecutan los procesos de
las otras dos. Un proceso se descarga a disco sólo cuando espera una entrada de usuario; se vuelve a
cargar cuando existe una partición libre y el usuario ha introducido una línea.
a. Para que la utilización de la UCP y del disco fuera del 100% ¿cuánto tiempo debería ejecutarse un
proceso que esté procesando una línea de entrada antes de esperar a la siguiente línea?
b. Si los usuarios enviaran una línea cada segundo para su procesamiento, ¿cuál es el número máximo de
usuarios que podría atenderse sin retardo extra?
4. Considerar un sistema con 4200 palabras de MP que implementa particiones variables. En un
cierto instante la memoria contiene las tres particiones siguientes:
P1 (dirección inicial=1000; tamaño=1000); P2 (2900; 500) y P3 (3400; 800)
Para cargar un nuevo bloque en memoria se utiliza la siguiente estrategia:
a. Probar el algoritmo del mejor ajuste para localizar un hueco del tamaño adecuado
b. Si esto falla, crear un hueco mayor desplazando particiones en memoria hacia la posición 0; empezar
siempre por la partición de menor dirección y continuar sólo hasta que se haya generado un hueco de
tamaño suficiente para albergar la nueva partición.
Suponer que van a cargarse tres nuevos bloques de tamaños 500, 1200 y 200, respectivamente (en el
orden indicado). Mostrar el contenido de la Mp después de satisfacer las tres peticiones de memoria.
5. El gestor de memoria recibe la siguiente secuencia de peticiones:
1. Asignar el bloque b1 de tamaño 100
2. Asignar el bloque b2 de tamaño 500
3. Asignar el bloque b3 de tamaño 60
4. Asignar el bloque b4 de tamaño 100
5. Liberar el bloque b1
6. Liberar el bloque b3
7. Asignar el bloque b5 de tamaño 50
8. Asignar el bloque b6 de tamaño 90
Suponiendo un tamaño de memoria total de 1024, indicar las direcciones iniciales y los tamaños de
todas las áreas libres para los esquemas de gestión (a) primer ajuste y (b) mejor ajuste, después que se
han procesado todas las peticiones.
6. Sea A el tamaño medio en bytes de los procesos que se ejecutan en un sistema y sea b el número
de bytes de cada una de las entradas en la tabla de mapa de páginas (TMP). Deducir, en función de A y
b, el tamaño de página p que minimiza la cantidad de memoria desaprovechada. Aplicar al caso en que
A = 1 MB y b = 4 bytes.
7. Un computador permite que cada proceso ocupe un espacio de direcciones de 65.536 bytes
dividido en páginas de 4096 bytes. Un programa particular está formado por tres segmentos: el de texto
(código) que ocupa 32768 bytes, el de datos que ocupa 16386 bytes y el de pila que ocupa 15870 bytes.
¿Encajará este programa en el espacio de direcciones del computador? ¿Encajaría si el tamaño de
página fuese 512 bytes?
8. Un computador cuyos procesos tienen 1024 páginas en sus espacios de direcciones mantiene las
TMP en memoria. El recargo necesario para leer una palabra de la TMP es de 500 ns. Para reducir este
recargo, el computador emplea una memoria asociativa (TLB) que contiene 32 pares (página virtual,
marco de página física), y que puede hacer una búsqueda en 100 ns. ¿Qué tasa de aciertos es necesaria
para reducir el recargo promedio a 200 ns?
9. Considerar los cuatro sistemas siguientes:
A B C D
Tamaño de página (en palabras)
Tamaño de palabra (en bits)
512
16
512
32
1024
16
1024
32
Para cada sistema determinar el número de entradas de la tabla de páginas (TMP). Suponer que sólo
existe una TMP para cada sistema y que cada dirección virtual ocupa una palabra (16 o 32b).
10. Considerar la siguiente tabla de segmentos
Segmento Base Límite
0
1
2
3
4
219
2300
90
1327
1952
600
14
100
580
96
Indicar las direcciones físicas para las
siguientes direcciones lógicas (seg-off):
(a) 0-430 (b) 1-10
(c) 1-11 (d) 2-500
(e) 3-400 (f) 4-112
11. Un sistema de paginación pura tiene un tamaño de página de 512 palabras, una memoria virtual de
512 páginas numeradas de 0 a 511, y una memoria física de 10 marcos de páginas numerados de 0 a 9.
El contenido actual de la memoria física es el siguiente:
Memoria
Física
0 ---
1536 Página 34
2048 Página 9
---
3072 TMP
3584 Página 65
---
4608 Página 10
a. Mostrar el contenido actual de la tabla de páginas, TMP
b. Mostrar el contenido de la TMP después de cargar la página 49 en la posición 0 y de sustituir la página
34 por la página 12
c. ¿Qué direcciones físicas referencian las direcciones virtuales 4608, 5119, 5120 y 33300?
d. ¿Qué ocurre cuando se referencia la dirección virtual 33000?
e. Si la página cargada en el marco de página 9 es un procedimiento y otro proceso q desea compartirlo,
dónde debe aparecer en la TMP de q? (Indicar la entrada afectada de la TMP)
12. Considerar dos procesos P1 y P2 en un sistema segmentado puro. Sus tablas TDS respectivas
contienen actualmente las siguientes entradas (no se muestra el tamaño de los segmentos):
TDS1 TDS2
0 4000 0 2000
1 6000 1 6000
2 9000 2 9000
3 2000
4 7000
a. ¿Cuáles son los segmentos compartidos, si hay alguno?
b. ¿Cuáles de las siguientes direcciones virtuales sería ilegal cuandoCompartir
Continuar navegando
Materiales relacionados
Preguntas relacionadas
Compartir