Teaching‎ > ‎

Operating Systems (Fall 2009)

Requirements

  • Basic knowledge of C or C++ language.

General rules

  • Exact amount of points is not specified. Instead of absolute points, a ratio of obtained points to maximum number of points will be calculated (in form of percentage).
  • Number of points will be nearly equally divided between laboratories and exercises. Minimum 40% of points must be obtained to pass.
  • If students are not prepared - labs and exercises may be used to continue conducting a lecture. Remember that all material presented during lecture will be required during an exam.
  • Each student is given three credit points, which can be used for purposes explained later.

RangeGrade
100% - 88%
5.0
87% - 76%
4.5
75% - 64%
4.0
63% - 52%
3.5
 51% - 40%
3.0
 39% - 0%
2.0

Labs rules

  • Assigned programs must compile (using GNU make command) and run under Linux operating system on computers in room no. 137.
  • Programs must be written in C or C++ language.
  • To obtain points for a program, a student must present it on labs. Moreover, the program must be sent to the instructor by e-mail immediately after being presented.
  • A student is not allowed to present a program after a deadline. For each program a deadline will be announced. Deadline may be postponed individually by one week using a credit point.

Exercises rules

  • Exercises will be conducted in a form of seminar. Each student will have about 30 minutes to make a presentation.
  • At least a week before exercises a set of subjects will be published. A student may propose his/her own subject.
  • A student who declared to prepare presentation and did not manage to do it will be given a penalty of one credit point.
  • A student should (although it's not mandatory) send a presentation before classes to be reviewed by the teacher. Notice that the reviewed presentation is likely to get a better grade.
  • A presentation which was shown during the classes MUST be sent to the teacher.
  • After the presentation topic is selected by a student, he or she must immediately send an e-mail to teacher with a reservation. A topic is considered to be reserved when it's marked with red colour and the name of student before it.

E-mail rules

  • Each sent e-mail must have a title starting with "[OS09]".

Exam

Rules

  • Maximum point possible to obtain during the exam is 100.
  • Solving true/false test gives possibility to obtain max. 60% of points. Each test question has from 4 to 6 answers. A student must leave T (for True) or F (for false) in the check-box for each answer. Answering properly will yield 1 points. A wrong answer will yield -1 points. Leaving a check-box empty yields no points. For each question there is unknown number of true or false answers (ie. it's possible that there is no true answer, or all answers are true).
  • 40% of points are possible to get providing answer to 4 questions. These will be general question requiring from student to write a few sentences that explain a problem.
  • The table in "general rules" section will be used to determine a grade.
  • The exam will last for two hours (120 minutes).

Date

  • The exam will be held at the 9th of February at 2 p.m in room 105 (actually was moved to 141 because of Olympics in Informatics).
  • The resit will be held at the 16th of February at 2 p.m. in room 105.

Repetition materials

You will find them at following subpage.

References

Books

Articles

Web pages

  • Gustavo Duarte's Blog - excellent articles containing explanation of operating system related concepts.
  • William Stallings' Web Page - online chapters of excellent book "Operating Systems: Internals and Design Principles", additional references and useful materials.

Syllabus

Achieved

    • Computer architecture: a quick review
    • Operating system overview
    • Basic abstractions: L4 micro-kernel
    • Processes and threads
    • Scheduling
    • Synchronization
    • Inter-process communication
    • Memory management

Skipped

  • File systems and mass-storage management
  • I/O management
  • Networking
  • Protection and security
  • Distributed operating systems
  • Domain specific operating systems

Lecture progress

  1. [06.10.2009] Computer architecture: a quick review (part 1)
    • general computer architecture,
    • CPU working modes,
    • registers,
    • Instruction Set Architecture,
    • interrupts.
  2. [13.10.2009] Computer architecture: a quick review (part 2)
    • interrupt handling, nested interrupts,
    • cache memory
    • memory management
    • paging
    • I/O devices
    • System bus
  3. [20.10.2009] Operating system overview
    • Operating system definition
    • Operating systems evolution
    • Achievements of OS evolution
  4. [27.10.2009] Canceled (lecturer absence due to illness) :(
  5. [03.11.2009] Operating system architectures (part 1)
    • OS core functionality and common services
    • OSes and software engineering
    • Architectural design patterns for OSes (Layers)
  6. [10.11.2009] Operating system architectures (part 2)
    • Architectural design patters for OSes (Micro-kernel)
    • Kernel design trends
    • Kernel architectures (monolithic, micro-kernel, hybrid)
  7. [17.11.2009] Mixed:
    • Operating system architectures (part 3)
      • Kernel architectures (exokernel, SASOS)
      • Virtual machines
    • L4 micro-kernel architecture (part 1)
      • memory management and address spaces
  8. [24.11.2009] Mixed:
    • L4 micro-kernel architecture (part 2):
      • Threads
      • IPC
      • Scheduling
    • Processes (part 1):
      • Introduction
      • Process Control Block
  9. [01.12.2009] Processes (part 2)
  10. [04.12.2009] Processes (part 3)
  11. [08.12.2009] Threads
  12. [15.12.2009] Synchronization (part 1)
  13. [22.12.2009] Synchronization (part 2)
  14. [05.01.2010] Inter-process communication
  15. [12.01.2010] Memory management.
  16. [19.01.2010] Virtual memory.
Remember that lecture notes are available at my wiki. They might be useful to you, though they're somewhat small in volume.

Outstanding lecture will be held at Friday (04.12.2009) at 5 p.m!

Classes progress

  1. [06.10.2009] Cancelled (first classes).
  2. [13.10.2009] [Labs] Practical exercises - compiling simple programs under Linux. Using GNU make, GNU gcc, writing Makefiles.
  3. [20.10.2009] [Ex] Presentations:
    • [Nam-1] Shared libraries, dynamic linking.
  4. [27.10.2009] Cancelled (lecturer absence due to illness) :(
  5. [03.11.2009] [Labs] Warm-up labs (assignment no. 1).
  6. [10.11.2009] [Labs] Compiling static / dynamic libraries. Linking executables against libraries.
  7. [17.11.2009] Cancelled (students not prepared) :/
  8. [20.11.2009] [Extra] Presentation review for Dina, Zhadyra, Marzhan.
  9. [24.11.2009] [Ex] Outstanding presentations:
    • [Zhadyra-1] Linux kernel architecture presentation.
    • [Marzhan-1] Windows NT kernel architecture presentation.
    • [Dina-1] Linux kernel boot process presentation.
  10. [01.12.2009] [Ex] Presentations:
    • [Ajami-1] Intel x86 caches.
    • [Nam-2] Intel x86 address translation.
  11. [08.12.2009] One hour converted into a lecture (students not prepared) :/
  12. [15.12.2009] [Ex] Presentations:
    • [Dina-2] Batch processing (job schedulers).
  13. [22.12.2009] [Ex] Presentations:
    • [Marzhan-2] Hardware virtualization.
    • [Zhadyra-2] Contemporary shells. Basics of bash shell.
  14. [05.01.2010] [Labs] Programming assignment no. 2
  15. [05.01.2010] [Ex] Presentations.
    • [Nam-3] Creating processes and threads in Linux.
  16. [08.01.2010] [Ex] Presentations.
    • [Dina-3] Contemporary PC memory hierarchy - spatial and temporal locality, hit ratio, performance.
  17. [12.01.2010] [Labs] Programming assignment no. 3
  18. [12.01.2010] [Ex] Presentations.
    • [Andrii-2] Linux processes information.
    • [Ajami-2] Security threats.
    • [Marzhan-3] Executable files and memory layout - brief ELF description, stack and heap, text and data segments, kernel mapping, Linux memory layout.
    • [Zhadyra-3] Call stack, routines and coroutines - stack frame (creation, contents), calling convention, unwinding, reentrancy. Application Binary Interface.
  19. [15.01.2010] [Final] Final presentations:
    • [Dina] ?
    • [Nam] ?
    • [Marzhan] ?
  20. [19.01.2010] [Final] Final presentations:
    • [Andrii] ?
    • [Zhadyra] ?
    • [Ajami] ?
  21. [?] [Ex] Presentations:
    • [Andrii-3] ?
    • [Ajami-3] ?
Outstanding classes will be held at:
  • Friday 18.12.2009 at 5 p.m.
  • Friday 08.01.2010 at 5 p.m.
  • Friday 15.01.2010 at 5 p.m.

Ranking


Exercises

General remarks

  • A beamer can (or even should) be used during presentation. I'll make a reservation if possible.
  • A presentation should be send to me at least a day before being presented (this may change into a rule).
  • Before choosing a subject ask me what I expect to be done regarding it. When possible I'll try to publish more detailed description of a subject here.
  • In case of any problem (miscomprehension, ambiguities) write an e-mail to me. I'll try to answer ASAP.

The list of topics

  • [Nam] Shared libraries (aka shared objects) relocation, ELF shared object vs. DLL.
  • [Ajami] Intel x86 caches.
  • [Nam] Intel x86 address translation.
  • [Dina] Linux boot process.
  • [Marzhan] Linux kernel architecture.
  • [Zhadyra] Windows NT kernel architecture.
  • [Andrii] Linux processes information:
    • resources (getrusage call) and accounting (getrlimit call)
    • procfs filesystem contents (processes and system-wide information)
    • top utility
  • [Marzhan] Hardware virtualization:
    • recall general virtualization concepts
    • describe Intel VT-x technology
    • describe one of the most popular virtualization application (ie. vmware, virtualbox, etc.) 
  • [Nam] Creating processes and threads in Linux:
    • describe fork and clone call
    • copy-on-write mechanism,
    • threads interaction with fork call.
  • [Dina] Batch processing (job schedulers):
    • historical and modern usage,
    • describe cron, at, anacron tools
  • [Zhadyra] Contemporary shells. Basics of bash shell:
    • bash as a programming language (variables, statements, control flow, functions),
    • bash as a shell (pipes, foreground, background, jobs).
  • Intel x86 security rings.
  • [Marzhan] Executable files and memory layout - brief ELF description, stack and heap, text and data segments, kernel mapping, Linux memory layout.
  • [Zhadra] Call stack, routines and coroutines - stack frame (creation, contents), calling convention, unwinding, reentrancy. Application Binary Interface.
    • Operating Systems: Internals and Design Principles. "Appendix 1B. Procedure control."
  • [Dina] Contemporary PC memory hierarchy - spatial and temporal locality, hit ratio, performance.
  • Computer security concepts (based on chapters 14.1, 14.2, 14.3 from Stallings).
  • Authorization and authentication. PAM (Pluggable Authentication Modules) stack description. (based on chapters 15.1 and 15.2 from Stallings).
  • [Ajami] Security threats (based on chapters 14.4, 14.5, 14.6 from Stallings).
  • Security threats prevention (based on chapters 15.3, 15.5, 15.6 from Stallings).
  • Automatic memory management - garbage collection.
    • motivation, advantages, disadvantages (performance)
    • reference counting, mark-and-sweep, tri-colour marking
    • implementation strategies

Final presentations

The list of topics

  • [Zhadra] Real-time operating systems (RTLinux, QNX, VxWorks):
    • characterictics of real-time operating systems (soft real-time, hard real-time)
    • special mechanisms for providing time safe operations
    • brief description of RTLinux, QNX, VxWorks
  • [Marzan] Embedded operating systems (TinyOS, eCos, SymbianOS):
    • characteristics of embedded operating systems (resource restrictions)
    • brief description of SymbianOS, TinyOs, eCos.
  • Distributed operating systems (Plan9, OpenVMS).
  • [Ajami] Distributed processing and clusters (Beowulf, SunCluster).
  • [Dina] Networking (Chapter 17 and Appendix "I" from Stallings - available online)
    • Protocols - motivation, datagram protocol, stream protocols
    • TCP/IP stack brief description (IPv4, IPv6, TCP, UDP)
    • Network software architecture - client-server, peer-to-peer
    • Using BSD-style sockets (as client, as server)
  • [Nam] I/O managment and disk scheduling.
  • Filesystems and secondary storage management.

Laboratories

General remarks

  • Remember that during labs your instructor can help you solving a problem. Labs are the time not only to present your solution, but also to explain things that are not clear. So please declare a solution even if it isn't fully working - we will try to work it out.

Assignment no. 1

Prepare a simple program printing a listing of a directory provided at command line. Use opendir / readdir / closedir / stat calls. Extract listing procedure to separate file. Your program must consist of at least 3 modules. Prepare three versions of Makefile:
      • all object files are linked into single executable file,
      • all files excluding one consisting main procedure are linked into static library,
      • same as above but into dynamic library.

Assignment no. 2

In this assignment there are two programs to be implemented. Both program must solve one of the classic synchronization problems. In the first problem we assume that cooperating task are implemented as Unix processes, in the second as POSIX threads. You should use proper API:
Choose only one of the problems listed below and provide its solution as the first program:
Choose only one of the problems listed below and provide its solution as the second program:

Assignment no. 3

Similarly to the previous assignment, you have to provide solution to two problems. Following manuals might be useful:

  • POSIX message queues: mq_close, mq_getattr, mq_open, mq_receive, mq_send, mq_unlink, mq_overview
  • mmap, munmap, open, close, read, write, stat

Simple program allowing two users to communicate using text console.

Two users should communicate over message queue. If one types a line finished with end of line character onto the standard input, application should read it, form a message and put it into the queue. Receiver should be notified of new message and print it to the standard output. You might use two methods of receiving messages - SIGEV_THREAD or SIGEV_SIGNAL. First will use an extra thread to receive new messages. Second one interrupts reading from stdin and calls signal handler function which will in the end print a message to stdout. Program must acquire a path to message queue from command line. It must be able to create and destroy a message queue if required or possible.

Program numbering lines of a text file.

Your program should work similarly to command "cat -n path_to_file". In other words: read a file line by line, put on standard output a prefix which is the number of line, following single space character and line contents. Use must use mmap call to read file contents. Prepare the same program using only open / read / close / stat calls. Compare their performance using time command.

Deadline: 09.02.2010 23.59

References

Examples

  1. The skeleton for first assignment can be found in attachments at the bottom of this page.
ċ
as1-skeleton.tgz
(1k)
Krystian Bacławski,
12 Nov 2009, 10:52
v.3