Resources

Requisite

Introduction

What is an operating system?

The operating system is the Computer land’s government.

What do operating systems do?

Operating system tasks are managing processor, memory, device, storage, and providing an application interface.

Story

A brief story from the 1950s to the present.

Mainframes.

No operating systems?

First operating system

The first industrial operating system released was GM-NAA I/O, sometimes called GMOS, of General Motors and North American Aviation for the IBM 704 computer in the May of 1956. Its purpose was batch processing.

However, the first operating system was released in 1953 for EDVAC.

Ryckman, George F. (April–June 1983). "17. The IBM 701 Computer at the General Motors Research Laboratories". Annals of the History of Computing. IEEE. 5 (2): 210–212. doi:10.1109/MAHC.1983.10026.

G. W. Reitwiesner, "The first operating system for the EDVAC," in IEEE Annals of the History of Computing, vol. 19, no. 1, pp. 55-59, Jan.-March 1997, doi: 10.1109/85.560738.

Batch processing systems

Batch processing systems are one that runs programs with no user interaction.

They are ongoing in scripts such as batch files (.ps) in Windows-based or bash files (.sh) in Unix-based. For instance, assuming a file with thousands of users, a possible need is to send emails to them every day at 6 am with an ad.

Notes

IBM Corporation. "What is batch processing?". zOS Concepts. Retrieved Oct 10, 2019.

Multiprogramming

Time-sharing

Multitasking

UNIX

Dennis Ritchie, Brian Kernighan, Ken Thompson, and others in Bell Labs released Unix in November of 1971.

Notes

Ritchie, Dennis, and Ken Thompson, “The UNIX Time-Sharing System,”, Communications of the ACM, 17,1 (July 1974), 1897-1920

Unix: A History and a Memoir. Brian Kernighan

Youtube Unix intro The Evolution of the Unix Time-sharing System, Dennis M. Ritchie, 1979.

Minicomputers

Multiprocessor systems

Virtualization

Emulation

Hypervisors

https://www.muylinux.com/2014/05/28/exirion-os-so-libre-mexico/

Today

Some popular distros are Ubuntu, CentOs, Fedora, Debian, and Red Hat Enterprise Linux. By the way, I use Arch Linux.

Notes

Just for Fun. The Story of Accidental Revolutionary. Linux Torvalds and David Diamond.

TempleOs

Today

[1] Samsung U.S. Newsroom, “Six Advantages of Tizen OS on Samsung Smart TVs,” Samsung US Newsroom, Jun. 15, 2021. [Online]. Available: https://news.samsung.com/us/six-advantages-of-tizen-os-on-samsung-smart-tvs/. [Accessed: Aug. 10, 2022]

[2] Trinder, Garry. "The Xbox Operating System". Xbox Engineering. MSDN. Archived from the original on November 2, 2018. Retrieved October 31, 2018.

[3] "Console Security - Switch". 30 December 2017. Retrieved 30 May 2018.

[4] Patel, N. (June 7, 2010). "iPhone OS 4 renamed iOS 4, launching June 21 with 1500 new features". Engadget.

[5] “EMUI 10.1 - HUAWEI Global,” Huawei.com, 2020. [Online]. Available: https://consumer.huawei.com/en/emui10-1/. [Accessed: Aug. 10, 2022]

[6] “PS5 System software (US),” Playstation.com, 2022. [Online]. Available: https://www.playstation.com/en-us/support/hardware/ps5/system-software/. [Accessed: Aug. 10, 2022]

Programming environment

https://wiki.osdev.org/How_kernel,_compiler,_and_C_library_work_together

API (Application Programming Interface)

“API” is a mechanism that enables two or more software components to communicate with each other with a specification hiding the internal details [1]. The simplest API is a client and server, where the server shows its headers, and the client calls them.

For instance, Amazon renders its amazon.com with Web APIs:

[1] “What is an API? - API Beginner’s Guide - AWS,” Amazon Web Services, Inc., 2022. [Online]. Available: https://aws.amazon.com/what-is/api/. [Accessed: Aug. 10, 2022]

POSIX

POSIX is an API chiefly UNIX-like and it stands for Portable Operating System Interface.

