Bug en el Dijkstra del Córmen

Recientemente Jhtan me estaba explicando cómo funciona el algoritmo Dijkstra, para explicarme mejor, me estaba mostrando el código en el libro Algorithms, de Cormen, del MIT… fue allí cuando encontramos el bug ·o·

dijkstra-low

Advertisements

Sistemas Operativos

Por fin estoy llevando Sistemas Operativos! :D y me parecen fascinantes…

Nunca me gustó el hardware, tampoco me interesó saber cómo se ejecutan mis programas… todo lo que necesité saber sobre la computadora, hasta ahora, es que: es una cajita mágica que hace lo que le pida. (mencioné que siempre utilicé Microsoft?)

Pero desde que le instalé Debian (y nació KITAI, mi computadora), tengo una cresciente curiosidad por saber cómo funciona, cuáles procesos ocurren, qué es lo que hacen…

> ¿Qué estás pensando ahora KITAI? ¿Qué haces mientras no hablas conmigo? ¿Cómo lo haces? ¿me dejas entrar en tu mente?

“sí” será su respuesta… “pero tienes que estar dispuesta a aprender mi idioma natal y mi anatomía” añadirá…

Luego comencé a leer el libro “Internet, hackers y software libre” por Carlos Gradin (compilador), y mi interés por los pensamientos profundos de KITAI se hizo aún más fuerte… (gracias por pasármelo Jhtan :D)

Ahora, en este semestre, comencé a llevar Sistemas Operativos, y mi interés ahora también es obligatorio… el docente (Miguel Ángel Villarroel) nos pidió que tomaramos notas, y que en el examen es obligatorio presentar las notas que hemos tomado. Mis notas suelen ser muy desordenadas y carentes de sentido para la mayoría, y como no me gusta pasar en limpio mis notas, prefiero utilizar este medio para llevar una especie de “cuaderno virtual” en el que explicaré los detalles más importantes (y fascinantes) de los Sistemas Operativos. De ese modo, no solo me ahorro problemas a la hora del examen, sino que también comparto con ustedes el conocimiento ;)

Sin embargo, este cuaderno virtual tiene una desventaja, que tengo que advertirles: como no soy una experta en el tema (estoy empezando casi desde 0), puede que la información expuesta no sea del todo verdadera… como sea, con el tiempo, y conforme vaya descubriendo errores en el conocimiento que reuno, los iré corrigiendo.

Este es el primero de una serie de posts que estaré escribiendo sobre los Sistemas Operativos en general. ¿Comenzamos?

Qué es un Sistema Operativo?

Esa es una pregunta profunda… Es difícil definir un Sistema Operativo. Para no confundirnos, podemos empezar desde aquí: hay algo que todos los sistemas operativos tienen en común: todos los sistemas operativos administran el hardware con el fin de lograr algún objetivo. De hecho, una definición menos ambigua, sería la de Rafa, que en los comentarios, afirma que el Sistemam Operativo administra los recursos del ordenador.

Los sistemas operativos cumplen diversos roles… En general, reciben datos de entrada para generan datos de salida.

¡Administrar el hardware (los recursos) no es una tarea fácil! Por ejemplo, al ejecutar un programa: primero hay que compilarlo, pero después, cuando ya se genera el ejecutable, el ejecutable tiene que pasarse a la RAM, y de la RAM, el CPU ya puede leer el programa. Pero el CPU es un tipo muy ocupado, todo el tiempo está haciendo operaciones, así que, para ejecutar tu programa, primero tiene que ‘interrumpir’ el trabajo que estaba haciendo, y ponerle atención a la ejecución de tu programa.

Y se complica más cuando le pides al OS que haga varias cosas a la vez… talvez no solo estés ejecutando tu programa, talvez incluso estás escuchando música, y chequeando tu correo electrónico. Para tí, todo pasa al mismo tiempo, pero el CPU no puede hacerlo “todo” al mismo tiempo (hay algunos CPUs que tienen varios núcleos, ellos sí pueden hacer tareas simultáneas, pero el número de tareas simultáneas se limita al número de núcleos que contiene). Para darte esta sensación de simultaneidad, el CPU se turna entre una aplicación y otra, ejecutando durante un corto tiempo los procesos de alguna tarea, y luego, los procesos de alguna otra tarea.

