OS Structures & Linux Overview

OS Design and Implementation

• There is no best/absolute answer for design and implementation of OS
  • But some approaches have proven successful
• Internal structure of different operating systems can vary widely
• Start the design by defining goals and specifications
  • Affected by choice of hardware and type of system
  • Specifying design requirements can be considered with
    • User goals – operating system should be convenient to use, easy to learn, reliable, safe, and fast
    • System developer goals – operating system should be easy to design, implement, and maintain, as well as flexible, reliable, error-free, and efficient
• The important principle is separating policy and mechanism
  • Policy
    • What should be done?
    • Policy decisions are important for all resource allocation problems
  • Mechanism
    • How to do something?
    • The tool for implementing a set of policies
• It allows maximum flexibility if policy decisions are to be changed later
  • Policies are likely to change depending on workloads, places, or over time
  • A general mechanism, separated from policy, is more desirable

Policy란 "무엇을 해야 하는가" 라고 설명할 수 있고
Mechanism이란 "결과물을 얻기위해 수행하는 일련의 기술, 프로세스" 라고 설명할 수 있다.

Separating Policy and Mechanism

• Example: CPU scheduler
  • Want to switch processes in the system
  • Policy (what)
    • Scheduling algorithm (FIFO, SJF, priority scheduling, …)
    • Quantum size (= time slice)
  • Mechanism (how)
    • Dispatcher for low-level context switching
    • Measure job length
    • Priority queues

Policy와 Mechanism에 대한 예를 하나 들어보자. CPU Scheduler는 어떤 시점에 어떤 프로세스가 CPU를 사용할지 관리하는 프로그램이다. 이 CPU 스케쥴러에서의 Policy는 어떤 프로세스를 어떤 식으로 줄세울지 관리하는 알고리즘이다.

즉, 어떤 CPU 스케쥴러의 Policy가 FIFO 알고리즘을 사용한다고 하면, 들어온 프로세스의 순서대로 CPU를 사용하게 할 것이다. 이런 Policy는 알고리즘마다 다르므로 관리자가 다른 알고리즘을 선택하면 Policy 자체가 바뀌므로 가변적이라고 할 수 있다.

반면, Mechanism으로는 프로세스를 교체하는 기능, 프로세스의 실행시간을 측정하는 기능 등 앞서 밝힌 Policy를 realize하는데 필요한 기능들이라고 할 수 있다.

OS Implementation

• Many variations …
  • Early OSes are written in assembly language
  • Then system programming languages like Algol, PL/1
  • Now C/C++ prevails
• Actually, a mix of languages in practice
  • Lowest levels in assembly
  • Main body in C
  • Systems programs in C, C++, scripting languages like PERL, Python, shell scripts
• High-level languages are easier to port to other hardware
  • But slower

Operating System Structure

• General-purpose OS is very large program
• Various ways to structure ones
  • Simple structure – MS-DOS
  • Monolithic – UNIX
  • Layered – Abstraction-based
  • Microkernel – Mach
  • Modules
  • Hybrid

Simple Structure: MS-DOS

• Written to provide the most functionality in the least space
• Not divided into modules
• Although MS-DOS has some structure, its interfaces and levels of functionality are not well separated
• Allow applications to access HW
• No user- and kernel - mode separation by Intel 8088

MS-DOS는 layer별로 완전히 분리되어 있지 않다.
일반적인 구조에서는 application이 하드웨어를 사용하기 위해서는 왼쪽 화살표와 같이 사용하길 권고한다.

하지만 MS-DOS는 layer 별로 분리되어 있지 않기 때문에 system program이나 application program이 직접 bypass를 통해서 HW에 접근 가능하다.
따라서 security 관점에서는 좋지 않음.

여기서 HW는 ROM BIOS device driver이다.

• Single-tasking, single memory space
• Shell (command interpreter) invoked(호출하다) when system booted
• Simple method to run program
• Loads program into memory, overwriting all but the kernel and a small part of CI
• No other processes created
• Program exits -> the remaining CI reloads the overwritten part from the disk

