알고리즘 문제 복습을 위한 블로그

Outline

① Process Concept

② Process Scheduling

③ Operations on processes

④ Inter-Process Communication

① Process Concept

프로세스

  - 실행중인 프로그램

상태

1. new

2. running

3. waiting

  - 입출력 완료. 신호 수신 등 어떤 사건이 일어나기를 기다림

4. ready

  - 프로세스가 처리기에 할당되기를 기다림

5. terminated

PCB (Process Control Block)

  - 프로세스와 연관된 여러 정보 수록1. Process state

2. Program Counter

3. CPU Registers4. CPU scheduling information5. Memory-managemen information6. Accounting information7. I/O status information

② Process Scheduling

Process scheduling queue

1. Job queue

  - 시스템 안의 모든 프로세스들, 메인 메모리로 불러올 프로세스 선택

2. Ready queue

  - 준비 완료 상태에서 실행 대기하는 프로세스들

3. Deivce queue

  - 특정 입출력 장치를 대기하는 프로세스들

Scheduler

1. Long-term scheduler (Job scheduler)

  - 레디 큐로 보낼 프로세스를 선택 (DISK -> 메모리)

2. Short-term scheduler (CPU scheduler)

  - 레디 큐에 있는 프로세스를 선택하여 CPU에 할당 (메모리 -> CPU)

3. Medium-term scheduler

  - 프로세스 swap in/out 결정 (Swapping)

Context Switch

CPU가 다른  프로세스로 전환될 때, 과거 프로세스의 문맥을 PCB에 저장

새 프로세스의 저장된 문맥 복구

문맥 교환 중에는 시스템이 유용한 일 못함 (overhead)

③ Operations on processes

프로세스 생성 시 고려사항

1. 자원 공유

  - 자식 프로세스는 부모 프로세스가 가진 자원의 부분집합을 사용

2. 실행

  - 부모는 자식이 실행 종료될 때까지 기다림 (대부분)

  - 부모, 자식 병렬적으로 실행

3. 주소 공간

  - 자식이 부모의 주소공간 복제

  - 자식 프로세스가 자신에게 적재될 새로운 프로그램을 갖고 있음

fork()

1. 자원 공유

  - 부모, 자식은 파일을 공유하지만 CPU time, 메모리는 공유하지 않음

2. 실행

  - 부모, 자식 병렬적으로 수행

3. 주소 공간

  - 부모 프로세스로부터 복제하여 새 프로그램을 로딩 (처음에는 스택, 지역변수, 힙, 프로그램 모두 똑같음)

exec()

자신의 메모리 공간을 새로운 프로그램으로 교체

자식이 종료될 때까지 준비완료 큐에서 자신을 제거하기 위해 wait() 호출

프로세스 종료

1. 자발적 종료

  -> exit() 시스템콜 호출하여 삭제 요청

  -> 부모 프로세스는 wait() 시스템콜 사용해서 종료된 자식의 PID 반환 받음

  -> 프로세스의 모든 자원(물리/가상 메모리, 열린 파일, 입출력 버퍼 등)을 운영체제로 반납

2. 강제 종료

  -> abort(), TerminateProcess()

  -> 자식이 할당된 자원 초과 사용

  -> 자식에게 할당된 태스크가 더이상 필요없을 때

  - 부모가 exit() 한 후에 자식이 계속 실행되는 것 허용 안할 때

좀비 프로세스

  - 종료되었지만 부모 프로세스가 아직 wait()를 호출하지 않은 프로세스

고아 프로세스

  - 부모 프로세스가 wait() 호출하지 않고 종료. 새로운 부모 프로세스로 init 프로세스를 지정

④ Inter-Process Communication

운영체제 내에서 실행되는 병행 프로세스들은 독립적이거나 협력적임

협력적 프로세스는 다른 프로세스와 영향을 주고받아야 함

1. 공유 메모리 (Shared memory)

  - 생산자-소비자 문제: 생산자가 정보 채워놓고, 소비자가 소모할 수 있는 항목들의 버퍼가 사용가능 해야 함

  - 동기화를 통해 생산되지 않은 항목들을 소비자가 소비하려고 시도하지 않음

  - 공유 영역 이외의 다른 프로세스의 메모리에 접근 불가

2. 메시지 전달 (Message passing)

  - 두 프로세스간 통신을 위해 통신 연결 (communication link) 필요

  1) 직접 통신 (Direct communication): 통신을 원하는 각 프로세스는 송/수신자의 이름을 명시해야 함

  2) 간접 통신 (Indirect communication): 메시지들을 메일박스, 포트로 송/수신

