Arquitectura de ordenadores

Ejercicios sobre Monoalgorítmez y Multialgorítmez

1

Imaginemos a Monoalgorítmez en una aplicación de control de una unidad de cuidados intensivos. Para ello, está dotado de un conversor analógico digital que recibe señales electrocardiográficas, las muestrea y las envía a la MP (mediante un controlador de acceso directo a memoria) en bloques de 512 muestras de ocho bits (al final de la transferencia de cada bloque genera una interrupción). Las tablas del sistema operativo ya se han modificado para que este periférico se reconozca como un fichero especial de bloques, con nombre "A:CAD".

Se trata en este ejercicio de escribir un programa, en un módulo llamado "MONITOR", que lea sucesivamente las muestras sin perder ninguna (las muestras llegan con una frecuencia constante, cuyo valor no hace al caso), las procese y, en caso de alguna anomalía, genere un aviso sonoro, se detenga y escriba en un fichero del disco A: (de nombre "ECG") el último bloque leído. Se supondrá lo siguiente:

SE PIDE:

2

Suponga que hemos escrito, compilado y montado en otro ordenador un ensamblador de dos pasos para Algorítmez. El programa fuente está estructurado en tres módulos: el primero corresponde al primer paso (que construye la tabla de símbolos), el segundo, al segundo paso (que, haciendo uso de esa tabla, genera el código objeto), y el tercero es la propia tabla de símbolos. Tras el montaje ha resultado un módulo de carga que ocupa 80KB, por lo que no podemos ejecutarlo en Monoalgorítmez.

Ahora bien, caemos en la cuenta de que 30KB corresponden al primer módulo, 40KB al segundo y 10KB a la tabla de símbolos. Por tanto, es factible cargar en la MP el primer módulo junto con la tabla de símbolos (30 + 10 = 40KB), y luego el segundo módulo con la misma tabla (40 + 10 = 50KB). Decidimos, pues, hacer uso de la técnica de módulos solapables.

Los módulos que implementan los pasos se convierten en subprogramas (ambos terminan con la instrucción RET), y sus módulos de carga residen en dos ficheros del disco "A", con nombres ENSP1 y ENSP2, y tamaños 30KB y 40KB, respectivamente.

Escriba el módulo raíz (que incluye a la tabla de símbolos) teniendo en cuenta que:

Suponiendo que el intérprete de órdenes ocupa quinientos bytes, calcule cuántos bytes de la zona de usuario se están ocupando durante la ejecución de cada uno de los pasos.

3

En este ejercicio le vamos a pedir que reproduzca algunos detalles del proceso que sigue el núcleo de Monoalgorítmez. Tendrá que haber comprendido bien qué son las "macros" y sus expansiones, cómo se cargan los programas en la MP, qué pasa en Algorítmez cuando aparece una interrupción de programa, y cómo funcionan la RIP (rutina de interrupciones de programa) y el SGM (sistema de gestión de memoria).

Suponga que en un momento determinado se está ejecutando un programa, al que llamaremos PROG1, cuya primera instrucción está cargada a partir del byte de dirección D'6.952. Este programa contiene una llamada LD_EX para pedir la ejecución de otro programa cuyo nombre es PROG2; el primer byte de la primera instrucción de la expansión de esta macro está en la dirección D'7.000. Es decir, la estructura de PROG1 es:

[6952]  ...
 ...    ...
        NPROG2  DATA.B  "A:PROG2",0
 ...    ...
   
