Arquitectura de ordenadores
Enunciados

Soluciones de los ejercicios sobre Monoalgorítmez y Multiagorítmez

1

          MODULE MONITOR
          FROM DONDESEA IMPORT PROCESAR
          NCAD   DATA.B  "A:CAD",0
          DCAD   RES.B   1
          NECG   DATA.B  "A:ECG",0
          DECG   RES.B   1
          ZONA   RES.B   512
          PRINC  OPEN(#NCAD, #0)  ; #4 según la 3ª edición
                 ST.B    .13, /DCAD
          BUCLE  READ(/DCAD, #ZONA, #512)
                 LD      .0,#ZONA
                 CALL    /PROCESAR
                 CMP     .0,#0
                 BZ      BUCLE
                 CLOSE(/DCAD)
                 OPEN(#NECG, #1)  ; #2 según la 3ª edición
                 ST.B    .13, /DECG
                 WRITE(/DECG, #ZONA, #512)
                 CLOSE(/DECG)
                 EXIT
                 END    PRINC
Sí podría utilizarse READ_A en lugar de READ, disponiendo de dos zonas alternantes, como en el programa 18.4 (20.4 en 3ª edición) (pág. 516, 518 en 3ª ed). En este caso no hay ninguna ventaja, y el inconveniente de mayor complejidad del programa de usuario.
2

Número de bytes

MODULE RAIZ ---------------

NPF DATA.B "A:PROG.ENS", 0 11

NPO DATA.B "A:PROG.OBJ", 0 11

NP1 DATA.B "A:ENSP1", 0 8

NP2 DATA.B "A:ENSP2", 0 8

MENS1 DATA.B "Paso 1", H'0D 7

MENS2 DATA.B "Paso 2", H'0D 7

AV RES.B 1 1

PUNT RES.B 2 2

TABLA RES.B 10240 10240

PRINC WRITE_A (#0, #MENS1, #AV) 31

LD .0, #NPF 4

ST .0, /PUNT 4

LD .0, #PUNT 4

LD_OV (#NP1) 16

CALL OVER 3

WAIT_A (#AV) 16

WRITE_A (#0, #MENS2, #AV) 31

LD .0, #NPO 4

ST .0, /PUNT 4

LD .0, #PUNT 4

LD_OV (#NP2) 16

CALL OVER 3

WAIT_A (#AV) 16

EXIT 4

OVER NOP 1

END PRINC -----

10.456

Observaciones:

Para acceder a PUNT no puede utilizarse direccionamiento relativo

La instrucción NOP sólo sirve para introducir la etiqueta "OVER" (los overlays se cargarán detrás de ella)

La llamada LD_OV machaca R0, pero antes lo salva en la pila, y este valor se recupera al volver del SO (antes de CALL OVER)

Cálculo de bytes:

Primer paso Segundo paso

Intérprete 500 500

Prefijo raíz 4 4

Raíz (con la tabla) 10.456 10.456

Módulo 30.720 40.960

------- -------

41.680 51.920

3

xxxx = 7.000 + 64 (expansión de LD_EX) = 7.064
yyyy = 7.080 + 4 (expansión de EXIT) + 4 (prefijo) = 7.088

zzzz = 7.088 + 250 - 4 (EXIT) = 7.334

    (PP)         (CIP)         (DPA)         (PDL)

al empezar
LD_EX 64.000 --- 6.948 7.084 6.948 = 6.952 - 4 (prefijo)
7.084 = 7.080 + 4 (EXIT)

tras la instrucción
BRK 63.970 1.280 6.948 7.084 63.970 =
64.000 - 26 (13 push) - 4 (CP y RE)

tras la instrucción
CALL /CARGAPROG 63.968 4.054 7.084 7.338 7.338 = yyyy + 250

antes de la instrucción
EX_SAL RETI 63.966 256 7.084 7.338 256 = H'0100 (RE inicial)

tras la instrucción
EX_SAL RETI 63.970 1.280 7.084 7.338

4

Errores:

No se puede acceder a DESCR con direccionamiento relativo (se detecta en tiempo de traducción)
Soluciones:

Poner DESCR RES.B 1 detrás de la zona reservada para ZESC (suponiendo que los bytes ocupados por lo que iría en las líneas de puntos no son tantos que lleguen a ocasionar un desplazamiento menor que -128 en la última referencia a DESCR, la de WRITE)

Hacer todos los accesos a DESCR con direccionamiento directo:
ST .13,/DESCR, READ(/DESCR,#ZLEC,#2000), etc.

Como el fichero se abre en modo de lectura, habría un error en tiempo de ejecución al intentar ejecutar la WRITE
Solución:
OPEN(#NOMBRE,#2) (según la 3ª ed. sería OPEN(#NOMBRE,#6))

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

   NBYP       NBL       NBYT       PUNTES       PUNTZU

2.000 1.417 512 1.500 7.000

1.488 122 512 1.500 7.512

976 392 512 1.500 8.024

464 55 464 1.500 8.536

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

   NBYP       NBL       NBYT       PUNTES       PUNTZU

1.000 122 24 1.988 9.000

976 392 512 1.500 9.024

464 55 464 1.500 9.536

5
¿Necesario corregir PID? NO
¿Necesaria PID? NO
¿Por qué? Porque el proceso padre no parece tener necesidad de identificar a los hijos.

¿Necesario corregir DLP? NO
¿Por qué? Porque son programas independientes, que se ensamblarán de manera independiente.

¿Necesario que los hijos abran la impresora? NO
¿Por qué? Porque los hijos heredan los ficheros abiertos por el padre.
Resultado(s) de la ejecución:
   Soy el padre
   Soy el hijo 1
   Soy el hijo 2
   Termino, hijos
La primera línea será "Soy el padre", pero las otras tres pueden aparecer en el orden indicado o en cualquier otro, dependiendo de en qué momento se activa cada uno de los tres procesos.
6

A cada paso por el bucle BUC se escribe "Soy de la generación i" (i = 1, 2, ...), se crea un proceso idéntico y se queda esperando que termine este proceso. Así hasta que i = 4: este proceso escribe lo de "muero sin hijos" y termina, lo que despierta al proceso 3, que escribe "Mis descendientes han muerto" y termina, lo que despierta al 2...

El resultado será:
Soy de la generación 1
Soy de la generación 2
Soy de la generación 3
Soy de la generación 4. Muero sin haber tenido hijos
Mis descendientes han muerto
Mis descendientes han muerto
Mis descendientes han muerto
Nota: El programa dado en el enunciado aparece en la página 588 del libro (4ª ed.) con algunas erratas que aquí se han corregido:
Dice                 Debe decir
MAX  EQU  34         MAX  EQU  H'34
GEN  DATA.B  31      GEN  DATA.B  H'31; ASCII de "1"
NLP  DATA.B  "lp",0  NLP  DATA.B  "A:lp",0
GN   OPEN(#NLP,#2)   GN   OPEN(#NLP,#1)
En la 3ª edición (pág. 589) había algunos errores:

Si se pone MAX = 4, como el valor inicial de GEN es 31 sólo puede llegar a 4 tras desbordar la capacidad de representación en un byte. Es decir, se repetiría el bucle 2⁸ - 31 + 4 = 219 veces.

La cadena M2 tiene 30 caracteres. Por tanto, si queremos que se escriba entera debemos poner WRITE(DLP,#M2,30) (con WRITE(DLP,#M2,17) sólo se escribirían los 17 primeros caracteres)

Se ha sustituido WRITE(DLP,#GEN,#3) por WRITE(DLP,#GEN,#1) para que la frase larga salga en una sola línea

Si se cuentan los bytes que ocupan las llamadas al sistema se verá que no es posible acceder a GEN con direccionamiento relativo (el ensamblador debería dar el error en tiempo de traducción)

7

Aunque no se dice explícitamente en el enunciado, FORK_EXEC devuelve al padre el PID del hijo, lo mismo que FORK.

Para comparar mejor con el programa original, se reproduce a continuación éste, con las instrucciones que deben desaparecer tachadas, y las nuevas a la derecha:
MODULE INIT
EXPORT INIT_ENT          
  PID0     RES.B  1
  PID1     RES.B  1
  PID2     RES.B  1
  PID3     RES.B  1
  NGETTY   DATA.B "A:getty",0
  NTTY0    DATA.B 0        
  NTTY1    DATA.B 1       
  NTTY2    DATA.B 2       
  NTTY3    DATA.B 3
  INIT_ENT FORK   FK_EX(#NGETTY,#NTTY0,#1) 
           CMP.B  .13,#0                           F0    FORK    FK_EX(#NGETTY,#NTTY0,#1) 
           BZ     TTY0                                   CMP.B  .13,#0
           ST.B   .13,PID0                               BZ     TTY0
           FORK   FK_EX(#NGETTY,#NTTY1,#1)               ST.B   .13,PID0
           CMP.B  .13,#0                                 BR     SIGUE
           BZ     TTY1                             F1    FORK    FK_EX(#NGETTY,#NTTY1,#1) 
           ST.B   .13,PID1                               CMP.B  .13,#0 
           FORK   FK_EX(#NGETTY,#NTTY2,#1)               BZ     TTY1
           CMP.B  .13,#0                                 ST.B   .13,PID1     
           BZ     TTY2                                   BR     SIGUE
           ST.B   .13,PID2                         F2    FORK    FK_EX(#NGETTY,#NTTY2,#1) 
           FORK   FK_EX(#NGETTY,#NTTY3,#1)               CMP.B  .13,#0
           CMP.B  .13,#0                                 BZ     TTY2  
           BZ     TTY3                                   ST.B   .13,PID2
           ST.B   .13,PID3                               BR     SIGUE
  SIGUE    WAIT(#0)                                F3    FORK    FK_EX(#NGETTY,#NTTY3,#1) 
           CMP.B  .13,PID0                               CMP.B  .13,#0
           BZ     F0                                     BZ     TTY3
           CMP.B  .13,PID1                               ST.B   .13,PID3
           BZ     F1                                     BR     SIGUE
           CMP.B  .13,PID2                         TTY0  EXEC(#NGETTY,#NTTY0,#1)  
           BZ     F2                               TTY1  EXEC(#NGETTY,#NTTY1,#1)  
           CMP.B  .13,PID3                         TTY2  EXEC(#NGETTY,#NTTY2,#1)    
           BZ     F3                               TTY3  EXEC(#NGETTY,#NTTY3,#1)  
           BR    SIGUE                                       END      
8

seg. TUCP1 PRIOR1 TUCP2 PRIOR2 TUCP3 PRIOR3 Activo

0 0 5 0 7 0 9 P1

1 5 10 0 7 0 9 P2

2 2 7 5 12 0 9 P1

3 6 11 2 9 0 9 P2

4 3 8 6 13 0 9 P1

5 6 11 3 10 0 9 P3

6 3 8 1 8 5 14 P1

7 6 11 0 7 2 11 P2

8 3 8 5 12 1 10 P1

9 6 11 2 9 0 9 P2

10 3 8 6 13 0 9 P1

fracción de tiempo para PROCESO 1: 1/2
fracción de tiempo para PROCESO 2: 1/3
fracción de tiempo para PROCESO 3: 1/6

9

SEG TUCP1 PRIOR1 TUCP2 PRIOR2 TUCP3 PRIOR3 ACTIVO espacio para hacer acotaciones de X

0 0 BASE=5 0 BASE=X 0 BASE=7 P1 X>=5;(5,6,7,8,9,10)

1 10/2=5 5+5=10 0/2=0 X 0/2=0 7 P2 X<=7;(5,6,7)

2 5/2=2 2+5=7 10/2=5 5+X 0/2=0 7 P1 X+5>=7; (5,6,7)

3 12/2=6 6+5=11 5/2=2 2+X 0/2=0 7 P3 X+2>7; (6,7)

4 6/2=3 3+5=8 2/2=1 1+X 10/2=5 5+7=12 P2 X+1<8; (6)

5 3/2=1 1+5=6 11/2=5 5+6=11 5/2=2 2+7=9 P1 X=6

6 11/2=5 5+5=10 5/2=2 2+6=8 2/2=1 1+7=8 P2 X=6

7 5/2=2 2+5=7 12/2=6 6+6=12 1/2=0 0+7=7 P1 X=6

8 12/2=6 6+5=11 6/2=3 3+6=9 0/2=0 0+7=7 P3 X=6

9 6/2=3 3+5=8 3/2=1 1+6=7 10/2=5 5+7=12 P2 X=6

10 3/2=1 1+5=6 11/2=5 5+6=11 5/2=2 2+7=9 P1 X=6

fracción de tiempo para PROCESO 1: 2/5
fracción de tiempo para PROCESO 2: 2/5
fracción de tiempo para PROCESO 3: 1/5

10

Se está utilizando el controlador de la Unidad de Gestión de Memoria para asignar las páginas lógicas a las páginas físicas

El máximo de páginas de los procesos es tres, ya que los registros R0, R1 y R2 se cargan con valores que pueden tener el bit de validez a 1 antes de enviarse al puerto de dirección 21

El Proceso 1 tiene una página pues #CT0 hace que el bit de validez sea 1.
El Proceso 2 tiene dos páginas pues #CT0 y #CT1 hacen que los bits de validez sean 1.
El Proceso 3 tiene tres páginas pues #CT0, #CT1 y #CT2 hacen que los bits de validez sean 1.

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 10/2=5 5+1=6 0/2=0 0+2=2 0/2=0 0+3=3 P2

2 5/2=2 2+1=3 10/2=5 5+2=7 0/2=0 0+3=3 P1

3 12/2=6 6+1=7 5/2=2 2+2=4 0/2=0 0+3=3 P3

4 6/2=3 3+1=4 2/2=1 1+2=3 10/2=5 5+3=8 P2

5 3/2=1 1+1=2 11/2=5 5+2=7 5/2=2 2+3=5 P1

6 11/2=5 5+1=6 5/2=2 2+2=4 2/2=1 1+3=4 P2

7 5/2=2 2+1=3 12/2=6 6+2=8 1/2=0 0+3=3 P1

8 12/2=6 6+1=7 6/2=3 3+2=5 0/2=0 0+3=3 P3

9 6/2=3 3+1=4 3/2=1 1+2=3 10/2=5 5+3=8 P2

Fracción de tiempo de uso de la UCP por cada proceso:
PROCESO 1: 2/5
PROCESO 2: 2/5
PROCESO 3: 1/5

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 10/2=5 5+1=6 0/2=0 0+2=2 0/2=0 0+3=3 P2

2 5/2=2 2+1=3 10/2=5 5+2=7 0/2=0 0+3=3 P3

3 2/2=1 1+1=2 5/2=2 2+2=4 10/2=5 5+3=8 P1

4 11/2=5 5+1=6 2/2=1 1+2=3 5/2=2 2+3=5 P2

5 5/2=2 2+1=3 11/2=5 5+2=7 2/2=1 1+3=4 P1

6 12/2=6 6+1=7 5/2=2 2+2=4 1/2=0 0+3=3 P3

7 6/2=3 3+1=4 2/2=1 1+2=3 10/2=5 5+3=8 P2

8 3/2=1 1+1=2 11/2=5 5+2=7 5/2=2 2+3=5 P1

9 11/2=5 5+1=6 5/2=2 2+2=4 2/2=1 1+3=4 P3

10 5/2=2 2+1=3 2/2=1 1+2=3 11/2=5 5+3=8 P2

11 2/2=1 1+1=2 11/2=5 5+2=7 5/2=2 2+3=5 P1

Fracción de tiempo de uso de la UCP por cada proceso:
PROCESO 1: 1/3
PROCESO 2: 1/3
PROCESO 3: 1/3

11

¿Cuántos procesos coexisten como máximo? ¿Porqué?
Coexisten 3 como máximo, pues el padre crea inicialmente dos hijos y espera a que terminen, para meterse en un bucle en el que crea un hijo y espera a que termine.
¿Si se sacara el contenido final del fichero por pantalla, qué se vería?
012345
¿Cuántos procesos distintos han escrito en el fichero?
6 (el padre escribe el 0 y cada uno de los hijos escribe 1,2,3,4,5)
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.
Una solución es:

	Primer paso	Segundo paso
Intérprete	500	500
Prefijo raíz	4	4
Raíz (con la tabla)	10.456	10.456
Módulo	30.720	40.960
	-------	-------
	41.680	51.920

	(PP)	(CIP)	(DPA)	(PDL)
al empezar `LD_EX`	64.000	---	6.948	7.084	6.948 = 6.952 - 4 (prefijo) 7.084 = 7.080 + 4 (`EXIT`)
tras la instrucción `BRK`	63.970	1.280	6.948	7.084	63.970 = 64.000 - 26 (13 push) - 4 (CP y RE)
tras la instrucción `CALL /CARGAPROG`	63.968	4.054	7.084	7.338	7.338 = yyyy + 250
antes de la instrucción `EX_SAL RETI`	63.966	256	7.084	7.338	256 = H'0100 (RE inicial)
tras la instrucción `EX_SAL RETI`	63.970	1.280	7.084	7.338

NBYP	NBL	NBYT	PUNTES	PUNTZU
2.000	1.417	512	1.500	7.000
1.488	122	512	1.500	7.512
976	392	512	1.500	8.024
464	55	464	1.500	8.536

NBYP	NBL	NBYT	PUNTES	PUNTZU
1.000	122	24	1.988	9.000
976	392	512	1.500	9.024
464	55	464	1.500	9.536

seg.	TUCP1	PRIOR1	TUCP2	PRIOR2	TUCP3	PRIOR3	Activo
0	0	5	0	7	0	9	P1
1	5	10	0	7	0	9	P2
2	2	7	5	12	0	9	P1
3	6	11	2	9	0	9	P2
4	3	8	6	13	0	9	P1
5	6	11	3	10	0	9	P3
6	3	8	1	8	5	14	P1
7	6	11	0	7	2	11	P2
8	3	8	5	12	1	10	P1
9	6	11	2	9	0	9	P2
10	3	8	6	13	0	9	P1

Enunciados

Arquitectura de ordenadores

			Número de bytes
`MODULE`	`RAIZ`		---------------
`NPF`	`DATA.B`	`"A:PROG.ENS", 0`	11
`NPO`	`DATA.B`	`"A:PROG.OBJ", 0`	11
`NP1`	`DATA.B`	`"A:ENSP1", 0`	8
`NP2`	`DATA.B`	`"A:ENSP2", 0`	8
`MENS1`	`DATA.B`	`"Paso 1", H'0D`	7
`MENS2`	`DATA.B`	`"Paso 2", H'0D`	7
`AV`	`RES.B`	`1`	1
`PUNT`	`RES.B`	`2`	2
`TABLA`	`RES.B`	`10240`	10240
`PRINC`	`WRITE_A`	`(#0, #MENS1, #AV)`	31
	`LD`	`.0, #NPF`	4
	`ST`	`.0, /PUNT`	4
	`LD`	`.0, #PUNT`	4
	`LD_OV`	`(#NP1)`	16
	`CALL`	`OVER`	3
	`WAIT_A`	`(#AV)`	16
	`WRITE_A`	`(#0, #MENS2, #AV)`	31
	`LD`	`.0, #NPO`	4
	`ST`	`.0, /PUNT`	4
	`LD`	`.0, #PUNT`	4
	`LD_OV`	`(#NP2)`	16
	`CALL`	`OVER`	3
	`WAIT_A`	`(#AV)`	16
	`EXIT`		4
`OVER`	`NOP`		1
	`END`	`PRINC`	-----
			10.456

seg.	TUCP1	PRIOR1	TUCP2	PRIOR2	TUCP3	PRIOR3	Activo
0	0	5	0	7	0	9	P1
1	5	10	0	7	0	9	P2
2	2	7	5	12	0	9	P1
3	6	11	2	9	0	9	P2
4	3	8	6	13	0	9	P1
5	6	11	3	10	0	9	P3
6	3	8	1	8	5	14	P1
7	6	11	0	7	2	11	P2
8	3	8	5	12	1	10	P1
9	6	11	2	9	0	9	P2
10	3	8	6	13	0	9	P1

seg.	TUCP1	PRIOR1	TUCP2	PRIOR2	TUCP3	PRIOR3	Activo
0	0	5	0	7	0	9	P1
1	5	10	0	7	0	9	P2
2	2	7	5	12	0	9	P1
3	6	11	2	9	0	9	P2
4	3	8	6	13	0	9	P1
5	6	11	3	10	0	9	P3
6	3	8	1	8	5	14	P1
7	6	11	0	7	2	11	P2
8	3	8	5	12	1	10	P1
9	6	11	2	9	0	9	P2
10	3	8	6	13	0	9	P1

seg.	TUCP1	PRIOR1	TUCP2	PRIOR2	TUCP3	PRIOR3	Activo
0	0	5	0	7	0	9	P1
1	5	10	0	7	0	9	P2
2	2	7	5	12	0	9	P1
3	6	11	2	9	0	9	P2
4	3	8	6	13	0	9	P1
5	6	11	3	10	0	9	P3
6	3	8	1	8	5	14	P1
7	6	11	0	7	2	11	P2
8	3	8	5	12	1	10	P1
9	6	11	2	9	0	9	P2
10	3	8	6	13	0	9	P1