Notas de última hora: sistemas operativos

Ver notas de última hora para todos los temas todos los temas aquí .

Sistemas Operativos: Es la interfaz entre el usuario y el hardware de la computadora.

Tipos de Sistema Operativo (SO):

1. Sistema operativo por lotes: un conjunto de trabajos similares se almacenan en la memoria principal para su ejecución. Un trabajo se asigna a la CPU, solo cuando se completa la ejecución del trabajo anterior.
2. Sistema operativo multiprogramación: la memoria principal consiste en trabajos que esperan el tiempo de la CPU. El sistema operativo selecciona uno de los procesos y lo asigna a la CPU. Cada vez que el proceso de ejecución necesita esperar por cualquier otra operación (como E/S), el sistema operativo selecciona otro proceso de la cola de trabajos y lo asigna a la CPU. De esta manera, la CPU nunca se mantiene inactiva y el usuario tiene la sensación de realizar múltiples tareas a la vez.
3. Sistema operativo multitarea: el sistema operativo multitarea combina los beneficios del sistema operativo multiprogramación y la programación de la CPU para realizar cambios rápidos entre trabajos. El cambio es tan rápido que el usuario puede interactuar con cada programa mientras se ejecuta
4. Sistema operativo de tiempo compartido: los sistemas de tiempo compartido requieren interacción con el usuario para indicarle al sistema operativo que realice varias tareas. El sistema operativo responde con una salida. Las instrucciones generalmente se dan a través de un dispositivo de entrada como el teclado.
5. Sistema operativo en tiempo real: el sistema operativo en tiempo real generalmente se crea para sistemas dedicados para realizar un conjunto específico de tareas dentro de los plazos.

Subprocesos:
un subproceso es un proceso ligero y forma la unidad básica de utilización de la CPU. Un proceso puede realizar más de una tarea al mismo tiempo al incluir varios subprocesos.

• Un hilo tiene su propio contador de programa, conjunto de registros y pila.
• Un hilo comparte recursos con otros hilos del mismo proceso, la sección de código, la sección de datos, archivos y señales.

Se puede introducir un nuevo subproceso, o un proceso secundario de un proceso determinado, utilizando la llamada al sistema fork(). Un proceso con n llamadas al sistema fork() genera 2 ⁿ – 1 procesos secundarios.
Hay dos tipos de hilos:

• Hilos de usuario
• Subprocesos del núcleo

Ejemplo: subproceso Java, subprocesos POSIX. Ejemplo: Windows Solaris.

Hilo de nivel de usuario	Subproceso de nivel de kernel
Los subprocesos de usuario son implementados por los usuarios.	Los subprocesos del núcleo son implementados por el sistema operativo.
El sistema operativo no reconoce los subprocesos de nivel de usuario.	Los subprocesos del kernel son reconocidos por el sistema operativo.
La implementación de subprocesos de usuario es fácil.	La implementación del hilo del Kernel es complicada.
El tiempo de cambio de contexto es menor.	El tiempo de cambio de contexto es más.
El cambio de contexto no requiere soporte de hardware.	Se necesita soporte de hardware.
Si un subproceso de nivel de usuario realiza una operación de bloqueo, se bloqueará todo el proceso.	Si un subproceso del kernel realiza una operación de bloqueo, otro subproceso puede continuar con la ejecución.

 
Proceso:
Un proceso es un programa en ejecución. El valor del contador de programa (PC) indica la dirección de la siguiente instrucción del proceso que se está ejecutando. Cada proceso está representado por un Bloque de Control de Procesos (PCB).

Programación de Procesos: A continuación se muestran diferentes tiempos con respecto a un proceso.

1. Hora de llegada: hora a la que el proceso llega a la cola de espera.
2. Hora de finalización: hora en la que el proceso completa su ejecución.
3. Tiempo de ráfaga: tiempo requerido por un proceso para la ejecución de la CPU.
4. Tiempo de vuelta: diferencia de tiempo entre el tiempo de finalización y el tiempo de llegada.

   Turn Around Time = Completion Time - Arrival Time 

5. Tiempo de espera (WT): diferencia de tiempo entre el tiempo de respuesta y el tiempo de ráfaga.

   Waiting Time = Turn Around Time - Burst Time 