프로그램이 시작되면 CI의 일부가 process로 overwrite 된 것을 확인할 수 있다.

Layered Structure

• OS is divided into a number of layers (levels), each built on top of a lower layer
  OS는 하위 계층 위에 구축된 여러 계층(레벨)으로 구분됩니다
  • The bottom layer (layer 0), is the hardware; the highest (layer N) is the user interface.
  • Layers are selected such that each layer uses functions (operations) and services of only lower-level layers
    각 계층이 하위 계층만의 기능(운영) 및 서비스를 사용하도록 함.
• Modular(모듈화)
  • Simplifies the extension and maintenance of the code base(모듈화의 장점)
  • os에서 확장성 있는 구조를 가져갈 수 있음
  • 새로운 기능을 추가하고 싶을때 layer 사이에 새로운 layer를 삽입이 가능하고 대신 interface를 생성하는 것 중요.
• E.g., Multics with 8 rings of protection

Traditional UNIX System Structure

• Beyond simple… but not fully layered
  유닉스의 monolithic 방식
  복잡하게 하지 않고 단순하게 user,kernel, hardware로 계층화를 한다.

• 각 계층 사이마다 system-call, kernel interface 존재.

Monolithic: UNIX

• “The Big Mass” – a single large software system
  • The kernel
• Consists of everything below the system-call interface and above the physical hardware
• Provides a large number of functions for one level
  • the file system, CPU scheduling, memory management, I/O, …
• Advantage: Performance!
  • All UNIX variants (Solaris, HP-UX, Linux, BSD), early Windows
• Disadvantages
  • Difficult to maintain and upgrade due to interdependencies(서로 참조하는 부분이 많다) in the code
    • Security / reliability
    • Any component of OS can ruin entire system
    • Entire OS code runs in a single memory space
    • E.g., Over 35,000 drivers with over 120,000 versions on Windows XP
      » 85% of Windows XP crashes are from drivers
      » Drivers are 7x buggier than the kernel core

큰 코드들이 하나의 layer에 있기 때문에 큰 덩어리에 버그가 없다는 것을 입증할 수 없다.

Microkernel

• Moves out as much as possible from the kernel to user-space services
• Mach is an example of microkernel
• Mac OS X kernel (Darwin) partly based on Mach
• Communication takes place between user modules using message passing

• Benefits
  • Easier to extend a microkernel
    • Modular structure (easy to add services)
  • Easier to port the operating system to new architectures
  • More reliable, secure
    • Less code is running in kernel mode
    • Can be tested more rigorously
• Disadvantages
  • The performance overhead of communicating with user-level system services

Monolithic vs. Microkernel

• Monolithic kernels
  • Pros: Simplicity and Performance benefits
  • Cons: Complexity and Less extensibility(확장성)
• Microkernels
  • Pros: Easier for extension, More reliable (less code is running in kernel mode)
  • Cons: Performance overhead of communicating with system services

Modules

• Many modern operating systems implement loadable kernel modules

  • Uses object-oriented approach
    각 system 서비스를 하나의 object로 보고 os를 설계한다.
  • Each core component is separate
  • Each talks to the others over known interfaces
  • Each is loadable as needed within the kernel
  • Linux, Solaris, etc

• Overall, similar to layers but with more flexible
  확장성 있는 os 구조를 가지고 유지보수가 쉬움. 이런 장점을 살펴보면 layer와 유사하다.
  기존 layer 구조에서는 한 layer가 본인 위와 아래 layer와 통신을 할 수 있었다. 하지만 이 모듈구조에서는 interface에 따라 여러 컴포넌트와 통신 가능하다.

• Similar to microkernel but no messaging communication
  마이크로커널은 유저레벨에서 시스템 서비스를 올려서 IPC 메커니즘이 필요했다
  여기서는 코어파트와 통신할때는 IPC가 아니라 function call 형태로 통신하므로 훨씬 속도가 빠르다

