ML: Week 1

• Supervised Learning

  • Regression(Continuous value)
  • Classification(Discrete value)

• Unsupervised Learning

Features

Infinite features

“Batch” Gradient Descent

Each step of gradient descent uses all the training examples.

Normal equation method

Note: Analysis

###5.3 Unbound Universal Quantifiers

####5.3.1 Generator Axioms and Exploding Scopes

####5.3.2 Omitting the Generator Axiom

###Question

1. What about

   module analysis/paramSets [t]

2. every relational expression in Alloy has a value

###Feb 28 Class

####Universal existential quantifier

some $x_0, x_1 ... x_{n-1}$ | all $y_0, y_1 ... y_{m-1}$

Using the bound of n will be sufficient.

####The monadic fragment

constraints:

• pred calculus
• only unary relations(K)

Bound: $2^k$

Mar 5 Class

Syntax v.s. Semantics

See my written notes

Mar 7 Class

domain v.s. co-domain:(Universe: 1,2,3,4,5,6…)

• domain: 1 ,2 ,3 ,4 ,5 ,6…
• co-domain: 1, 4, 9, 16…

Instance:

• atoms
• functions
• relations

Propositional logic(boolean logic)

Mar 10 Class

Not symmetric

run 3 expect 1

What about the algorithm for Aluminum?

Note: Weenix

###Processes and Threads

####Thoughts

1. How different functions interact with each other is really hard to figure out. - First time working on such a large code base.
2. Thread should always be in some queue, or it will never be run again.
3. In our model, do_exit and kthread_exit are the same because we only have one thread each process. Things will change if we have multi-threaded processes.
4. proc_kill and proc_kill_all are only for sys_halt. So maybe we don’t care about the return value?

####Keep in mind

1. the thread kthread_destroy destroys should not wait in any queue.
2. when cleanup, just destroy the struct is not enough, need to delete itself from the list.
3. don’t forget to use the p_wait queue.(in do_waitpid and exit)
4. test all the features that you had, don’t presume that you are doing it right.

5. idleproc-> first process

   initproc-> second process

####Questions

1. Why the data structure for kernel stack and context in thread are different?
2. retval == NULL?
3. do_exit works now because there is only one thread, what if MTP

4. why can I make myself runnable and switch to other process, the kt_wchan is not NULL and should fail the KASSERT

   When curthr acquire the mutex, it’s waitq will contain nothing! It’s acturally on the state of KT_RUN. Only when it’s waiting for a mutex will it be on some waitq.

5. exit a thread(use return or use kthread_exit)?
6. return value minus?
7. examine in sched_switch if nextthread == currentthread?

###Drivers

####Keep in mind

####Questions

1. Why is it that if I delete something, the last char kept showing up

   Delt with using a different dbgq.

2. How to handle the case about ckdtail and rhead.

   off by 1 issue

3. Why we only need to lock the rlock in n_tty_read?

4. How to deal with full buffer?

   discard the newly inputted character

5. How to acknowledge interrupt?

   dma_reset(see dma.h)

###VFS

####Keep in mind

1. the difference between file_t and fs_t
2. a lot things missing for do_open
3. vput when error in namev
4. the pairing between *get/ *ref and *put

• vnode->lookup: error -ENOENT
• namev:lookup error -ENOTDIR

####Questions

1. what does it mean if f_pos == -1
2. figure facq and vn_ops->acquire
3. what about vfs_is_in_use
4. readdir
5. how to initialize p_cwd in proc_t
6. deal with const char **
7. how to kmalloc in namev
8. any other elegant way to examine if it’s directory
9. dir_namev algorithm
10. About returning EPERM: vfs_test:292
11. vnode->mknod only get the file for special devices, When and how to initialize the corresponding vnode?

###S5FS

####Keep in mind

1. pin and unpin page frames when there’s a chance to block

   Even if the blocking operation is not operating on the same page frame

   Guard around blocking operations

2. mark page frame busy when in the middle of a state transitions
3. watch out for the return value from pframe_get_resident
4. pframe_migrate: read it later
5. dirty the page when the content is modified
6. the block acquired from s5_alloc_block is uninitialized
7. watch out for vn_len, it can change when write to the file
8. every time you modify an inode, even it’s just modifying the linkcount, dirty it!
9. there’s no bug with linkcount!!!
10. always check that the size of dir is a multiple of dirent size
11. I add a panic in s5fs_mkdir when there’s no space, it should be removed once I’m sure there is no bugs
12. pinned page is allocated
13. off_t is signed int
14. the contents of block corresponding to s5_alloc_block are undefined
15. block number cannot be 0, but inode number can be 0- it’s the root directory

####TODO

1. s5_link: linkcount on inode_child
2. watch out for linkcount: it should always be greater than 1
3. Add lock mechanisms in s5fs.c
4. add more KASSERT for s5fs_mkdir(check the linkcount)
5. check around s5_seek_to_block(it takes in an offset not blocknum and check the offset is not exceeding the file size)
6. the block acquired during seek_to_block of inode is memseted, what about file data block
7. check all funcions that are calling s5_write_file
8. lock the vnode if it will block

• assert at the end of mkdir
• decrement linkcount at s5_remove_dirent

####Questions