¿Por qué necesitamos programar?
Un proceso típico implica tiempo de E/S y tiempo de CPU. En un sistema de uniprogramación como MS-DOS, el tiempo de espera de E/S se desperdicia y la CPU está libre durante este tiempo. En los sistemas de multiprogramación, un proceso puede usar la CPU mientras otro está esperando E/S. Esto solo es posible con la programación de procesos.

Objetivos del algoritmo de programación de procesos:

• Utilización máxima de la CPU (mantenga la CPU lo más ocupada posible)
• Asignación justa de CPU.
• Max throughput (Número de procesos que completan su ejecución por unidad de tiempo)
• Tiempo de respuesta mínimo (Tiempo que tarda un proceso en finalizar la ejecución)
• Tiempo de espera mínimo (Tiempo que un proceso espera en la cola de espera)
• Tiempo de respuesta mínimo (Tiempo en que un proceso produce la primera respuesta)

Diferentes algoritmos de programación:

1. First Come First Serve (FCFS) : el algoritmo de programación más simple que programa de acuerdo con los tiempos de llegada de los procesos.
2. El trabajo más corto primero (SJF) : los procesos que tienen el tiempo de ráfaga más corto se programan primero.
3. El tiempo restante más corto primero (SRTF) : es el modo preventivo del algoritmo SJF en el que los trabajos se programan de acuerdo con el tiempo restante más corto.
4. Programación Round Robin (RR) : A cada proceso se le asigna un tiempo fijo, en forma cíclica.
5. Programación basada en prioridades (no preventiva) : en esta programación, los procesos se programan de acuerdo con sus prioridades, es decir, el proceso de mayor prioridad se programa primero. Si las prioridades de dos procesos coinciden, la programación se realiza de acuerdo con la hora de llegada.
6. Tasa de respuesta más alta siguiente (HRRN) : en esta programación, se programan los procesos con la tasa de respuesta más alta. Este algoritmo evita la inanición.

   Response Ratio = (Waiting Time + Burst time) / Burst time

7. Programación de colas multinivel (MLQ) : de acuerdo con la prioridad del proceso, los procesos se colocan en las diferentes colas. Generalmente, los procesos de alta prioridad se colocan en la cola de nivel superior. Solo después de completar los procesos de la cola de nivel superior, se programan los procesos en cola de nivel inferior.
8. Programación de cola de retroalimentación de niveles múltiples (MLFQ) : permite que el proceso se mueva entre colas. La idea es separar los procesos según las características de sus ráfagas de CPU. Si un proceso usa demasiado tiempo de CPU, se mueve a una cola de menor prioridad.

Algunos datos útiles sobre los algoritmos de programación:

1. FCFS puede causar largos tiempos de espera, especialmente cuando el primer trabajo requiere demasiado tiempo de CPU.
2. Tanto SJF como el algoritmo de tiempo restante más corto primero pueden causar inanición. Considere una situación en la que hay un proceso largo en la cola lista y siguen llegando procesos más cortos.
3. Si la cantidad de tiempo para la programación Round Robin es muy grande, entonces se comporta igual que la programación FCFS.
4. SJF es óptimo en términos de tiempo de espera promedio para un conjunto dado de procesos. SJF proporciona un tiempo de espera promedio mínimo, pero el problema con SJF es cómo saber/predecir el tiempo del próximo trabajo.

El problema de la sección crítica:

1. Sección crítica: la parte del código en el programa donde se accede y/o se actualizan las variables compartidas.
2. Sección restante: la parte restante del programa, excluyendo la sección crítica.
3. Race around Condition: el resultado final del código depende del orden en que se accede a las variables. Esto se denomina como la carrera alrededor de la condición.

Una solución para el problema de la sección crítica debe satisfacer las siguientes tres condiciones:

1. Exclusión mutua: si un proceso Pi se está ejecutando en su sección crítica, ningún otro proceso puede ingresar a la sección crítica.
2. Progreso: si no se ejecuta ningún proceso en la sección crítica, ningún otro proceso que se esté ejecutando en su sección restante puede tomar la decisión de ingresar a una sección crítica. La selección del proceso no puede posponerse indefinidamente.
3. Espera limitada: existe un límite en la cantidad de veces que otros procesos pueden ingresar a la sección crítica después de que un proceso haya realizado una solicitud para acceder a la sección crítica y antes de que se conceda la solicitud.

 
Herramientas de sincronización:
un semáforo es una variable entera a la que se accede solo a través de dos operaciones atómicas, espera() y señal(). Una operación atómica se ejecuta en un solo intervalo de tiempo de la CPU sin ninguna preferencia. Los semáforos son de dos tipos:

1. Semáforo de conteo: un semáforo de conteo es una variable entera cuyo valor puede variar en un dominio sin restricciones.
2. Mutex: un mutex proporciona exclusión mutua, tanto el productor como el consumidor pueden tener la clave (mutex) y continuar con su trabajo. Mientras el productor llene el búfer, el consumidor debe esperar, y viceversa.

   En cualquier momento, solo un subproceso puede trabajar con todo el búfer. El concepto se puede generalizar usando semáforo.

   Concepto erróneo:
   existe una ambigüedad entre el semáforo binario y la exclusión mutua. Es posible que nos hayamos encontrado con que un mutex es un semáforo binario. ¡Pero no lo son! El propósito de mutex y semáforo es diferente. Puede ser, debido a la similitud en su implementación, un mutex se denominaría semáforo binario.

Interbloqueo :
una situación en la que un conjunto de procesos está bloqueado porque cada proceso está reteniendo un recurso y esperando otro recurso adquirido por algún otro proceso. Puede surgir un interbloqueo si las siguientes cuatro condiciones se cumplen simultáneamente (condiciones necesarias):

1. Exclusión mutua: uno o más de un recurso no se pueden compartir (solo se puede usar un proceso a la vez).
2. Retener y esperar: un proceso está reteniendo al menos un recurso y esperando recursos.
3. Sin preferencia: un recurso no se puede tomar de un proceso a menos que el proceso libere el recurso.
4. Espera circular: un conjunto de procesos se esperan unos a otros en forma circular.

Métodos para manejar interbloqueos: Hay tres formas de manejar interbloqueos

1. Prevención o evitación de interbloqueos: la idea es no permitir que el sistema entre en un estado de interbloqueo.
2. Detección y recuperación de interbloqueos: Deje que ocurra un interbloqueo, luego haga una preferencia para manejarlo una vez que ocurra.
3. Ignore el problema por completo : si el interbloqueo es muy raro, deje que suceda y reinicie el sistema. Este es el enfoque que adoptan tanto Windows como UNIX.

Algoritmo del banquero:
este algoritmo maneja múltiples instancias del mismo recurso.

Gestión de memoria:
estas técnicas permiten que la memoria se comparta entre múltiples procesos.

• Superposiciones: la memoria debe contener solo aquellas instrucciones y datos que se requieren en un momento dado.
• Intercambio: en la multiprogramación, las instrucciones que han utilizado el intervalo de tiempo se intercambian fuera de la memoria.

Técnicas de gestión de la memoria:

(a) Esquemas de asignación de partición única:
la memoria se divide en dos partes. Una parte se guarda para que la use el sistema operativo y la otra para que la usen los usuarios.

(b) Esquemas de Partición Múltiple –

1. Partición fija: la memoria se divide en particiones de tamaño fijo.
2. Partición variable: la memoria se divide en particiones de tamaño variable.

Esquemas de asignación de partición variable:

1. First Fit: al proceso que llega se le asigna el primer hueco de la memoria en el que encaja por completo.
2. Mejor ajuste: al proceso que llega se le asigna el hueco de la memoria en el que encaja mejor dejando la memoria mínima vacía.
3. Peor ajuste: al proceso que llega se le asigna el hueco de la memoria en el que deja el espacio máximo.

Nota:

• El mejor ajuste no da necesariamente los mejores resultados para la asignación de memoria.
• La causa de la fragmentación externa es la condición en el particionamiento fijo y el particionamiento variable que dice que todo el proceso debe asignarse en una ubicación de memoria contigua . Por lo tanto, se utiliza la paginación .

1. Paginación:
   la memoria física se divide en marcos de igual tamaño. La memoria principal se divide en páginas de tamaño fijo. El tamaño de un marco de memoria física es igual al tamaño de un marco de memoria virtual.
