ADMINISTRADOR DE PROCESOS

marzo 8, 2009

INTERRUPCIONES:

DEFINICIÓN:

Una petición de interrupción IRQ (“Interrupt Request”) es una señal que se origina en un dispositivo hardware (por ejemplo, un periférico), para indicar al procesador que algo requiere su atención inmediata;  se solicita al procesador que suspenda lo que está haciendo para atender la petición.

Una interrupción es un evento que altera la secuencia en que el procesador ejecuta las instrucciones. La interrupción es generada por el hardware del sistema de cómputo. Cuando ocurre una interrupción.

 

 

CLASES DE INTERRUPCIONES:

  Existen seis clases de interrupciones:

 

Interrupciones SVC (supervisor call, llamadas al supervisor).

Son iniciadas por un proceso en ejecución que ejecute la instrucción SVC. Una SVC es una petición generada por el usuario de un servicio particular del sistema, como realizar una operación de entrada/salida, obtener más memoria o comunicarse con el operador del sistema. El mecanismo de las SVC ayuda a proteger el sistema operativo de las acciones de los usuarios. Un usuario no puede entrar arbitrariamente al sistema operativo, sino que debe solicitar un servicio por medio de una SVC. El sistema operativo está al tanto de todos los usuarios que intentan rebasar sus limites y puede rechazar ciertas peticiones si el usuario no tiene los privilegios necesarios.

 

Interrupciones de E/S. 

  Son iniciadas por hardware de entrada y salida. Estas interrupciones indican a la UCP el cambio de estado de un canal o dispositivo. Las interrupciones de E/S se producen cuando finaliza una operación de E/S o cuando un dispositivo pasa al estado listo.

 

Interrupciones externas.

  Son causadas por diversos eventos, incluyendo la expiración de un cuanto de un reloj que interrumpe, la pulsación de la tecla de interrupción de la consola o la recepción de una señal procedente de otro procesador en un sistema de múltiples procesadores.

 

Interrupciones de Reinicio.

  Se produce cuando se presiona el botón de reinicio de la PC o cuando llega de otro procesador una instrucción de reinicio en un sistema de multiprocesamiento

 

Interrupciones de verificación del programa.

  Son causadas por una amplia clase de problemas que pueden ocurrir cuando se ejecutan las instrucciones en lenguaje máquina de un programa. Dichos problemas incluyen la división entre cero, el exceso o defecto de los números que pueden ser manejados por las operaciones aritmeticas, el intento de hacer referencia a una localidad de memoria que esté fuera de los límites de la memoria real. Muchos sistemas ofrecen a los usuarios la opción de especificar las rutinas que deben ejecutarse cuando ocurra una interrupción de verificación del programa.

 

Interrupciones de verificación de la máquina.

Son ocasionadas por el mal funcionamiento del hardware.

 

 

CAMBIO DE CONTEXTO: 

 

Cuando el CPU es “switcheado” de un proceso a otro se requiere salvar el estado del proceso viejo y cargar el estado salvado del proceso nuevo. Esto es conocido como cambio de contexto y es puramente overhead, pues el sistema no hace ningún trabajo útil mientras se realiza tal tarea.

 

Un cambio de contexto siempre se ejecuta ante una interrupción ya sea de software o hardware. Un cambio de contexto no necesariamente implica un cambio de proceso.

 

Un cambio de proceso puede producirse en cualquier momento en que el sistema de operación haya tomado el control a partir del proceso que está actualmente ejecutándose

 

Pasos que se ejecutan durante el cambio de contexto que implica un cambio de proceso:

 

El Hardware:

Guarda algunos registros en el stack, como el pc y el sp (stack pointer).

Coloca en el pc del CPU la dirección del servicio de interrupción

 El procesador, al continuar con el ciclo de lectura de instrucción, trae la primera instrucción del servicio de interrupción encargada de atender dicha interrupción.

Lenguaje Ensamblador (del servico de interrupción):

Coloca el bit a modo monitor e inhabilita las Interrupciones