● 동기화

1. Blocking send(봉쇄형 / 동기식 보내기)

  - 송신자는 메시지가 수신될 때까지 막힘. 수신되면 다음 작업 진행

2. Non-blocking send(비봉쇄형 / 비동기식 보내기)

  - 송신자가 메시지를 보내고 작업 재시작. 계속 보낼 수 있음

3. Blocking receive(봉쇄형 / 동기식 받기)

  - 메시지가 이용 가능할 때까지 수신자 막힘

  - receive() 호출했는데 메일박스에 메시지 없으면 waiting 상태로 전환 (멈춤)

4. Non-blocking receive(비봉쇄형 / 비동기식 받기)

  - 송신자가 유효한 메시지 또는 null을 받음. 메시지 도착 안해도 다음 라인 수행

● 버퍼링

통신하는 프로세스들에 의해 교환되는 메시지는 임시 큐에 들어가있음

1. 무용량(zero capacity)

  - 송신자는 수신자가 메시지를 수신할 때까지 기다려야 함

2. 유한용량(bounded capacity)

  - 큐가 꽉 차면 송신자는 block됨

3. 무한용량(unbounded capacity)

  - 송신자 절대 block 안됨

● 공유 메모리 VS 메시지 패싱

1. 공유 메모리

  - system call이 공유 영역을 attach 할 때만 필요함. 속도 빠름

  - 보호 메커니즘 필요 (spin lock, 동기화)

2. 메시지 패싱

  - 네트워크에 연결된 컴퓨터간 통신에 용이. (컴퓨터 간에는 메모리 공유 불가)

  - 작은 양의 데이터 교환에 용이

  - system call이 매번 호출되기 때문에 속도 느림

  - 프로그래밍이 용이

Outline

① 운영체제 Service

② System Calls

③ OS Degisn & Implementation

④ 운영체제 Structure

⑤ System Boot

① 운영체제 Service

● For user

1. 사용자 인터페이스

  - CLI, GUI, Batch interface

2. 프로그램 실행

3. I/O 연산

4. 파일 시스템 조작

  - 읽기, 쓰기, 생성, 삭제, 검색

5. Communications

  - 프로세스 간 정보 교환

6. Error detection

● For efficiency

1. 자원 할당

2. Accounting

  - 현재 실행중인 프로세스 확인 가능 (작업 관리자)

3. Protection

  - 시스템 자원에 대한 모든 접근이 제어됨을 보장

4. Security

  - 외부 I/O 장치들을 invalid access로 부터 방어. 사용자의 접근 제어 (authentication)

② System Calls

운영체제에게 서비스를 요청할 수 있는 메커니즘

응용 프로그램이 하드웨어에 접근할 필요가 있을 때 호출

커널 모드 진입 방법

Policy: What will be done? (무엇을)

Mechanism: How to do it? (어떻게)

● System Call API

1. Win32 API

  - win32 API: CreateProcess()

  - system call: NTCreateProcess()

2. POSIX

  - POSIX API: malloc()

  - system call: sbrk()

● System call 직접 호출하지 않고 API로 호출하는 이유

1. 호환성: 각 시스템에 적합한 시스템콜을 간접적으로 호출

2. 쉬운 프로그래밍: 시스템콜의 자세한 내용을 몰라도 됨

● System call Interface

  - OS에서 다루는 모든 시스템 콜을 모은 테이블

  - system call number에 따라 테이블에 저장

  - system call이 호출되면 system call interface에서 lookup해서 실행

1) library 함수 호출

2) library에서 system call number 찾기

3) interrupt vector에서 system_call() 호출

4) system call interface에서 실제 system call 함수 호출

● 종류

1. 프로세스 관리

2. 파일 관리

3. 장치 관리

4. 정보 유지

5. 통신

③ OS Degisn & Implementation

● 설계 목표

1. 사용자 목적

  - 편리한 사용, 쉽게 배움, 안전, 빠름, 믿을만함

2. 시스템 목적

  - 설계·구현·유지·조작 용이, 구현, 유지보수, error-free

Policy (정책)가 변경되어도 내부 mechanism (기법)은 변경 안되도록

④ 운영체제 Structure

1. Simple structure

  - 현재 사용되지 않음

2. Layered approach

  - 운영체제가 여러 개의 층으로 나눠짐

  - 장점: 구현, 디버깅 간단함

  - 단점: 여러 층을 적절히 정의하는 것이 어려움, 효율 낮음