2. Segmentación:
   la segmentación se implementa para dar a los usuarios una vista de la memoria. El espacio de direcciones lógicas es una colección de segmentos. La segmentación se puede implementar con o sin el uso de paginación.

Falla de página:

una falla de página es un tipo de interrupción, provocada por el hardware cuando un programa en ejecución accede a una página de memoria que está asignada al espacio de direcciones virtuales, pero no cargada en la memoria física.

Algoritmos de reemplazo de página:

1. Primero en entrar, primero en salir (FIFO):
   este es el algoritmo de reemplazo de página más simple. En este algoritmo, el sistema operativo realiza un seguimiento de todas las páginas en la memoria en una cola, la página más antigua está al frente de la cola. Cuando es necesario reemplazar una página, se selecciona la página que está al frente de la cola para eliminarla.

   Por ejemplo, considere la string de referencia de página 1, 3, 0, 3, 5, 6 y 3 ranuras de página. Inicialmente, todos los espacios están vacíos, por lo que cuando aparecen 1, 3, 0, se asignan a los espacios vacíos -> 3 fallas de página. Cuando llega 3, ya está en la memoria, así que —> 0 Fallos de página. Luego viene 5, no está disponible en la memoria, por lo que reemplaza la ranura de página más antigua, es decir, 1. —> 1 Fallo de página. Finalmente, viene 6, que tampoco está disponible en la memoria, por lo que reemplaza la ranura de página más antigua, es decir, 3 —> 1 Fallo de página.

   Anomalía de Belady :
   la anomalía de Belady demuestra que es posible tener más fallas de página al aumentar el número de marcos de página mientras se usa el algoritmo de reemplazo de página Primero en entrar, primero en salir (FIFO). Por ejemplo, si consideramos la string de referencia 3 2 1 0 3 2 4 3 2 1 0 4 y 3 ranuras, obtenemos 9 fallas de página en total, pero si aumentamos las ranuras a 4, obtenemos 10 fallas de página.

2. Reemplazo óptimo de página:
   en este algoritmo, se reemplazan las páginas que no se usarán durante la mayor cantidad de tiempo en el futuro.

   Consideremos la string de referencia de página 7 0 1 2 0 3 0 4 2 3 0 3 2 y 4 ranuras de página. Inicialmente, todas las ranuras están vacías, por lo que cuando se asignan 7 0 1 2 a las ranuras vacías —> 4 fallas de página. 0 ya está allí, así que —> 0 Error de página. Cuando llegue el 3, ocupará el lugar del 7 porque no se usará durante mucho tiempo en el futuro.—> 1 Error de página. 0 ya está allí, así que —> 0 Error de página. 4 tendrá lugar de 1 —> 1 Fallo de página. Ahora, para la siguiente string de referencia de página —> 0 Error de página porque ya están disponibles en la memoria.

   El reemplazo de página óptimo es perfecto, pero no es posible en la práctica ya que un sistema operativo no puede conocer las requests futuras. El uso del reemplazo de página óptimo es establecer un punto de referencia para que otros algoritmos de reemplazo puedan analizarse en comparación con él.

