CS计算机代考程序代写 distributed system concurrency algorithm Course Recap

Course Recap

Lecture 22
CS 111: Operating System Principles

Course Recap
1.0.0

Jon Eyolfson
June 1, 2021

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License

cba

http://creativecommons.org/licenses/by-sa/4.0/

There are 4 Major Concepts in This Course

You’ll learn how the following applies to operating systems:
• Virtualization
• Concurrency
• Persistence
• Security (out of scope, somewhat touched on in Virtual Machines)

1

Kernel Interfaces Operate Between CPU Mode Boundaries

The lessons from the lecture:
• Code running in kernel mode is part of your kernel
• Different kernel architectures shift how much code runs in kernel mode
• System calls are the interface between user and kernel mode
• Everything involved to define a simple “Hello world” (in 178 bytes)

• Difference between API and ABI
• How to explore system calls

2

Operating Systems Provide the Foundation for Libraries

We learned:
• Dynamic libraries and a comparison to static libraries

• How to manipulate the dynamic loader
• Example of issues from ABI changes without API changes
• Standard file descriptor conventions for UNIX

3

The Operating System Creates and Runs Processes

The operating system has to:
• Loads a program, and create a process with context
• Maintain process control blocks, including state
• Switch between running processes using a context switch
• Unix kernels start an init process
• Unix processes have to maintain a parent and child relationship

4

We Used System Calls to Create Processes

You should be comfortable with:
• execve
• fork
• wait

This includes understanding processes and their relationships

5

We Explored Basic IPC in an Operating System

Some basic IPC includes:
• read and write through file descriptors (could be a regular file)
• Redirecting file descriptors for communcation
• Pipes (which you’ll explore)
• Signals
• Shared Memory

6

Scheduling Involves Trade-Offs

We looked at few different algorithms:
• First Come First Served (FCFS) is the most basic scheduling algorithm
• Shortest Job First (SJF) is a tweak that reduces waiting time
• Shortest Remaining Time First (SRTF) uses SJF ideas with preemptions
• SRTF optimizes lowest waiting time (or turnaround time)
• Round-robin (RR) optimizes fairness and response time

7

Scheduling Gets Even More Complex

There are more solutions, and more issues:
• Introducing priority also introduces priority inversion
• Some processes need good interactivity, others not so much
• Multiprocessors may require per-CPU queues
• Real-time requires predictability
• Completely Fair Scheduler (CFS) tries to model the ideal fairness

8

Page Tables Translate Virtual to Physical Addresses

The MMU is the hardware that uses page tables, which may:
• Be a single large table (wasteful, even for 32-bit machines)
• Be a multi-level to save space for sparse allocations
• Use the kernel allocate pages from a free list
• Use a TLB to speed up memory accesses

9

Page Replacement Algorithms Aim to Reduce Page Faults

We saw the following:
• Optimal (good for comparison but not realistic)
• Random (actually works surprisingly well, avoids the worst case)
• FIFO (easy to implement but Bélády’s anomaly)
• LRU (gets close to optimal but expensive to implement)
• Clock (a decent approximation of LRU)

10

Both Processes and (Kernel) Threads Enable Parallelization

We explored threads, and related them to something we already know (processes)
• Threads are lighter weight, and share memory by default
• Each process can have multiple (kernel) threads
• Most implementations use one-to-one user-to-kernel thread mapping
• The operating system has to manage what happens during a fork, or signals
• We now have synchronization issues

11

We Want Critical Sections to Protect Against Data Races

We should know what data races are, and how to prevent them:
• Mutex or spinlocks are the most straightforward locks
• We need hardware support to implement locks
• We need some kernel support for wake up notifications
• If we know we have a lot of readers, we should use a read-write lock

12

We Explored More Advanced Locking

Before we did mutual exclusion, now we can ensure order
• Semaphores are an atomic value that can be used for signaling
• Condition variables are clearer for complex condition signaling
• Locking granularity matters, you’ll find out in Lab 3
• You must prevent deadlocks

13

The Kernel Has To Implement It’s Own Memory Allocations

The concepts are the same for user space memory allocation
(the kernel just gives them more contiguous virtual memory pages):
• There’s static and dynamic allocations
• For dynamic allocations, fragmentation is a big concern
• Dynamic allocation returns blocks of memory

• Fragmentation between blocks is external
• Fragmentation within a blocks is internal

• There’s 3 general allocation strategies for different sized allocations
• Best fit
• Worst fit
• First fit

• Buddy allocator is a real world restricted implementation
• Slab allocator takes advantage of fixed sized objects to reduce fragmentation

14

Disks Enable Persistence

We explored two kinds of disks: SSDs and HDDs
• Magnetic disks have poor random access (need to be scheduled)
• Shortest Positioning Time First (SPTF) is the best scheduling for throughput
• SSDs are more like RAM except accessed in pages and blocks
• SSDs also need to work with the OS for best performance (TRIM)
• Use RAID to tolerate failures and improve performance using multiple disks

15

Filesystems Enable Persistence

They describe how files are stored on disks:
• API-wise you can open files, and change the position to read/write at
• Each process has a local open file and there’s a global open file table
• There’s multiple allocation strategies: contiguous, linked, FAT, indexed
• Linux uses a hybrid inode approach
• Everything is a file on UNIX, names in a directory can be hard or soft links

16

Sockets are IPC Across Physical Machines

We can now create servers and clients, but there’s much more to learn!
There’s networking and distributed systems courses

However, today we learned the basics:
• Sockets require an address (e.g. local and IPv4/IPv6)
• There are two types of sockets: stream and datagram
• Servers need to bind to an address, listen, and accept connections
• Clients need to connect to an address

17

Virtual Machines Virtualize a Physical Machine

They allow multiple operating systems to share the same hardware
• Virtual machines provide isolation, the hypervisor allocates resources
• Type 2 hypervisors are slower due to trap-and-emulate and binary translation
• Type 1 hypervisors are supported by hardware, IOMMU speeds up devices
• Hypervisors may overcommit resources and need to physically move VM
• Containers aim to have the benefits of VMs, without the overhead

18

Next Lecture We’ll Go Over Example Final Questions

Take the extra time to wrap up Lab 4!
• Everything is valid to put on the final
• Same idea as the midterm, just 50% larger
• June 8th, 24 hour window
• I’ll post the 2020 final on Discord for you to go over
• Bring questions for the last lecture!

19