3. Microkernel

  - 중요치 않은 구성 요소를 커널로부터 제거, 그들을 시스템 및 사용자 수준 프로그램으로 구현

  - 장점: 운영체제 확장 용이, 보안성 및 신뢰성 높음

  - 단점: 메시지 전달 오버헤드 높음 (대부분 user level process)

4. Module

  - 커널은 핵심적인 구성요소의 집합만 가지고 있고, 부가적인 서비스는 모듈을 통해 동적으로 링크

5. Virtual machine

  - 서로 다른 운영체제를 하나의 하드웨어에서 수행

  - 장점: 하나의 기계로 여러 OS 환경에서 SW 테스트 가능

  - 단점: 구현이 어려움

⑤ System Boot

SYSGEN

   - 시스템은 각 특정 컴퓨터 사이트를 위해 구성 및 생성되어야 함

부팅

  - The procedure of starting a computer by loading the kernel

부트스트랩 로더

  - 커널 위치 찾기 -> 메모리에 load -> 시작

Outline

① 운영체제 Definition

② 컴퓨터 시스템 Organization

③ 컴퓨터 시스템 Architecture

④ 운영체제 Structure

⑤ 운영체제 Operation

① 운영체제 Definition

● 운영체제 역할

1. 컴퓨터 하드웨어 관리 

2. 프로그램 실행 제어

-> 운영체제 그 자체로는 유용한 기능 못함.

-> 다른 프로그램이 유용한 작업을 할 수 있는 환경 제공

●  운영체제 위치

응용 프로그램과 컴퓨터 하드웨어 사이

●  운영체제 목표

1. 사용자 프로그램 실행 및 사용자 문제 해결 용이하도록

2. 컴퓨터 시스템 사용 편리하게

3. 컴퓨터 하드웨어 효율적인 방법으로 사용하도록

●  운영체제

1. resource allocator

  - 효율적이고 공평한 자원 사용을 위해 자원을 어떻게 할당할 지 결정

2. control program

  - 에러와 부적절한 컴퓨터 시스템의 사용을 방지하기 위해 프로그램 실행을 제어

② 컴퓨터 시스템 Organization

● 4가지 기본 원리

1. Computer system I/O operation

2. I/O structure

3. Interrupt

4. Storage structure

+ Multi-processor systems

1. Computer system I/O operation

    I/O: 메모리 <-> 로컬 버퍼 간 데이터 이동

    I/O device와 CPU가 동시에 작업 수행

    인터럽트를 발생시킴으로써 Device controller가 CPU에게 I/O 연산이 끝났다는 것을 알려줌

2. I/O structure

    Bus

    A bus is a collection of parallel wires that carry address, data, and control signals.

    DMA (Direct Memory Access)

    CPU의 간섭 없이 I/O Device <-> 메모리 간 데이터 송수신

    I/O Device가 전송 작업을 수행하고 있는 동안 CPU는 다른 작업 수행 가능

3. Interrupt

    Operating System -> Interrupt driven (수많은 interrupt가 지속적으로 발생)

    Program Counter: 다음에 실행될 명령어의 주소 저장

    1) Interrupt: 프로세서 외부에서 발생 (Hardware)

      - Ctrl + C

    2) Trap: instruction 실행의 결과로 발생하는 이벤트에 의해 발생 (Software)

      - System call, Segmentation fault, exception

    소프트웨어 에러 또는 요청 -> exception, trap 생성

      - div by 0, request for operating system service

4. Storage structure

    1) Main memory

    2) Secondary storage

    Caching is an important principle of computer systems

③ 컴퓨터 시스템 Architecture

● Multiprocessors

장점

1. throughput 증가

2. 경제적

3. 신뢰성 증가

※ 오버헤드 때문에 성능 n배 보다 작음

④ 운영체제 structure

● Multiprogramming

CPU와 I/O device 동시에 작업 수행하도록 유지

Job scheduling에 의해 진행됨

CPU Scheduling

  - If several jobs ready to run at the same time

Job Scheduling

  - If several jobs are ready to be brought into memory, and there is not enough room for them

Swapping

  - If processes don't fit in memory, swapping moves them in and out to run

Virtual memory

  - allows execution of processes that are not completely in memory

  - Virtual memory (CPU가 보는 주소) > Physical Memory (실제 공간)

⑤ 운영체제 operation

Dual mode

1. user mode

2. kernel mode (previleged mode)

-> mode bit 사용

-> OS 보호하기 위해서

previleged instruction

-> 커널 모드에서만 실행됨

-> 사용자 모드에서 실행할 경우 trap 발생

-> trap, interrupt 발생 시 사용자 모드에서 커널 모드로 전환됨