What is an OS?

  1. An operating system is the abstraction that helps connect userspace and hardware! There are many layers of abstractions built for us: we have C code thats been compiled, which relies on system libraries (think cstdlib), which makes use of syscalls which are provided by the OS! e.g. We never manually interact with the filesystem

  2. Distribute resources! Imagine multiple users (or processes) trying to run their program. How do we choose who evently recieves what data? the operating system is in charge of that! It could be done through a policy as well (quota, first come first serve, etc)

  3. from the perspective of the system, the OS is the software running in priviliged mode! this could be like ring0 or whatever but there are physical hardware checks (think lgdt, tss, etc in x86) Theres a flag set in hardware that shows if the current software can do more stuff (accesss memory, etc)

Structure of a system?

Theres two 'bubbles' of a system: We usually have userspace and kernel mode. Applications in userspace make use of system libraries; which are just normal libraries as well. Its just ordinary code that interacts with the kernel to get stuff done. If you think about it, everything lives somewhere on memory. The operating system has the ability to view memory and theres some memory that can only be touched by the OS.

If processes want to do stuff that involve os actions, they need to make use of syscalls, which are like function calls but its a protected way of nicely asking the os to do something for you. These can be written by yourself but most often you want to do them via syscalls (open, close, read, etc). These syscalls are then created to have another abstraction layer (malloc, memcpy, etc)

tldr; the operating system is just code that has more power and that lets it interact with hardware (like memory)

System approaches

How should we arrange an OS internally? There is a layered by layer approach: dependencies point downwards into the core of the system. For instance, the usermode would be in the shell of the system, with layers of abstraction behind each other, with processor management and memoryu management at the core! However, this isn't really realistic.

A different implimentation is a monolithic kernel; everything is interlinked with everything else! Think linux, windows, etc. However, a general prevailing structure will usually form.

Processes and threads

Remember how we said the os needs to be able to run more than one thing? The processor will give the os the ability to do so, but the processor itself cannot run more than one thing at once unless you have multithreading: but you still want more processes than you ahve threads.

what is a process? what is a thread?

A process is closer to an abstraction of a thing that "runs", or a user level execution. It owns resources allocated for program execution. It encompasses one more more threads.

A thread is the sequence of instruciotns that are ran.

Think of processes as a space in memory of a thing to be executed, and a thread being the instructions that make up that process being ran

the thread model

Assume there is a multithreaded process: At the langauge level; that means that each thread within the process has its own separate stack that can still share state (global varaibles) since they live in the same memory. But for local variables, they should have their own local variables (per thread)

scope

  • local varialbes are per thread
  • global variables are shared (written in the .bss segment i think)
  • dynamically allocated variables could be local OR global... (think malloc())

Scheduling

So how do we run muiltiple processes on one thread? We can have a dispatcher (scheduler) that decides which process to run by having each process run for a few instructions, before returning back to the dispatcher which makes a jump. States have to be preserved in between (storing register data), loaded and restored.

Using this, it appeares that multiple processes are running at once, but in reality only one program is active at one point. Thus, there is a model of having sequential processes with a single thread each "running" at the same time.

When do we return back to the dispatcher?

If you remember from our example of having programs scheduled in between, we jump between different processes by having program A run for a few instruction cycles before returning back to the dispatcher, which then decides on the next ready process to execute. How do we actually return back to the dispatcher in that instance?

There is a feature within the CPU when certain hardware needs attention, it asks the CPU to stop executing its current instructions and then transition to the interrupt handler within the OS. Like a syscall, it forces a transition to the OS to timeout threads that have met its quota and transitions to the dispatcher (scheduler).

How are processes created?

The os doesn't like setting things itself; it likes being reactive. Normally, that means handing it over to an init system (think systemd and openrc) that handles starting up other processes and etc. Theres different types of processes as well: foreground processes and background processes (known as daemons)

Processes can start other processes as well! think login prompts that start you into a desktop environment once you login. All these processes mostly just make use of one syscall to create new processes!

how to processes end?

  1. normal exit (return 0)
  2. error exit (exit(1))
  3. fatal error (runtime error, div 0)
  4. kileld by another process (sigterm, ctrl-c)

implementation of processes

