BSD-UNIX
university of california
bell labs
Time-sharing

clock algorithm / second chance algorithm
   circularly linked list
   walk incircle, check ref of pages (if set clear)
   if reach page wi/out reference, means it wasn't accessed so kill it
   second chance

  concurrency issues...

block devices - hard drives -
character devices - keyboard, mouse, /dev/null
sockets - pipes (named, unnamed), network socket ex. tcpip based ....

modem  = character device
freebsd = complete & free...

MOCK
//carnagie mellon
where all processes are in user space

microkernel root;

pg 125 dinosaur
   ports in mach (like mailbox)

NUMA

xNU = X (not unix) kerenel for mac
   freebsd but for mac
   from freebsd, took:
         process model,
        network stack,
       virtual file system

  from Mach, took kernel

RealTime

Real time is where computation has to be done by deadline

Hard Realtime vs. Soft Realtime

ex: windows or linux or bsd or solaris

      some kind of real time guarantee (not strong)

Hard realtime - embedded devices

EX walking robot adjust balance

   System on Chip

NVRAM  = power persists despite power outage. solid state drive 

Real Addressing mode

Logical address IS Real address

Relocation register

   just adds offset to real address

Lynx OS

priority inheritance and inversion

no on demand paging

Preemptive vs. Reentrant

all kernels are reentrant, but not all are preemptive

Preemptive will stop for something mid-task,

Reentrant just makes a note of something

for real time, should be preemptive

  preemptive lends itself to bugs like race conditions though.

priority based scheduling

n * ( 2 ^ (1/n) -1 )

where n is number of processes

Earliest deadline first

(….rate monotonic scheduling … ??)

Microkernel - one small kernel that does limited amount

basically just passes caller's request to function

work for realtime systems

ex: tinyOS

OpenBSD called me a Burrito Brain...

Only made root at first. Had to do the following to add smargonz user (openbsd)


adduser smargonz
sudo user mod -G wheel smargonz

http://www.bleepingcomputer.com/forums/topic127237.html
http://www.openbsd.org/faq/faq10.html#wheel
http://bsdsupport.org/2007/04/q-how-do-i-add-a-user-to-the-wheel-group-in-openbsd-or-netbsd/


Using emacs equivalent "mg" text editor.
      Shortcuts listed here: http://www.openbsd.org/cgi-bin/man.cgi?query=mg


Part 5 tip - use malloc, find when slow calls occur, count bytes between them.
      http://discuss.joelonsoftware.com/default.asp?interview.11.520685.12

Virtual File System
inode vs file descriptor
422         425

examples-
inode created for pipe put in fd

Contiguous allocation
    - block of hard drive allocated to file
    - not common, external frag is issue

Linked allocation
     - works like linked list
     - allocate blocks
     - read block, also read pointer to next block
     - can't randomly access file (have to trace it )
   linked allocation makes optimization difficult (different spots on disk so have to physically  move)

indexed allocation
     - Linked Scheme
              straightforward way, you know where blocks are
     - Multi Level Scheme
               like multi level page tables
               indices of indices
     - Combined Scheme  **LINUX**
             
...............................,,,,,.................
worry about concurrency
deadlocks

page cache block
      - 4kb blocks
Swap cache block
     - good way to avoid race conditions
     - try taking away each process's mapping then schedule out harddrive........errrr, what......
      - 4kb blocks

Buffer cache
     - not like other two @ 4kb chunks , chosen when formated hd
     - have to block read requests of user space processes til we know we have the blocks of data that we need
     - slower


===================
loop back device

dd copies raw bytes (careful, can screw up your disk)
     dd if=/dev/zero of=myhardriveimage.img bs=1024 count=81920
     makes 80 meg hardrive image of 1k blocks with input file if and output file of

sudo losetup /dev/loop0 mylhardrive.img
     loopback that allows us to pretent fils on other filesystem are devices themselves
   
journaling filesystem started with ext4 that tracks allocation of space to files
can go through journal if power is yanked, treat as atomic statements

ls /mnt/

sudo mount -t ext3 /dev/loop0 mnt/myfilesystem/
df -Th
         (gives info on filesystem)
cd mnt/myfilesystem/
sudo dd if=/dev/urandom mybigfile.bin
     (will eventually run out of space)

sudo debugfs /dev/loop0
ls
stat mybigfile.bin
    can see inode for mybigfile.bin
    inode number
   

Midterm Review

open book, open note, no devices

1. buzz words : spacial, temporal locality;
    memory hierarchy : cpu (has registers in it) --> L1 cache-->L2 cache --> DRAM
    all ^ have own physically addressed space
    off to side, some harddrive
    gets slower but bigger as we go down
    spacial - will move whole 512 block data - move in blocks
    temporal - leave in memory thinking we will access again soon.
2. buzz words: multiple queues
    there's always something being done
    concurrency
    if more than one request for one resource, kernel can optimize
    pg 103 dinosaur book
    w/premptive, timer goes off
