Courses/Computer Science/CPSC 457.F2014/Lecture Notes

From wiki.ucalgary.ca
Jump to: navigation, search

Course notes are available from here.

Contents

Scribe Notes

Courses/Computer_Science/CPSC_457.F2014/Lecture Notes/Scribe1

Courses/Computer_Science/CPSC_457.F2014/Lecture Notes/Scribe2

Courses/Computer_Science/CPSC_457.F2014/Lecture Notes/Scribe3

Course notes are available from here.

Week 1

September 8: Course Overview

Courses/Computer_Science/CPSC_457.F2014/Lecture Notes/Overview

September 11: What Problem Do Operating Systems Solve?

Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/ProblemOS

September 12: From Programs to Processes, Part 1

Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/Prog2Proc

Courses/Computer_Science/CPSC_457.W2012/Lecture Notes/Prog2Proc

Week 2

The unifying theme for this week is the focus question: "how does a program become a process?", which we began to discuss last Friday. In discussing the transformation of a program code to a running process, the environment of multiple processes supported by the OS and hardware, and the concept of CPU multiplexing, we arrive at a fundamental understanding of the operating system as a piece of software that enables a collection of software applications to make efficient use of the underlying hardware.

Sept 15: From Programs to Processes, Part 2

Today we will consider questions of process control.

We will defer details of process creation and the properties of a process until next week.

Class starter exercise

http://pages.cpsc.ucalgary.ca/~locasto/teaching/2014/CPSC457/code/mathx

Directions

Pair up (work in twos and threes). Using hexdump and the ELF spec, find:

  1. the entry point address
  2. start of section headers
  3. verify the contents at the above offset


Primary OS responsibility

  • provide an execution environment for "user-level" software applications (i.e., programs)
  • in other words, be invisible -- apps are what people care about

