Operating Systems 2021F Lecture 21
Video
Video from the lecture given on December 2, 2021 is now available:
Video is also available through Brightspace (Resources->Class zoom meetings->Cloud Recordings tab)
Notes
Lecture 21
----------
Yes you can make your own filesystem
- in fact, you can do this in userspace, see FUSE
(this is how sshfs works)
In the kernel, a file is a file struct
- in userspace, it is a file descriptor (a small number)
- note that a file struct represents an *open* file
- and thus is referenced in task_struct
When we look in /proc/<PID>, we are looking at task_struct's
- each file/directory corresponds to parts of the task_struct
System calls in the kernel are defined with special macros
- SYSCALL_DEFINEX where X is a number for number of args
- need this because system calls aren't invoked like regular functions on the kernel side either, need to do machine language magic
- after initial entry, kernel uses regular C functions like
userspace
As you can see, kernel code is C code, but there's a lot and
it has lots of abstractions
- I get lost following it sometimes
- but if you're patient you can see the patterns
file descriptor is an index into an array of file structs in the kernel
process IDs identify task_struct's in the kernel
- the process that made a given system call is always "current"
in the kernel
The current position in a file is inside a file struct
- that's the offset
VFS = virtual file system
- abstraction in the kernel for filesystems
- allows for many implementations
In kernel data structures, you'll see mutexes and spinlocks
- logically, they are the same thing
- but a spinlock busy waits, while a mutex can go to sleep/wake up
A busy wait is just a loop "spinning"
- typically a while loop on a condition or equivalent
logically:
int lock = 0; /* shared variable */
while (lock) {
/* wait */
}
lock = 1;
/* do something assuming the condition is true */
lock = 0;
Note that in the loop we're doing no useful work,
just waiting
- very inefficient for long period of times
- but going to sleep and waking up later takes a while
It is more complicated because the above code can't ever work properly on modern computers
The problem is the separation between the testing (the while loop) and the setting (the assignment)
- another process or thread could set lock to 1 between the end
of the while loop and the assignment,
- so logically two processes/threads would have the lock,
but we wouldn't know it
This is known as a race condition
- state depends on relative speed of different concurrent executions
The only way to do this safely on modern systems is using special machine language instructions
- the exact ones vary from processor to processor
- but all modern processors that support multiple cores have them
(Yes, you can't make a mutex using standard C!)
These instructions either swap two values as one atomic operation,
or they do a test & set as one atomic operation
- they are implemented by one core sending messages to other cores
saying "hey I'm messing with this memory, nobody else touch it
until I'm done"
a "spinlock" is a mutex that busy waits
a "mutex" is a mutex that can sleep
a mutex is a semaphore that can take on a value of 1 or 0
a semaphore is just a counting variable that has exclusive access properties
- will always have a coherent state when being accessed concurrently
When you're doing concurrent programming, you need to guarantee mutual exclusion
- "mutex" is just short for mutual exclusion
How do processes and kernel threads share the CPU?
When a process runs, it has exclusive access to a core
- but the core is in user mode, so limited access
But it only gets the core for a limited time. Its use will end when
- it makes a system call
- it is preempted (interrupted)
The kernel sets timers (timer interrupts) to make sure it gets back the CPU
- at least every .01 seconds, but can be more often
What is an interrupt?
- an event where a device sends the CPU a message that
it must act on immediately
- signals are modeled on hardware interrupts
- but for processes/kernel messages, not devices
When you type on a keyboard, an interrupt is send by the keyboard to the CPU
- and so the CPU has to stop and acknowledge a key has been pressed before continuing its business
- (in reality it is more complicated because keyboards have their
own little CPU)
So the kernel has to constantly switch to service interrupts from devices
- especially network interfaces, that data has to be dealt with quickly or it will be lost
Sometimes polling is used, depends
- so then the kernel periodically asks the device for its state,
rather than the device telling it it has data
Nowadays we don't use polling so much because it wastes resources
most of the time
- polling would consume resources when you aren't typing, for example
When your machine freezes, the kernel is no longer servicing interrupts
- so it is REALLY messed up
Keyboard death is a bad thing
One quirk of linux - magic sysrq key
- only works on real hardware I think? Haven't tried with VMs
- you can hit alt-sysrq-X and do all kinds of things
- alt-sysrq-S will sync file systems
- alt-sysrq-R will instantly reboot the system
(sync first otherwise some data may not have been
written to disk and will be lost)
So if the magic sysrq key is working, part of the kernel is still alive
- if it fails, the kernel truly is dead
On a linux box, it is possible for the display to freeze up but the system is still running
- the X server or Wayland server has died
- can still ssh in, and can restart any misbehaving processes
Note that when a task loses a core it is then in another state
- "blocked" - it is waiting on I/O
- "sleep" - it is waiting for its next turn on a core
The scheduler in the kernel is responsible for deciding what task to run next
- it is a doubly linked list I think, with some additions to allow for efficient scheduling
Scheduling needs to be efficient
- can't spend too long deciding
- but can precompute things to make it easier
If you look at top, you'll see a PR and NI value
- NI is "niceness", the priority the user can set,
basically static priority
- PR is the dynamic priority, which is constantly updated
based on past behavior of the process
- if it has been using a lot of CPU time, it
will get a lower priority
- if it was waiting on I/O, it will get a higher
priority when that wait is over
So the big difference with a mutex versus a spinlock is with a mutex you give up the CPU when waiting, while with a spinlock you don't.
- if it is a short wait, better to hold the CPU
- but otherwise better to give it up so someone else can use it
When you go to sleep (give up the core you had), you have no guarantee when you'll get a core again
- waits can be arbitrarily long on a busy system
a core should only idle if there is nothing to do
- no processes in a "ready to run" state
In tutorial 8
- with 3000pc-fifo, calls to read/write can cause the process to sleep (when the kernel buffer for the pipe is full/empty)
- but with 3000pc-rendezvous, we manage the buffer manually in
userspace using mutexes
UNIX is preemptively multitasking
- so a task can always be kicked off a core
Some systems are cooperatively multitasking
- so a task running cannot be interrupted, it has to give
up use of a core
Key advantage of doing it yourself in userspace
- grabbing lock successfully doesn't involve making a system call,
- only need system calls when you sleep
With 3000pc-fifo, putting a word in the queue always involves a system call
- with rendevous, we may not need to make a system call
(and hence may not need to give up the CPU)
- but clearly the Linux kernel is very efficient at file I/O,
including pipes, even with system call overhead