decide which schedulers are preemptive
shorted job first
red-robin
mlevel feedback queue
 user level threads work...how
    can manage them anyway you want
    for portability
   
    won't have to stay in waiting to a
    anytime you have interrupts,  you have conccurrenciy ->  have race conditions ....??
    consider 1. Load,  2.Inc, 3.store.

    Producer  onsumer
    interrupt handler
    puts in buffer, returns,
    buffer interrupted/changed  mid -read

   how might you get extra bytes?
    if interrupt is interrupted by another one, waiting
//   race conditions can  have many levels of ...

     mutex, semaphore, critical section

3.  how do we know it's not a deadlock that's crashing?  (look at deadlock chapter... need all for conditions for deadlock) priority inversion, priority inheritance

4.

5. 4 kb --> not to big/small,
    buzz word: fragmentation, spacial locality,
    if we can bring in whole 4kb page, fewer page faults
    external fragmentation-

segmentation = > have physical memory, using chunks all over. Need more memory, but don't have large enough contiguous (continuous) memory. this is why we do paging.

virtual addressing
10 10 12
            ^ sorta naturally becomes address for 4kb page : 2^12 = 4098
           (nice num to work with)


//"northbridge"... connects DRAM

Hello World ubuntu

Hello world in c

• linker and loader
• gcc helloworld.c -o helloworld -g
• g gives debugging 
• default in ubuntu doesn't have current directory in path
• good for security reasons

Shell is just user space binary (shell searches for executable, for instance, not kernel)

ps -el |grep hello

    tell if ptrac attached to process

               ptrace doesn't affect process at all

xless -S /proc/4DIGPROCESSNUM

       shows virtual space of helloworld binary

       last 3 nibbles are 0s. why? ...page if 4 kB = 2 ^12....

       maps to one page

readable and executable will be in .tech section 

      

       gdb ./helloworld

      disas main

in gdb: disas main

in gdb: x/10c addressgoeshere(for the movl one)

    10 characters

x/3i addresshere

    3 instructinons

break *ADDRESSHERE

global vars in .data

heap & stack, trying to view gdb (perhaps has heap)

if try acces memory between /usr/bin/gdb and heap (nothing there), page fault. 

ask for memory with malloc. if not enough space and has to grow the heap, will execute sbrk system call

if ask heap to grow, will kernel give us new page table mappings?

          probably not. linux = lazily as possible. wait until necessary to do something

          

if request when virtual memory only (not mapped to physical), traps to kernel, which looks at which process was running when occurred.

  

            99.9% page faults NOT 6segv

            

how userspace ...maps memory

stack grows down.

ubuntu randomizes where things go

man strace

linker loader in user space

in gdb: catch syscall

     will break for any system call

i r (shows registers)

eax register holds value - number assiciated with writesys (write system call)

gdb parent hw

screen parent gdb

bash parent screen

system calls have return values stored in eax register 

sudo netstat | less

     ...

  NEXT: 

process scheduling

plt, global offset table

Architecture Review - Rough Notes

Page tables & TLB & System Calls

32 bit virtual address :     10 --------10 ------------12------

if paging on in processor, every pointer has to be translated to physical address.

linux will create virtual address for physical if it doen't have one

ControlRegister3 (CR3) register is base of page table

change which virtual address we're in

CR3 protected (cant' change from user mode)

thread vs process - threads share addresses

"kernel level thread" = lightweight processes = share address space

when kernel changes from one process to another, changes cr3

for any process, first-level page table exists (4kb = 2 ^ 10, but each 4 bit word, 1024 entries)

How paging works:

first 10 bits used as index into first level pg table

first level - supervisor bit, user or kernel permission, valid bit,

everything done in lazy way - kernel won't put something in memory until absolutely necessary  

first level pg table is valid pointer to 2nd level pt table

get pointer out of second (if valid/accessible/etc) 

VM_struct

list of all diff pieces of virtual memory

page faults

expanding stack (3 pg tolerance)

bogus ptr

mapped memory - trying to write to library example - permissions

sbrk - system call to resize heap

if mapping gone (if process hasn't used process in long time, kernel writes a page back to disk)

thrashing 

os moving pages 

SWAP

ext4 filesystem

precise interrupts

stack grows backwards in virtual memory in x86

//////////

Table LookAside Buffer

Replaces need to look at page table (unless page fault)

x86 has to worry about what - 

have to flush it if switch to new process

virtual to physical address mappings aren't the same from process to process

some (not x86) can tag & choose to not use those TLB entries

Context Switches & System Calls

processor can give up cpu by doing system call

System Call

exception = specific to process 

interrupt = 

int(errupt) 0x80

paging system keeps user in 'is place!

Back to pg tables: 

"Copy on Write" - when you fork child, shares everything w/ parent (binary, permissions, etc)

makes separate pg table for each child.

optimization

when parent and child write to same page, shouldn't be able to see each others' writes

perl python ruby code usable

C

process scheduling

less /proc/588/maps  

look atthis to understand diff mem structures are & virtual space.