Salva el estado del proceso (los registros de CPU y la información del stack) en la tabla de procesos del proceso interrumpido. Esto implica cambiar el estado del proceso a alguno de los otros estados.

Remueve la información del stack

Coloca el sp (stack pointer) del CPU al stack temporal manejado por el servicio de interrupción.

Llama a un procedimiento en C.

Procedimiento en C:

Mueve el PCB del proceso a la cola apropiada

Realiza el trabajo correspondiente. Si fue una int de E/S, despierta al proceso (waiting ==> ready).

Llama al despachador (Scheduling). Esto es seleccionar otro proceso para ejecución.

Llama al despachador

Despachador (lenguaje ensamblador):

Carga en CPU los registros y mapa de memoria del primer proceso en la cola ready.

Habilita las interrupciones

 

Cuando ocurre una interrupción que sólo genera un cambio de contexto más no un cambio de proceso, todo lo que se debe hacer es salvar la información de estado del procesador cuando se produzca la interrupción y restaurar dicha información cuando el control vuelva al programa que estaba en ejecución. Las funciones de salvar y restaurar suelen llevarse acabo en el hardware.

 

 

PLANIFICACIÓN DE PROCESOS:

 

DEFINICIÓN:

Podemos definir a la planificación como un conjunto de políticas y mecanismos incorporados al sistema operativo, a través de un módulo denominado planificador, que debe decidir cuál de los procesos en condiciones de ser ejecutado conviene ser despachado primero y qué orden de ejecución debe seguirse. Esto debe realizarse sin perder de vista su principal objetivo que consiste en el máximo aprovechamiento del sistema, lo que implica proveer un buen servicio a los procesos existentes en un momento dado.

 

Un “buen” servicio podría traducirse en tiempo de respuesta aceptable, productividad y eficiencia del procesador.

 

OBJETIVOS Y FUNCIONES DE LA

PLANIFICACIÓN:

 OBJETIVOS:

–          Los objetivos de la planificación de proceso son:

–          Equidad, todos los procesos deben poder ejecutarse

–          Eficacia, mantener ocupada la CPU un 100% del tiempo

–          Tiempo de respuesta, minimizar el tiempo de respuesta al usuario

–          Tiempo de regreso, minimizar el tiempo que deben esperar los usuarios por lotes para obtener sus resultados

–          Rendimiento, maximizar el número de tareas procesadas por hora.

 

 

EL NÚCLEO DEL SISTEMA OPERATIVO (FUNCIONES):

El “núcleo” del Sistema Operativo controla todas las operaciones que implican procesos y representa solo una pequeña porción del código de todo el Sistema Operativo pero es de amplio uso.

Generalmente permanece en el almacenamiento primario.

El proceso de interrupciones se incluye en el núcleo ya que debe ser rápido (especialmente en sistemas multiusuario), para optimizar el uso de los recursos del sistema y proveer tiempos de respuesta aceptables a los usuarios interactivos.

El núcleo inhabilita las interrupciones mientras responde a una interrupción. Las interrupciones son habilitadas de nuevo después de completar el proceso de una interrupción.

 

El núcleo del Sistema Operativo generalmente realiza las siguientes funciones:

  • Manipulación de interrupciones.
  • Creación y destrucción de procesos.
  • Cambio de estados de procesos.
  • Despacho.
  • Suspensión y reanudación de procesos.
  • Sincronización de procesos.
  • Comunicación entre procesos.
  • Manipulación de bloques de control de proceso.
  • Soporte de las actividades de Entrada / Salida.
  • Soporte de la asignación y desasignación de almacenamiento.
  • Soporte del sistema de archivos.
  • Soporte de un mecanismo de llamada / regreso al procedimiento.
  • Soporte de ciertas funciones contables (estadísticas) del sistema.

 

 

CRITERIOS A CONSIDERAR:

 

Los principales “criterios” respecto de un buen algoritmo de planificación  son la equidad, la eficacia, el tiempo de respuesta, el tiempo de regreso y el rendimiento  

CRITERIO

DESCRIPCIÓN

Equidad

Garantizar que cada proceso obtiene su proporción justa de la cpu

Eficacia