메모리는 user와 kernel 영역이 존재, 기존에는 모든 os 기능을 kernel 영역에 올렸다면 지금은 필요한 핵심 기능만 kernel에 올리는 구조이다.

따라서 LKM은 secondary storage에 저장되어 있다가 필요하면 kernel에 올라가서 역할을 수행한다. dynamic linking과 유사..
이때 LKM이 커널에 올라가면 기존에 있던 core 파트와 통신하기 위한 인터페이스가 필요하다.

아래는 solaris의 구조이다.

Hybrid Systems

• Most modern operating systems are actually not one pure model
  • Hybrid combines multiple approaches from different systems to address(해결하다) performance, security, usability needs
  • Linux and Solaris kernels are monolithic by having the OS in a single kernel address space
  • Plus modular for dynamic loading of functionality(모듈러 구조도 동시에 사용하고 있다)
  • Windows mostly monolithic, plus microkernel for different subsystem personalities Apple Mac OS X hybrid, layered, Aqua UI plus Cocoa programming environment
    • Below is kernel consisting of Mach (microkernel) and BSD(Monolithic) Unix parts, plus I/O kit and dynamically loadable modules (called kernel extensions) (modular 구조까지 사용하고 있음)

iOS

• Apple mobile OS for iPhone, iPad
  • Structured on Mac OS X, added functionality
  • Cocoa Touch
    • Framework for developing mobile apps
  • Media services
    • Layer for graphics, audio, video
  • Core services
    • Provides cloud computing, databases
  • Core operating system, based on Mac OS X kernel

Android

