|
Categorias
|
Sistemas Operativos II
Sistemas Operativos II Introducción a los procesos.- * PCB (Process Control Block).- * FCFS (First Come First Served) * MQS (Multilevel Queue Schedulling) * Comunicación entre procesos.- * Algoritmos de Soluciona al Problema de Sección Critica * Deshabilitación de Interrupciones * Algoritmo de Variables de Cierre * Algoritmo de alternación Estricta * Condiciones Necesarias para que se produzca DEADLOCK * Resourse Allocation Graph(Grafo de utilizacion de recursos) * Mecanismos para tratar con Deadlocks * Detección y Recuperación de Deadlocks * Administración de Memoria Real.- * Asignación contigua de almacenamiento de un solo usuario.- * Multiprogramación de partición fija.- * Multiprogramación de partición variable.- * Estrategias de colocación en el almacenamiento.- * Almacenamiento de Memoria Virtual.- * Algoritmos de remplazo de página.- * Algoritmo de Segunda Chance.- * LFU (Least Frequently Used).- * MFU (Most Frequently Used).- * Estructuras de directorios.- * Implementación de File Systems.- * Método de Asignación Contigua.- * Implementación de la lista de espacio libre.- * Implementación de Directorios.- * Estructura del Almacenamiento Secundario.- * Algoritmos de Selección de Cola de I/O.- * FCFS (First Come Firs Served).- * Manejo del espacio de Swap.- * Un sistema operativo es un conjunto de programas que hacen al hardwareutilizable. El sistema operativo es un administrador de recursos: cpu,dispositivos de E/S, memoria, datos. Las funciones del sistema operativo son:
Proceso : es un programa en ejecución.Cada proceso dentro de su información tiene el código del programa, el áreade datos, el program counter, registros e información adicional. El sistema operativo debe poder crear un proceso, destruirlo, suspenderlo,retomarlo, debe tener un mecanismo para retomar un proceso y para sincronizalos,y mecanismos de concurrencia. Los procesos tienen una estructura jerárquicatipo árbol. Manejo de Memoria: el S.O. carga en memoria toda la información de cadaproceso. El manejo de memoria debe mantener información de los espaciosocupados y por quien, decidir que procesos usara la memoria en la medida queesta se torne disponible y ocupar y liberar memoria. La memoria secundaria ovirtual es la capacidad que tiene el sistema operativo para manejar espacios dedisco como si fuera una extensión de la memoria; esto sirve para elgerenciamiento del espacio libre y la ocupación de espacio. Sistema de Archivos: La estructura de un sistema de archivos es en formade árbol. El sistema de archivos son los archivos y directorios. Las funcionesson crear y eliminar archivos, compartir archivos para intercambiar información,agrupar archivos en forma conveniente al usuario, respaldo y recuperación, elacceso de los usuarios a la información sin la necesidad de conocer la ubicaciónfísica (sabiendo solo los nombres simbólicos). Interprete de comandos: Es una forma amigable de trabajar sin necesidadde usar programas de bajo nivel para comunicarse con el S.O. System calls: Son un conjunto de primitivas que brinda el sistemaoperativo y que sirven para comunicarse con el Hardware en forma"entendible". Para el manejo de los procesos hay system calls para :crear_proceso, destruir_proceso, etc.... Para el manejo del sistema de archivos:crear_archivo, borrar_archivo, abrir_archivo, etc ... Para el manejo de losdispositivos: solicitar_dispositivo, liberar_dispositivo, etc... Todas las computadoras modernas pueden realizar varias tareas al mismotiempo. En estos sistemas de multiprogramación la CPU debe cambiar de unprograma a otro, ejecutando cada uno en decenas o cientos de milisegundos. Peroen cualquier instante de tiempo la CPU puede estar ejecutando solo un programa. Todo el software ejecutable en la computadora, que con frecuencia incluye alsistema operativo, se organiza en varios procesos secuenciales. Un proceso es básicamenteun programa ejecutante donde intervienen los valores corrientes del contador deprograma, registros y variables. Estados de un proceso.- Un proceso puede variar entre 5 distintos estados: New: cuando el proceso esta siendo creado. Running: cuando el proceso se esta ejecutando. Waiting: cuando el proceso esta esperando que se cumpla algún otroevento. Ready: cuando el proceso esta pronto para ejecutar, esperando por la CPU. Terminated: cuando el proceso esta terminado.
Internamente los procesos se almacenan en una lista encadenada en donde cadanodo almacena la información anterior. Cada nodo tiene información de:
Colas de Schedulling : Los procesos queestán en estado de espera se quedan en una lista llamada lista o cola de ready.Los procesos que hacen uso de E/S se guardan en una cola de E/S. Hay una cola deE/S por cada dispositivo.Schedullers: Componente del sistema operativo responsable de decidirquien hara uso de la CPU. FCFS (First Come First Served) Cuando un proceso llega a la cola de ready su PCB es agregado al final de lalista. El uso de la CPU es otorgado al primero de la lista y una vez que unproceso comienza a ejecutar no deja de hacerlo hasta que se termina. El tiempomedio de espera para este algoritmo suele ser bastante alto. Una vez que un proceso ejecuta no deja de hacerlo hasta que voluntariamentecambia de estado (no hay interrupción por tiempo). Asocia a cada proceso eltiempo de CPU que habrá de usar en su próxima vuelta y va a decidir por el máspequeño. Si hubiera mas de uno utiliza FCFS para desempatar. El mayor problemade este algoritmo radica en el cálculo de tiempo de uso de CPU. Este se puedeaproximar a: T n+1=a.tn+(1-a)Tn0< a<1 Tiempo calculado en la vuelta nPróximo uso de CPU Tiempo usado en la vuelta n El problema de este algoritmo es que el tiempo de espera para los procesoslargos puede ser demasiado largo. Constantemente se están entregando losprocesos mas cortos y el más grande nunca será ejecutado. El FJS se puede subdividir en 2 tipos de algoritmos: PREEMPTIVO o NOPREEMPTIVO Preemptivo significa que si mientras un proceso se esta ejecutando, entra ala cola de ready un proceso mas corto, el proceso en la cola de ready se apropiade la CPU y comienza su ejecución. Asocia a cada proceso una prioridad. Luego selecciona el proceso con masprioridad para desempatar. En caso de que hubieran dos o mas procesos con lamisma prioridad, se usa FCFS para desempatar. Hay dos tipo de prioridad en losprocesos: la prioridad externa definidas a través del sistema operativoy la prioridad interna definida por el tiempo de uso de la CPU, elcontrol de E/S, etc. Este algoritmo también se puede ejecutar de dos maneras:preemptivo y no preemptivo. El algoritmo soluciona el problema del looping peroel problema es que los procesos con prioridad muy baja tienen chance de noejecutarse nunca. Para solucionar este problema de espera infinita elenvejecimiento de un proceso eleva su prioridad. Este es un algoritmo basado en FCFS. Trata la cola de ready como una listacircular. Introduce el concepto de "Quantum" o "Time slice": mayor tiempo de cpu que podrá hacer uso un proceso en cada vuelta. Si elvalor del Quantum fuese muy grande, el algoritmo funcionara como un FCFS. Si elQuantum fuera muy chico se produce un overhead por context switch (significa queel Quantum se setea en un tiempo menor al que demora el context switch). Estealgoritmo es fuertemente dependiente del Quantum o Time Slice. El Quantum debeser mayor que el 80% de los tiempos de CPU que hagan uso los procesos, pero noel proceso entero sino por cada burst. MQS (Multilevel Queue Schedulling) Este algoritmo parte la cola de ready en un numero de colas n. Luego existeun criterio para clasificar en que cola será colocado un proceso cuando quequeda en estado de ready. Cada cola puede manejar su propio algoritmo deschedulling
MFQS (Multilevel Feed Back Queue Schedulling) Define los siguientes parámetros:
Para que mas de una CPU no tomen el mismo proceso de la cola de ready seutilizan mecanismos de sincronización. Otro mecanismo seria partir la cola en ncolas (n CPUs), pero si se hiciera esto podría llegar a suceder que losprocesos de una CPU fueran todos cortos y los de otra fueran largos por lo cualhabría una CPU que quedaría libre y otra ejecutando. Otra forma sería que unaCPU decidiera cual CPU va a ejecutar cual proceso. Esto puede llevar a que laCPU que esta seleccionando quede un poco mas cargada porque en algún momentoestará ejecutando el algoritmo de selección y un proceso asignado a ella. Hay dos tipos de procesos: los independientes que no afectan ni puedenser afectados por ningún otro proceso y los cooperativos que afectan ypueden ser afectados por algún otro proceso del sistema operativo. Los procesos con frecuencia precisan comunicarse entre si, Para esto existenciertos contratiempos que debieron ser superados. Para prevenir este problema enlas situaciones en la que interviene cualquier recurso compartido se debeimpedir que mas de un proceso haga uso del recurso compartido al mismo tiempo.Lo que se necesita es exclusión mutua, La parte del programa que accesa lamemoria compartida se le llama sección crítica. Para tener una soluciónadecuada los procesos deben cumplir estos cuatro puntos:
Algoritmos de Solucionaal Problema de Sección Critica Deshabilitación de Interrupciones La solución mas simple es que cada proceso desactive todas lasinterrupciones justo después de entrar en su sección crítica y las vuelva aactivar antes de salir de ella. Con las interrupciones deshabitadas no puedenocurrir interrupciones al reloj por lo cual no se cambiara a otro proceso. Estemétodo no es muy atractivo ya que no es muy prudente dar a los procesos delusuario el poder de desactivar las interrupciones.. Si un usuario lo hiciera ynunca las volviera a activar sería el fin del sistema. Además si fuera unsistema con mas de una CPU la desactivación de interrupciones solo afectaríauna de ellas y las otras podrían accesar la memoria compartida.
Algoritmo de Variables de Cierre Este algoritmo utiliza un flag. Al entrar a la sección crítica se fija sies uno o cero si es cero lo pone en uno y entra a la sección crítica; si esuno espera hasta que valga cero. Antes de salir de la sección crítica igualael flag a cero. Repeat If (flag = 0) then { Flag:=1 Seccion crítica Flag:=0 Seccion no crítica} Until 0 = 1 Este algoritmo si embargo no resuelve el problema de la sección críticaporque si hubiera una interrupción justo después de comprobar el estado delflag y se accediera a la memoria compartida antes de cambiar el flag, otroproceso podría acceder a la memoria compartida, cambiar el flag a uno y habríandos procesos accesando la memoria compartida. Algoritmo de alternación Estricta En este algoritmo dos procesos comparten una variable flag, pero en vez deutlizar el mismo codigo se usa distinto codigo para cada proceso.
El problema aquí radica en que si un proceso tiene una sección no críticamuy larga el otro tendrá que esperar para entrar en su sección crítica apesar qe no se este ejecutando nada que la afecte.
Algoritmo de Peterson (o Algoritmo de Dekker) Este algoritmo combina las dos ideas anteriores. Se comparten una variableflag y una variable turno.
Este algoritmo soluciona el problema de la sección crítica y evite que unproceso quede en espera mientras que otro proceso este en su sección no crítica.Para n procesos la idea es un poco mas compleja: Flag::array[0..n-1] Turn::0..n-1 El while se tornara en una evaluación de n condiciones Son una herramienta de sincronización. Es una variable protegida que solopuede ser modificada por la rutina de inicialización y por otras dosoperaciones atómicas: P( ) <- wait V( ) <- signal Las operaciones a las cuales se puede acceder son: Inicialización: Crea un nuevo semáforo asignándole un valor inicial P(s): while (s=0) do no_op ATÓMICA s:=s-1 V(s): s:=s+1 ATÓMICA Existen básicamente dos tipos de semáforos:
A continuación se presenta una solución mediante semáforos del problemaproductor/consumidor. #define N 100 semaphore mutex = 1; semaphore empty = N; semaphore full = 0; void productor(void) {int item; while(1){ produce_item(item); down(empty); down(mutex); enter_item(item); up(mutex); up(full);} } void consumidor(void) { int item; while(1){ down(full); down(mutex); remove_item(&item); up(mutex); up(empty); consume_item(item);} } En este caso tenemos la utilización de 3 semáforos, uno destinado alcontrol de la exclusión mutua y los otros dos destinados a la sincronizaciónde los procesos para el control de buffer lleno y vacío. Podríamos utilizar semáforos para un algoritmo de espera ocupada con nprocesos, pero los n procesos que están ejecutando el while de la función P(s)van a la cola de ready en un instante de tiempo reduciendo la performancegeneral del equipo. Para evitar la espera ocupada se crea un semáforo que sea un registro de unnuevo tipo: Semáforo = Record Valor:Integer L:Lista_de_Procesos End P(s) { s.Valor:= s.valor - 1 if s.Valor < 0 then agregar este proceso a s.L bloquear; end} V(s){ s.Valor:=s.Valor + 1 if s.Valor £0 then quitar un proceso y a s.Ldespertar(y) }
Es un tipo de procedimientos, variables y estructuras de datos que se agrupanen un tipo de modulo especial. Tienen una propiedad importante: solo un procesopuede estar activo en un monitor en un instante de tiempo. Los monitores proveen un nuevo tipo de variables de condición con dosoperaciones que operan sobre el (solo se usan dentro del procedimiento de elmonitor). Wait -> wait(a) : produce que el proceso que ejecuta la instrucciónsea interrumpido y removido de la cola de ready hasta que otro proceso lohabilite ejecutando la instrucción signal( )con la misma variable de condición. Signal -> signal(a) : Habilita la ejecución de algún proceso enespera por la ejecución de la instrucción wait con la misma variable decondición.
Si un conjunto de procesos esta en estado de espera por recursos y nuncacambia de estado porque los recursos por los que espera están siendo utilizadospor otros procesos en estado de espera tenemos un DEADLOCK. Los recursos son lamemoria, dispositivos de E/S, semáforos, archivos, etc. La forma en que unproceso hace uso de un recurso es: Solicitud: si el recurso esta disponible se le otorga, si no el procesopasa a estado de espera. Uso: El proceso utiliza el recurso Liberación: el proceso debe liberar el recurso. Condiciones Necesariaspara que se produzca DEADLOCK Si se presentan simultáneamente las cuatro siguientes condiciones el sistemaesta en DEADLOCK.
Resourse AllocationGraph(Grafo de utilizacion de recursos) Conjunto de Vértices: U =P U R P={P1,P2,....,Pn} R={R1,R2,...,Rn} Conjunto de Aristas: Una arista de un proceso Pi a un Recurso Rj significa que el proceso i estahaciendo una solicitud por el recurso Rj. Una arista del recurso Rj al proceso Pi, significa que el recurso estaasignado al proceso. Si un RAG no tiene ciclos el sistema no esta en DEADLOCK, sis si los tiene nose puede afirmar nada. Mecanismos para tratarcon Deadlocks La estrategia consiste en anular alguna de las cuatro condiciones necesariaspara que se produzca un Deadlock.
Si se tiene cuidado al en la forma de asignar los recursos se pueden evitarsituaciones de Deadlock. Supongamos un ambiente en el que todos los procesosdeclaren a priori la cantidad máxima de recursos que habá de usar. Estado Seguro: un estado es seguro si se pueden asignar recursos a cadaproceso (hasta su máximo) en algún orden sin que se genere Deadlock. El estadoes seguro si existe un ordenamiento de un conjunto de procesos {P1...Pn} tal quepara cada Pi los recursos que Pi podrá utilizar pueden ser otorgados por losrecursos disponibles mas los recursos utilizados por los procesos Pj,j<i. Silos recursos solicitados por Pi no pueden ser otorgados, Pi espera a que todoslos procesos Pj hayan terminado. Algoritmo del banquero de Dijkstra Asigna peticiones de recursos siempre que las mismas den como resultadoestados seguros. Solicitudes que den como resultado estados inseguros seránnegadas hasta que puedan ser satisfechas. Este algoritmos evita situaciones deDeadlock asignando los recursos en forma correcta. Las debilidades del algoritmo son: que requiere que la cantidad de recursosdel sistema sea constante, requiere una cantidad de procesos constante yrequiere que los procesos garanticen que los recursos van a ser devueltos en unintervalo finito de tiempo. Detección y Recuperaciónde Deadlocks Algoritmos de Detección de Deadlock Procedure detecta_deadlock var Disponible:array[1..n] of integer //# de recursos Usados:array[1..n] of integer Solicitados:array[1..n] of integer Finalizado:array[1..n] of boolean Begin Work:=Disponibles; For i:=1..n do if(usados[i]≠0) then finish[i]:=false Else finish[i]:=true; While(encontrar_indice_i = true) do { Work:=work + usados[i]; Finish[i]:=true; } If ((finish[i] = false) para algun i), 1≤i≤n then End Function encontrar_indice_i : Boolean Begin If (existe i tal que (Finish[i]=false && solicitados[i] ≤ work) Then -> true Else -> false End
Los programas residen en disco como ejecutables binarios y deben ser traídosa memoria para su ejecución. El conjunto de programas residentes en discoesperando para ser cargados en memoria forman la cola de entrada. Los programas pueden direccionar memoria en varias formas:
Administración de Memoria Real.- Asignación contigua de almacenamiento de un solousuario.-
Protección de Memoria: Se incorpora un registro de limite (limit register) a la cpu. Cada petición de acceso a la memoria realizada por el usuario se compara con el registro limite. Si la dirección a la que se quiere acceder es menor o igual al registro limite se cancela la solicitud.
Multiprogramación de partición fija.- La memoria se divide en particiones de tamaño fijo (puede ser distinto el tamaño de cada partición). Originalmente los programas se compilaban y link editaban para ejecutar en una partición en particular (direcciones absolutas). Posteriormente los compiladores y link editores generan código reubicable para que un programa pudiera ejecutar en cualquier partición de memoria suficientemente grande. Con esta estructura de administración de memoria se desperdicia memoria y tiempo de CPU (si hay un programa corriendo los demás quedan encolados aunque haya otra partición libre).
Multiprogramación de partición variable.- Cada programa o usuario utiliza tanta memoria como sea necesaria siempre quequepa en el almacenamiento real. Cuando los programas van terminando su ejecuciónse van generando agujeros en memoria. Métodos de solucion al problema de agujeros en meoria: Combinación .-Cuando un programa termina su ejecución el sistem,a operativo verifica sihay algun bloque de memoria contigua libre (antes o después) en cuyo caso loscombina para generar un único bloque de memoria libre de tamaño igual a lasuma de ambos. Agrupa toda la memoria disponible en un único bloque de memoria al final. Desventajas:
En definitiva no es conveniente utilizar este método para solucionar elproblema de los agujeros en memoria debido al alto costo.
Estrategias de colocación en el almacenamiento.- En cualquiera de estas estrategias cuando a una petición le es asignada unapartición y sobra memoria el sistema operativo se da cuenta y deja a esteespacio sobrante como una nueva partición. Los bloques de memoria son asignados según las necesidades del programa quese esta ejecutando Asignan la primera partición disponible en la que pueda entrar el programa.Esta estrategia es mas rápida pero se desperdicia mucho espacio de memoria. Consiste en asignar la partición en la que sobra mas espacio. Almacenamiento de Memoria Virtual.- Las direcciones de memoria no están necesariamente contenidas en elalmacenamiento real. El S.O. se apoya en el almacenamiento secundario paraextender el uso de la memoria. Las direcciones referidas por los procesos son direcciones virtuales. Losprocesos no tienen por que saber en que posición de almacenamiento real osecundario están almacenados. Las direcciones de memoria que direcciones dememoria que referencian al almacenamiento primario (memoria real) se denominan"direcciones reales". Por mas que los procesos hagan referencia adirecciones virtuales, estos solo pueden ejecutar en el almacenamiento primario;por lo tanto las direcciones virtuales deben ser transformadas en direccionesreales mientras el proceso esta en ejecución. Como el almacenamiento real es compartible por varios procesos solo semantiene al mismo tiempo una pequeña parte de cada uno de ellos en memoriareal. El mecanismo de traducción de direcciones deberá mantener mapas queilustren que direcciones del almacenamiento virtual se encuentran en memoriareal, y donde se encuentran. La información se agrupa en bloques y el sistema operativo debe estarinformado del lugar en que se encuentra almacenada cada página). bloque. Cuando los bloques son del mismo tamaño se denominan páginasy el mecanismo de administración del almacenamiento virtual asociado sedenomina paginación. Si los bloques son e tamaño variable se denominan segmentos y elmecanismo de administración del almacenamiento virtual segmentación. Las direcciones en un esquema de almacenamiento virtual son un par (b,d)donde b indica el bloque y d el desplazamiento desde el inicio del bloque. Las direcciones en un sistema de paginación están dadas por:
Desplazamiento Página Las páginas se transfieren del almacenamiento secundario al primario enbloque llamados page frames (los cuales tienen el mismo tamaño de las páginas). El sistema lleva una tabla de páginas para cada proceso. De esta forma seasegura la protección. Cuando un proceso debe ser cargado en memoria par ejecutar se siguendeterminados pasos:
Como la tabla de páginas de cada proceso puede llegar a tornarse demasiadogrande, se buscan mecanismos que permiten acelerar el tiempo de búsqueda en esainformación. La solución mas simple es la utilización de un conjunto deregistros dedicados (no usar tabla de paginación de cada proceso). El CPUdispatcher será el encargado de cargar y actualizar la información de estosregistros con cada context switch. Esta solución sería razonable si se hablarade pocos registros pero en la realidad no se utiliza. La solución mas común es apoyarse en un cache de acceso muy rápido llamadoTLB (Translation Location Buffer). La TLB solo puede contener algunas entradasde la tabla de páginas. Con cada context switch la TLB debe ser variada paraevitar que un proceso haga referencia a direcciones de memoria utilizadas porotro proceso (protección). Si se hace referencia a una dirección que no estabacargada en TLB, se debe cargar en esta, eliminando alguna otra dirección sifuera necesario. Por la forma en que se construyen las tablas de página los procesos solo vana hacer referencia a direcciones de su espacio virtual. La protección seimplementa por un conjunto de bits que son asociados a cada frame. Un bit puededefinir si una página es read-only o read-write y cada vez que se hace unaoperación sobre un page frame se verifica sobre estos bits. En algunos sistemas se busca minimizar el tiempo de búsqueda en la tabla depáginas utilizando un sistema de paginación de 2 niveles. Una dirección es de la forma: (P1,P2,d) donde P1 y P2 corresponde al númerode página y d al desplazamiento. Se lleva una tabla de páginas para todos los procesos. Cada entrada de páginacontiene la siguiente información: <process-id, nro. Pagina,desplazamiento> Es posible que los procesos compartan código común (reentrante) El códigocomún no podrá ser modificado durante su ejecución, por lo cual se deberánproteger mediante los bits de protección. En un esquema de segmentación un espacio de direcciones lógicas es unconjunto de segmentos. Cada segmento tendrá un nombre y un largo. Lasdirecciones van a hacer referencia tanto al nombre como al desplazamiento dentrodel segmento. <nro.segmento, desplazamiento> Mecanismo de traduccion de direcciones.- Se lleva un tabla de segmento por cada proceso, cada entrada a la tabla desegmento lleva la siguiente informacion: segment base (dirección base delsegmento) segment limit (largo del segmento) La protección se asegura verificando cada acceso a la memoria con la tablade segmentos para asegurar que se esta direccionando dentro del espacio dedirecciones lógicas del proceso. Además el mecanismo de traducción de direcciones asegura que no sedireccione fuera de un segmento en particular. Existen también bits de protecciónpara cada entrada de la tabla de segmentos que indicaran si el segmento es readonly o read-write. Similar a lo visto para paginación. Se comparte la totalidad de un segmento El sistema operativo deberá asignar memoria utilizando algunos algoritmos yavistos (first fit, worst fit, best fit) Cuando el sistema operativo intentacargar un segmento y no hay ningún segmento disponible de tamaño suficientepara almacenarlo se procederá a compactar la memoria. Es similar a lo visto para la paginación introduciendo el concepto deswapping. Los procesos residen en el disco y al ser ejecutados deben sercargados en memoria. Cuando un proceso va a ser ejecutado, el mismo es swappeadoa memoria, utilizando lazy swapping. El lazy swapping nunca trae paginas amemoria si no van a ser ejecutadas. Se necesita determinar si un pagina esta enmemoria o en disco, por lo cual se utiliza el bit de válido / inválido de latabla de páginas. Si el bit = 1 la página es valida y esta cargada en memoriasi es 0 la página es inválida y no esta cargada en memoria (esta en disco). Cuando un proceso intenta acceder a una página que no esta cargada enmemoria ocurre un page fault (tomo de página). El procedimiento paramanejar un page fault es el siguiente:
Si al momento de generarse un page fault no hubiera ningún frame disponible,se debe proceder a reemplazar una pagina de memoria. LA rutina de page faultdebe ser modificada para incluir reemplazo de páginas:
Algoritmos de remplazo de página.- Asocia a cada página el tiempo en que fue cargada en memoria. Cuando debereemplazar una página, se selecciona la que hace mas tiempo que esta enmemoria. También se puede implementar mediante la utilización de una lista. Sereemplazan las páginas de la cabeza y se agregan al final. Se selecciona la página que hace mas tiempo que no se utiliza. Asocia cada páginael tiempo de la última vez que fue utilizada. En LRU se necesita llevar tiempode última utilización de cada página: Contadores: Se asocia a cada entrada en la tabla de páginas, el tiempode la última vez que se uso. Cada vez que se accede a una página se actualizael contador. Stack: Se lleva un stack con los números de página cada vez que una páginaes accedida, se quita del stack y se quita al tope. En el tope del stack estarála página que fue utilizada por última vez, y en el fondo la página que hacemas tiempo que no se accede. Es una variante del algoritmo FIFO. Cada vez que se selecciona una página,se inspecciona un bit de referencia. Si el valor es cero se procede a reemplazarla página. Si el valor es uno, se da una segunda oportunidad a la página y seselecciona la siguiente víctima por criterio FIFO. Cada vez que una páginarecibe una segunda oportunidad, se carga en ceo el bit de referencia. Si una páginavuelve a ser accedida, se incrementa el bit de referencia a uno. Establece que la página con menos cantidad de referencias debe serreemplazado. Una contra del algoritmo es que una página puede haber sido muyutilizada en la fase de carga de un proceso, pero no ser vuelta a utilizar, porlo cual se estaría manteniendo en memoria páginas que no son necesarias parala ejecución. La pagina con mayor cantidad de referencias es la víctima a ser reemplazada.El argumento es que si una pagina fue utilizada pocas veces, se debe a que reciénfue cargada en memoria y aún deba ser utilizada. Se lleva un pool de frames disponibles. Cuando ocurre un page fault se eligeuna víctima utilizando alguno de los mecanismos ya vistos (anteriores). Enlugar de hacer el cambio de frame en una sola operación se carga la pagina enmemoria en uno de los frames disponibles (pool) permitiendo que el procesoretome su ejecución. El S. O. Se encargará luego de descargar la página yagregarla al pool de frames disponibles (es decir que agrego a la lista depaginas del pool la página liberada en memoria) Cuando un proceso consume mas tiempo paginando que ejecutando se dice que elproceso esta en situación de trash. Una forma de evitar esta situación esutilizar un mecanismo de reemplazo de paginas "local". Cuando unproceso comienza a paginar, no puede robar frames de otros procesos solamentepodrá reemplazar páginas de su propio proceso. Es el conjunto de la páginas activas de un proceso que son almacenadas enmemoria. Se define un número n por proceso. Las n páginas más activas delproceso son mantenidas en memoria. Se controla el page fault rate de cada proceso. Si un proceso tiene pagefault rate muy bajo probablemente se deba a que este utilizando demasiadosframes en memoria. Si el page fault rate es muy alto, probablemente no tengasufiecientes frames otorgados. La idea de esta técnica es definir limitesuperior e inferior para page fault. Es una estrategia para evitar el alto nivel de paginación inicial, consisteen cargar en memoria de una vez todas las páginas que el proceso necesite. Un proceso no necesita tener todos los segmentos cargados en memoria paraejecutar. Solamente se deben cargar en memoria aquellos que estén siendoactivamente utilizados. La tabla de segmentos mantiene un bit de validez (idempaginación por demanda) para indicar si un segmento esta en memoria o en disco.Cada vez que se direcciona un segmento se chequea el bit de validez. Si elsegmento no esta cargado en memoria se produce un segmento fault. Una vezdetectada la necesidad de un segment fault, se utiliza la siguiente técnica:
Atributos : nombre, tipo, tamaño,protección (información de control de acceso asociado), fecha y hora de creación,fecha y hora de modificación, usuario propietario.Operaciones sobre archivos:
Para minimizar los tiempos de búsqueda en la estructura de directorios sesuele llevar una tabla de archivos abiertos. La primera vez que un archivo esreferenciado se agrega su referencia a esta tabla. Cuando los archivos dejan deser utilizados se procede a cerrarlos eliminándolos de la tabla. Todos los archivos son contenidos en un único directorio, lo cual hace quela búsqueda sea muy fácil pero no se pueden repetir los nombres de archivos. Cada usuario va a tener un single level directory lo cual soluciona elproblema de los nombres. Estos directorios de cada usuario se llaman UFD (UserFile Directory). Se mantiene un directorio MFD (Master File Directory) el cualindica dado un usuario que directorios posee. El problema de esta estructura esque no permite los archivos compartidos. Esta es la estructura más común. Existe un directorio raíz que contiene unconjunto de archivos y subdirectorios. Hay un bit en la estructura dedirectorios que indica si una entrada es un archivo o un subdirectorio. Si un archivo puede estar referenciado por dos o mas entradas de undirectorio el sistema operativo deberá proveer mecanismos que eviten procesarmas de una vez la información en operación que recorren la estructura dedirectorios. El sistema operativo debe llevar una lista de referencias de losarchivos (file reference list) para poder determinar en que momento se debeliberar el espacio ocupado al borrar un archivo. Los algoritmos de búsqueda en la estructura de directorios deben contemplarla posibilidad de entrar en loop infinito. Implementación de File Systems.- Método de Asignación Contigua.- Cada vez que se crea un archivo el mismo es almacenado en disco en formacontigua (conjuntos de bloques contiguos en disco). Simplifica los mecanismos deacceso a la información del archivo. La estructura de directorios sería:
Los archivos no se pueden extender, se les asigna el disco cuando se crea conun tamaño que se cree conveniente, por mas que los cálculos sean buenos, sepuede llegar a desperdiciar espacio. La dificultad es que no siempre se tiene la información del espacio quehalla e ocupar un archivo al momento de su creación. Cada archivo en un conjunto de bloques encadenados que pueden estardistribuidos en cualquier lugar del disco. Los archivos pueden crecer librementesiempre que haya espacio en sico. Para encontrar el bloque i-ésimo es necesarioi bloques en memoria para poder seguir la cadena. Variante: Tabla FAT (Ms-DOS) Cada archivo mantiene un bloque que indica en donde se almacena los puentes atodos los bloques ocupados por el archivo. Un archivo puede crecer libremente yen la búsqueda es más rápido. Soluciona los problemas de la asignacióncontinua (los archivos pueden crecer libremente mientras haya espacio en disco yespacio en el archivo de índices). El problema de este método es que se puedeproducir pérdida de espacio ya que cada archivo por chico que sea tiene unbloque índice. Por otro lado existe un límite para el tamaño de un archivodado por la cantidad de índices. La ventaja del método es la velocidad en elacceso a la información en el archivo. La lista de espacio libre (Free Sapce List), que lleva información de todoslos bloques de disco que no estén siendo ocupados por ningún archivo odirectorio. Cada vez que un archivo es creado, el sistema operativo recorre estalista asignando los bloques necesarios. Implementación de la lista de espacio libre.- La lista de espacio libre es llevada como un vector de bits, donde 1 indicaque el bloque esta ocupado y 0 indica un bloque libre. Es simple encontrar cuales el primer bloque disponible, o n bloque consecutivo. El problema es que la técnicadeja de ser eficiente a menos que el vector sea cargado en memoria principal, loque puede ser un problema. Llevar una estructura de lista donde estén encadenadas la información detodos los bloques libres en disco. Se lleva en memoria un puntero al primerbloque libre. Esta técnica no es eficiente para asignación contigua Implementación de Directorios.- Consiste en llevar una lista de nombres de archivos con punteros a losbloques de datos. La búsqueda de esta implementación consume considerabletiempo cada vez que se referencia a un archivo, debe recorrerse toda laestructura de la lista. Consiste en llevar una estructura de hash para representar la información dedirectorio. El principal problema de esta implementación es fijar el largo dela tabla de hash. Si la tabla es muy grande (como es un vector) la búsqueda es rápida pero sedesperdicia mucho espacio. Si la tabla es chica los tiempos de búsqueda casicomo los de la lista encadenada. Estructura del Almacenamiento Secundario.- Las direcciones en disco son referidas como una dirección compuesta, dondese incluye el numero de dispositivo, la cara, la pista y el sector. El conjuntode sectores que pueden ser leídos sin que se muevan las cabezas del disco sedenominan cilindro. El sector es la menor unidad que puede ser leída o escritade un disco. Los tiempos involucrados en una operación de E/S son:
Mientras el disco esta resolviendo una solicitud, las solicitudes adicionalesserán encoladas en cola de E/S. Existen algoritmos para resolver maseficientemente el problema de cómo ordenar la cola de E/S. Algoritmos de Selección de Cola de I/O.- FCFS (First Come Firs Served).- Se accede a las direcciones en el disco de la misma forma en que fueronentrando. SSJF (Shortest Seek Time First).- La idea es servir juntos todos los requerimientos que estén cerca de laposición actual de la cabeza del disco. Los requerimientos que están muyapartados de la posición de la cabeza no van a ser tomados en cuenta nunca (lacola es dinámica, siempre están llegando requerimientos). Es decir que puedenhaber requerimientos que no sean satisfechos nunca o que sean postergadosindefinidamente. Propone resolver todos los requerimientos en el sentido en que se estamoviendo la cabeza del disco hasta llegar a su extremo o a que no hayrequerimientos para resolver en ese sentido, en cuyo caso comienza a resolver ensentido contrario. Similar al anterior pero los requerimientos se resuelven siempre en el mismosentido. Si no hay mas requerimientos para satisfacer en ese sentido o se llegóal extremos del disco se salta al comienzo del mismo y se continúa resolviendo. Consiste en escribir un conjunto de sectores en el disco en cada pista quelas cabezas puedan leer. Cada uno de estos sectores contiene el numero desector, información de ECC (error Correctin Code) el cual permite identificarerrores en la lectura de un sector del disco. Cada vez que se escribe un sectorse calcula un valor aplicando una formula a todos los bytes del sector y sealmacena en este. Al momento de leer el sector, se recalcula el valor y secompara con el valor guardado. Si son distinto el sector puede estar dañado yel sistema operativo puede decidir marcarlo como malo. (bad blocks). Inicializa la información del file systems: directorio vacío, informaciónde i-nodos, fat, etc, free space list, etc. El espacio de swap puede ser utilizado de diferentes maneras dependiendo delsistema operativo en cuestión. El espacio de swap puede residir en el filesystem o en una partición separada. Si es un archivo mas las primitivasnormales del file system se utilizan para crearlo, asignarle espacio,escribirlo, etc. Compite con los demás requerimientos de E/S del file system. Lo mas común es almacenar el espacio de swap en una partición separadadonde no se coloque ningun file sstem ni estructura de directorios (rawdevices). Se utilizan algoritmos de gerenciamiento del espacio de swap paraasignar y desasignar bloques. La ventaja es la velocidad ya que se evitan lasprimitivas de E/S del file system y no se compite con la cola de E/S deldispositivo. Refiere a los mecanismo para controlar el acceso de programas, usuarios oproceso a los recursos definido en el sistema. Un sistema es un conjunto derecursos (CPU, memoria, impresoras, etc.) en donde cada objeto o recurso tieneun nombre único. Las operaciones que se pueden hacer sobre cada objeto dependendel objeto. Cada proceso opera dentro de su dominio de protección, que indica lasoperaciones que el proceso puede hacer sobre un determinado conjunto de objetos.La habilidad de un proceso de ejecutar una operación sobre un objeto sedenomina derecho (acces right). Un dominio es un conjunto de derechos cada unode los cuales es un par ordenado <objeto, lista de derechos> Un dominio puede estar definido de varias formas: Un usuario es un dominio. El conjunto de objetos que pueden ser accedidosdependen de la identidad del usuario. Un proceso es un domino. El conjunto de objetos que pueden ser accedidosdependen de la identidad del proceso. Un procedimiento es un dominio. El modelo de protección puede ser visto mediante una matriz de acceso. Lasfilas representan dominios y las columnas representan objetos. Las entradas dela matriz representan el conjunto de derechos para el objeto en cuestión, paradeterminado dominio.
Trabajo enviado por: Marcelo Bendahan
Articulos relacionados:
|
|
Copyright © 2011 ilustrados.com, Monografias, tesis, bibliografias, educacion. Tofos los temas y publicaciones son propiedad de sus respectivos autores ©