El tiempo de ejecuci\u00f3n de cada tarea es conocido.<\/li>\n<\/ol>\nM\u00e9tricas del Programador<\/h3>\n \n Adem\u00e1s de algunos supuestos sobre la carga, tambi\u00e9n se necesita alguna herramienta para comparar diferentes pol\u00edticas de programaci\u00f3n: m\u00e9tricas del programador. Una m\u00e9trica es simplemente una medida de algo. Existen varias m\u00e9tricas que se pueden utilizar para comparar programadores.<\/p>\n
Por ejemplo, utilizaremos una m\u00e9trica llamada tiempo de respuesta<\/b> (turnaround time). El tiempo de respuesta de una tarea se define como la diferencia entre el tiempo de finalizaci\u00f3n de la tarea y el tiempo de llegada de la tarea al sistema.<\/p>\n
Tturnaround=Tcompletion\u2212Tarrival<\/u><\/p>\n
Dado que hemos supuesto que todas las tareas llegan al mismo tiempo, entonces Ta=0 y as\u00ed Tt=Tc. Este valor naturalmente cambiar\u00e1 cuando modifiquemos los supuestos anteriores.<\/p>\n
Otra m\u00e9trica es justicia<\/b> (fairness). La productividad y la justicia a menudo son caracter\u00edsticas opuestas en la programaci\u00f3n. Por ejemplo, un programador puede optimizar la productividad, pero a expensas de la espera para iniciar otras tareas, disminuyendo as\u00ed la justicia.<\/p>\nPRIMERO EN ENTRAR, PRIMERO EN SALIR (FIFO)<\/h3>\n
\n El algoritmo m\u00e1s b\u00e1sico que podemos implementar se llama FIFO o el primero en llegar (dentro), el primero en ser servido (fuera)<\/b>. Este algoritmo tiene varias ventajas: es muy simple de implementar y se adapta a todas nuestras suposiciones, realizando el trabajo bastante bien.<\/p>\n
Consideremos un ejemplo simple. Supongamos que 3 tareas se han asignado al mismo tiempo. Pero asumamos que la tarea A lleg\u00f3 un poco antes que las dem\u00e1s, por lo que estar\u00e1 en la lista de ejecuci\u00f3n antes que las otras, al igual que la B en relaci\u00f3n con la C. Supongamos que cada una de ellas tomar\u00e1 10 segundos. \u00bfCu\u00e1l ser\u00eda, en este caso, el tiempo medio de ejecuci\u00f3n de estas tareas?<\/p>\n
Como resulta, los diferentes tiempos de ejecuci\u00f3n de las tareas afectan negativamente la productividad del algoritmo FIFO. Supongamos que la tarea A se ejecuta durante 100 segundos, mientras que B y C siguen siendo de 10 cada una.<\/p>\n
efecto de convoy<\/b>, cuando algunos consumidores de recursos de corta duraci\u00f3n est\u00e1n en cola detr\u00e1s de un consumidor pesado. Es similar a una fila en el supermercado, cuando delante de usted hay un comprador con un carrito lleno. La mejor soluci\u00f3n al problema es intentar cambiar de caja o relajarse y respirar profundamente.<\/p>\nShortest Job First<\/h3>\n
\n \u00bfSe puede resolver de alguna manera esta situaci\u00f3n con procesos pesados? Por supuesto. Otro tipo de planificaci\u00f3n se llamaShortest Job First<\/b> (SJF). Su algoritmo tambi\u00e9n es bastante primitivo: como se entiende por el nombre, las tareas m\u00e1s cortas se ejecutar\u00e1n primero una tras otra.<\/p>\n
50 en lugar de 110<\/b>, lo que es pr\u00e1cticamente el doble de mejor.<\/p>\n
Por lo tanto, bajo la suposici\u00f3n de que todas las tareas llegan al mismo tiempo, el algoritmo SJF parece ser el m\u00e1s \u00f3ptimo. Sin embargo, nuestras suposiciones a\u00fan no parecen realistas. Esta vez, cambiamos la suposici\u00f3n 2 y presentamos que las tareas pueden llegar en cualquier momento, no todas al mismo tiempo. \u00bfQu\u00e9 problemas podr\u00eda ocasionar esto?<\/p>\n
Shortest Time-to-Completion First (STCF)<\/h3>\n \n Para mejorar la situaci\u00f3n, omitamos la suposici\u00f3n 3 de que el programa se inicia y funciona hasta completarse. Adem\u00e1s, vamos a necesitar soporte de hardware y, como pueden suponer, vamos a utilizar un temporizador<\/b> para interrumpir la tarea en ejecuci\u00f3n y realizar cambios de contexto<\/b>. De este modo, el planificador puede actuar en el momento en que llegan las tareas B y C: interrumpir la ejecuci\u00f3n de la tarea A y procesar las tareas B y C, y despu\u00e9s de finalizarlas, continuar con el proceso A. Este tipo de planificador se llama STCF<\/b>o Preemptive Job First<\/b>.<\/p>\n
M\u00e9trica Tiempo de respuesta (Response Time)<\/h3>\n \n As\u00ed, si conocemos el tiempo de ejecuci\u00f3n de las tareas y sabemos que estas utilizan solo CPU, STCF ser\u00e1 la mejor soluci\u00f3n. Y en tiempos antiguos, estos algoritmos funcionaban bastante bien. Sin embargo, ahora el usuario pasa la mayor parte del tiempo frente al terminal y espera una interacci\u00f3n productiva e interactiva. As\u00ed naci\u00f3 una nueva m\u00e9trica \u2014 tiempo de respuesta<\/b> (response time).<\/p>\n
El tiempo de respuesta se calcula de la siguiente manera:<\/p>\n
Tresponse=Tfirstrun\u2212Tarrival<\/u><\/p>\n
Por lo tanto, para el ejemplo anterior, el tiempo de respuesta ser\u00e1: A=0, B=0, C=10 (abg=3,33).<\/p>\n
Y resulta que el algoritmo STCF no es tan bueno en la situaci\u00f3n en la que 3 tareas llegan al mismo tiempo; tendr\u00e1 que esperar hasta que las tareas peque\u00f1as se completen completamente. As\u00ed, el algoritmo es bueno para la m\u00e9trica de tiempo de retorno, pero malo para la m\u00e9trica de interactividad. Imagina que, sentado frente a la terminal tratando de escribir caracteres en un editor, tuviste que esperar m\u00e1s de 10 segundos porque alguna otra tarea est\u00e1 ocupando el procesador. No es nada agradable.<\/p>\n
Round Robin<\/h3>\n \n Para resolver este problema, se desarroll\u00f3 un algoritmo Round Robin<\/b> (RR). La idea b\u00e1sica es bastante simple: en lugar de ejecutar las tareas hasta que se completen, ejecutamos una tarea durante un cierto per\u00edodo de tiempo (llamado cu\u00e1ntum de tiempo) y luego cambiamos a otra tarea de la cola. El algoritmo repite su trabajo hasta que todas las tareas est\u00e1n completas. En este proceso, el tiempo de ejecuci\u00f3n del programa debe ser un m\u00faltiplo del tiempo tras el cual el temporizador interrupta el proceso. Por ejemplo, si el temporizador interrumpe el proceso cada x=10 ms, el tama\u00f1o de la ventana de ejecuci\u00f3n del proceso debe ser m\u00faltiplo de 10 y puede ser 10, 20 o x*10.<\/p>\n
Consideremos un ejemplo: las tareas A, B y C llegan al sistema al mismo tiempo y cada una quiere trabajar 5 segundos. El algoritmo SJF ejecutar\u00e1 cada tarea hasta el final antes de iniciar otra. En cambio, el algoritmo RR con ventana de ejecuci\u00f3n=1s pasar\u00e1 por las tareas de la siguiente manera (fig. 4.3):<\/p>\n
El tiempo promedio de respuesta para el algoritmo RR (0+1+2)\/3=1, mientras que para SJF (0+5+10)\/3=5.<\/p>\n
Es l\u00f3gico suponer que la ventana de tiempo es un par\u00e1metro muy importante para RR; cuanto menor sea, mayor ser\u00e1 el tiempo de respuesta. Sin embargo, no se puede hacer que sea demasiado peque\u00f1a, ya que el tiempo de cambio de contexto tambi\u00e9n jugar\u00e1 un papel en el rendimiento general. As\u00ed, la elecci\u00f3n del tiempo de ventana se establece por el arquitecto del sistema operativo y depende de las tareas que se planea ejecutar en \u00e9l. Cambiar de contexto no es la \u00fanica operaci\u00f3n auxiliar que consume tiempo; el programa en ejecuci\u00f3n opera con muchos otros elementos, como diferentes cach\u00e9s, y en cada cambio es necesario guardar y restaurar este entorno, lo que tambi\u00e9n puede requerir mucho tiempo.<\/p>\n
RR es un excelente planificador si solo se considera la m\u00e9trica del tiempo de respuesta. Pero, \u00bfc\u00f3mo se comportar\u00e1 la m\u00e9trica del tiempo de rotaci\u00f3n de tareas con este algoritmo? Consideremos el ejemplo anterior, donde el tiempo de ejecuci\u00f3n de A, B y C es de 5 segundos y llegan al mismo tiempo. La tarea A terminar\u00e1 a las 13, B a las 14 y C a las 15 segundos, por lo que el tiempo promedio de rotaci\u00f3n ser\u00e1 de 14 segundos. Por lo tanto, RR es el peor algoritmo para la m\u00e9trica de rotaci\u00f3n.<\/p>\n
En t\u00e9rminos m\u00e1s generales, cualquier algoritmo del tipo RR es justo; divide el tiempo de ejecuci\u00f3n de la CPU equitativamente entre todos los procesos. As\u00ed, estas m\u00e9tricas entran en conflicto constantemente entre s\u00ed.<\/p>\n
Por lo tanto, tenemos varios algoritmos contrapuestos y a\u00fan quedan algunas suposiciones: que el tiempo de la tarea es conocido y que la tarea solo utiliza la CPU.<\/p>\n
Mezcla con I\/O<\/h3>\n \n Primero eliminemos la suposici\u00f3n 4, que el proceso solo utiliza la CPU; esto no es cierto ya que los procesos pueden acceder a otro hardware.<\/p>\n
En el momento en que un proceso solicita una operaci\u00f3n de entrada\/salida, el proceso pasa al estado bloqueado, esperando la finalizaci\u00f3n de la I\/O. Si la I\/O se env\u00eda al disco duro, tal operaci\u00f3n puede tardar unos milisegundos o m\u00e1s, y en ese momento el procesador estar\u00e1 inactivo. Durante este tiempo, el planificador puede usar el procesador para otro proceso. La siguiente decisi\u00f3n que debe tomar el planificador es cu\u00e1ndo el proceso completar\u00e1 su I\/O. Cuando esto suceda, habr\u00e1 una interrupci\u00f3n y el sistema operativo cambiar\u00e1 el proceso que solicit\u00f3 la I\/O al estado listo.<\/p>\n
Consideremos un ejemplo de varias tareas. Cada una de ellas necesita 50 ms de tiempo de CPU. Sin embargo, la primera acceder\u00e1 a I\/O cada 10 ms (tambi\u00e9n se ejecutar\u00e1 cada 10 ms). Y el proceso B simplemente utiliza 50 ms de CPU sin I\/O.<\/p>\n
Ya no hay or\u00e1culos.<\/h3>\n \n Ahora tratemos de deshacernos de la suposici\u00f3n de que el tiempo de ejecuci\u00f3n de la tarea es conocido. Este es, en general, el peor y m\u00e1s irrealista supuesto de toda la lista. De hecho, en los sistemas operativos promedio, el propio SO geralmente sabe muy poco sobre el tiempo de ejecuci\u00f3n de las tareas, \u00bfc\u00f3mo entonces construir un programador sin saber cu\u00e1nto tiempo ejecutar\u00e1 una tarea? Quiz\u00e1s podr\u00edamos utilizar algunos principios de RR para resolver este problema.<\/p>\n
Summary<\/h3>\n \n Hemos revisado las ideas b\u00e1sicas de la planificaci\u00f3n de tareas y hemos considerado 2 familias de programadores. El primero lanza la tarea m\u00e1s corta primero, aumentando as\u00ed el tiempo de rotaci\u00f3n, mientras que el segundo se divide equitativamente entre todas las tareas, mejorando el tiempo de respuesta. Ambos algoritmos son deficientes donde los algoritmos de la otra familia son efectivos. Tambi\u00e9n hemos visto c\u00f3mo el uso paralelo de CPU e I\/O puede mejorar el rendimiento, pero no hemos resuelto el problema de la visi\u00f3n del SO. En la pr\u00f3xima clase, discutiremos un programador que mira al pasado cercano y intenta predecir el futuro. Se llama cola de retroalimentaci\u00f3n de m\u00faltiples niveles.habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0435 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u041f\u0440\u0438\u0432\u0435\u0442, \u0425\u0430\u0431\u0440! \u0425\u043e\u0447\u0443 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0432\u0430\u0448\u0435\u043c\u0443 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u044e \u0441\u0435\u0440\u0438\u044e \u0441\u0442\u0430\u0442\u0435\u0439-\u043f\u0435\u0440\u0435\u0432\u043e\u0434\u043e\u0432 \u043e\u0434\u043d\u043e\u0439 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u0439 \u043d\u0430 \u043c\u043e\u0439 \u0432\u0437\u0433\u043b\u044f\u0434 \u043b\u0438\u0442\u0435\u0440\u0430\u0442\u0443\u0440\u044b \u2014 OSTEP. \u0412 \u044d\u0442\u043e\u043c \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u0435 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0433\u043b\u0443\u0431\u043e\u043a\u043e \u0440\u0430\u0431\u043e\u0442\u0430 unix-\u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0445 \u0441\u0438\u0441\u0442\u0435\u043c, \u0430 \u0438\u043c\u0435\u043d\u043d\u043e \u2014 \u0440\u0430\u0431\u043e\u0442\u0430 \u0441 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0430\u043c\u0438, \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u043c\u0438 \u043f\u043b\u0430\u043d\u0438\u0440\u043e\u0432\u0449\u0438\u043a\u0430\u043c\u0438, \u043f\u0430\u043c\u044f\u0442\u044c\u044e \u0438 \u043f\u0440\u043e\u0447\u0438\u0438\u043c\u0438 \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u043c\u0438 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u0430\u043c\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e \u041e\u0421. \u041e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0432\u0441\u0435\u0445 \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u043e\u0432 \u0432\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0432\u043e\u0442 \u0442\u0443\u0442. […]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":23990,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[688],"tags":[],"class_list":["post-32158","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-administrirovanie"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t