[7000]          LD_EX(#NPROG2,#DARG)
[xxxx]  ...     ; (instrucción siguiente)
 ...    ...
 ...    ...

[7080]  EXIT
Por su parte, PROG2 (del que sólo sabemos que, una vez traducido a binario, ocupa 250 bytes) tendrá un conjunto de instrucciones y seudoinstrucciones que no hacen al caso: 
[yyyy]  ...
 ...    ...

[zzzz]  EXIT

4

El siguiente programa pretende operar con los datos de un fichero llamado "TEMP":

 DESCR   RES.B   1
 NOMBRE  DATA.B  "A:TEMP",0
 ZLEC    RES.B   2000
 ZESC    RES.B   1000
         ---
         OPEN(#NOMBRE,#0) ; abre en modo de sólo lectura (según especificación
                          ; de la cuarta edición; para ediciones anteriores
                          ; el segundo parámetro sería #4)
         ; suponemos que no hay error
         ST      .13,DESCR
         READ(DESCR,#ZLEC,#2000)
         ---
         ---    ; procesa ZLEC 
         ---    ; y rellena ZESC
         POS(DESCR,#1000,#0)
         WRITE(DESCR,#ZESC,#1000)
         ---
Hay dos cosas mal en este programa (una daría un error en tiempo de traducción, y la otra daría el error en tiempo de ejecución). Corríjalas, y escriba en las tablas (a) y (b) los valores sucesivos que van tomando las variables NBYP, NBL, NBYT, PUNTES y PUNTZU del registro del periférico en el que está el fichero A:TEMP. Necesitará los siguientes datos:

 

(a) Durante la ejecución de READ(DESCR,#ZLEC,#2000):

   NBYP       NBL       NBYT       PUNTES       PUNTZU   
         
         
         
         
         

 

(b) Durante la ejecución de WRITE(DESCR,#ZESC,#1000):

   NBYP       NBL       NBYT       PUNTES       PUNTZU   
         
         
         
         
         

5

Considere el siguiente fragmento de programa con llamadas al núcleo de Multialgorítmez:

    PID RES.B  1
    DLP RES.B  1
    CAB DATA.B "Soy el padre",H'0D,H'0A
    PIE DATA.B "Termino, hijos",H'0D,H'0A
    NLP DATA.B "A:lp",0
    NP1 DATA.B "A:PROGH1",0
    NP2 DATA.B "A:PROGH2",0
        ---
         OPEN(#NLP,#1) ; abre en modo de sólo escritura
                       ; para ediciones anteriores a la cuarta, #2
         ST.B    .13,DLP
         WRITE(/DLP,#CAB,#14)
         FORK
         CMP.B   .13,#0
         BZ      HIJO1
         ST.B    .13,PID
         FORK
         CMP.B   .13,#0
         BZ      HIJO2
         ST.B    .13,PID
         WRITE(/DLP,#PIE,#16)
         ---
    HIJO1  EXEC(#NP1,#DLP,#1)
    HIJO2  EXEC(#NP2,#DLP,#1)
         ---

"PROGH1" y "PROGH2" son nombres de ficheros en los que residen programas ejecutables. Entre otras cosas que no hacen al caso, el código fuente de PROGH1 contiene lo siguiente:

    DLP  RES.B 1
    MENS DATA  "Soy el hijo 1",H'0D,H'0A
         ---
         POP   .0
         ST.B  .0,DLP
         ---  
         WRITE(DLP,#MENS,#15)
         ---

PROGH2 tiene una estructura similar (pero en MENS contiene "Soy el hijo 2").

6

Analice el siguiente programa, y escriba el resultado de su ejecución:

    MODULE GENERACIONES
    MAX EQU    H'34
    DLP RES.B  1
    GEN DATA.B H'31; ASCII de "1"
    RET DATA.B H'0D,H'0A
    M1  DATA.B "Soy de la generación "
    M2  DATA.B ". Muero sin haber tenido hijos"
    M3  DATA.B "Mis descendientes han muerto"
    NLP DATA.B "A:lp",0
    GN   OPEN(#NLP,#1) ; modo de sólo escritura
         ST.B   .13,/DLP
    BUC  WRITE(/DLP,#M1,#21)
         WRITE(/DLP,#GEN,#3)
         LD.B   .0,/GEN
         ADD.B  .0,#1
         ST.B   .0,/GEN
         FORK
         CMP.B  .13,#0
         BNZ    ESP
         LD.B   .1,/GEN
         CMP.B  .1,#MAX
         BN     BUC
         WRITE(/DLP,#M1,#21)
         WRITE(/DLP,#GEN,#1)
         WRITE(/DLP,#M2,#30)
         WRITE(/DLP,#RET,#2)
        EXIT
    ESP  WAIT(#0)
         WRITE(/DLP,#M3,#28)
         WRITE(/DLP,#RET,#2)
        EXIT
       END GN

7

La separación de la creación de procesos (FORK) y la carga de programas (EXEC) sigue el modelo de UNIX, en el que ambas funciones están perfectamente diferenciadas, y se justifica porque facilita la implementación de ciertas características que no se han incluido en el modelo funcional de Multialgorítmez (como la "redirección"). Pero no es estrictamente necesaria. Otros sistemas operativos (por ejemplo, VMS) combinan las dos funciones en una sola llamada, que crea un nuevo proceso con la imagen en memoria correspondiente a un nuevo programa (y también hay sistemas, como Windows NT, que permiten las dos formas). Si en Multialgorítmez siguiésemos el segundo modelo, muchos programas, como el correspondiente a "init", se simplificarían. Vamos a comprobarlo. Suponga que, en lugar de FORK y EXEC, tenemos una llamada FK_EX con los mismos parámetros que EXEC: FK_EX(#NPROG,#ARG,LONG). En el procesamiento de esta llamada, el sistema crea un nuevo proceso (hijo) y le hace corresponder una imagen en memoria de acuerdo con el programa cuyo nombre está en NPROG, dejando preparados a los dos procesos (el padre y el hijo). Codifique en ensamblador el programa init haciendo uso de esta nueva llamada.

8

Imagine tres procesos en Multialgorítmez, P1, P2 y P3, con prioridades de base 5, 7 y 9, respectivamente, y que durante un tiempo indefinidamente grande ninguno de ellos queda bloqueado, y la única interrupción que aparece es la del reloj. Inicialmente está activo P1. Calcule y ponga en el cuadro adjunto los valores sucesivos, segundo a segundo, de TUCP1, TUCP2 y TUCP3 (valores de los campos "TUCP" para cada uno de los procesos) y PRIOR1, PRIOR2 y PRIOR3 (valores respectivos de los campos "PRIOR"), señalando qué proceso pasa a estar activo al final de cada período de un segundo. Como consecuencia, calcule también el porcentaje de tiempo de la UCP que ocupa cada proceso si la situación se repite durante un período de tiempo muy grande. Suponga que en caso de "empate" (es decir, si coinciden los valores de PRIOR para dos procesos) el algoritmo da preferencia a P1 sobre P2 y a éste sobre P3.

seg. TUCP1 PRIOR1 TUCP2 PRIOR2 TUCP3 PRIOR3 Activo
0 0 5 0 7 0 9 P1
1              
2              
3              
4              
5              
6              
7              
8              
9              
10              

9

Imagine tres procesos en Multialgorítmez. Conocemos la prioridad de base de dos de ellos (PRIOR1 BASE=5 y PRIOR3 BASE=7), pero no la prioridad base del tercero (PRIOR2 BASE=X), y se trata de deducirla.

Para determinar el valor de X conocemos cuál es el proceso activo en los 5 primeros segundos y suponemos que no hay más cambios de procesos activos que los producidos por el planificador, así como que en caso de empate en el valor de PRIOR, el proceso 1 tiene prioridad sobre el 2 y éste sobre el 3.

10

Suponga tres procesos en Multialgorítmez, de los cuales conocemos sus prioridades base: PRIOR1 BASE=1, PRIOR2 BASE=2 y PRIOR3 BASE=3.

Cada vez que el sistema decide conceder el procesador a uno de estos procesos ejecuta las instrucciones siguientes:

    LD  .0,#CT0
    LD  .1,#CT1
    LD  .2,#CT2
    LD  .3,#0
    LD  .4,#21
    LD  .5,#20
    LD  .6,#2
    OUT .0,[.4] 
    OUT .1,[.4]
    OUT .2,[.4]
    OUT .3,[.4]
    OUT .3,[.4] 
    OUT .3,[.4]
    OUT .3,[.4]
    OUT .3,[.4]
    OUT .6,[.5]

Tabla 1 (prioridad al proceso de menor número de páginas en caso de igualdad de PRIOR)

SEG TUCP1 PRIOR1 TUCP2 PRIOR2 TUCP3 PRIOR3 ACTIVO
0 0 BASE=1 0 BASE=2 0 BASE=3 P1
1 ? ? ? ? ? ? ?
2 ? ? ? ? ? ? ?
3 ? ? ? ? ? ? ?
4 ? ? ? ? ? ? ?
5 ? ? ? ? ? ? ?
6 ? ? ? ? ? ? ?
7 ? ? ? ? ? ? ?
8 ? ? ? ? ? ? ?
9 ? ? ? ? ? ? ?

Tabla 2 (prioridad al proceso de mayor número de páginas en caso de igualdad de PRIOR)

SEG TUCP1 PRIOR1 TUCP2 PRIOR2 TUCP3 PRIOR3 ACTIVO
0 0 BASE=1 0 BASE=2 0 BASE=3 P1
1 ? ? ? ? ? ? ?
2 ? ? ? ? ? ? ?
3 ? ? ? ? ? ? ?
4 ? ? ? ? ? ? ?
5 ? ? ? ? ? ? ?
6 ? ? ? ? ? ? ?
7 ? ? ? ? ? ? ?
8 ? ? ? ? ? ? ?
9 ? ? ? ? ? ? ?
10 ? ? ? ? ? ? ?
11 ? ? ? ? ? ? ?

11

Considere el siguiente programa para Multialgorítmez: 

MODULE	FICH
N		DATA.B	H´30,H´0A,H´0D; ASCII de 0,nueva línea, retorno
DF		RES.B		1
NF		DATA.B	"A:TXT",0
PRINC		OPEN(#NF,#2); abre el fichero en modo lec/esc y pone pos =0
		ST.B		.13,DF
		CLR		.0
		WRITE(DF,#N,#3)
		FORK
		CMP.B		.13,#0
		BZ		/HIJO
BUC		FORK
		CMP.B		.13,#0
		BZ		/HIJO
		WAIT(#0)
		WAIT(#0)
		ADD.B		.0,#1
		CMP.B		.0,#4
		BZ		/FIN
		BR		/BUC
HIJO		POS(DF,#-3,#1)
		READ(DF,#N,#1)
		LD.B		.0,/N
		ADD.B		.0,#1
		ST.B		.0,/N
ESC		WRITE(DF,#N,#3)
FIN		EXIT
		END	PRINC

Suponga que cuando un proceso hijo comienza a ejecutarse nunca es interrumpido hasta que termina.

  1. ¿Cuántos procesos coexisten como máximo? ¿Porqué?
  2. ¿Si se sacara el contenido final del fichero por pantalla, qué se vería?
  3. ¿Cuántos procesos distintos han escrito en el fichero?
  4. Dibuje y complete un diagrama similar al de la transparencia 15 de Multialgorítmez, que indique la situación en el caso del máximo de procesos simultáneos, si el descriptor del fichero es 2, la entrada en la tabla de posiciones de fichero es 3 y la entrada en la tabla de ficheros abiertos es 4. Escoja para el pid de cada proceso cualquier número comprendido entre 1 y 15.
Arquitectura de ordenadores