Mantener ocupada la cpu el ciento por ciento del tiempo

Tiempo de respuesta

Minimizar el tiempo de respuesta para los usuarios interactivos

Tiempo de regreso 

Minimizar el tiempo que deben esperar los usuarios por lotes (batch) para obtener sus resultados

Rendimiento

Maximizar el número de tareas procesadas por hora

CRITERIOS DE UN BUEN ALGORITMO DE PLANIFICACIÓN.

Algunas de estas metas son contradictorias, por ejemplo, minimizar el tiempo de respuesta para los usuarios interactivos significaría no ejecutar las tareas batch.

Cada proceso es único e impredecible, es decir que pueden requerir intensivamente operaciones de Entrada / Salida o intensivamente cpu; el planificador del Sistema Operativo no tiene la certeza de cuánto tiempo transcurrirá hasta que un proceso se bloquee, ya sea por una operación de Entrada / Salida o por otra razón.

Para evitar que un proceso se apropie de la cpu un tiempo excesivo, los equipos poseen un dispositivo que provoca una interrupción en forma periódica, por ejemplo 60 hz, o sea sesenta veces por segundo.

En cada interrupción del reloj el Sistema Operativo decide si el proceso que se está ejecutando continúa o si el proceso agotó su tiempo de cpu y debe suspenderse y ceder la cpu a otro proceso.

 

PLANIFICACIÓN APROPIATIVA Y NO APROPIATIVA:

 

Los principales conceptos relacionados con Planificación del Procesador son los siguientes:   

Planificación Apropiativa: Es la estrategia de permitir que procesos ejecutables (desde el punto de vista lógico) sean suspendidos temporalmente.

Planificación no Apropiativa: Es la estrategia de permitir la ejecución de un proceso hasta terminar.

Planificación del Procesador: Determinar cuándo deben asignarse los procesadores y a qué procesos, lo cual es responsabilidad del Sistema Operativo.

 

Una manera muy frecuente de categorizar los criterios de planificación es distinguiendo entre criterios orientados al usuario y orientados al sistema. Los primeros se relacionan con el comportamiento del sistema percibido por el usuario individual. Los segundos se enfocan sobre el uso efectivo y eficiente del procesador. Teniendo en cuenta lo anterior, clasificar los criterios dados en clase.

 

Leonardo Aldana Tello.

LIN 1675.

MULTIPROGRAMACIÓN Y PROCESAMIENTO POR LOTES

marzo 24, 2009

MULTIPROGRAMACION

Es la técnica que permite que dos o mas programas ocupen la misma unidad de memoria principal y que sean ejecutados al mismo tiempo. Así por ejemplo mientras se ejecutan operaciones de entrada y salida de un programa, la unidad central de proceso puede ocuparse en realizar operaciones distintas de las de E/S pertenecientes a otros programas. La multiprogramación se refiere a dos o mas programas corriendo o procesándose al mismo tiempo; La multiprogramación se controla a través del sistema operativo, el cual observa los programas y los vigila hasta que estén concluidos. El numero de programas que pueden multiprogramarse en forma efectiva, depende de una combinación de la cantidad de memoria, de la velocidad de la CPU y del numero y velocidad de los recursos periféricos que tenga conectados, así como de la eficiencia del SISTEMA OPERATIVO.

http://www.gratisweb.com/atlasernesto/5.htm

 

 

PROCESAMIENTO POR LOTES

 

Archivos de Procesamiento por Lote

Un archivo de procesamiento por lote proporciona una forma abreviada de ejecutar uno o varios mandatos del MS-DOS. Cuando se teclea solo el nombre de un archivo de procesamiento por lote, el archivo ejecuta cada línea como si se la estuvieran introduciendo desde el teclado.

Los archivos de procesamiento por lote pueden automatizar instrucciones largas o repetitivas. La posibilidad de cometer errores en la digitación de un mandato se reduce, y las tareas largas se pueden comenzar y dejar que se ejecuten sin prestarles atención.

La escritura de esta clase de archivos se puede concebir como una forma de programar MS-DOS.

Creación de Archivos de Procesamiento por Lote