What does the code/data that implements a process look like? It needs to hold metadata for the os to make use of, and is held within the process control block (PCB). The PCBs form a process table that shows

Assume this is for a single thread/process model:

process metadata would include: registers, program counter, stack pointer, process state, pointers to stack, text, data segments, process ID, cpu time used, children of CPU time, etc. these all are used by the operating system to control and make use of processes, like scheduling or terminating based off other processes.

Threads/Process states

there can be alot of variable thread or process states. Ideally, we should have as many running processes as there are threads in cpus.

running -> ready - voluntary yield() - end of timeslice (quota) ready -> running running -> blocked - waiting for input (file, network, keyboard) - waiting for a timer sleep() - waiting for a resource to become avaliable blocked -> ready

for the transition from runnign to ready for a thread, this could be a thread that is currently running, but its time budget is now used up and will be reassigned to a different process! It's still ready to run, its just not one of the ready threads.

For ready -> running, the currently running task got stopped so we need to replace the thread to keep the cpu busy.

For running -> blocked, something like a syscall could happen: a process wants to sleep(), or the process wants to use a syscall to fetch file contents. Its not current avaliable, so the thread becomes blocked. It's not allowed to run until some situation changes. Eventually, this will be ready to run again, which will put it from the blocked -> ready state.

The scheduler

The scheduler (or a dispatcher) has to pick things to run. It has to pick one of its ready threads to start! How does it do taht though...

We could have a queue! the scheduler picks from the head of the queue!!

What about blocked processes though? When an unblocking event happens (file is read, keyboard is inputted, network is recieved/sent), we could scan through all processes to check which processes to unblock, but thats inefficient!

We could have a queue of blocked tasks for each blocked event, which will then trigger and push it to the end of the ready queue.

Concurrency

Consider two pieces of code which shares a global varialbe count.

void increment()
{
    int t;
    t = count;
    t = t + 1;
    count = t;
}

void decrement()
{
    int t;
    t = count;
    t = t - 1;
    count = t;
}

if both pieces of code were to be ran, there could be a race condition! imagine if the increment() thread were to hand over control to the decrement() thread after t = t+1 This would mean that after decrement, count is decresed by 1. However, when the thread is handed back to increment(), count would be count + 1, intead of 0.

Kernel level concurrency

Think back on scheduling. To run our dispatcher (scheudler), we would need a kernel level thread to execute that dispatcher, right? That would mean keeping track of queues of ready and blocked processes. Likewise, we need to upkeep the PCB (process control block) to ensure metadat is kept up to date.

Critical regions

A critical region is a position where a shared location is accessed. If uncorrindated access to this is done, then it coudl result in race conditions or other nasty stuff

to ensure protection within critical regions, we can force different processes to wait until their turn:

                               A enteres critical region
                               /-------------\

Process A: ------------------------===============---------------------------- Process B: -----------------------------..........===========----------- \---------/ B attempts to access critical region, fails.

solving critical regions

We need to coordinate access to critical regions! We need to: - mutually exclude processes accessing critical regions - make no assumptions about the number of threads - no process running outside the critical region can block another process (defeats whole point of multitrheading) - no process waits forever to enter critical region!

Locks!!

We could haev a global lock varaible that won't let code execute if it is true. Code that did enter the critical region would set lock = 1 and when its done will lock = 0

while(TRUE) {
    while(lock == 1)
        ;
    lock = 1;
    critical();
    lock = 0
    non_critical();
}

while(TRUE) {
    while(lock == 1)
        ;
    lock = 1;
    critical();
    lock = 0
    non_critical();
}

However, another issue may be posed: if the while(lock == 1) condition has passed for a process, then the thread is handed over to the other process, both locks will be 1, and the critical region will be hit! what do we do??

taking turns

We could take turns!! We have a global turn variable that specifies which thread is allowed to run (i.e. turn = 0 represents process A, =1 represents process B, etc)

The problem with taking turns is that processes must wait to take their turn, even if other processes are doing something else.

hardware support

You can actually disable interrupts! its a builtin thing via hardware. The downsides is that it delays everyone else, and it doesnt work on multiprocessors :(

test and set

another hardware instruction! It's atomic, meaning that its the smallest unit of instruciton executable. Using this, it can test the value of a lock AND set it at the same time.