As a consequence, one major task for an OS is to transform binary code into a "live" entity

  • Process: a program in execution (or: "a program experiencing/undergoing execution")
  • ELF (and other binary formats are contracts between the compiler and the OS; in some sense, they are the protocol format defining how the OS should accept code+data for execution

So far, we have discussed the following utilities:

  • ps(1) (see also jobs(1))
  • pstree(1)
  • top(1)
  • kill(1)
  • strace(1)
  • wc(1)
  • grep(1)
  • yes(1)

Process Control

  • What is running?
  • How do I control it?
  • How do I observe it?

Sept 17: What is an Operating System? / OS History (Guest Lecture)

Prof. Williamson will discuss some OS history and the evolution of OS software.

The Unix family tree:

Sept 19: OS Structure and Components

Up to this point, we have spoken about some of the primary responsibilities and concepts involved in operating systems, along with some of their history. Today, we will consider the "big picture" of OS structure.

Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/WhatOS

Slides: http://www.cpsc.ucalgary.ca/~locasto/teaching/2014/CPSC457/talks/whatos-2014.pdf

Week 3

Sept 22: System Architecture

This session will draw a link between what you know (or should remember) from your Computer Architecture or Computer Organization class to the picture we discussed last session. It will provide the context for some of the fundamental services operating systems provide.

Courses/Computer_Science/CPSC_457.F2014/Lecture Notes/SysArch

Note the relationship between faults and delivering signals to processes, e.g., the delivery of SIGSEGV for a GPF: http://lxr.cpsc.ucalgary.ca/lxr/#linux+v2.6.32/arch/x86/kernel/traps.c#L289

Sept 24: System Calls Intro

In this session, we will consider the key layer between the kernel and userland processes: the API defined by the system call layer. We will observe how deep the call chains originating in the system call layer go into the kernel.

We will examine how to invoke system calls via assembly code. We will consider how to observe the events taking place at the system call layer (via the strace(1) tool).

Courses/Computer_Science/CPSC_457.F2014/Lecture Notes/SystemCalls

Sept 26: System Calls (Continued)

We will begin by (re)tracing the steps of making a system call and trapping to the kernel.

  • execute the sample ASM code
  • trace the mechanism again (briefly)
  • highlight difference between function call calling convention

Example of the function call conventions on x86 setting up an activation record between main() and foobar(): 

08048414 <foobar>:
 8048414:	55                   	push   ebp
 8048415:	89 e5                	mov    ebp,esp
 8048417:	8b 45 0c             	mov    eax,DWORD PTR [ebp+0xc]
 804841a:	8b 55 08             	mov    edx,DWORD PTR [ebp+0x8]
 804841d:	8d 04 02             	lea    eax,[edx+eax*1]
 8048420:	5d                   	pop    ebp
 8048421:	c3                   	ret    
08048422 <main>:
 8048422:	55                   	push   ebp
 8048423:	89 e5                	mov    ebp,esp
 8048425:	83 e4 f0             	and    esp,0xfffffff0
 8048428:	83 ec 20             	sub    esp,0x20
 804842b:	c7 44 24 1c 2a 00 00 	mov    DWORD PTR [esp+0x1c],0x2a
 8048432:	00 
 8048433:	c7 44 24 04 08 00 00 	mov    DWORD PTR [esp+0x4],0x8
 804843a:	00 
 804843b:	c7 04 24 07 00 00 00 	mov    DWORD PTR [esp],0x7
 8048442:	e8 cd ff ff ff       	call   8048414 <foobar>
 8048447:	89 44 24 1c          	mov    DWORD PTR [esp+0x1c],eax

Calling the write(2) system call via the INT 0x80 mechanism: 

(eye@mordor syscalls)$ objdump -d -M intel mywrite 
mywrite:     file format elf32-i386
Disassembly of section .text:
08048080 <_start>:
 8048080:	b8 04 00 00 00       	mov    eax,0x4
 8048085:	bb 01 00 00 00       	mov    ebx,0x1
 804808a:	b9 a0 90 04 08       	mov    ecx,0x80490a0
 804808f:	ba 0b 00 00 00       	mov    edx,0xb
 8048094:	cd 80                	int    0x80
 8048096:	89 c3                	mov    ebx,eax
 8048098:	b8 01 00 00 00       	mov    eax,0x1
 804809d:	cd 80                	int    0x80
(eye@mordor syscalls)$



We will continue by looking at the implementation and entry points for several "interesting" system calls.

notes

Week 4

Sept 29: Process Creation and the Process Control Block

In this session, we consider how the kernel represents and keeps track of the metadata about each process. A consideration of the task_struct in Linux. Also a consideration of how processes come into existence (tying back to our earlier discussions of the OS's role in helping programs become processes).

Courses/Computer_Science/CPSC_457.F2014/Lecture Notes/Creation

Oct 1: Process Creation (continued)

We will examine fork(), vfork(), and clone() in more detail and discuss some of the practical considerations of creating new processes.

Courses/Computer_Science/CPSC_457.F2014/Lecture Notes/Creation

Oct 3: The Process Address Space

Another important element of what a process is besides a PCB (i.e., pieces of meta-data kept by the kernel) is its address space: the range in memory where the process has access to the program code and both static and dynamic data. In Linux, this address space has a rich structure of memory regions that partly corresponds to sections from an executable file as well as regions generated at load time or during runtime.

In this session, we consider what the components of a PAS are and how parts of an ELF are mapped to it. The process address space is one of the two major defining elements of a process (the other being the process control block, e.g., the Linux task_struct), which contains the CPU context and other meta-data of the process).

Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/ProcAddrSpace

Week 5

Oct 6: Memory Address Translation

In this session, we see yet another place where the OS and hardware work hand-in-hand to establish a comfortable operating environment for user processes. Memory address translation is the building block of the concept of virtual memory and helps support the fiction (i.e., abstract notion) of a address space for each process.

Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/MemAddr

Announcements: HW1 has been modified/updated. Problem 2 is removed and the HW itself is due on Oct 17.

Oct 8: Memory Address Translation, Paging, and Virtual Memory

Courses/Computer_Science/CPSC_457.F2014/Lecture Notes/VirtualMemory

Oct 10: Paging and Virtual Memory (cont)

Week 6

Oct 13: Thanksgiving, No Class

Oct 15: Midterm Exam

Oct 17: Virtual Memory and Page Replacement

Courses/Computer_Science/CPSC_457.F2014/Lecture Notes/PageReplacement

Week 7

Oct 20: User-Level Memory Management

A consideration of memory allocation approaches, schemes, and algorithms. Also a review/introduction to the existing dynamic memory allocation facilities available to user level programs.

Courses/Computer_Science/CPSC_457.F2013/Lecture_Notes/UserMem

Oct 22: User-level Memory Management (cont)

A review of concepts from Oct 20.

A closer look at what malloc() does to your heap when it "allocates" memory for instances of data types.

Time permitting, a closer look at the brk(2) system call implementation.

Oct 24: Kernel Memory Management

How does the kernel manage its own memory needs? Through a combination of careful a priori static allocation and dynamic memory allocation. It also is careful to cache certain groups of data structures.

Courses/Computer_Science/CPSC_457.F2014/Lecture_Notes/KernMem

Week 8

Oct 27: System Startup

We begin the transition from talking about memory to discussing concurrency. How does the computer go from sequentially executing boot code to concurrently executing multiple processes?

Courses/Computer_Science/CPSC_457.F2014/Lecture_Notes/Startup

Oct 29: Process Scheduling Concepts and Algorithms

We've seen how the OS can transition from sequential code execution to concurrent execution; it:

  • initializes the scheduler
  • creates two processes (via do_fork and via sys_execve)
  • enables interrupts;
  • and then allows the newly created scheduler to begin choosing between these two processes.
  • In the meanwhile, one of the processes (the init process) begins creating children via do_fork() and sys_execve()

This procedure naturally brings up the question: as more processes are created, and some hundred or thousand processes come to exist, how does the OS choose which process should be given the CPU?

Courses/Computer_Science/CPSC_457.F2014/Lecture Notes/Scheduling

Oct 31: Scheduling, Preemption, Timing, and Context Switching in Linux

A guided tour of the kernel's evolving scheduling infrastructure and context switching.

The 2.4 Kernel

The 2.6 Kernel

Courses/Computer_Science/CPSC_457.F2014/Lecture Notes/LinuxSched

Week 9

Nov 3: Concurrency Concepts: Communication and Synchronization

Courses/Computer_Science/CPSC_457.F2014/Lecture Notes/Concurrency

Nov 5: Deadlock

Courses/Computer_Science/CPSC_457.F2014/Lecture Notes/Deadlock

Nov 7: Kernel Synchronization Primitives

Courses/Computer_Science/CPSC_457.F2014/Lecture Notes/KernSync

Week 10

Nov 10: No lecture (Reading Days)

Nov 12: Threads (User--level Concurrency)

Today we'll take a look at pthreads.

http://pages.cpsc.ucalgary.ca/~locasto/teaching/2014/CPSC457/pthread-exercise.txt

Nov 14: Signals and IPC

Courses/Computer_Science/CPSC_457.F2014/Lecture Notes/SignalsIPC

Week 11

Nov 17: Files and File I/O

We begin our discussion of persistent storage.

Courses/Computer_Science/CPSC_457.F2014/Lecture Notes/FileIO

Nov 19: File Systems Overview

Courses/Computer_Science/CPSC_457.F2014/Lecture Notes/Filesystems

Nov 21: Extended Attributes

Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/XAttr

Week 12

Nov 24: The Linux VFS

Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/VFS

Links

You can install / add an open file record here via the open(2) system call, which eventually calls:

Nov 26: Example File Systems

Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/ExampleFileSystems

Nov 28: Disk and I/O Scheduling

Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/DiskScheduling

Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/Devices

Week 13

Dec 1: User-level Networking

Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/UserNetworking

http://www.cpsc.ucalgary.ca/~locasto/teaching/2014/CPSC457/talks/networks-OS.pdf

Dec 3: USRI and Kernel Networking Architecture

Today we discussed the kernel's role in processing packets for local delivery and forwarding.

http://www.netfilter.org/documentation/HOWTO/netfilter-hacking-HOWTO-3.html

We also saw how the kernel is responsible for interfacing with device and handling device I/O with NICs as an example.

Sending, Receiving, and Listening for ICMP 

(eye@mordor networking)$ cat ./ping.script 
#!/bin/bash
sudo strace -o ping-csl.trace -e trace=network ping -c 1 -p "FEEF1EF0EF0B" 136.159.5.22
(eye@mordor networking)$ ./ping.script

A view of the syscall layer: What the kernel does to support sending an ICMP packet and receiving a response 

(eye@mordor networking)$ cat ping-csl.trace 
socket(PF_INET, SOCK_RAW, IPPROTO_ICMP) = 3
socket(PF_INET, SOCK_DGRAM, IPPROTO_IP) = 4
connect(4, {sa_family=AF_INET, sin_port=htons(1025), sin_addr=inet_addr("136.159.5.22")}, 16) = 0
getsockname(4, {sa_family=AF_INET, sin_port=htons(37818), sin_addr=inet_addr("10.0.2.15")}, [16]) = 0
setsockopt(3, SOL_RAW, ICMP_FILTER, ~(ICMP_ECHOREPLY|ICMP_DEST_UNREACH|ICMP_SOURCE_QUENCH|ICMP_REDIRECT|ICMP_TIME_EXCEEDED|ICMP_PARAMETERPROB), 4) = 0
setsockopt(3, SOL_IP, IP_RECVERR, [1], 4) = 0
setsockopt(3, SOL_SOCKET, SO_SNDBUF, [324], 4) = 0
setsockopt(3, SOL_SOCKET, SO_RCVBUF, [65536], 4) = 0
getsockopt(3, SOL_SOCKET, SO_RCVBUF, [131072], [4]) = 0
setsockopt(3, SOL_SOCKET, SO_TIMESTAMP, [1], 4) = 0
setsockopt(3, SOL_SOCKET, SO_SNDTIMEO, "\1\0\0\0\0\0\0\0", 8) = 0
setsockopt(3, SOL_SOCKET, SO_RCVTIMEO, "\1\0\0\0\0\0\0\0", 8) = 0
sendmsg(3, {msg_name(16)={sa_family=AF_INET, sin_port=htons(0), sin_addr=inet_addr("136.159.5.22")}, msg_iov(1)=[{"\10\0\201\335\30\6\0\1\33G\177TR\37\n\0\36\360\357\v \376\357\36\360\357\v\376\357\36\360\357\v"..., 64}], msg_controllen=0, msg_flags=0}, 0) = 64
recvmsg(3, {msg_name(16)={sa_family=AF_INET, sin_port=htons(0), sin_addr=inet_addr("136.159.5.22")}, msg_iov(1)=[{"E\0\0T\0\215@\0?\1\241X\210\237\5\26\n\0\2\17\0\0\211\335\30\6\0\1\33G\177T"..., 192}], msg_controllen=20, {cmsg_len=20, cmsg_level=SOL_SOCKET, cmsg_type=0x1d /* SCM_??? */, ...}, msg_flags=0}, 0) = 84
(eye@mordor networking)$


Listening for traffic: 

[root@mordor eye]# tcpdump -i eth0 -s0 -n -A -v -X icmp

ICMP Packet crafting with Scapy

Documentation: http://www.secdev.org/projects/scapy/doc/usage.html 

$ sudo scapy
myp=ICMP()
myp
myp.type="echo-request"
myp.show
myp.payload="FEEF1EF0EAAAAAAA"
myp
ping=IP()/myp
ping
ping.dst="136.159.5.22"
ping.ttl=6
ping
answer=sr1(ping)
answer
p=IP(dst="136.159.5.22")/ICMP(type="timestamp-request")/Raw("BBBBBBBBBBBBB")
p.show()
a=sr1(p)

Dec 5: Final Exam review

Agenda

  • concept map
  • syllabus topic list
  • major problem types
    • threading
    • deadlock
    • file indexing / FS structure
    • disk scheduling
    • process scheduling
    • memory allocation
    • page replacement
    • memory address translation
    • performance questions (timing, I/O speed, etc.)
  • all MOS readings

Exam Parameters

  • entire semester
  • 2 hours
  • 300 points (30% of your grade)
  • 1 sheet of notes

Collected Readings

  • MOS: 1.1: What is an Operating System?
  • MOS: 1.2: History of Operating Systems
  • MOS: 1.4: The Operating System Zoo
  • MOS: 1.5: Operating System Concepts
  • MOS: 10.1: History of Unix and Linux
  • MOS: 13.1: The Nature of the Design Problem
  • MOS: 1.3: Computer Hardware Review
  • MOS: 1.6: System Calls
  • MOS: 1.7: Operating System Structure
  • MOS: Section 2.1: Processes (this should be partly review of what we've talked about in class)
  • MOS: Section 3.2.1: The Notion of an Address Space
  • MOS: Section 3.7 (all except 3.7.2) (this should review some of what we touched on in the previous class and lay some groundwork for talking about memory management)
  • MOS: Section 10.2.5 (Linux kernel structure)
  • MOS: Section 10.3.1 (about processes in Linux) should reinforce some class discussion
  • MOS: 10.3.5: "Booting Linux"
  • MOS: 2.4.1 "Introduction to Scheduling" (plus 2 intro paragraphs in S2.4)
  • MOS: 2.4.5 "Policy vs. Mechanism"
  • MOS: 10.3.4: "Scheduling in Linux"
  • MOS: 2.7 "Summary" (this talks about some things we'll consider next)
  • MOS: 5.5 "Clocks"
  • MOS: 3.2.3
  • MOS: 3.1 "No Memory Abstraction"
  • MOS: 3.2 "A Memory Abstraction: Address Spaces"
  • MOS: 3.3 "Virtual Memory" (this subsection also contains a review of paging and TLBs)
  • MOS: 3.7.3 "Segmentation with Paging: The Intel Pentium"
  • MOS: 3.4
  • MOS: 2.2 "Threads"
  • MOS: 2.3 "Interprocess Communication"
  • MOS: 2.5 "Classical IPC Problems" Beware typos in Figure 2-23, pg 122 (semicolon placement)
  • MOS: 6.2 "Introduction to Deadlocks" (NB: MOS 6.2.1 should be memorized!)
  • MOS: 6.4 "Deadlock Detection and Recovery"
  • MOS: 6.5 "Deadlock Avoidance"
  • MOS: 6.6 "Deadlock Prevention"
  • MOS: 4.1
  • MOS: 4.2
  • MOS, Chapter 4.3: File System Implementation
  • MOS, Chapter 4.5: Example File Systems
  • MOS, Chapter 10.6: The Linux File System
  • MOS: 5.1 Principles of I/O Hardware
  • MOS: 5.2 Principles of I/O Software
  • MOS: 5.4 Disks

Final Exam December 10 8am to 10am

Command Line Log

This is a log of my command line work from class sessions. As it grows, I'll probably split it up into sessions and associate with the appropriate session above. 

 1001  cd 457
 1002  mkdir 2014-intro
 1003  cd 2014-intro/
 1004  ls
 1005  emacs -nw math.c
 1006  arch
 1007  uname -a
 1008  cat /proc/cpuinfo 
 1009  clear
 1010  gcc -Wall -o mathx math.c 
 1011  ll
 1012  file mathx
 1013  file math.c
 1014  ./mathx
 1015  echo $?
 1016  objdump -d -M intel mathx
 1017  clear
 1018  ll
 1019  ls -l
 1020  file mathx
 1021  cat mathx
 1022  clear
 1023  man cat
 1024  man hexdump
 1025  hexdump -C mathx
 1026  bless mathx
 1027  file mathx
 1028  ./mathx
 1029  clear
 1030  echo "ELF" > myprogram.x
 1031  cat /dev/random >> myprogram.x 
 1032  hexdump -C myprogram.x 
 1033  clear
 1034  ll
 1035  ./myprogram.x
 1036  chmod +x myprogram.x 
 1037  ll
 1038  ./myprogram.x 
 1039  clear
 1040  man readelf
 1041  gcc -Wall -o mathx math.c 
 1042  readelf -a mathx
 1043  readelf -a mathx | more
 1044  man readelf
 1045  readelf -x ".text" mathx
 1046  objdump -d mathx
 1047  objdump -d -M intel mathx
 1048  ./mathx
 1049  strace ./mathx
 1050  ps
 1051  pstree
 1052  man fork
 1053  clear
 1054  ls
 1055  readelf -h mathx
 1056  hexdump -C mathx
 1057  printf "%x\n" 1904
 1058  sftp locasto@csl.cpsc.ucalgary.ca
 1059  sftp locasto@csf.cpsc.ucalgary.ca
 1060  clear
 1061  ps
 1062  ps maux
 1063  clear
 1064  ps aux
 1065  clear
 1066  kill
 1067  yes
 1068  clear
 1069  lll
 1070  ll
 1071  hexdump -C mathx | more
 1072  clear
 1073  yes
 1074  yes "hello 457"
 1075  ps aux | wc
 1076  yes hello
 1077  fg
 1078  ps
 1079  pstree
 1080  ps
 1081  fg
 1082  strace yes "hello"
 1083  strace -o yes.out yes "hello"
 1084  ssh locasto@csf.cpsc.ucalgary.ca
 1085  yes h
 1086  jobs
 1087  history
(eye@mordor 2014-intro)$
Retrieved from "http://wiki.ucalgary.ca/index.php?title=Courses/Computer_Science/CPSC_457.F2014/Lecture_Notes&oldid=70032"