Soma-notes - User contributions [en]

Operating Systems 2017F Lecture 13

2017-10-27T02:24:41Z

CindyYu: /* Note */

==Video==

Video from the lecture given on October 19, 2017 [http://homeostasis.scs.carleton.ca/~soma/os-2017f/lectures/comp3000-2017f-lec13-19Oct2017.mp4 is now available].

==Code==

Files from the lecture [http://homeostasis.scs.carleton.ca/~soma/os-2017f/code/lec13/ are available].

==Note==

===Questions:===
Mutex and semaphore?

Mutex is a binary semaphore, it is a semaphore that take a value that is zero or one, a classic semaphore can count.

Mutex stands for ‘mutual exclusion’: I am exclusive access, no one else does.

More general semaphore is used when you need to keep track of numbers.

Most classic semaphore: read write semaphore. which will be seen in the kernel. The idea is multiple reader and only one writer.

Most of the time we use mutex.

=== dinner philosopher problem ===

Wiki page: https://en.wikipedia.org/wiki/Dining_philosophers_problem

You have five philosophers sitting around the table, these philosophers will talk, and they will talk so much, they don’t really want to focus on eating. And for some reason there is not enough of forks at the table. There is one fork at every position between the plates. In order to eat anything, you need two forks.(Maybe better to think about using chopsticks instead of forks). There are five people there and only five forks.

*Senario 1: they all pick the left one at the same time, they all now have one fork.- can any of them eat? no, they suppose to use two forks to eat.
*Senario 2: Immediately put a fork down, wait for five seconds, and pick a fork. (have a delay, and pick it up) -they will never eat, because they always get one fork.
*Senario 3: randomize it? When they get one fork and couldn’t get the other one, they put it back down, wait a random amount of time and get the next one. -Yes this will work on average, except sometime randomly they will pick up a fork at the same time and starve to death. (unless you have a timeout)

This illustrate the concept of '''deadlock''': you get to the point where the computation cannot proceed any further. Because the concurrence processes cannot get all the resource. Some of them can access the resources and some of them do not have the resources, so everyone stuck.

Wiki page: https://en.wikipedia.org/wiki/Deadlock

When your computer logs up, a lot of time it is because of the deadlock. Something get locked and never get unlocked at the driver.

One way to avoid deadlock: if you have enough resources you never have to share, deadlock never happen.
If you have shared resources, you can’t have deadlock.

After the midterm we will do more kernel hacking.

Operating Systems 2017F Lecture 13

2017-10-27T01:38:15Z

CindyYu:

Operating Systems 2017F Lecture 10

2017-10-10T18:58:46Z

CindyYu: Blanked the page

Operating Systems 2017F Lecture 10

2017-10-10T18:58:38Z

CindyYu:

Assignmen is due Thursday

Concurrency
-more than one thing happening at the same time

challenge with concurrency is keeping shared state consistent
-Files that are written to by multiple proceses
-Two or more processes communicating
-multiple threads within a process

if you have two thing access one thing at the same time, which one reaches first?

Concurrency leads to race conditions:
-order of interleaved actions affects output
-ex. did process A or B modify the file first?

(generate random number, we will get different result, which we don’t want)
We want deterministic behavior from concurrent computations
-How to make sure they dont corporate each other?
-Need to have some sort of cordination

To get consistent computation, we need to coordinate. (need to somehow interact with each other)
-but you can’t interact via regular variables (IMPORTANT)

Regular variables are subject to the memory hierarchy
-variables are stored in registers, L1 chache, L2 chache, L3 chache, main memory
-can be deeper in some contexts
-so what if coordination variable is in L1 cache for one thread and in main memory for another?
-hardware maintains consistency… eventually

How caching works
CPU caches are small pools of memory that store information the CPU is most likely to need next. Which information is loaded into cache depends on sophisticated algorithms and certain assumptions about programming code. The goal of the cache system is to ensure that the CPU has the next bit of data it will need already loaded into cache by the time it goes looking for it (also called a cache hit).
A cache miss, on the other hand, means the CPU has to go scampering off to find the data elsewhere. This is where the L2 cache comes into play — while it’s slower, it’s also much larger. Some processors use an inclusive cache design (meaning data stored in the L1 cache is also duplicated in the L2 cache) while others are exclusive (meaning the two caches never share data). If data can’t be found in the L2 cache, the CPU continues down the chain to L3 (typically still on-die), then L4 (if it exists) and main memory (DRAM).

(refs: https://www.extremetech.com/extreme/188776-how-l1-and-l2-cpu-caches-work-and-why-theyre-an-essential-part-of-modern-chips)

Variable: ranges of address, stored in multiple places.
L1: fastest, smallest, closest to the core
L2,
L3
Mechanisms for coordinating concurrent computatiosn must bypass the memory hierachy
instead use:
-filesystem locking primitives(kernel)
-special machine language instructions
going to use abstraction to do conccurency
operating systems - kernels in particular - are highly concurrent
-make them painful to code
-have to always worry about having exclusive (or safe) access to data, have to make sure it is done properly

abstruction, help us think about cuncurrency
Abstruction for managing concurrency:
-atomic variables guarantee strict ordering of operations (only one can be modified one time)

Ex.
Variable x: ****** <-range of memory locations

What does the cpu do to modify variable x?
-load x into register
-modify the register
-save the register to x

Can i just modified directly in memory? Yes but it is much slower than using register.
register: very small relative to memory.
(to see more Register vs Memory : http://techdifferences.com/difference-between-register-and-memory.html)

What if two cores try to modify variable x at the same time?
-both could have x in a register

Let’s say x is 5
-core A increments by 1
-core B decrements by 1

what’s x after both have run? Just go back to 5?
-coreA will increment 1, but coreB doesn’t register 5 yet, so will be 4
If B chages x but doesn’t see A’s change, you get 4.
If A changes x but doesn’t see B’s change… you get 6
-This is bad.

What do I need?
I nee x to be atomic, ^^^ shouldn’t be possible.
-has to make sure only one core accesses x at a time

only one core can load x in the memory and modify
cache have just different speed and differnet sizes.
(memory address, when you access the register? dont need to load data, it is in the register)

Classic promitive
Atomic variables are typically used to build semaphores…
but what we really want is mutual exclusion
-only one threat/process/cpu can access the resource at a time
if A be there, B can’t be there. it is exclusive access.
want mutual exclusion for larger resources, e.g. data structures, devices

higher-level languages directly support mutual exclusion, e.g. Java synchronized methods
(you have a object, it is synchronized, it only can happen one at a time.)
Semaphores are analogy to a railraod control mechanism
-only one train on the track

Change both direction on that one track, otherwise collision
They are using light signal.If that train is going south, the other one can’t go north…
If zero track, I can grab it. until I am done, no one can get it
semaphore is used to implement lock. its more primitive concept.

when a train enters the shared track
-grab the semaphore (increment atomic variable)
-if not available, wait (check first to see if it is 0)

when a train leaves the shared track
-release the semaphore(decrement atomic variable)

lesson: don’t implement semaphores yourself, please!

In the linux kernel
-locks semaphores of various types are associated with all kinds of data structures
e.g inodes
if you wanna access and modify inodes, it is a struct, you need to lock , otherwise if someone want to modify it, it would be dangerous.
Key question: when you can’t get the lock, what do you do?
-Sleep
(tell the scheduler to wake you up when the lock is available)
Can the scheduler go to sleep? no.
what do they do try to grab something but can’t get it?
-deal with not getting resource
-spin (do a null loop) (spin in circle)

If the wait time is short, spinning is the fastest thing you can do
-what happen when you sleep?
-can my sleep be woke up?

where possible, everything should be exclusive, minimize sharing

but in userspace…
-shared memory? NOooo
unless you use atomic variable, or something higher level
like semaphore
all the problem that kernel need to deal with it, you need to deal with it
-in general, shared memory is painful
-better way in general, use messages.
-series of meesges can be used to synchronize state

3-way handshakes, e.g. opening a TCP connection(everytime you conncect a website...)
it have to sychrnoize state
-send SYN (synchronize) packet client->server
-SYN ACK (acknowlege SYN) server-> client
-ACK(acknowlege) client->server
why have to be 3-way?
first packet necessary to open the communicate, second one: the server tell the client i got your packet, all good.
what happen if SYN ACK get lost?

there are message passing happening underneath many things.

Where do i want to send message? I can send messages between processes, using...
-Signals!
-other ways too
(lots of different ways)

classic pattern in concurrency
point: used to build compare solution
for example: sorting

concurrency pattern: Producer/consumer
-two processes P and C
-P ‘makes’ things, C’consumes’ them
-want to coordinate P and C
-P shouldn’t produce too much (C gets too far behind)
-C shouldn’t waste tiem waiting for P
thinks you stuffing envelope
someone is opening, someone is sealing it, someone is stuffing inside the envelope
sometimes there would be someone is really slow stuffing, and someone is opening the envelope very fast. Or there are too much paper to make envelopes, which is kind of wastes.

we want a signal say: hey hold on, when you get to some point, just stop, let other people catchup, or switch job.

-shared circular buffer for string output of P and input of C
-when buffer is empty, c should sleep?
-when the buffer is full, P should sleep?
(solution is suprising tricky)
what happen if the consumer is sleeping, the producer wake them up? don’t corrupt the buffer? how to you minimize the cost? Anil will talk about this next time.

producer consumer in real life:
‘ls | more ‘
pipe is producer, consumer, one process producer, other is consumer, there is a buffer between this two things. kernel maintain this buffer.
How does it handle the coordination?
consumer read from the buffer (stdin, stdout), kernel knows it and implement it.

Operating Systems 2017F Lecture 7

2017-10-03T20:20:59Z

CindyYu: /* Notes */

==Video==

Video from the lecture given on September 28, 2017 [http://homeostasis.scs.carleton.ca/~soma/os-2017f/lectures/comp3000-2017f-lec07-28Sep2017.mp4 is now available].

==Notes==

3000 Sep28
Next week: Anil is away from Sunday to Thursday morning. Review section.

Topic today: File system

'''What is a file?'''
It is a key - value pair.

Key: hierarchiacal filename (pathname)

value: arbitrary number of bytes

'''In principle, you can use files to store very small values'''

-most filesystems have a minimum file size of at least 1k, often 4K or more

-one byte of data wastes a lot of space

'''A set of files ‘stored’ together, sharing a common hierarchical root, is a filesystem.'''

Why quote ‘stored’ ?

- Because there is no storage for virtual filesystems (such as /proc and /sys)

when you first start a UNIX system, you start with the ‘root’ filesystem. (have nothing to do with root user.)

-But other filesystems can be put on top by "mount"-ing them.

CODE DEMONSTRATION:

Run ‘mount’

it shows‘/dev/vda1 on / type ext4 (rw, relatetime,data=ordered) ‘

- /dev is root filesystem

- / is the top of hierachy

-‘rw’ means read write

-/def/vda1 is a Special file, files in /dev are special files.

(Special files are actual files, it would be stored on disk, nowadays they are not.)

Run ‘df .’ (df is for displaying the amount of available disk space for file systems on which the invoking user has appropriate read access.)

-There is a filesystem called ‘udev’, which is a virtual file system with zero space used, since it is created automatically on run time

Run ‘who’ in another terminal

-it display ‘soma tty7 2017-09-28 12:59 (:0)’

Run ‘ls /dev’

-Instead of ''vda'', it shows ''sda''. The ‘v’ in ''vda'' stands for ‘virtual’. The ‘s’ in ''sda'' stands for SCSI (The Small Computer System Interface).

-Any device you want to access on unix system has /dev

Run ‘ls-a’ in /dev

-Looking at the permissions (e.g ‘crw--rw----’), first letter for normal file is blank , directory is ‘d’, ‘c’ is for Character Devices, ‘b’ is for Block Devices

-Character devices example: keyboard, mouse.

-What makes b-disk different?caches.

-Special files are either Character Devices or Block Devices,

-Block divce is for block storage, to cache result.

Traditional filesystems are stored in block devices

-but a filesystem can be anything that provides a filesystem interface.

'''file interface basics:'''

-open, read, write, seek, close

-open directory, read/write directory, close directory

'''Block size issues:'''

-larger blocks, less overhead(fixed overhead for each block access)

-smaller blocks, more efficient space usage(fewer files smaller than one block)

'''filesystem interface basics:'''

-mount and unmount

filesystem blocksize is a multiple of disk blocksize

How do you structure a filesystem?

'''Inode:'''

First, you have to understand inodes.

CODE DEMONSTRATION:

1.Run ‘cp lec07.txt test.txt’

-There is no different between those files

2.Run ‘ln test.txt duplicate.txt’

-There is difference between duplicate.txt and test.txt: A number for test.txt changed from ‘1’ to ‘2’. That number is inode count

3. Run ‘ln duplicate.txt alsodup.txt’

-Inode count number changed ‘2’ from ‘3’

'''ln' stands for link''

4.Run ‘ln -s duplicate.txt another.txt’

-There is no different between another.txt lec07.txt

5.Run ‘ls -la has diffrence’

-It shows another.txt -> duplicate.txt (symbolic link pointing one to the other

6.Run ‘rm duplicate.txt’

-The arrow is still pointing, but inode count number goes down. (From ‘3’ to ‘2’)

7.Run ‘cat another.txt’

-It shows there is such file, because the file that pointing to is not exist

-‘ln’ creates hard links to an item by default.

-File name is a pointer to an inodes.

-‘rm’ is not remove, just unlink, which reduces the link count for inode

-When you clear storage, when inode inbound number go to 0, is not link to other file,system will remove it.

-When the user open a file, referece count is incremented.

A file sys doesn’t have to be a block device? It can store anywhere as long as you provide the api.

A file system can be made in a file (the basic of virtual machine)

One other file api: mmap

Inode store permision

mmap, munmap: map or unmap files or devices into memory, this is the piece that unify the file sys with process memory.

What ‘read’ does: read directly into RAM

Run ‘top’

-There are ‘VIRT’, ‘RES’ and ‘SHR’

VIRT stands for the virtual size of a process
RES stands for the resident size, which is an accurate representation of how much actual physical memory a process is consuming.
SHR indicates how much of the VIRT size is actually sharable (memory or libraries).

==Code==

Code and files from the lecture (captured as they were at the end) are available [http://homeostasis.scs.carleton.ca/~soma/os-2017f/code/lec07/ here].

Operating Systems 2017F Lecture 7

2017-10-03T20:20:24Z

CindyYu: /* Video */

Operating Systems 2017F Lecture 7

2017-10-03T20:19:19Z

CindyYu: /* Code */

==Video==

Video from the lecture given on September 28, 2017 [http://homeostasis.scs.carleton.ca/~soma/os-2017f/lectures/comp3000-2017f-lec07-28Sep2017.mp4 is now available].

3000 Sep28
Next week: Anil is away from Sunday to Thursday morning. Review section.

Topic today: File system

'''What is a file?'''
It is a key - value pair.

Key: hierarchiacal filename (pathname)

value: arbitrary number of bytes

'''In principle, you can use files to store very small values'''

-most filesystems have a minimum file size of at least 1k, often 4K or more

-one byte of data wastes a lot of space

'''A set of files ‘stored’ together, sharing a common hierarchical root, is a filesystem.'''

Why quote ‘stored’ ?

- Because there is no storage for virtual filesystems (such as /proc and /sys)

when you first start a UNIX system, you start with the ‘root’ filesystem. (have nothing to do with root user.)

-But other filesystems can be put on top by "mount"-ing them.

CODE DEMONSTRATION:

Run ‘mount’

it shows‘/dev/vda1 on / type ext4 (rw, relatetime,data=ordered) ‘

- /dev is root filesystem

- / is the top of hierachy

-‘rw’ means read write

-/def/vda1 is a Special file, files in /dev are special files.

(Special files are actual files, it would be stored on disk, nowadays they are not.)

Run ‘df .’ (df is for displaying the amount of available disk space for file systems on which the invoking user has appropriate read access.)

-There is a filesystem called ‘udev’, which is a virtual file system with zero space used, since it is created automatically on run time

Run ‘who’ in another terminal

-it display ‘soma tty7 2017-09-28 12:59 (:0)’

Run ‘ls /dev’

-Instead of ''vda'', it shows ''sda''. The ‘v’ in ''vda'' stands for ‘virtual’. The ‘s’ in ''sda'' stands for SCSI (The Small Computer System Interface).

-Any device you want to access on unix system has /dev

Run ‘ls-a’ in /dev

-Looking at the permissions (e.g ‘crw--rw----’), first letter for normal file is blank , directory is ‘d’, ‘c’ is for Character Devices, ‘b’ is for Block Devices

-Character devices example: keyboard, mouse.

-What makes b-disk different?caches.

-Special files are either Character Devices or Block Devices,

-Block divce is for block storage, to cache result.

Traditional filesystems are stored in block devices

-but a filesystem can be anything that provides a filesystem interface.

'''file interface basics:'''

-open, read, write, seek, close

-open directory, read/write directory, close directory

'''Block size issues:'''

-larger blocks, less overhead(fixed overhead for each block access)

-smaller blocks, more efficient space usage(fewer files smaller than one block)

'''filesystem interface basics:'''

-mount and unmount

filesystem blocksize is a multiple of disk blocksize

How do you structure a filesystem?

'''Inode:'''

First, you have to understand inodes.

CODE DEMONSTRATION:

1.Run ‘cp lec07.txt test.txt’

-There is no different between those files

2.Run ‘ln test.txt duplicate.txt’

-There is difference between duplicate.txt and test.txt: A number for test.txt changed from ‘1’ to ‘2’. That number is inode count

3. Run ‘ln duplicate.txt alsodup.txt’

-Inode count number changed ‘2’ from ‘3’

'''ln' stands for link''

4.Run ‘ln -s duplicate.txt another.txt’

-There is no different between another.txt lec07.txt

5.Run ‘ls -la has diffrence’

-It shows another.txt -> duplicate.txt (symbolic link pointing one to the other

6.Run ‘rm duplicate.txt’

-The arrow is still pointing, but inode count number goes down. (From ‘3’ to ‘2’)

7.Run ‘cat another.txt’

-It shows there is such file, because the file that pointing to is not exist

-‘ln’ creates hard links to an item by default.

-File name is a pointer to an inodes.

-‘rm’ is not remove, just unlink, which reduces the link count for inode

-When you clear storage, when inode inbound number go to 0, is not link to other file,system will remove it.

-When the user open a file, referece count is incremented.

A file sys doesn’t have to be a block device? It can store anywhere as long as you provide the api.

A file system can be made in a file (the basic of virtual machine)

One other file api: mmap

Inode store permision

mmap, munmap: map or unmap files or devices into memory, this is the piece that unify the file sys with process memory.

What ‘read’ does: read directly into RAM

Run ‘top’

-There are ‘VIRT’, ‘RES’ and ‘SHR’

VIRT stands for the virtual size of a process
RES stands for the resident size, which is an accurate representation of how much actual physical memory a process is consuming.
SHR indicates how much of the VIRT size is actually sharable (memory or libraries).

==Code==

Code and files from the lecture (captured as they were at the end) are available [http://homeostasis.scs.carleton.ca/~soma/os-2017f/code/lec07/ here].