COMP 3000 2012 Week 11 Notes

2012-12-13T10:58:05Z

Shahanahmed: /* Misc */

== CPU SCHEDULING ==

* Kernel operations:
** switch to supervisor-> caused by interrupt
** when we switch back into user, we need to figure out what process to run next. THIS IS SCHEDULING

* CPU state
** ready
** running
** loading (loading into memory)
** blocked (waiting for I/O)
** Scheduling takes processes and changes its state
** [http://en.wikipedia.org/wiki/Process_state see diagram]

Which process does the scheduler run next?
* To avoid starvation, uses round robin algorithm
* preemption: max time a process can use the CPU
* prioritize unblocked processes: those using limited resources are prioritized
* priorities set by nice values and other jigging

* Scheduling is HARD. Figuring out fine grained scheduling is still an open problem. Everything we have is a bit "hacky"

CFS (completely fair scheduler) is the linux scheduler

I/O scheduling
* Disk scheduling.
** Elevator algorithm
*** "Get on elevator when it passes by, get off when it gets to your floor, but you're not controlling the elevator
*** there are exceptions though. Some processes "can control the elevator"
*** To avoid long "queues", we batch I/O requests together (I/O reordering)
*** We employ HD caches to help deal with batching and I/O reordering

== Filesystems -- Journaled (revisted) ==

FSCK walks the FS checking for errors. Takes long time. Bad idea. Journaled FSes fixes this.

Journaled FSes
* Transactions do not happen directly to disk.
* We first write to a journal.
* Later, the journal will be read and the transactions will write to disk
* These transactions happen in a stream (sequentially), which will be much faster than random writes
* We're actually writing twice as much (time, transactions, not data) to the disk
* we actually write to the rest of the disk in the background, when nothing is relying on I/O

* If you're writing a lot to your FS, though, this'll be slow. We're writing twice to disk.
** To solve this issue, convert the FS to a log structured FS.
** the entire file system becomes the FS.

Log structured FS
* All data is added sequentially to the disk
* the actual log of additions becomes the FS, telling us where to find data on that disk

SSDs use wear leveling. Each memory cell has a dedicated lifespan. We try to lengthen their life by spreading the wear across the SSD.

== Top ==
Top command. Memory Types:
* virt- size of virtual address space - number of pages (doesn't typically matter)
* RES - how many frames in physical ram are taken up (should be smaller than virt)
* SHR - Shared memory between processes (shared frames amongst ALL processes)

== Working set ==
* [http://en.wikipedia.org/wiki/Working_set]
* Memory that you need for a certain task to make efficient progress.
* if you don't have enough space on the working set, your process will be spending alot of time writing and reading from disk
* there are many ways to manage the working set (page replacement)
* Optimal WS: The optimal working set is the one where you know ahead of time which pages you'll need to load into memory and those you won't. You're effetiively predicting the future
* LRU: least recently used (good for non streaming)
** Updating the last access time for every page would have alot of overhead, so we approximate this instead....
*** We can use the page table entry's metadata to help with this
*** Basic strategy: Clock algorithm. Sets zero to all page entry access metada every second. If we haven't accessed that page, the bit will still be zero.

== Misc ==

Page replacement algorithm
*** If a page is not dirty and hasn't been accessed, kick it out
* '''Please Expand'''
* Dirty: If a page has data waiting to be written on disk, it is considered 'dirty'
* Accessed: Some measure of the last time it was accessed, if it hasn't been accessed in a while (from the last sweep?) it is considered 'not accessed'

Ubuntu's memory management is optimistic

File caches
* write back caching: when writing to a file, a promise is made that we've written the bits to disk, despite not having done.
* allows the coder not to worry.

Unified Page Cache
''' please expand '''

TLB: Cachei of page table entries of working set of current process
Address space is page table

Copy on write
* how forks are made
* after fork, parent and child share memory until memory is accessed
* share pages until write
* detect by marking all pages read only
* informally, it is making a shallow copy. It'll make a "deeper copy" when needed.

Fairness
* devoting resources to the programs you want is hard to implement

COMP 3000 2012 Week 8 Notes

2012-10-31T17:24:06Z

Shahanahmed:

Practice questions and their associated answers:

<ol>
<li>
Q: You can create a sparse file in UNIX by writing sequences of zeros to a file. 

A: False. Sparse file means holes. Zeroes aren't holes.
You need to move the file pointer. You have to use a
seek. The data will be READ as zeros, though...
Look up truncate command and strace it. It ain't just writing zeros
</li>
<li>
Q: Are environment variables ``global variables? Specifically, if you change the value of an environment variable X in one process, what happens to the value of X in other processes? 

A:Nothing happens. Env vars aren't globals. They're passed in with Execve. Environments
variables are typically process specific.
</li>
<li>
Q: In UNIX, there are three permissions associated with the user, the user's group, and everyone else. What are those three permissions? 

A: rwx (Read, Write, Execute)
</li>
<li>
Q: If you see a zombie process during normal system operation, how can you get rid of it? 

A: Kill the parent
Why? init will own the zombie process and then kill it
</li>
<li>
Q: I can copy a file using I/O redirection as follows: cat /bin/ls > bar. If I now type ./bar, it won't run. However, if I run another command before typing ./bar, I will get
a file listing. What needed to be changed to get bar to run? 

A: chmod +x
Default non executable. Need to make it executable. (--x)
</li>
<li>
Q: System calls cannot normally be made using standard function calls. What CPU mechanism is used by regular processes to invoke kernel functionality? 

A: Software interrupt. Signals are a form of of software interrupt. 

Note:

"A system call is an entry point into the Linux kernel. Usually, system calls are not invoked directly: instead, most system calls have corresponding C library wrapper functions which perform the steps required (e.g., trapping to kernel mode) in order to invoke the system call. Thus, making a system call looks the same as invoking a normal library function." from man 2 intro 

"The call to the library function itself does not cause a switch to kernel mode (if the execution was not already in kernel mode) and is usually a normal subroutine call (using, for example, a "CALL" assembly instruction in some Instruction set architectures (ISAs)). The actual system call does transfer control to the kernel (and is more implementation-dependent and platform-dependent than the library call abstracting it). For example, in Unix-like systems, "fork" and "execve" are C library functions that in turn execute instructions that invoke the "fork" and "execve" system calls. Making the system call directly in the application code is more complicated and may require embedded assembly code to be used (in C and C++) as well as knowledge of the low-level binary interface for the system call operation, which may be subject to change over time and thus not be part of the application binary interface; the library functions are meant to abstract this away." from http://en.wikipedia.org/wiki/System_call

</li>
<li>

Q: After a fork system call, what runs first, the child process runs or the parent process? 

A: Don't know... Undefined. Can not depend on ordering

</li>
<li>

Q: Signal handlers can be called at almost any point in a process's execution. (T/F) 

A: True. That's the purpose of signals 

Register a normal C function as a signal handler 

They every signal has a default signal handler defined in the C Standard Library. 
Most can be overwritten to have user-defined signal handlers, however some, (e.g. sigkill) cannot be overwritten. 

Signals can be called at any point in execution. 

"When a signal is sent, the operating system interrupts the target process's normal flow of execution. Execution can be '''interrupted during any non-atomic instruction.''' If the '''process has previously registered a signal handler, that routine is executed. Otherwise''' the default signal handler is executed." from http://en.wikipedia.org/wiki/Unix_signal

</li>
<li>

Q: System V init scripts run programs sequentially or in parallel? 

A: Sequentially (sysV). Shell script that runs every ''command'' sequentially 

Upstart does it in parallel though. This is the reason sysV is being replaced by Upstart.

</li>
<li>

Q: Without errors, what does the execve system call return? # Who calls a signal handler? 

A: On success, execve() does not return, on error -1 is returned, and errno is set appropriately. 

The program itself calls the signal handler

</li>
<li>

Q: What program is used to check the consistency of the data structures of a filesystem? 

A: fsck <- wrapper function 
fsck.FMT <- called by fsck for a specific format (ex: fsck.ext4)

</li>
<li>

Q: What allocates the storage for environment variables and command-line arguments? 

A: The kernel. The kernel is the only thing that can allocate this space.(execve) 
This also makes sense because execve is a system call.

Note that the kernel is the only thing that can change the size of a program's data segment directly (the wrapper for this system call is sbrk), but malloc is often implemented to call sbrk in advance, then divide up the space as malloc is called.

</li>
<li>

Q: A file that has a logical size of one gigabyte but only takes up 100K on disk is called what kind of file in UNIX? 

A: Sparse file.

</li>
<li>

Q: What is an easy (but not foolproof way) way to tell that you are running in a virtual environment on Linux? What command do you run to get this information? 

A: lspci, lshw. 
In /proc/, you may be able to also. 
These commands display the machine's "hardware". 

Not /dev/ because that's the abstraction.

</li>
<li>

Q:What is the purpose of the PATH environment variable? 

A: At the command line, the $PATH variable is where the shell looks for binaries/files.
The path is walked when the fullPATH/filename of the command line hasn't been specified

</li>
<li>

Q: When would you expect ltrace to output more lines than strace? When should strace output more than ltrace? 

A: Some libraries make no sys calls (strlen). Libraries that do basic string and math
operations -> no sys calls 

Programs with lots of I/O will use lot of sys calls

</li>
<li>

Q: What command is used to change the priority of a process? 

A: nice and renice 
nicess is policy value (default value and you can modify this) 
priority (dynamic) is based on niceness and the amount of time the process has run on
cpu 
Priority doesn't apply to I/O. I/O will continue despite other processing having high
priority. I/O will always slow down the system.

</li>
<li>

Q: What is the difference between a library call and a function call? 

A: The former requires a library card and a telephone.
 [[User:Spenner2|Spenner2]] ([[User talk:Spenner2|talk]]) nice
</li>
</ol>

Soma-notes - User contributions [en]

COMP 3000 2012 Week 11 Notes

COMP 3000 2012 Week 8 Notes