IEEE Standard 1003.1

C++ https://www.iso.org/standard/79358.html

C https://www.iso.org/standard/74528.html

Windows systems

https://docs.microsoft.com/en-us/windows/win32/

Windows, POSIX equivalence

FORK, spawn …

Operating system

Operating System provides an API to processes, memory, filesystem, I/O devices, storage, network, users, and shell since it manages hardware resources.

For instance, printf in C, it’s provided by stdio.h-—UNIX headers to the standard I/O [2].

[2] Kernighan, Brian; Ritchie, Dennis M. (March 1988). The C Programming Language (2nd ed.). Englewood Cliffs, NJ: Prentice Hall. ISBN 0-13-110362-8.

The operating system zoo (Classification of Operating Systems)

Embedded operating systems

Real-time operating systems

Operating systems distinguish by their key parameters: time. In other words, they focus on doing tasks by a deadline. Examples are nuclear reactor systems, automobile manufacturing assembly line systems, military drone systems, or ballistic missile systems.

Instructional operating system and kernels

PINTOS

Pfaff, B., Romano, A., & Back, G. (2009). The pintos instructional operating system kernel. ACM SIGCSE Bulletin. Association for Computing Machinery. doi: 10.1145/1508865.1509023

"Xv6, a simple Unix-like teaching operating system". Retrieved 2014-09-22. Xv6 is a teaching operating system developed in the summer of 2006

MINIX

OS/161

System/161 2.x Software and Hardware Manual

David A. Holland, Ada T. Lim, and Margo I. Seltzer, A New Instructional Operating System. Proceedings of the 2002 ACM SIGCSE Conference on Computer Science Education, March 2002. PDF

Research

https://dl.acm.org/sig/sigops

https://ieeexplore.ieee.org/search/searchresult.jsp?newsearch=true&contentType=periodicals&queryText=operating systems

https://cacm.acm.org/magazines/2022/5/260363-technical-perspective-what-is-the-ideal-operating-system/fulltext

Ecosystem

CISCO

RedHat

Jobs as Sysadmin,

X operating system contributor where X is Linux, Windows, Android, and so on.

HelpDesk

https://www.youtube.com/watch?v=v7fKfDp6cQs&ab_channel=PeladoNerd

How to learn operating systems?

1. Understanding high levels concepts and using a real operating system.

2. Implementing an operating system.

3. Using an instructional operating system.

https://www.studytonight.com/tests/?subject=operating-system

FAQ

Why do we need operating systems?

Even though the operating system produces an overhead, it is necessary because it reduces development time in user applications and that is beneficial to final users.

What is the difference between GNU/Linux and Unix?

Although Dennis Ritchie considers Linux as the de facto Unix system (Interview with Dennis M. Ritchie Manuel Benet, LinuxFocus, July 1999) and the current Unix commercial versions and Linux are POSIX complain, they don’t have the same codebase, they extended that specification in a different way, and of course, they have a different license.

What do I call Operating System API?

Some interfaces are in libraries (for instance, stdio.h or unistd.h) and for others, you have to use exec stuff. So, you have got to search for your problem.

Worked example in Linux.