En fin… no es fácil! el Sistema Operativo debe mantener a todos contentos haciendo malavares con los recursos que tiene a su disposición.

Los sistemas operativos se pueden clasificar de varias formas, una de ellas es la clasificación entre Sistemas Operativos de propósito general (general-purpose OS) y los Sistemas Operativos de propósito especializado (special-purpose OS).

Los Sistemas Operativos de propósito general son los más conocidos… Están en nuestros Smartphones y en nuestras computadoras personales. Son sistemas operativos que nos permiten realizar una gran cantidad de tareas que no se limitan a un propósito en especial.

Los Sistemas Operativos de propósito especializado, son los que tienen tareas muy específicas. Por ejemplo, la inyección automática del combustible en un automóvil inteligente, y, si no me equivoco. El firmware de los routers… no sé si entraría en esta categoría… ¿es el bootstrap parte del OS? si no, entonces el firmware no es un OS.

Aunque esta clasificación parece muy intuitiva, no tiene muchas referencias. He encontrado más referencias sobre una que clasifica a los OS en: Real-Time Operating System (RTOS), Single-user Single-task, single-user multi-task y multi-user…

Los sistemas operativos de propósito especial entran en esta categoría (??). Son Sistemas Operativos que tienen una interfaz con el usuario muy limitada. Están diseñados para que, al ser incluidos en una máquina, esta máquina actúe como una caja cerrada con un propósito muy específico.

Los OS Single-user Single-task, son sistemas operativos que solo aceptan a un usuario haciendo una única tarea a la vez.

Los OS single-user multi-task son sistemas operativos que, pese a que soportan que varias tareas se ejecuten al mismo tiempo, solamente aceptan a un usuario (como Microsoft Windows).

Y los OS multi-user son sistemas operativos que aceptan a varios usuarios haciendo varias tareas al mismo tiempo (como Linux). Esta clasificación abre nuevos retos, el OS no solo debe encargarse de distribuir los recursos de forma apropiada para las tareas que quieren ejecutarse simultáneamente, sino que también deberá distribuir los recursos de forma justa entre los distintos usuarios que lo usen.

A la próxima escribiré un poco sobre el Hardware y la forma en la que se comunica el CPU con los dispositivos periféricos (I/O)

Estoy de vuelta :D

Finalmente estoy de vuelta….

Estuve teniendo muchos problemas con mi conexión, algunas páginas cargaban a medias, algunas solo cargaban el texto y no cargaban las hojas de estilos… otras no cargaban su javascript, y por eso no podía entrar a Twitter ni a ningún blog de WordPress o de Tumblr :S pero el colmo fue cuando, hoy, al intentar acceder al internet, simplemente ya no respondió /heartattack

Podía hacerle ping a google de esta forma: ping 8.8.8.8 pero cuando hacía esto: ping http://www.google.com no respondía :S intenté conectarme a google desde Chromium y desde mi firefox, pero no funcionaba D: lo más raro es que no tenía problemas para comunicarme con el módem, así que ping 192.168.1.1 funcionaba… ¡incluso mi Transmission estaba funcionando bien! estaba haciendo seeding de algunos torrents a 18 kb/s, pero pidgin también se colgó.

Bueno, más adelante escribiré algún post explicando qué es el enigmático DNS, pero por ahora (y porque aún ni siquiera entiendo lo que es) solo explicaré cómo arreglé el problema:

Aparentemente, era un problema con el DNS, la configuración de IPv4 estaba automática, pero no estaba agarrando al DNS correcto, así que el error debería corregirse si corriges el DNS. ¿Cómo? bueno, mi network manager me dio unos cuantos problemillas con esto, ya que no estaba guardando la configuración que le ponía mediante la interfaz gráfica :S

Así que, lo que hice fue esto: mediante la interfaz gráfica del network manager, cambié la configuración del IPv4 a manual. Luego, en el archivo /etc/resolv.conf comenté todo lo que había, y hasta arriba agregué la DNS correcta… la DNS correcta la conseguí de una máquina cuya red estaba bien configurada xD

nameserver direccion.dns.correcta.aqui

Luego solo hay que reiniciar el network manager:

/etc/init.d/networking restart

Y tadah~ las páginas deberían cargar bien…