• Developed by Open Handset Alliance (mostly Google)
  • Similar stack to iOS
  • Open Source (AOSP, https://source.android.com/)
• Based on Linux kernel but modified
  • Provide process, memory, device-driver management
  • Add power management
• Runtime environment includes core set of libraries and Android RunTime machine (ART)
  • Apps developed in Java API + Android API
    • Java class file -> Java byte code via Java compile -> (on-device) Native code via AOT compile
  • Libraries include frameworks for web browser (webkit), database (SQLite), multimedia, smaller libc

Android Architecture

Linux Overview

Why Linux?

• Learning Linux means improving the ability to develop/test applications using various commands and tools provided by Linux
  • vim, emacs, make, gcc, gdb, etc.
• Why should we learn Linux?
  • Most devices used in the IT industry are based on the Linux OS
    • E.g., Android for mobile, cloud server, network equipment, GENIVI for vehicle control and infotainment, Yocto project for IoT devices, etc.
  • Many open source programs run in the Linux-based environments.

Why Linux Kernel?

• Learning Linux Kernel means understanding the detailed operation of the kernel and improving the ability to modify several parts of the kernel
• Why should we learn Linux kernel?
  • You need to know detailed knowledge of the kernel to be an advanced programmer
    • Code optimization, debugging skills, etc.
  • It is essential if you want to be an embedded system developer dealing with low-level hardware interfaces (device drivers)
  • Linux kernel is an open-source based OS

The Birth of Linux

• Linux is a modern, free operating system based on UNIX standards
• First developed as a small but self-contained kernel (version 0.01) in 1991 by Linus Torvalds, with the major design goal of UNIX compatibility(호환성), released as open source

LoC per Linux Kernel Version

방대한 프로그램 코드다~

The Linux System

• Linux uses many tools developed as part of Berkeley’s BSD OS, MIT’s X Window System, and the Free Software Foundation's GNU project (여러 오픈 소스를 통해 개발되었다)

  • The Linux system is maintained by a loose network of developers collaborating over the Internet (the Linux community)
    특정 회사가 아니라 여러 개발자들이 개발한다는 의미입니다. 우리도 참여 가능
  • The main system libraries were started by the GNU project, with improvements provided by the Linux community

• File System Hierarchy Standard document maintained by the Linux community to ensure compatibility(호환성) across various system components

  • Specifies overall layout of a standard Linux file system, and determines under which directory names configuration files, libraries, system binaries, and run-time data files should be stored
    표준 Linux 파일 시스템의 전체 레이아웃을 지정하고 어떤 디렉토리 이름 구성 파일, 라이브러리, 시스템 바이너리 및 런타임 데이터 파일을 저장할지 결정합니다

Design Principles of Linux

• Linux is a multiuser, multitasking system with a full set of UNIX-compatible tools
  • Its file system adheres to traditional UNIX semantics, and it fully implements the standard UNIX networking model
• Main design goals are speed, efficiency, and standardization
• Linux is designed to be compliant(준수하는) with the relevant POSIX documents
  • The Portable Operating System Interface (POSIX) is a family of standards specified by the IEEE Computer Society for maintaining compatibility between operating systems
    휴대용 운영 체제 인터페이스(POSIX)는 운영 체제 간의 호환성을 유지하기 위해 IEEE 컴퓨터 협회에서 지정한 표준 제품군입니다.

Linux OS Structure

• It is based on UNIX and is structured similarly, i.e., Monolithic rather than Microkernel
  • Placing all of the functionality of the kernel into a single, static binary file that runs in a single address space
    커널의 모든 기능을 단일 주소 공간에서 실행되는 정적 이진 파일에 배치
  • Distinct(뚜렷한) performance advantages in terms of speed and efficiency
• Linux also has a modular design that allows the kernel to be modified during run time
  • Using loadable kernel modules (LKMs), primarily for supporting device drivers and file systems
  • LKMs can be “inserted OR removed” into/from the kernel as the system is started or during run time, such as when a USB device is plugged into/out a running machine
• Like most UNIX implementations, Linux is composed of three main bodies of code; Kernel, System libraries and System utilities
  대부분의 UNIX 구현처럼 리눅스는 커널, 시스템 라이브러리, 시스템 유틸리티의 세 가지 주요 코드로 구성되어 있습니다
  

Components of the Linux System

• Kernel

  • Responsible for maintaining all the important abstractions of the OS
  • All the kernel code executes in the processor’s privileged mode(= kernel mode) with full access to all the physical resources of the computer
  • All kernel code and data structures are kept in the same single address space

• System Libraries

  • Define a standard set of functions through which applications interact with the kernel, and which implement much of the operating-system functionality that does not need the full privileges of kernel code
    어플리케이션이 커널과 interaction할때의 함수들의 집합을 system library라고 한다.
  • The most important system library is the C library, known as libc

• System Utilities (= System Services)

  • Programs that perform individual, specialized(구체적인,전문화 된) management tasks
  • Some are invoked just once to initialize and configure some aspect of the system.
  • Others (known as daemons in UNIX terminology) run permanently, handling such tasks as responding to incoming network connections, accepting logon requests from terminals, and updating log files
    다른 것들(유닉스 용어로 데몬이라고 함)은 영구적으로 실행되며, 수신 네트워크 연결에 대한 응답, 터미널의 로그온 요청 수락, 로그 파일 업데이트와 같은 작업을 처리합니다

Kernel Modules

• Sections of kernel code that can be compiled, loaded, and unloaded independent of the rest of the kernel
• A kernel module may typically implement a device driver, a file system, or a networking protocol
• The module interface allows third parties to write and distribute, on their own terms, device drivers or file systems that could not be distributed under the GPL
  모듈 인터페이스를 통해 제3자가 GPL(free sofeware를 위한 general public license)에서 배포할 수 없었던 장치 드라이버나 파일 시스템을 자체적으로 작성하고 배포할 수 있습니다

  커널 모듈을 사용하는 비즈니스 측면에서의 이유
  GPL 라이센스를 따르지 않고 별도의 커널 모듈을 만들어서 자신들의 기술을 제공한다. 커널 모듈은 리눅스 커널 코드와는 별개의 코드로 간주하므로 GPL 라이센스를 따를 필요가 없다. 즉 자신들의 코드를 공개할 필요가 없다.

• Kernel modules allow a Linux system to be set up with a standard, minimal kernel, without any extra device drivers built in
• Four components to Linux module support:
  • module-management system
  • module loader and unloader
  • driver-registration system
  • conflict-resolution mechanism

Module Management

• Supports loading modules into memory and letting them talk to the rest of the kernel
• Module loading is performed in two stages
  1) The module loader asks the kernel (i.e., module management system) to reserve a continuous area of virtual kernel memory for the module
  모듈 로더는 커널(즉, 모듈 관리 시스템)에게 모듈에 대한 가상 커널 메모리의 연속 영역을 예약하도록 요청합니다
  2) The module loader passes the module, plus any symbol table that the new module wants to export, to the kernel.
  모듈 로더는 모듈과 새 모듈이 내보내고자 하는 모든 기호 테이블을 커널로 전달합니다.