3. Usado menos recientemente (LRU):
   en este algoritmo, se reemplazará la página que se usó menos recientemente.

   Digamos la string de referencia de la página 7 0 1 2 0 3 0 4 2 3 0 3 2 . Inicialmente, tenemos espacios de 4 páginas vacíos. Inicialmente, todas las ranuras están vacías, por lo que cuando se asignan 7 0 1 2 a las ranuras vacías —> 4 fallas de página. 0 ya es su so —> 0 Error de página. Cuando llegó el 3, ocupará el lugar del 7 porque es el que se usó menos recientemente —> 1 Error de página. 0 ya está en la memoria por lo que —> 0 Error de página. 4 tendrá lugar de 1 —> 1 Fallo de página. Ahora, para la siguiente string de referencia de página —> 0 Error de página porque ya están disponibles en la memoria.

    
    

   Sistema de archivos : un archivo es una colección de información relacionada que se registra en un almacenamiento secundario. O archivo es una colección de entidades relacionadas lógicamente.

   Directorios de archivos: la colección de archivos es un directorio de archivos. El directorio contiene información sobre los archivos, incluidos los atributos, la ubicación y la propiedad. Gran parte de esta información, especialmente la relacionada con el almacenamiento, es administrada por el sistema operativo.

   1. DIRECTORIO DE NIVEL ÚNICO : En este se mantiene un directorio único para todos los usuarios
   2. DIRECTORIO DE DOS NIVELES : debido a los dos niveles, hay un nombre de ruta para cada archivo para ubicar ese archivo.
   3. DIRECTORIO ESTRUCTURADO EN ÁRBOL : El directorio se mantiene en forma de árbol. La búsqueda es eficiente y también hay capacidad de agrupación.

    

   Métodos de asignación de archivos :

   1. Asignación continua : un único conjunto continuo de bloques se asigna a un archivo en el momento de la creación del archivo.
   2. Asignación vinculada (asignación no contigua) : la asignación se realiza por bloques individuales. Cada bloque contiene un puntero al siguiente bloque de la string.
   3. Asignación indexada : Aborda muchos de los problemas de la asignación contigua y enstringda. En este caso, la tabla de asignación de archivos contiene un índice de un nivel separado para cada archivo.

    

   Programación de discos :
   los sistemas operativos realizan la programación de discos para programar las requests de E/S que llegan al disco. La programación de discos también se conoce como programación de E/S.

   1. Tiempo de búsqueda: el tiempo de búsqueda es el tiempo necesario para ubicar el brazo del disco en una pista específica donde se leerán o escribirán los datos.
   2. Latencia de rotación: La latencia de rotación es el tiempo que tarda el sector deseado del disco en girar a una posición que le permita acceder a los cabezales de lectura/escritura.
   3. Tiempo de transferencia: el tiempo de transferencia es el tiempo para transferir los datos. Depende de la velocidad de rotación del disco y del número de bytes a transferir.
   4. Tiempo de acceso al disco: tiempo de búsqueda + latencia de rotación + tiempo de transferencia
   5. Tiempo de respuesta del disco: el tiempo de respuesta es el promedio de tiempo que una solicitud tarda en esperar para realizar su operación de E/S. El tiempo de respuesta promedio es el tiempo de respuesta de todas las requests.

    

   Algoritmos de programación de disco :

   1. FCFS: FCFS es el más simple de todos los algoritmos de programación de disco. En FCFS, las requests se abordan en el orden en que llegan a la cola del disco.
   2. SSTF: en SSTF (tiempo de búsqueda más corto primero), las requests que tienen el tiempo de búsqueda más corto se ejecutan primero. Por lo tanto, el tiempo de búsqueda de cada solicitud se calcula de antemano en una cola y luego se programan de acuerdo con su tiempo de búsqueda calculado. Como resultado, la solicitud cerca del brazo del disco se ejecutará primero.
   3. SCAN: en el algoritmo SCAN, el brazo del disco se mueve en una dirección particular y atiende las requests que llegan en su camino y, después de llegar al final del disco, invierte su dirección y nuevamente atiende la solicitud que llega en su camino. Entonces, este algoritmo funciona como un ascensor y, por lo tanto, también se conoce como algoritmo de ascensor.
   4. CSCAN: En el algoritmo SCAN, el brazo del disco vuelve a escanear la ruta que ha sido escaneada, después de invertir su dirección. Por lo tanto, es posible que haya demasiadas requests en espera en el otro extremo o que haya cero o pocas requests pendientes en el área escaneada.
   5. MIRAR: Es similar al algoritmo de programación de disco SCAN, excepto por la diferencia de que el brazo del disco, a pesar de ir al final del disco, va solo a la última solicitud para ser atendida frente al cabezal y luego invierte su dirección desde allí. solamente. Por lo tanto, evita el retraso adicional que se produjo debido a un recorrido innecesario hasta el final del disco.
   6. CLOOK: Como LOOK es similar al algoritmo SCAN, CLOOK es similar al algoritmo de programación de disco CSCAN. En CLOOK, el brazo del disco, a pesar de ir al final, va solo a la última solicitud a atender frente al cabezal y luego de allí va a la última solicitud del otro extremo. Por lo tanto, también evita el retraso adicional que se produjo debido a un recorrido innecesario hasta el final del disco.