Se pueden crear archivos de procesamiento por lote utilizando COPY CON, cualquier procesador de palabras capaz de crear archivos de texto (la mayoría puede), o un editor de texto (incluso el editor EDLIN del MS-DOS). COPY CON no se recomienda para los ejemplos largos dada la inconveniencia para corregir errores de digitación.

Si se utiliza un procesador de palabras, utilizar el modo ASCII o no documento. El modo normal de muchos procesadores de palabras almacena los caracteres tecleados en un código que es el MS-DOS. Si el programa de procesamiento de palabras no hace distinción entre documentos y no documentos, utilizar el siguiente método para probar crear un archivo de procesamiento por lote.

  • Digitar un archivo de procesamiento por lote sencillo. Cada línea del archivo debe ser un solo mandato ejecutable del MS-DOS. Evitar el subrayado, las negritas u otro formato especial. Asegurarse de que no aparezcan los símbolos de cambio de línea u otros en la pantalla.
  • Guardar el archivo con una extensión de tipo .bat; después intentar ejecutarlo en la línea de solicitud del MS-DOS.
  • Si aparece el mensaje “BAD COMMAND OR FILE NAME” (Mandato o nombre de archivo incorrecto), consulte el índice del manual de su procesador de palabras los archivos ASCII para ver como el programa los archivos en modo ASCII o no documento.
  • MS-DOS acepta letras minúsculas excepto en los casos especiales que se señalan en el texto.

    Reglas para crear Archivos de Procesamiento por Lote

  • Un archivo de procesamiento por lote contiene texto en código ASCII. Se puede crear esta clase de archivo utilizando el comando COPY CON del MS-DOS, EDLIN (un editor de línea) u otro editor de texto. Si se usa un programa para procesamiento de palabras, asegurarse de que esté en modo de programación, o de no documento, cuando se cree el archivo de procesamiento por lote.
  • El nombre raíz del archivo de procesamiento por lote puede constar de uno a ocho caracteres y debe adecuarse a las reglas para crear nombres de archivos.
  • La extensión del nombre del archivo debe ser .bat.
  • Un archivo de procesamiento por lote no debe tener el mismo nombre raíz que el de un archivo de programa(un archivo que termine con .COM o .EXE) en el directorio en curso. Tampoco se debe usar un mandato interno del MS-DOS como COPY o DATE, a modo de nombre raíz. Si se usa uno de estos nombres raíz para denominar a un archivo de procesamiento por lote, y después se intenta ejecutarlo, MS-DOS ejecutara en su lugar el programa o el mandato.
  • Se pueden introducir cualesquiera de los mandatos que sean validos en el nivel del sistema del MS-DOS. También se pueden utilizar los marcadores de parámetros (%0 a %9), las variables de ambiente con el nombre de la variable entre signos de porciento (como %COMSPEC%), y los submandatos de procesamiento por lote.
  • Se puede introducir cualquier submandato de procesamiento por lote valido.
  • Para utilizar el signo de porciento (%) en un nombre de archivo en un mandato, introduzca dicho signo dos veces. Por ejemplo, para usar un archivo llamado A100%.TXT, se debe introducir A100%%.TXT. Esta regla no se aplica a los marcadores de parámetros (%0 a %9) o a las variables ambientales.
  • Se puede suprimir la presentación de cualquier línea del archivo de procesamiento por lote si se pone @ como el primer carácter que no es un espacio en esa línea.
  • Ejecución de un Archivo de Procesamiento por Lote

    Se puede ejecutar un archivo de procesamiento por lote introduciendo el nombre del archivo en la línea de solicitud del MS-DOS mediante la siguiente sintaxis:

    um:trayectoriam\nombrearchivo parámetros

    um: es el nombre de la unidad de disco que contiene al archivo de procesamiento por lote.

    Trayectoriam\ es la trayectoria del archivo de procesamiento por lote.

    Nombrearchivo es el nombre raíz del archivo de procesamiento por lote.

    Parámetros son los parámetros que utilizara el archivo de procesamiento por lote.

    Reglas para la ejecutar archivos de Procesamiento por Lote

  • Un archivo de procesamiento por lote debe tener la extensión .bat
  • si no se proporciona el nombre de una unidad de disco, se usa la unidad de disco en curso.
  • Si no se proporciona un nombre de trayectoria, se usa el directorio en curso.
  • Para invocar un archivo de procesamiento por lote, basta con teclear su nombre raíz. Por ejemplo, para invocar el archivo de procesamiento por lote FREC.BAT, digitar FREC, y después pulsar la tecla ENTER
  • MS-DOS ejecuta cada mandato en una línea a la vez. Los parámetros especificados se sustituyen por los marcadores cuando se usa el mandato.
  • MS-DOS reconoce un máximo de diez parámetros. Se puede usar el submandato SHIFT para superar esta limitación.
  • Si el MS-DOS encuentra un submandato de procesamiento por lote incorrectamente escrito, emite un mensaje de error de sintaxis, para después continuar con los mandatos restantes del archivo.
  • Se puede detener la ejecución de un archivo de procesamiento por lote presionando ctrl.-Break. MS-DOS presentara este mensaje:
  • Termnate batch job (Y/N)?_

    (Terminar el trabajo de procesamiento por lotes (S/N)?

    Si se contesta Y(S) por yes (si), el resto de los mandatos se ignoran, y aparece la línea de solicitud del sistema. Si se contesta N por no, MS-DOS se “salta” el mandato en curso pero continua el proceso de los otros mandatos de archivo.

  • MS-DOS “recuerda” cuál directorio contiene al archivo de procesamiento por lote. Su propio archivo puede hacer que el directorio en curso cambie en cualquier momento.
  • MS-DOS “recuerda” cuál disquete contiene el archivo de procesamiento por lote, y se pueden cambiar los disquetes en cualquier momento. MS-DOS solicitara que se inserte el disquete que contiene el archivo de procesamiento por lote, si es necesario. Sin embargo para la versión V3.0, si el archivo de procesamiento por lote esta en disquete no se puede retirar, pues de lo contrario MS-DOS presenta un mensaje de error y suspende el procesamiento por lote.
  • Se puede hacer que el MS-DOS ejecute un segundo archivo de procesamiento por lote inmediatamente después de que finalice el primero. Simplemente se debe introducir el nombre del segundo archivo como el ultimo mandato del primer archivo. También se puede ejecutar un segundo archivo dentro del primer archivo y regresar a éste usando el subcomando CALL.
  • Los submandatos de procesamiento por lote son validos solo para archivos de este tipo. No es posible, pues, ejecutar submandatos de procesamiento por lote como mandatos normales del MS-DOS.
  • No se puede redirigir la entrada o salida de un archivo de procesamiento por lote. Sin embargo, se puede usar redirección en las líneas dentro de un archivo de este tipo.
  • Uso de Comandos de Arribos de Procesamiento por Lote

    Se puede usar cualquier mandato valido de MS-DOS en un archivo de procesamiento por lote. MS-DOS cuenta también con un conjunto de mandatos para usarse específicamente en los archivos de procesamiento por lote: los submandatos de procesamiento por lote. A continuación hay una lista de submandatos (siguiente tema).

    http://html.rincondelvago.com/procesamiento-por-lotes.html

    ALGOTRITMOS DE PLANIFICACIÓN

    marzo 17, 2009

     

    FIFO:

     

    FIRST-COME, FIRST SERVED (FCFS)

     

    La política más simple de planificación es la FCFS. A medida que un proceso pasa al estado listo, este es agregado a la cola de listos. Cuando el proceso que actualmente está ejecutando cesa su ejecución entonces el proceso más viejo en la cola es seleccionado para correr. La implementación de esta política es a través de colas FIFO (First-In, First-Out). Cuando el CPU está libre, éste es asignado al proceso que está en la cabeza de la cola.

     

    FCFS es un algoritmo nonpreemptive, pues una vez que el CPU es asignado a un proceso, este lo mantiene hasta que espontáneamente lo suelta, ya sea porque el proceso finalizó o por algún requerimiento de E/S.

     

    El tiempo de espera bajo esta política tiende a ser alto. Además , tiende a favorecer aquellos procesos que requieren más tiempo de CPU (CPU-bound). Consideren el caso donde tenemos una colección de procesos. Uno de ellos utiliza más CPU que los otros, y el resto de los procesos requieren más trabajo de E/S (I/O-bound). Cuando el proceso CPU-bound ejecuta, los otros procesos esperan. Algunos de estos estarán en las colas de los dispositivos de E/S pero eventualmente en algún instante pasarán a la cola de procesos listos. En este momento, muchos de los dispositivos de E/S estarán ociosos. Cuando el proceso en ejecución deje el estado Running, los procesos I/O-bound pasarán a ejecutar y rápidamente volverán a bloquearse en espera de E/S. Si el proceso CPU-boundse encuentra bloqueado, entonces el procesador estará ocioso. Por lo tanto, FCFS puede ocasionar un uso indeficiente tanto del procesador como de los dispositivos de E/S.

     

     

     

    Proceso

    Tiempo de llegada

    Tiempo de Servicio

    Tiempo de Comienzo

    Tiempo de Finalización

    Turnaround

    Tiempo de Espera

    A

    0

    1

    0

    1

    1

    0

    B

    1

    100

    1

    101

    100

    0

    C

    2

    1

    101

    102

    100

    101-2=99

    D

    3

    100

    102

    202

    199

    102-3=99

    Promedio

     

     

     

     

    100

    49.50

     

     

    Proceso

    Tiempo de llegada

    Tiempo de Servicio

    Tiempo de Comienzo

    Tiempo de Finalización

    Turnaround

    Tiempo de Espera

    B

    0

    100

    0

    100

    100

    0

    D

    1

    100

    100

    200

    199

    100-1=99

    A

    2

    1

    200

    201

    201-2=199

    200-2=198

    C

    3

    1

    201

    202

    202-3=199

    201-3=198

    Promedio

     

     

     

     

    232

    123.50

     

     

    El tiempo promedio de espera bajo una política FCFS generalmente no es mínimo y puede variar sustancialmente si hay mucha diferencia entre las duraciones de ciclo de los procesos.

     

    En el segundo ejemplo, se presenta un efecto convoy donde los procesos esperan a que un proceso grande deje el CPU

     

    ROUND ROBIN(TURNO PRIORITARIO)

     

    Una manera rápida de reducir la penalización que los procesos cortos sufren con FCFS es usar expropiación basada en un reloj. Una interrupción de reloj es generada a intervalos periódicos. Cuando ocurre la interrupción, el proceso en ejecución es colocado en la cola de procesos listos y el próximo trabajo es seleccionado basado en el esquema FCFS. A cada proceso se le da un trozo de tiempo.

    La principal decisión de diseño que surge con Round Robin es el tamaño del trozo o quantum. Si el quantum es muy corto, entonces los procesos se moverán a través del sistema rápidamente. Por otro lado, hay un cierto overhead o desperdicio de tiempo envuelto con el manejo de la interrupción de reloj y las funciones de planificación y despacho. Por lo tanto quanta muy pequeños deberían evitarse. Una alternativa es usar un quantum de tiempo que sea un poco más grande que el tiempo promedio requerido para una interacción típica.

    Round Robin es particularmente efectivo para sistemas generales de tiempo compartido. Se implementa con una cola FIFO de procesos. Nuevos procesos son agregados al final de la cola, y toma el proceso que se encuentra en la cabeza de la cola. Actualiza el timer para que interrumpa después del quantum de tiempo.

    El desempeño de este algoritmo dependerá del tamaño del quantum. Si el quantum es infinito entonces degenera en FCFS. Si el quantum es muy pequeño entonces Round Robin es llamado compartición de CPU y en teoría pareciera que cada proceso tiene su propio procesador corriendo a 1/n la velocidad del procesador real.

    Bajo este esquema es importante considerar el efecto del cambio de contexto.

     

    Round Robin (RR q=3)

    Proceso

    Tiempo de llegada

    Tiempo de Servicio

    Tiempo de Comienzo

    Tiempo de Finalización

    Turnaround

    Tiempo de Espera

    A

    0

    8

    0, 12, 21

    3, 15, 23

    23

    15

    B

    1

    4

    3, 15

    6, 16

    16-1=15

    11

    C

    2

    9

    6, 16, 23

    9, 19, 26

    26-2=24

    15

    D

    3

    5

    9, 19

    12,21

    21-3=18

    11

    Promedio

     

     

     

     

    20

    13

     

     

    PRIORIDAD:

     

    En muchos sistemas, los procesos tienen prioridades asignadas, y el planificador escogerá aquel proceso con mayor prioridad.

    Cuando un proceso debe ser seleccionado, el planificador por prioridades seleccionará aquel proceso que tenga mayor prioridad. Si hay más de un proceso entonces se deberá seguir alguna política de selección.

    Un problema que presenta un esquema de planificación por prioridades puro es que los procesos con la prioridad más baja pueden sufrir de inanición o bloqueo indefinido. Un proceso que está listo para correr pero espera porque siempre hay procesos con prioridad más alta.

    Para evitar este problema, se puede ir incrementando gradualmente la prioridad de los procesos (envejecimiento).

    SJF es un caso especial de planificación por Prioridad, donde la prioridad es el inverso del valor estimado del próximo ciclo de CPU ( a menor ciclo, mayor prioridad).

     

    Proceso

    Tiempo de llegada

    Prioridad

    Tiempo de Servicio

    Tiempo de Comienzo

    Tiempo de Finalización

    Turnaround

    Tiempo de Espera

    A

    0

    2

    8

    0

    8

    8

    0

    B

    1

    1

    4

    22

    26

    26-1=25

    22-1=21

    C

    2

    4

    9

    8

    17

    17-2=15

    8-2= 6

    D

    3

    2

    5

    17

    22

    22-3=19

    17-3=14

    Promedio

     

     

     

     

     

    16.75

    10.25

     

    Este algoritmo puede ser preemptive y nonpreemptive. En el caso de preemptive, cuando un proceso llega a la cola de procesos listos, su prioridad es comparada con la prioridad del proceso que está corriendo. Si la prioridad del nuevo proceso es mayor, entonces se atiende al nuevo proceso.

     

     

    SHORTEST-JOB-FIRST (SJF)

     

    Este algoritmo selecciona al proceso con el próximo tiempo de ejecución más corto. Un proceso corto saltará a la cabeza de la cola. La ejecución de un proceso consiste en ciclos de ejecución de CPU y ciclos de espera por E/S. El algoritmo selecciona aquel proceso cuyo próximo ciclo de ejecución de CPU sea menor. El problema está en conocer dichos valores, pero podemos predecirlos usando la información de los ciclos anteriores ejecutados.

     

    SJF

    Proceso

    Tiempo de llegada

    Tiempo de Servicio

    Tiempo de Comienzo

    Tiempo de Finalización

    Turnaround

    Tiempo de Espera

    A

    0

    8

    0

    8

    8

    0

    B

    1

    4

    8

    12

    12-1=11

    8-1=7

    C

    2

    9

    17

    26

    26-2=24

    17-2=15

    D

    3

    5

    12

    17

    17-3=14

    12-3=9

    Promedio

     

     

     

     

    14.25

    10.33

     

    FCFS

    Proceso

    Tiempo de llegada

    Tiempo de Servicio

    Tiempo de Comienzo

    Tiempo de Finalización

    Turnaround

    Tiempo de Espera

    A

    0

    8

    0

    8

    8

    0

    B

    1

    4

    8

    12

    12-1=11

    8-1=7

    C

    2

    9

    12

    21

    21-2=19

    12-2=10

    D

    3

    5

    21

    26

    26-3=23

    21-3=18

    Promedio

     

     

     

     

    20.33

    11.66

     

    El SJF es probablemente optimal pues da el mínimo tiempo promedio de espera. El problema está en conocer la duración del próximo requerimiento de CPU para cada proceso. Esta duración puede predecirse suponiendo que el próximo ciclo puede ser similar a los anteriores.

     

    Este algoritmo puede ser preemptive o no. Cuando un nuevo proceso llega a la cola de procesos listos mientras otro se está ejecutando, el nuevo proceso puede tener el ciclo de duración de CPU más corto que lo que falta por ejecutar del proceso actual. En el caso de un esquema preemptive, el CPU será asignado al proceso que acaba de llegar a la cola. Este algoritmo se conoce como Shortest Remaining Time First (SRTF).

     

    http://www.ldc.usb.ve/~spd/Docencia/ci-3821/Tema4/node8.html

     

    Algoritmo de Planificación SJF en C

    SJF

    http://www.utpl.edu.ec/blog/sistemasoperativos/category/algoritmos-de-planificacion/

     

     

     

     

     ALGORITMO SRTF (“SHORTEST REMAINING TIME FIRST”)

    _ Asociar a cada proceso el tiempo de ráfaga de CPU restante.

    Seleccionar el proceso con menor ráfaga de CPU restante.

    En caso de empate, aplicar FCFS.

    _ Algoritmo expulsivo: Realizar cambio de contexto si llega un proceso a la

    cola de procesos listos con ráfaga de CPU menor que el tiempo restante

    del proceso en ejecución.

    _ Óptimo al minimizar el tiempo medio de espera.

     

     http://www3.uji.es/~castillo/ii11/teoria/TraspasTema3.pdf

     

     

    COLAS MÚLTIPLES:

     

     

    Colas multinivel con realimentación:

    _ Varias colas para los procesos listos.

    _ Un proceso se mueve de una cola a otra.

    _ Sistema de colas definido por:

    _ Número de colas.

    _ Algoritmo de planificación de cada cola.

    _ Cola en la que entrará un proceso al llegar a preparado.

    _ Planificación entre colas.

    _ Método para determinar la realimentación:

    _ Cuándo promover un proceso a una cola de mayor prioridad.

    _ Cuándo degradar un proceso a una cola de menor prioridad.

     

    Colas multinivel sin realimentación:

    _ Varias colas para los procesos listos.

    _ Cada cola tiene su propio algoritmo de planificación.

    _ Sistema de colas definido por:

    _ Número de colas.

    _ Algoritmo de planificación de cada cola.

    _ Planificación entre colas.

    _ Prioridad a cada cola.

    _ Cuantum de CPU a cada cola, que se reparte entre los

    procesos de cada cola.


    EJEMPLOS DE C++:

    #include <stdlib.h>

    #include <iostream.h>

    struct estudiante {

    char nombre [20];

    int edad;

    estudiante *enlace;

    };

    estudiante *cabeza=NULL;

    estudiante *cola=NULL;

    void insertar(char *nombre, int edad);

    void presentarlista();

    int main()

    {
    char continua = ’s’;

    char nombre [20];

    int edad;

    while (continua == ’s’){

    cout<< “Ingrese el nombre y la edad del estudiante”<> nombre >> edad;

    insertar(nombre, edad);

    cout<> continua;

    }

    presentarlista();
    system(”PAUSE”);
    return 0;

    }

    void insertar(char *nombre, int edad) {

    if (cabeza == NULL) { // Si no hay ningún nodo en la lista

    cabeza = new estudiante;

    cola = cabeza;

    }
    else { // Si ya hay nodos en la lista

    cola->enlace = new estudiante;

    cola = cola->enlace;

    }
    // strcpy (cola->nombre, nombre);

    cola->edad = edad;

    cola->enlace = NULL;

    }

    // Rutina que presenta la lista ingresada

    void presentarlista(){

    estudiante *recorrer=cabeza; // variable auxiliar

    while (recorrer != NULL) { // si aun hay elementos en la lista

    // presentar el nombre y la edad

    cout<< “Nombre: “<nombre << ” edad: “<edad <enlace;

    }
    }

     

    http://www.utpl.edu.ec/blog/sistemasoperativos/category/algoritmos-de-planificacion/

     

     

    Hello world!

    marzo 6, 2009

    Welcome to WordPress.com. This is your first post. Edit or delete it and start blogging!