1. pframe_alloc: what if the pframe is already resident
2. what’s the semantics of pframe_fill
3. what is the layout of vnode, s5fs, mmobj, pframe
4. when should I dirty a page frame?
5. should I pin the pframe in pframe_get when the pf is busy
6. am I doing the right thing when get NULL from pframe_alloc call pageout deamon
7. there’s a potential in pframe_get that it falls into infinite loop of calling pageout deamon
8. why pin inodep then dirty_super in s5_alloc_inode
9. what to do in s5_seek_to_block when indirectblock is 0
10. check seekptr valid- should I do it in s5_seek_to_block?
11. how to dirty the page frame that particular inode is residing in
12. nice extension for s5_remove_dirent?
13. can we always assume that vnode->vn_len == inode->s5_size
14. about linkcount, 0 or 1
15. the order of pin, unpin, dirty

###VM

####Questions

1. any other things for vmmap_destroy?
2. vmmap_find_range: page starts at 0?
3. why it’s in page resolution instead of byte
4. why unexpected kernel page fault is bad in Weenix
5. how to differenciate anonymous object and shadow object

6. when to pframe_pin the pages for anon obj(I guess it should be during mmap)

   during mmap(the first time we get the pages for the anonymous object)

7. what’s different between shadow_put and anon_put
8. the realation and operation with mmo_vmas

###TODO

1. Review the refcount with anon

   no problem with refcount

2. still pretty shaky about mmo_vmas field, try figure it out

   now have a better understanding

3. ref the mmobj when initialize the vmarea

   done during vmmap_clone

4. watch out for mmo_shadowed field for shadow object
5. Review vmmap_read and vmmap_write, sys_read and sys_write

###Ask

1. the infinite loop
2. kthread stack

####If I have time

• S5_NAME_LEN off by one
• s5fs shutdown and restart bug
• eatmem fail in Dynamic

Note: Processor Management

###5.1 Threads implementations

####5.1.1 Strategies

#####5.1.1.1 One-Level Model

Each user thread is mapped one-to-one to a kernel thread.

#####5.1.1.2 Two-Level Model

Single Kernel Thread

N-to-1 model

Multiple Kernel Thread

M-to-N model

#####5.1.1.3 Scheduler Activations

upcall: as opposite to system call, going from system code to user code.

####5.1.2 A Simple Threads Implementation

• A global variable: CurrentThread
• A run queue
• Each resource(eg. mutex) has a wait queue

####5.1.3 Multiple Processors

• CAS(atomatically compare and swap)
• spin lock
• block lock
• futex

###5.2 Interrupts

####5.2.1 Interrupt Handlers

#####5.2.1.1 Synchronization and Interrupts

On uniprocessor systems with non-preemptive kernels, things are easy, just mask interrupt when synchronization is needed

Systems with preemptive kernels, trickey.

#####5.2.1.2 Interrupt Threads

####5.2.2 Deferred Work

• Handle more interrupts
• DPC

####5.2.3 Directed Processing

#####5.2.3.1 Asynchronous Procedure Calls

APC

#####5.2.3.2 Unix Signals

• Save all registers on entry to the handler and restore them on return
• Unblock the signal on return

###5.3 Scheduling

####5.3.1 Strategy

#####5.3.1.1 Simple Batch Systems

#####5.3.1.2 Multiprogrammed Batch Systems

#####5.3.1.3 Time-sharing Systems

#####5.3.1.4 Shared Servers

Stride scheduling(use scaled-integer arithmetic)

#####5.3.1.5 Real-time Systems

Priority inheritance(cascading inheritance)

####5.3.2 Tactics

#####5.3.2.1 Handoff Scheduling

#####5.3.2.2 Preemption Control

#####5.3.2.3 Multiprocessor Issues

####5.3.3 Case Studies

#####5.3.3.1 Scheduling in Linux

#####5.3.3.2 Scheduling in Windows

Note: Language

###4.1 An example: self-grandpas

###4.2 Signatures and Fields

####4.2.1 Signatures

• extends: extension or subsignature, mutually disjoint
• abstract: no elements of itself
• univ: can be viewed as an implicit abstract signature that all top-level signatures extend
• in: not necessarily mutually disjoint

• union of sets

    sig C in A + B {}
  

  the union is the only operator can appear in a sig declaration

• multiplicity keyword before sig

    m sig A {}
  

  enumeration

    abstract sig T {}
    one sig A, B, C extents T {}
  

####4.2.2 Basic Field Declarations

####4.2.3 Grouping Disjoint Fields

###4.4 Types and Type Checking

####4.4.1 Basic Types

####4.4.2 Relational Types

####4.4.3 Type Errors

####4.4.4 Field Overloading

###Questions:

1. P111 what exactly is overapproximation?
2. P113 Example alias?
3. all this: Course and some this: Course

###Notes during asgn 2

• I’ve never thought that we can use Alloy to model something like songs or lyrics. I guess it’s because sentence contains logic, and Alloy can model the logic.

###Feb 21 Class

• Alloy only runs within the scope, so it’s never exhaustive to the whole searching space. This should always be kept in mind.
• But, bugs tend to appear with smaller scope.(not always)

###Feb 24 Class

• seq vs order
• seq doc
• the existence of ++ operator

• override module name

    open util/ordering[Cats1] as trace1
    open util/ordering[Cats2] as trace2
  

###Feb 26 Class

####Skolemization

#####Skolem Depth:(my experiment)

• It counts all x: S| all y: S as one depth
• Same quantifiers in sequence is 1 depth
• top level is 0 depth

#####Useful for:

Debugging

#####Tradeoff:

###Note during asgn 3

• Don’t over-think things. Just follow the first instinct.
• The idea of representing infinity in Alloy is to be learned.