· 8 years ago · Dec 11, 2017, 07:22 PM
1# CS 439H
2## Gheith's spinLock
3```c++
4class SpinLock{
5 Atomic<bool> isTaken = false;
6public:
7 lock(){
8 while(isTaken.exchange(true));
9 // exchange returns value at location
10 }
11 unlock(){
12 isTaken.set(false);
13 }
14}
15```
16If ```isTaken``` is true to start with you will just an infinite loop. If initially false, and is changed to true and that is returned, we know we are allowed to go and do work.
17
18## Semaphore
19```c++
20class Semaphore {
21 uint32_t count;
22 Queue<Thread> blocked
23public:
24 Semaphore (uint32_t count) : count(count), blocked(new Queue<Thread>());
25 void down(){
26 if (count == 0){
27 blocked.add(Thread::current);
28 Thread::yield(); // don't add self to readyQ
29 }else{
30 count--; // being atomic would not help much
31 }
32 }
33 void up(){}
34}
35```
36You cannot surround ```down()``` with a lock i.e.
37```c++
38lock.lock(){
39
40}lock.unlock
41```
42System would spin, and there would be no way to unlock the lock. Semaphore would be done with.
43Must build mechanism to release the Semaphore
44
45
46```c++
47//down:
48lock();
49if(count == 0){
50 blocked.add(me);
51 unlock();
52}
53```
54Thread A is running the former. Around the same time Thread B (runs the latter) gets spinlock and tries to help Thread A onto the readyQ
55```c++
56//up:
57lock();
58if(someoneIsWaiting){
59 readyQ->add(someone);
60}
61```
62* What if someone changes ```count``` while a thread is trying to block.
63 * Run yield before unlock, and only unlock if yield is successful
64 * Add a new **DND** state that tells other threads not to bother you. Allowing you to finish your job
65
66
67Create idleThread for cores to run when they have nothing to do.
68```c++
69if(first){
70 // .
71 // .
72 // .
73 kernelMain();
74}else{
75 while(true)Thread::yield();
76}
77```
78```currentThread``` using ```PerCPU```
79
80Figuring out who you are using ```SMP::me()```
81
82## Other uses of Semaphores
83### Networking
84* Consider multiple threads running on server, producing data
85 * Called **Producers**
86* Consumers, or workers
87 * pick up what the produceres output and do work on given data
88 * Called the Producer/Consumer problem
89* Any data structure that does not forget, like a Queue, sits between them
90 * Keep it atomic
91* Put backpressure on Producers (flow control)
92 * When consumers cannot handle work they tell Producers to ```Stop It```
93 * Have to be able to tell Producers to wait if the finite-queue is full
94
95### Bounded-buffer
96Can handle the Q and telling the sender a status
97```c++
98template<typename T, int N> //N is # of elements in buffer
99class BB{
100 T data[N];
101 void put(T e){ ... }
102 T get(){ ... }
103}
104```
105* Both ```put()``` and ```get()``` are able to block
106 * In the scenario that the buffer is full on ```put()```, or if the buffer is empty on ```get()```
107 * Must have two flags instead of semaphore to say whether semaphore is empty/full
108```c++
109class B <N>{
110 Semaphore nEmpty = N;
111 Semaphore nFull = 0;
112 Semaphore lock; // just used for protection of data structure, could also be a spin
113
114 put(T e){
115 nEmpty.down(); // if nEmpty is 0, then you block
116 lock.down();
117 // need an atomic Q
118 // .
119 // . compete over it
120 // .
121 lock.up();
122 nFull.up();
123 }
124
125 T get(){
126 nFull.down();
127 //compete over the Q
128 nEmpty.up();
129
130 }
131}
132```
133By competing over the semaphore, we know that the right number of threads are allowed in.
134```c++
135lock.down();
136// need an atomic Q
137// .
138// . compete over it
139// .
140lock.up();
141```
142This is simply a thread safe Q
143
144### Example of bad put and get
145```c++
146//put:
147lock();
148nEmpty.down();
149//.
150//.
151//.
152nFull.up();
153unlock();
154
155//get:
156lock();
157nFull.down();
158//.
159//.
160//.
161nEmpty.up();
162unlock();
163```
164By swapping pairs of commands, we can be deadlock free
165
166## Barrier
167```c++
168Barrier(int n) : n(n){}
169void sync(){
170 //up to n - 1 threads can sync
171 //nth thread makes every other thread wake up
172 n = n - 1;
173 if(n.add_fetch(-1) == 0){
174 wait.up();
175 }else{
176 wait.down();
177 wait.up();
178 }// add check to see if less than 0 for invariant
179
180}
181```
182## Monitor
183```c++
184Monitor_bounded_buffer{
185 condition queueIsNotFull;
186 condition queueIsNotEmpty;
187 //gurantees mutual exclusion
188 void put(T v){
189 [lock]
190 while(queueIsFull()){
191 [unlock]
192 wait queueIsNotFull; // wait is a keyword
193 [lock]
194 // condition is pulse not a state. have to wait for the signal
195 // once out of wait we know q is not full
196 }
197 signal queueIsNotEmpty;
198 }
199 T get(){
200 if(queueIsEmpty()){
201 wait queueIsNotEmpty;
202
203 }
204 <<is not empty>>
205 // do stuff to get from queue
206 <<isNotFull>>
207 // q cannot be full since something is removed
208 signal queueIsNotFull;
209 // hand off lock
210 // what if I want to continue doing work here
211 }
212}
213bounded_buffer{
214 synchronized void put(){}
215 synchronized void get(){}
216}
217```
218* Have to say synchronized
219* Would be a good alternative that upon wake up you hand off the lock
220* When signaled, the lock is given away to other monitor so no one can sneak in and change the state
221* When singaling, we expect the other monitor to check the state of the Queue
222### Problems
223* If want to work after I signal
224 * just make it illegal to work after the signal
225* actually very difficult to atomically unlock and then wait
226 * if not atomic there will be race conditions
227
228### Fundamental Problem
229* Nested Monitor Problem
230
231## P6
232For every data structure we have to ask ourselves:
233* is it global
234* per per thread
235* per CPU
236Try to make everything per thread.
2371. Examine every data structure in P4 and check what scope it can have
238* active thread ptr, should be per core
239 * use PerCpu to get
2402. Figure out locking mechanism
2413. Find shortest time needed to hold the lock, otherwise race conditions will arise
242```c++
243if(readyQ.isEmpty()){
244 // stuff
245}
246```
247Need lock to preserve invariants. Want to presrve the fact that the Q is empty while dealing with the Q (that is supposed to be empty)
248### Semaphore details
249```c++
250//down:
251spin.lock(); // lock should be of the same scope as the data structure
252if(count == 0){
253 waitingForMe.add(Thread::current());
254 // cannot unlock here because thread could be picked up before contextSwitch happens
255 // set state that youre in the state of blocking
256 yieldButDontReady(); // without unlock its a deadlock
257}
258//up:
259spin.lock();
260```
261Ask next thread on readyQ to unlock for you
262* Use the callback class
263
264### Deadlocks
265Dining philosophers problem
266Reason for deadlocks
2671. Mutual exclusion
268 * avoid this to never have deadlocks
269* Things don't exclude each other from getting work done
2702. Hold and wait
271 * Someone holds a resource and prevents others from using it
272 * never grab more than one thing at a time. Set one lock at a time
273 build hierarchical locks
2743. Non-preemption
275 * notion of transactions so that there is some history of some transaction
276 * 2 phase locking
277 * get all locks up front.
278 * You tell me all the locks you want, in any order you like. Go through phase where we get all your resources. While doing this, if system detecs a deadlock, it can take away resources to give to someone else. Then later these resources can be given back.
2794. Cycles
280 * cyclical waiting
281 * change natural order and remove one
282
283If we construct of resource graph, and we have a cycle, we immediately have a deadlock.
284
285Have to start implementing tech for recovert
286## Midterm
287```c++
288monitor BB{
289
290 condition c1;
291 condition c2;
292 /* cannot tough condition from outside */
293
294 void m1(){
295
296 }
297 void m2(){
298 if(notHappy) return;
299
300 }
301}
302```
303
304```c++
305class Barrier{
306 Atomic<uint32_t> ctr;
307 Semaphore wait;
308public:
309 Barrier(uint32_t ctr): ctr(ctr), wait(0){
310
311 }
312 void sync(){
313 if(ctr.add_fetch(-1) == 0 ){
314 // terminal state
315 wait.up();
316 }else{
317 wait.down();
318 wait.up();
319 }
320 }
321}
322```
323
324```c++
325monitor Barrier{
326 condition allHere;
327 uint32_t ctr;
328
329 void sync(){
330 if(ctr == 0) return;
331 ctr--;
332 if(ctr == 0){
333 signal allHere;
334 }else{
335 while(ctr != 0){
336 wait allHere;
337 }
338 signal allHere;
339 }
340 }
341}
342```
343
344```c++
345sem2.down()l
346bool isSecond = firstIsHere(true);
347if(isSecond){
348 y = data;
349 secondIsHere.up();
350 xIsReady.down();
351
352 return x;
353}else{
354 x = data;
355 xIsReady.up()
356 secondIsHere.down();
357 T temp = y
358 sem2.up();
359 return y;
360}
361```
362
363## P8
364* Program
365 * file with executable things in it
366 * file
367 * bytes that belong together that can be written to and read from
368 * executable
369 * has meta-data that describes the contents of the file
370 * magic number
371 * headers that show what needs to be loaded from memory
372 * most linux exec.'s are ELF files
373 * data
374 * instructions
375 * after being read in, executable is converted to a process
376 * process is a program loaded in memory
377 * give it a thread
378 * set address space
379 * n/a
380 * fork
381 * creates copy of process
382 * copy will have a different pid
383 * when copy returns it returns again (since it is a copy of running process)
384 * ultimately they run independently
385 * has ppid (parent pid)
386```c
387int id = fork();
388if (id < 0){
389 /* parent,
390 no child, failed */
391 printf("%d\n", errno);
392}else if(id == 0){
393 /* child */
394}else{
395 /* parent */
396 /* id is the child pid */
397}
398```
399
400### exec
401start running new program from entry point ```exec???("gcc",...)```
402
403### wait
404wait(...)
405waitpid(. ) - parent waits (join)
406### system calls needed for p8
407fork
408exec
409wait ( family )
410kill
411alarm ( read about these )
412open (files )
413creat
414
415-o -e: fork, open files, change stdout/err,
416
417# Virtual Memory
418We have managed to get processes to run in parallel etc.
419Now what we want to do is
420* Give the illusion that they are using the full address space
421* Also want to isolate them from other processes
422* That there is more virtual than physical memory
423 * give 64MB but make it seem that there is 4GB
424* less virtual memory than physical
425* demand paging
426 * Only bring things into memory when they are requested.
427 * Don't have memory so will have to kick someone out
428* protection
429 * mechanism that allows reading but not writing
430* optimize program loading
431 * thanks to demand paging, don't have to load the whole thing
432* copy-on-write (COW)
433
434### MMU (Memory management unit)
435Handles the memory mapping for different processes
436Takes an address (virtual address) and outputs an address (physical address)
437* base register is added to virtual address and creates physical address
438 * this is a simple memory management method
439 * depending on the process running, you put different values in the reigster
440 * doesn't achieve isolation
441 * typical solution is to add a limit register which specifies the highest limit on how much memory one can use
442 * have a compare circuit that checks the virtual address with the limit. if VA is greater than limit we throw a segmentation violation
443 * cannot do demand paging though
444* When the system resets, the "trustMeImTheKernel" register is set to 1
445 * This needs to be set to 0 right before a user program called
446 * Hardware has to implement switch of this register on call to kernel
447 * In x86 there is a CPL, which is a number from 0-4
448### Problems with external fragmentation
449Cannot have some number of registers that have multiple bases
450* What if we just split up the address space into equal sized blocks of 1 MB
451 * make pages 1000 B
452 * VA = 1700
453 * virtual page # (VPN) = VA / page size = 1700 / 1000 = 1
454 * By restricting page size to a power of two, all you have to do is shift by $\log_2(\text{pagesize})$
455 * Now how do we get the physical page number?
456 * (PPN, ok) = MMU(VPN) for some function in the MMU
457 * "ok" tells you whether there is an actual corresponding page number
458 ```c
459 (ppn, ok) = pageTable[vpn]
460 // with multi level (ppn,ok) = PD[l1][l2]
461 if(ok){
462 pa = ppn * pagesize + offset;
463 }else{
464 pageFault
465 }
466 ```
467 * PA = PPN * pageSize + offset
468 * in this case... offset = VA % pageSize
469 * **All these calculations are done by the hardware**
470 * in x86 the head of the multi level tables is called the page directory (PD)
471 * children are called page table (PT)
472 * the whole thing is also called the page table (PT)
473 * for context switching, a register is dedicated to pointing to the page directory
474 * this register is called CR3
475 * PDE is a page directory entry (x86)
476 * contains PPN of following PT
477 * stored in high order 20 bits
478 * starting at the least significant bit:
479 * present bit. 0 = invalid, 1 = valid
480 * RW, read/write, 0 = read-only, 1 = write
481 * US, user supervisor, 0 = supervisor (CPL == 0 [most privileged process]), 1 = user
482 * D, dirty, if a program is writing to this PDE hardware will set the dirty bit.
483 * A, accessed, 0 = has not been accessed, 1 = has been accessed
484 * Redirects us to a PTE, this has the same flags as the PDE
485
486
487## Page Tables
488Cannot have a table with an entry per memory address.
489So we increase the page size; however, now we increase the page size.
490* Physical pages
491 * AKA
492 * page frames
493 * frames
494 * physical frames
495The table index is representative of the VPN, while the returned value within the table is the PPN
496Don't use magic values for things being empty etc.
497* TLB
498 * translation look-aside buffer
499 * cache of finite size. while traversing page table (walking), answers are put in the TLB
500 * TLB holds the VPN & PPN (along with extra bits)
501 * every core has its own TLB
502 * only way virtual memory actually works
503 * TLB is not aware of modification to the Virtual Memory
504 * x86 has INVLPG instruction which clears TLB page address
505 * TLB shootdown, have to go invalidate other TLB if there are multi processors
506
507# User process
508Need to give it some address space - give it a tree
509* Have to have a loader
510 * The thing that reads ELF file
511 * This action sits behind exec
512## Disk
513 * is a just an array of sectors
514 * used to be 512 byte sectors
515 * in modenr times the sectors are 4k
516* Put files in a tree
517 * Files in this hierarchy have permissions (and other things)
518 * files are first created in a sector, where the last 4 bytes are a pointer to the next sector containing more data
519 * the super block has information about where the information about the file system is
520 * This is usually stored at the beginning of the file system
521 * meta data
522 * file name
523 * starting block
524 * size
525 * permissions
526 * type
527 1. directory
528 2. file
529Similar to virtual memory. The offeset in the beginnin gets you into the file sytem to get the first sector of the file
530## i-node
531* mode
532* type
533 * regular
534 * directory
535* size
536* ~~pointer to some block 0, for a file~~ direct block
537 * if overflow use indirect block
538 * after that we have an even deeper one (3 levels of inderection)
539 * block that points to block that points data block
540## ext2 filesystem
541* has **super block**, needs place to store indoes and data blocks
542 * hence there exists an i-table, which is full of inodes
543 * the index of the inode will tell you which one it is in the table
544 * i.e. the inodes are acutally stored in the itable, there aren't any pointers there or anthing
545* often one will run out of inodes, even though there is a lot of storage space left
546* file system memory
547 * super block
548 * the ~~following data~~ super block and following data is called a group and repeats multiple times
549 * to know where there are entries in the i table we have a **i-node bitmap**
550 * the bitmap is at the beginning of the filesystem somehwere right arond where the super block is
551 * **data bitmap**
552 * is after the i-node bitmap
553
554* IDE
555 * integrated device electronicse
556* mounting a filesystem is similar to opening a file
557 * mount opens the device, looks for superblock (index 0), make sure it is "bobfs"
558 * questions, does inode represent file, directory, how many bytes are there in the file, how many things point to the inode
559* every system has certain end of file activty
560
561## size of i-table
562consider block size of 1kb
563on disk we have
564* super lbock
565* data bitmap
566* inode bitmap
567* itable
568* data
569
570number of inode = $2^10$*8 = 2^13 = 8kb sinode
571bytes per itable = 2^13 * 16 = 2^17 = 128k
572blocks per itable = 2^17/2^10 = 2^7 = 128 blocks
573number of data blocks ≤ 8k
574max data ≤ 8k (data blocks) * 1kb (block size) = 8MB
575can store 8k - 1 files since we have to reserve one for a the root
576
577* what is the largst file you can have?
578 * depends on levels of indirection, we only have one
579 * in a our first indirect block we can have 256 more blocks, plus the single direct block
580 * we can have 257 blocks representing a signle file
581 * largest possible file = 257 blocks = 257 kb
582 * total space = 257k data + 1k indirection block + 16 bytes for inode + 258 bits for data bitmap + 1 bit for inode bitmap
583 * actual data
584 * 257k data
585 * over head
586 * 1k indirection block + 16 bytes for inode + 258 bits for data bitmap + 1 bit for inode bitmap
587* i nodes don't have names, don't know what their name is when inside the block
588* linux only allows one link going into files
589 * directories can only have one name so .. can simply list parent by name
590 * some entries in directories contain files while others point to other directories
591* files
592 * can have as many links to them as they want
593
594devices are access by ```mount <what> (/dev/sdl) <where> (/volume/backup) ```
595* Two types of devices
596 * block devices
597 * character device
598 * networks are kind of another, kinda like a character device
599 * graphics have their own special behavior too
600## i node
601there are different types
602* special node
603 * needs to know how to lie about file system operation
604 * store major and minor number inside special i-node
605 * major number represents the device you represent
606 * minor number
607
608# Multiple groups
609* order of design
610 * super block
611 * group descriptor
612 * block bitmap
613 * inode bitmap
614 * inode
615 * block
616* i-node
617 * mode (2 bytes)
618 * first 4 bytes, file directory, link, BLK, CHAR, socket
619 * last 12, permission
620 * owner (2 bytes)
621 * user will have UID
622 * owner GID (2 bytes)
623 * size
624 * block 0- 11
625 * one level
626 * two level
627 * three level
628 * gen
629 * a time ( 4 bytes ), data
630 * last time accessed
631 * m time ( 4 bytes ), data
632 * last time modified
633 * c time, i node
634 * ?
635## Process
636read, write,
6379 bits, 3 apply to user, 3 apply to group, 3 apply to others
638* user
639 * rwx
640* group
641 * rwx
642* others
643 * rwx
644* 3 more bits
645 * set uid, can run with privileges of uid given.
646 * sticky bit was a hack at first
647 * tells the kernel that something should stick in memory (usually runs a lot)
648access control list - list of actors/processes allowed to modify resources/ passive entities
649* fd is index into file descriptor list
650```int fd = open(name, flags, node)``` fd represents the "capability box" which has to be signed
651
652general form of capabilities
653* who
654* what
655* whom
656* when
657* where
658
659f = m^p mod n. signature is f.
660
661entries
662* name and a correspodning number
663* ability to read something is the ability to read these entries
664
665# Distance from hardware
666Python vs C.
667C is not safe because classes can stop being classes etc.
668
669* Rings
670 * Hw
671 * Ring 0
672 * supervisor, kernel
673 * trap, interrupt (software interrupts), faults, aborts
674 * TSS - task state segment
675 * stack will have 3 more pointers to 3 other stacks
676 * TSSR points to the TSS (TSSR is protected)
677 * IDTR points to IDT
678 * who ever writes the system says where to point to when you have a page fault
679 * it is exactly like signals at the hardware level
680 * ring 1 (CPL 1)
681 * Ring 2 (CPL 2)
682 * Python runtime
683 * ring 3 (CPL 3)
684 Whenever there is an iterrupt, the harware decides whetehr its witching stacks. and if so it saves all the stack information (whichi si two parts, area where stack lives).
685 NOw its safe to switch stacks since we know its safe to switch. Nothing is pushed to the user stack, it is not trusted.
686 * EIP (3)
687 * CS (3)
688 * EFLAGS (3)
689 * ESP (3)
690 * SS (3)
691Trap and interrupt are very similar in structure.
692
693# IDK
694there are virtual machines and containers.
695* Containers grab a process and tell the machine that they are actually a different operating system.
696* can create a jail, so that we make a seperate file system specific to a single process within a file system
697 * command called ``chroot`` in unix
698 * once in jail, cannot get out
699 * problem is that PIDs are system wide
700 * keep mapping inside kernel
701
702process dfines an adress space, that is the virtual memory for that process
703process is also something that runs, so it better have a thread that executes. and that thread should know who it belongs to
704what ever reosuces that belong to the process, semaphore, etc. this is where file descriptors would go etc.
705the process class better tie all of this together
706
707user level process is similar to kernel level thread - also ask yourself where it gets the stack from?
708# TODO
709Read about phantom references
710check page 872
711783 - mkdir, rmdir, link, unlink ( read this )
712iret