• Module requestor
  • Manages loading requested, but currently unloaded, modules
  • Also, regularly queries the kernel to see whether a dynamically loaded module is still in use, and will unload it when it is no longer actively needed
    또한 동적으로 로드된 모듈이 여전히 사용 중인지 확인하기 위해 커널에 정기적으로 쿼리하고, 더 이상 능동적으로 필요하지 않을 때 커널을 언로드합니다

Driver Registration

• Allows modules to tell the rest of the kernel that a new driver (i.e., new fucntionality) has become available
• The kernel maintains dynamic tables of all known drivers, and provides a set of routines to allow drivers to be added to or removed from these tables at any time
  커널은 알려진 모든 드라이버의 동적 테이블을 유지하며, 드라이버가 언제든지 이러한 테이블에 추가되거나 제거될 수 있도록 일련의 루틴을 제공합니다.
• Registration tables include the following items:
  • Device drivers
  • File systems
  • Network protocols
  • Binary format
    모듈이 어떤기능이 제공하는지에 따라 테이블은 달라질 수 있다.

Conflict Resolution

• A mechanism that allows different device drivers to reserve hardware resources and to protect those resources from accidental use by another driver
• The conflict resolution module aims to:
  • Prevent modules from clashing over access to hardware resources
  • Prevent autoprobes from interfering with existing device drivers
  • Resolve conflicts with multiple drivers trying to access the same hardware:
    1) Kernel maintains list of allocated HW resources
    커널이 할당된 HW 리소스 목록을 유지합니다
    2) Driver reserves resources with kernel database first
    드라이버가 커널 데이터베이스로 리소스를 먼저 예약합니다
    3) Reservation request rejected if resource not available
    리소스를 사용할 수 없는 경우 예약 요청이 거부됨

Example

• You can make a custom kernel module easily
  • Make a source file & a build file (Makefile)

__init 키워드가 붙어있으면 커널로 load 될 때
__exit 키워드가 붙어있으면 커널로 unload 될 때
콜백 함수 형태로 호출된다.

module_init, module_exit은 어떤 함수가 init인지 exit인지 알려주는 것

hello.c 파일을 build를 하기 위함.

• You can make a custom kernel module easily
  • Compile the source file using the command make
    • You can acquire the module file (.ko)
  • And load the module using the command insmod
  • You can remove the module using the command rmmod

두개의 파일이 있는 디렉토리에서 make라는 명령어를 치면 자동으로 c코드를 build 해준다.

build 실행 이후, 최종적으로 .ko로 확장명이 끝나는 모듈 파일을 얻을 수 있다.
이게 kernel module binary이다.
이 binary를 얻으면 언제든지 kernel에 load 할 수 있다.
insmod 명령어를 통해 load 하게 된다.

hello.c에서 printk인점을 확인하자. 이는 커널 메시지를 출력하기 위한 함수이고, background에서 kernel log로써 출력한다. 따라서 hello world는 출력되지만 화면에는 보이지 않는다.
커널 메시지를 확인하기 위해서 dmesg 명령어를 사용한다.
커널 모듈을 unload 할때에는 rmmod를 사용한다.

Linux System Architecture

user space는 system call을 통해 kernel space를 이용할 수 있다.

5 Core Functions of Linux

• Process management
• Memory management
• File System management
• I/O (Device Driver) management
• Network management