As user view (https://man7.org/linux/man-pages/man1/kill.1.html)

kill -KILL 3333

From programmer's view (https://man7.org/linux/man-pages/man2/kill.2.html)

#include <signal.h>

int main() {
    kill(3333, SIGKILL);
    return 0;
}

Some references are https://www.kernel.org/doc/man-pages/ and ‘The Linux Programming Interface’ (published in October 2010, No Starch Press, ISBN 978-1-59327-220-3).

Operating system development and its architecture. Design Considerations.

Common operating system components

• PlantUML

  @startuml
  !theme mars
  User ..-> [Applications]: use
  node "Applications" {
    node "User interfaces" {
      [batch] 
      [command line]
      [GUI]
    }
  }
  note left of batch: For instance, job schedulers. Cron is job scheduler in UNIX-like.
  
  node "Operating system" {
    portin "System Calls" as SystemCalls
    [command line] -down-> SystemCalls
    [batch] -down-> SystemCalls
    [GUI] -down-> SystemCalls
    SystemCalls -down- [Process Management]
    SystemCalls -down- [Storage Management]
    SystemCalls -down- [Communication]
  SystemCalls -down- [Protection and security]
  SystemCalls -down- [Resource allocation]
  SystemCalls -down- [Input/Output Management]
  SystemCalls -down- [Accounting]
  SystemCalls -down- [Error detection]
  }
  @enduml

Operating system services

System calls are operations that the operating system makes for you.

Design Philosophy

Simple is beautiful sometimes called small-is-beautiful philosophy. Examples: Unix, Latin, RISC.

UNIX is done with only six basic system calls which are fork, executing another process, open, close, read, and write files.

https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/unistd.h.html

Start off on complexity. Examples: Windows, Chinese, CISC.

Windows is done with every imaginable system call.

Operating system architectures. Operating system structures. Kernel models.

Monolithic systems

Layered systems

Microkernels

Client-Server Model

Virtual Machines

Exokernels

Modular Kernel

Low-level tools

Large Programming Projects

Vim, Make, C, GNU, Clang, GNU, C++,

Rust?

Instruction set architecture (ISA)

Because operating systems use low-level tools you as operating systems really have concerns about your ISA, but x86 is the most common so we are going to work with it. x86-32 and x86-64.

If you are an application programmer (including a compiler programmer), operating systems make a lot of work for your specification or requirements but they limited all work that you can in a computer.

Boot process

A typical boot process for personal computers.

1. Motherboard

2. Firmware. BIOS/EFI. Bootloader. Real mode.

3. Kernel. Protected mode. Kernel mode.

4. User interface. User mode.

5. User Applications.

Firmware

Today, firmware can be BIOS or UEFI. If your firmware is BIOS, you have to write your bootloader, but you don’t on UEFI, because it has a bootloader manager called bcfg. UEFI has more benefits than a program that aims to load the kernel. Both you have got implement GDT, IDT, and so on.

Notes and references

interrupts

IRQ

Programmable Interrupt Controller (PIC)

Real Mode

Protected mode

https://wiki.osdev.org/Interrupts

https://arjunsreedharan.org/post/99370248137/kernels-201-lets-write-a-kernel-with-keyboard

Mastering Embedded Linux Programming

https://wiki.osdev.org/BOOTBOOT

https://www.codeproject.com/Articles/664165/Writing-a-boot-loader-in-Assembly-and-C-Part

https://en.wikibooks.org/wiki/X86_Assembly/Bootloaders

https://wiki.osdev.org/Rolling_Your_Own_Bootloader

https://www.codejam.info/2021/08/super-fast-boot-linux-efistub.html

https://wiki.archlinux.org/title/Arch_boot_process

https://www.rodsbooks.com/efi-bootloaders/

https://wiki.osdev.org/UEFI

https://interrupt.memfault.com/blog/zero-to-main-1

https://developer.ibm.com/articles/l-linuxboot/

https://wiki.osdev.org/UEFI

https://stackoverflow.com/questions/58002542/how-does-uefi-boot-mode-boot-flows

"Beyond BIOS" book

https://github.com/torvalds/linux/blob/master/arch/x86/boot/main.c

Virtualization = Program management + memory management

Process description

A process is a running program.

A program from an operating system’s view is a bunch of isolated instructions on the disk.

Process data structures

Global Descriptor Table

ACPI MADT table

ELF

Machine state

Create

Destroy

Wait

Status

Process API

fork, exec, process tree, spawn

Direct Execution

Scheduling

CPU Scheduling

Ostrich algorithm?

Goals

Concepts

Algorithms for batch processing

Arrival Time

Completion time

Burst time

Turn Around time

Waiting Time (W.T.).

First come, First served (FCFS)

Shortest-Job-Next

Priority Scheduling

Shortest Reaming Time

Expropiative version

Round Robin

Expropiative version

Quantum

Multiple-Level Queues Scheduling

Summarize

https://docs.google.com/spreadsheets/d/1SBEBDR7Lux3Xo-Jac3bKvISdmSSQdnNkYpb8zOeKKYI/edit?usp=sharing

CPU Scheduling – Jerry Breecher

Notes

https://www.tutorialspoint.com/operating_system/os_process_scheduling_algorithms.htm

http://perugini.cps.udayton.edu/teaching/courses/cps346/lecture_notes/scheduling.html

https://www.geeksforgeeks.org/program-fcfs-scheduling-set-1/

http://laurel.datsi.fi.upm.es/_media/docencia/asignaturas/dso/planificacion_2010_4pp.pdf

http://perugini.cps.udayton.edu/teaching/courses/cps346/lecture_notes/scheduling.html

http://www2.latech.edu/~box/os/ch05.pdf

https://cryptomex.org/SlidesSistOp/AdmonProcs.pdf

Segmentation. Stack-based memory allocation.

https://stackoverflow.com/questions/45303014/explanation-of-all-columns-in-size-command-output

Inter-process communication (IPC) models

It depends on what OSI model we are.

Message-passing

Example include Pipes, Sockets, Queue passing.

Shared Memory or Shared-state

Example include Threads and Shared memory systems.

Note. Making a child i.e. fork() doesn’t mean sharing memory.

Inter-process communication (IPC) strategies

Interrupts & Signals

Interrupts, sometimes called traps, are

References

harismuneer. (2022, September 30). BelalHashmi-Assembly-Exercise-Solutions. Retrieved from https://github.com/harismuneer/BelalHashmi-Assembly-Exercise-Solutions

https://www.youtube.com/watch?v=54BrU82ANww&ab_channel=Computerphile

Microprocessor Design/Interrupts - Wikibooks, open books for an open world. (2022, September 16). Retrieved from https://en.wikibooks.org/wiki/Microprocessor_Design/Interrupts

x86 Assembly/Advanced Interrupts - Wikibooks, open books for an open world. (2022, September 16). Retrieved from https://en.wikibooks.org/wiki/X86_Assembly/Advanced_Interrupts

5.-IRQs and the PIT. (2017, January 15). Retrieved from http://www.jamesmolloy.co.uk/tutorial_html/5.-IRQs and the PIT.html

Interrupt Service Routine -Keyboard Interrupt Example | Hitch Hiker's Guide to Learning. (2022, September 30). Retrieved from https://www.hitchhikersguidetolearning.com/2021/05/09/interrupt-service-routine-keyboard-interrupt

Shared memory systems

Queue passing

Pipes

User mode

Example

ls | grep .c | wc -l

It means

stdin → ls → grep .c → wc -l → stdout

Programming mode

Named pipes

Worked example

1. Communicate two processes made in two different programming languages by pipes.

References

Johnny Huang » Linux IPC with Pipes. (2015, August 08). Retrieved from https://hzqtc.github.io/2012/07/linux-ipc-with-pipes.html

Sockets

“Socket” is a generalized interprocess communication that can exchange data between applications in a network.

Application Protocols are above sockets such as RPC (remote procedure calls), HTTP, FTP, REST, WebSocket …

Case study.

Sockets in POSIX

References and notes

https://en.wikipedia.org/wiki/Inter-process_communication

Worked examples

• Considerando la existencia de cuatro procesos (P1, P2, P3 y P4), un recurso R1 con dos ejemplares, un recurso R2 con tres ejemplares, y los recursos R3 y R4 cada uno con un ejemplar. Describa un escenario en el cual cada proceso tenga asignado al menos un recurso y esté solicitando al menos otro, de tal forma que genere un deadlock.

  Condiciones para generar un deadlock:

  1. Ciclo P1 → …. → P1.

  2. Cada proceso tenga asignado al menos un recurso y esté solicitando al menos otro. Los nodos adyacentes a un recurso son procesos y al revés.

  3. La cantidad de ejemplares es menor a la cantidad de aristas. Esto es la cantidad aristas es mayor a 7.

  graph LR
    P1((P1))
    P2((P2))
    P3((P3))
    P4((P4))
    R1[R1..]
    R2[R2...]
    R3[R3.]
    R4[R4.]
    P1-->R1
    R1-->P2
    P2-->R2
    R2-->P3
    P3-->R3
    R3-->P4
  	P4-->R4
    R4-->P1
    P3 --> R1
  

References

Chapter 7 Abraham Silberschatz Operating System Concepts 9th

Notes and references

https://www.cs.cmu.edu/~ralf/files.html

FAQ

Concurrency & Parallelism

“Concurrency” is a computing model (language concept) where a system executes $n$ computations during overlapping time periods at most $n$ ($< n$) processors and over on memory.

“Parallelism” is a computing model (hardware concept) where a system executes $n$ computations during overlapping time periods of at least $n$ ($\ge n$) processors and over on memory.

Multiprogramming refers to concurrency and parallelism, informally multiprogramming is a situation where you cannot say which event will happen first by looking at the program.

Time slicing.

Scheduler.

Examples of the systems that deal with multiprogramming are

• Distributed systems

• Operating systems

• Process

• Threads

Competitive and Independent concurrency is the event where two or more concurrent subsystems do not communicate with each other nor sync with each other neither. You don't worry about how to share the subsystem states and sync processes.

gantt
    title Competitive and Independent concurrency
    dateFormat m mm
    section Process are independent
    Process A           :a1, 0
    Process B           :a1, 0

Cooperative concurrency is the event where two or more concurrent subsystems communicate or sync with each other. You worry about Synchronization and Inter-process communication (IPC) models.

References

Reading 21: Concurrency. (2022, May 23). Retrieved from https://web.mit.edu/6.031/www/sp22/classes/21-concurrency

https://www.info.ucl.ac.be/~pvr/VanRoyChapter.pdf section 4.3 page 25

Classic problems

Reader & Writer

Race condition

A race condition or race hazard is the condition of a system where the system’s substantive behavior is dependent.

Non-determinism or Indeterminate.

Generally speaking, multiprogramming is a non-determinism situation.

Suppose two concurrent tasks:

print("yes")

print("no")

Because tasks run concurrently, the order of execution depends on the scheduler. So the output might be “yes no” o “no yes”.

Heisenbugs

Threads

While the processes are isolated, threads share the same data (Shared memory systems). So, if you want multi lightweight tasks or need to share data easily with each other a sound choice is threads.

An introduction to programming with threads, Andrew Birrell, Research Report 35, Digital Equipment Corporation Systems Research Center, 1989.

Synchronization

In computer systems, synchronization is the relationship between events. We have seen problems if the events were free, so your system has to deal with two constraints:

Serialization.

Mutual exclusion.

Piece of advice for making safe Synchronization

• Confinement

• Immutability

• Use existing threadsafe data types
  • Synchronization

Dining Philosophers

Mechanisms for Synchronization

Mutual exclusion

Locks

Critical section

Thread Safety

Interrupts & Signals

Promises

Semaphores

Monitor Brinch Hansen (1973), Hoare (1974)

Actor model

Dekker’s algorithm

Peterson's algorithm

Remove Method Invocation (RPC)

CORBA Web Services

J2EE

COM/DCOM

Websocket

Banker’s algorithm

References

The Little Book of Semaphores, Allen B. Downey.

FAQ

What is the difference between fork and thread?

Memory management.

Background

Memory addressing

Heap

Dynamic Relocation

Static Relocation

MMU (memory management unit)

Protection

Sharing

Base

Worked examples

Continuous Memory Allocation

Paging

Structure of the Page Table

Swapping

Virtual Memory

ZRAM

Debugging

Valgrind Home. (2022, November 14). Retrieved from https://valgrind.org

References

• http://www.sc.ehu.es/acwlaroa/SO2/Apuntes/Cap4.pdf

• Memory Management

• https://www.inf.ed.ac.uk/teaching/courses/os/slides/09-memory16.pdf

• Administración de la memoria – C ejemplos

• http://www.dc.fi.udc.es/~so-grado/SO-Memoria.pdf

Memory Management

• https://www.dc.fi.udc.es/~so-grado/2018-19/Temas/SO-Memoria.pdf

• Block swap

• https://mht.technology/post/block-swap/

Storage management. File systems. Persistence.

File system

Partitioning Table GPT/MBR

FUSE

Potpourri. (2022, October 27). Retrieved from https://missing.csail.mit.edu/2020/potpourri

Input/Output device management

Text rendering

VGA text mode

Interruptions and traps

Interrupt descriptor table

Keyboard & Mouse

Graphics

No.

Assignment

References

[Intel (2011)] Intel 64 and IA-32 Architectures Software Developer’s Manual, Com- bined Volumes: 1, 2A, 2B, 3A and 3B. Intel Corporation (2011).

Protection and security

Virtual machines

Emulators

DosBox

Windows managers

Booting as User

Live USBs

https://missing.csail.mit.edu/2020/potpourri/

Distributed systems

POSIX in Linux

We introduce you to the most common APIs. If you want to know more, please consult the documentation.

Shell scripting

Command-line Environment. (2022, October 27). Retrieved from https://missing.csail.mit.edu/2020/command-line

Dotfiles

Process

systemd

Daemons

Systemd

Parallel process

prog1 & prog2 &

https://stackoverflow.com/questions/3004811/how-do-you-run-multiple-programs-in-parallel-from-a-bash-script

User commands

Interlude

IPC

Interlude

Pipes

Interlude

Queue Messaging

ipcrm -q

Interlude

Shared Memory

Interlude

Sockets in POSIX

Socket system call

socket(domain, type, protocol) is a system call that creates a new socket where domain={AF_UNIX, AF_INET, AF_INET6, …}, type={SOCK_STREAM, SOCK_DATAGRAM, …}, listen=0.

Some Socket Domains. It is also known as the “Address families”.

You can find a full list of address families on the address_families(7) - Linux manual page. (2022, September 26). Retrieved from https://man7.org/linux/man-pages/man7/address_families.7.html

Socket Types. You can find it as “Communication styles” too.

If type=SOCK_STREAM, then the sequence is the following:

sequenceDiagram
		    Note over Passive socket (server), Active socket (client): Create sockets
        Passive socket (server) ->> Passive socket (server): socket()
        Passive socket (server) ->> Passive socket (server): bind()
        Passive socket (server) ->> Passive socket (server): listen()
        loop block until client connects
          Passive socket (server) ->> Passive socket (server): accept()         
        end
		    Note over Passive socket (server), Active socket (client): Start connection
        Active socket (client)->> Active socket (client): socket()
        Active socket (client) ->> Passive socket (server): connect()
		    Note over Passive socket (server), Active socket (client): Start communication
        loop they transfers data
          Passive socket (server) --> Active socket (client): write()/read() or send()/recv()
        end
		    Note over Passive socket (server), Active socket (client): Close communication
        Passive socket (server) ->> Passive socket (server): close()
        Active socket (client)->> Active socket (client): close()

Reuse Port

How do I use setsockopt(SO_REUSEADDR)? (2022, September 26). Retrieved from https://stackoverflow.com/questions/24194961/how-do-i-use-setsockoptso-reuseaddr

Interlude

🕸️Tic-tac-toe Web on POSIX Sockets and WebRTC

References

Sockets (The GNU C Library). (2022, September 26). Retrieved from https://www.gnu.org/software/libc/manual/html_node/Sockets.html

TCP/IP Sockets in C: Practical Guide for Programmers, Second Edition

Sockets (The GNU C Library). (2022, September 24). Retrieved from https://www.gnu.org/software/libc/manual/html_node/Sockets.html

Beej's Guide to Network Programming, Using Internet Sockets

Coverage: [OSCJ8] Chapter 5 (pp. 193-239); [OSC8] Chapter 5 (pp. 183-223)?

rpc(3) - Linux manual page. (2022, September 26). Retrieved from https://man7.org/linux/man-pages/man3/rpc.3.html

Semaphores

Writers and readers

Summary

References and notes

FAQ

What is the difference between POSIX, Single UNIX Specification, and Open Group Base Specifications?

https://unix.stackexchange.com/questions/14368/difference-between-posix-single-unix-specification-and-open-group-base-specifi

Windows 7

We introduce you to the most common APIs. If you want to know more, please consult the documentation.

Synchronization tools

Write your modern simple operating system from scratch, but it won’t be easy.