• Optimal Policy 를 위한 과정
• 주어진 MDP를 이용해 Transition Probability와 reward function을 구함

  GOAL

1. 목적함수를 사용하여 리워드의 총합을 최대화하는 policy를 찾기
2. 최적의 state값 또는 action 값 함수 기반하여 optimal policy 찾기

즉, 최적의 state value와 state를 찾으면 최적의 policy를 찾을 수 있다.

그렇다면 어떻게 q*와 v*를 어떻게 구할 것인가?

그 방법은 다음 2가지

1. Policy Iteration (policy evaluation and policy improvement)
   • policy를 반복적으로 업그래이드 하겠다.
2. Value Iteration

이를 dynamic programming이라고 부른다.

Planning by Dynamic Programming

1. For prediction • Input: MDP S, A, p, r, ρ0, γ and policy π • Output: value function vπ

2. For control • Input: MDP S, A, p, r, ρ0, γ • Output: optimal value function v∗ and optimal policy π∗

   Planning by DP: Methods

   MDP에 관한 모든 정보를 알고 있고, 문제가 작을 때 활용 가능

3. Prediction : mdp와 policy가 주어졌을때, policy를 반복적으로 평가 (벨만 ex pectation 방정식 활용)

4. Control : mdp와 policy가 주어졌을때, policy반복적으로 평가 및 greedy policy (Bellman Expectation Equation) 와 value iteration (Bellman Optimal Equation)

Optimal Value Function vs. Optimal Policy

fixed-point iteration method의 필요성

fixed-point iteration method

fixed-point : 함수를 만족하는 해 fixed-point iteration : 해를 구하는 정의

어떻게 해를 구하는가? 초기값 x0에서 시작해서 반복적으로 찾아가겠다.

시간이 고정되어있다고 가정하면 순간의 state, action, reward는 랜덤변수 전체 Trajectory는 랜덤 프로세스

목표는 다음과 같다.

1. trajectory의 joint 확률을 규정 (여기서 쓰이는 과정이 markov 정리)
2. trajectory의 평균을 최대화를 하도록 어떤 액션을 취할지 결정

강화학습은 여기에서부터 시작된다.

1. Markov Process (state로 이루어진 프로세스) 여기에 reward 개념이 들어감
2. Markov Reward Process 여기에 action policy가 들어감
3. 최종 Markov Decision Process 완성

Markov Property

random process 특별히 마르코브 특징을 갖는다. 현재 직전까지의 history가 다음 상태에 영향을 미치지 않는다. (conditional independence)

마르코브는 state transition 확률만 알면 복잡한 joint 확률 대신에 마르코브 프로세스를 알 수 있게 된다.

예를 들면, 상태가 맑음, 흐림 두가지만 존재한다고 하자. transition matrix (오늘 날씨에만 의존한다고 가정)은 다음과 같다. 최초의 확률은 P(맑음) = 0.6, P(흐림) = 0.4

오늘 상태가 '맑음'이라고 가정하고 다음 상태를 구하면 다음과 같다. P(맑음,맑음,흐림 | 맑음) = P(맑음|맑음) * P(맑음|맑음) * P(흐림|맑음) = 0.8 * 0.8 * 0.2

• 0≤𝑃[𝐴𝐴]≤1
• 𝑃[Ω] = 1
• 𝑃[𝐴𝐴 ∪ 𝐵𝐵]=𝑃𝑃[𝐴𝐴] + 𝑃𝑃[𝐵𝐵]

  랜덤변수

  확률을 정의하기 위한 변수

  Discreate X

• Probability Mass Function (PMF)
• 반드시 확률은 0보다 클것
• 확률의 합은 반드시 1

  Continuous X

• Probability Density Function (PDF)
• 확률은 0보다 크거나 같을 것
• 랜덤변수 x가 A보다 크고 B보다 작을 확률은 적분으로 구할 수 있음

  Discrete Distriubution

  Bernoulli

  두개의 아웃풋을 내는 확률 실험 (0또는1, 동전 뒤집기)

Categorical

강화학습을 확률적으로 모델링하는데 가장 중요한 분포

주사위 던지기 할때, 1-6까지 경우의 수 가능했던 것을 생각해보면, 강화학습에서 현재 상황에서 어디로 갈지 하나를 고르는 문제와 동일

Continuous Distribution

Gaussian

강화학습시 policy를 결정하는데 중요한 역할을 하는 함수

• 평균, 분산의 분포

  Uniform

  min, max 값이 파라미터로 들어오는 함수

Multivariate Gaussian Distribution

covariance 값에 따라서 모양이 많이 달라진다.

• full
• diagonal
• spherical

In RL

예시

1. Frozen Lake example : 현재 상태가 어떠한지, 현재 상태에서 어떤 액션을 취할지 모른다 => 랜덤변수로 정의 -> state와 action은 이산 확률 변수
2. Cart Pole example : 현재 막대가 어느정도로 위치해있고, 각도는 어느정도로 틀어져 있는지 모른다. => state 랜덤 액션의 경우 오른쪽으로 갈지, 왼쪽으로 갈지 두개의 액션 존재 => action 이산 (2가지 -> 베르누이)
3. Pendulum example : 스테이트 : 벡터 연속변수 / 액션 : 스칼라 연속 변수
4. 많은 상태, 액션, 보상이 있으나 이 모든 확률을 모아서 (joint) 만드는 것

--

조건부 확률

Random Variable 사이 관계

두 확률변수 사이의 관계를 정의하자 : joint 분포

• joint : 두개가 동시에 발생했을때
• marginal : 하나만 일어났을때 확률값
• conditional : 한개의 랜덤변수가 주어졌을때, 다른 하나의 랜덤변수를 결정 가능 => policy 결정하는데 이용

현재 a 상태에 있다고 가정하면 앞으로 어떤 상태로 나아가야 하느냐를 결정하는 것 조건부 확률이자 policy 개념에 해당

independence & Conditional Independence

independence : 𝑋⊥Y

Y가 발생했다고 해서 X에 영향을 미치지 않는다. n개의 독립변수라면 각각의 합에 의해서 정의

conditional : 𝑋⊥Y | Z

이미 z 확률 변수가 알고있다고 가정했을때, x와 y가 어떻게 만들어지는가

in RL

Policy는 state와 action을 매핑한 함수 => 조건부 확률에 의해 결정 Markov Property : 과거의 상태와 독립적으로 작용하여 미래 결정 State Transition Probability : 다음 상태를 현재상태와 액션에 의해 결정

예시

1. Frozen-Lake -discrete policy : Categorical
2. Cart Pole -discrete policy : Categorical
3. Pendulum
   • continuous policy : Gaussian

강화학습의 goal : 끝날때마다 리워드의 합이 달라지고, 언제 끝날지도 모르기 때문에 전체적인 평균이 최대가 되게

조건확률과 베이즈

chain-rule

조건부 확률을 n개의 변수에 대한 것으로 확장 상태에서 다음 액션을 하고 다시 상태가 변하고 액션을 하고 ... 체인과 같이 연결

베이즈

이러한 베이즈와 체인룰을 사용해서 조인트에서 conditional, marginal 과의 관계를 정의 가능

conditional expectation

조건에 따라 두가지 유형으로 구분할 수 있다.

1. 임의의 값이 주어졌다는 조건 하에
   • 하나의 상수로 나온다
2. 임의의 랜덤변수가 주어졌다는 조건하에
   • 정해지지않아서 그것의 평균을 가져오나 여전히 랜덤변수

가령, 초등학교에 5학년의 키평균을 알고싶다고 가정한다면 값이 오로지 하나 (5학년이라고 특정) 1~6학년 어떤 학년인지 모르나, 그런 경우의 평균은 값이 6개의 값이 가능 후자에 대해서 평균을 다시한번 한다고 생각하면 평균의 평균이 되고, 다음과 같은 식으로 구성

Law of Total Expectation (law of iterated expectation, or Tower property) E[X] = E[E[X|Y]] 로 표현

다양한 용어 정리

확률 VS 통계

확률 : 현상을 정의하고 어떤 데이터를 예측하고, 생성하는 것

• 데이터가 없지만 확률 모델로부터 예측하거나, 생성할 수 있다는 것

• 데이터를 생성하고, 예측 가능

  통계 : DATA를 다루는 것

• 데이터로부터 확률을 추정하거나, 결론을 도출해내는 것

• 데이터에 숨겨진 다양한 특성 (분포)를 꺼낼 수 있음

분포가 갖는 파라미터가 존재한다면 분포로부터 데이터를 만들 수 있으며 (sampling)

sampling methode, generative model (생성형)

데이터가 존재한다면 데이터로부터 분포를 추정할 수 있음 (estimation)

maximum likelihood (ML) estimation method

*큰수의 법칙 : 데이터의 크기가 커질수록 분포에 가까워짐

Monte Carlo (MC) Estimation : 확률과 통계가 만나는 지점

샘플링을 통해서 복잡한 수학적인 값들을 근사화 하겠다.

• 문제 : 주어진 함수의 기댓값은 함수와 pdf의 곱을 적분 만일 주어진 함수가 아주 복잡해진다면 계산이 불가해진다. 그래서 나온 기법 MC

분포를 알면 데이터를 생성할 수 있다. -> 분포에서 N개의 데이터를 샘플링한후 -> 복잡한 주어진 함수에 대입하여 나온값들을 평균하면 실제 평균과 근사해진다. (N이 무한대로 갈때)

Random Process

랜덤변수는 값하나를 할당하는 것

예를 들어, 랜덤변수의 값이 정해지면 그와 매칭되는 하나의 랜덤 확률 P(X=0.4)가 결정되어야함

랜덤프로세스는 랜덤변수의 함수. 변수가 시간/공간에 따라 바뀌는 것 = stocastic process

이는 강화학습에서 상황, 액션, 리워드에 따라 만들어지는 trajectory가 시간에 따라 이어지는 것을 표현하는데 이용되는 개념이다. (이산적인 개념)

시간이 계속 변하나 이를 join해서 하나의 확률로 규정

joint 확률은 시간의 개념을 고려하지않고, 하나의 확률로 규정하는 것인데, 이 시간을 고려하지않는다는걸 지지하는 정리가 markov 이다.

과거의 개념을 잊는다?

이전에 어떻게 움직였든 관계없이 현재 상황에 따라서 액션을 결정하겠다는 것

Stationary Markov Process

시간에 무관하게 값들이 같다.

이 개념은 transiton probability, policy, reward 에 적용

• 모델은 함수다
• 모델의 모양은 parameter에 의해 결정된다.
• 이는 모델이 1차함수가 될 수도 있고, 2차식이 될 수도 있다는 의미
• loss/cost 함수 : 모델이 input과 output을 잘 설명하고 있는지 알려주는 척도
• optimization : 모델이 가진 파라미터를 최적의 파라미터로 만들기위한 목적
• 훈련이 얼마나 잘 되었는가 -> 테스트 과정
• 학습의 5단계 : data -> 모델 (함수, 파라미터) -> loss함수 정의 -> 최적화 -> 테스트
• 모델의 파라미터는 사용자가 정하는 것 (data를 보고 data의 특성이 가장 잘 드러나도록 정하는 것)
• 데이터가 들어오면 모델이 파라미터에 의해 값을 내고 이 값이 타겟을 얼마나 잘 설명하는지 loss함수로 값을 내고, 이 손실함수의 값을 가져와 파라미터를 업데이트하며 최적화(GD)를 진행한다. => target을 잘 설명하는 파라미터의 최적값을 찾아내는 것이 학습의 목표
• 최적의 파라미터를 찾아내면 그 파라미터를 이용해 새로운 data를 넣어서 아웃풋을 보고 테스트 진행
• 검증데이터와 테스트 데이터는 다른것 (검증은 train 데이터의 일부를 떼서, 검증에 활용) (data를 묶어서 처리하는 방식 : batch, 묶음, 다발)
• full-batch : 모든데이터를 한번에 입력해서 파라미터를 업데이트
• mini-batch : 데이터셋을 쪼개서 사용
• 데이터는 tensor로 표현 (스칼라 : 하나의 값(점) | 벡터 : 스칼라의 모음(선) | 메트릭스 : 행과 열로 표현(면) | 텐서 : 3차원 공간상에 depth도 포함)
• 이미지 : 픽셀로 구성 (픽셀은 0~255 크기)

           - 다중분류 - target이 k개의 정수인경우 (여러 정수중 하나로 예측하는 것) (학점 분배)

비지도학습

• target이 없는 학습 형태
• 비슷한 것끼리 모을수 있다. (input 만가지고 데이터의 특징을 발견해내는 일을 하는 학습 방법)

강화학습

• 학습의 구조가 전혀 다름
• agent(인공지능 프로그램) <-> environment (에이전트 외의 것 예를들어, 로봇/게임/ 강화학습 수행의 대상)
• 1. state (화면전체의 상태) 2. reward (보상) 3. action (행위) : action으로 인해 화면이 어떻게 바뀌고 보상이 어떻게 되는지 행동의 목적이 존재 (예를 들면 점수를 얻고자 하는것
• 미래의 보상을 최대화하는 인풋에 대하여 보상 진행
• 한번에 학습이 되는 것이 아니라 시간에 따라서 (goal : select actions to maximize total future reward)
• 피드백, delay, 순차적
• 어디에 쓰이냐 ? sequential decision making problems : 한번에 끝나는 것이 아니라 순차적으로 천천히 학습 / 시간마다 어떤 action을 할것이냐를 학습하는 것
• 순간에 어떤 결정을 할래? 이걸 결정하는 함수를 구하는 것이 강화학습의 목적 (future reward 극대화)

import gymnasium as gym

1. 다양한 실습 환경

* cartpole 환경

• continuous state / discret env / reward (넘어지지않으면 1점, cart의 위치가 벗어났을때, 막대의 각도가 넘어갈때 끝)

  * frozen lake

• 구멍에 빠지지않고, goal에 도달하기
• discrete state (16개의 공간) / discrete action (상하좌우이동) / slipperiness (환경을 stocastic하게 만들수있음)

  * pendulum

• 막대기를 돌려서 수직으로 세우는 것이 목표
• continuous state (세워진각도, 가속도 값 코사인값) / continuous action (회전력의 힘) / reward (세워지면 +1, 기운 각도가 세운것에멀어질수록 -)

  * nujoco : ant

• 8개의 관절에 힘을줘서 앞으로 잘 가도록 하게 만드는 것이 목표
• continuous state / continuous action

  2. 기본적인 코드

1. 환경을 준비하라 : 환경을 준비하고 초기 상태로 리셋 (make, reset)
2. policy에서 action을 선택해서(action_space.sample) environment로 보냄(step(action) : step 함수가 action을 받아서 결과를 output) => loop
3. 결과 출력 env.render 이후 env.close() : 환경 종료

   3. 개인적인 환경을 만들고 싶을때 사용할 class

• print(env.action_space)
• print(env.observation_space) (state)
• step() : action을 받아서 5개의 요소를 출력으로 뱉는다.
• fundamental space : box(=continuous) / discrete / multidiscrete / ..
• wrapper : gym을 만들고 wrapper로 감싸면 super class를 상속받아서 환경의 일부를 수정가능 (예를들어, 원래는 step 마다 0이었는데, step마다 -1이 되도록 변경 가능)

1. 강화학습의 개념 ( 아래 6개의 키워드 기억하기 )

• componants : agent, environment

• data : action, state, reward

• function : policy

  2. Componants

  agent, environment => interaction의 주체

• 주거니 받거니 하는 주체들

• 에이전트 : ai 프로그램 (연구 도메인의 ai 프로그램, 학습자, 결정알고리즘)

• 환경 : 에이전트가 상호작용하는 대상 => 에이전트가 환경에 진입하여 상호작용

  3. action, state, reward

• action의 주체 : 에이전트 (예, 자율주행차가 핸들을 꺽는 행위)

• action의 객체 : 환경 ( 핸들을 꺽는 행위를 환경이 받아들이고, 환경을 변화시킴) => 환경을 변화시키는 것 환경이 변화된다는것은 state가 바뀐다는 것이고, 그에 따른 reward를 에이전트에 보낸다. => 에이전트는 state와 reward를 받아와서 action을 만들고, 환경은 액션을 받아 state와 reward를 보낸다.

• state : 환경의 상황, 상태

• reward : 값이 딱 하나인 실수값 (action에 대한 좋은지 나쁜지에 대한 피드백)

  4. policy

• agent에 속해있는 함수

• state 기반 최적의 어떤 액션을 낼 것인가에 대한 전략

  5. trajectory (학습의 시퀀스)

• 시간에 따라서 멀티스탭

• 각 스탭마다 전략(policy/함수)가 존재. 이걸 위해 reward라는 개념이 존재

• 행동이 좋은지 나쁜지는 지금 당장은 모르나, 나중에 피드백이 발생

  6. state 의 정의가 반드시 필요

• state는 환경의 상황에 대한 모든 정보 포함

• 환경은 이전상태 + 현재 액션을 반영해 다음 상태를 결정 = 상태 전이 (state transition)

• 상태의 모든 정보가 에이전트에 제공되는 경우 : fully observable

• 모든걸 알 수 없고 부분적인 것만 알수 있는 경우 : partial observable

  7. reward

  하나의 스칼라값

• 액션에 대한 좋고 나쁨을 피드백하는 값

• 에이전트는 리워드가 굉장히 중요함 (왜? 지도학습은 목적이 확실, 강화학습은 학습하려는 함수 f를 만드는 기준이 리워드가 되기 때문)

• 리워드가 함수 f를 어떻게 만들어야 잘만든것인지 가이드를 해줌

• 이러한 피드백은 즉시가 아니라 한참뒤에 나올 수 도 있음 즉, 과거, 미래의 리워드를 고려해야한다는 의미

• 미래의 리워드가 어떻게 되어야 좋은 결과를 낼것인가 f를 정의 예를들어, 주식도 지금 당장 10만원보다 1년뒤에 총 1억을 버는것이 더 낫다. => 이과정에는 지금 당장은 오르거나 잃을 수도 있으나 전체적인건 1억을 벌고자함 리워드도 그때그때의 리워드를 생각할 것이 아니라 "누적"된 리워드를 생각

• 순간의 리워드 : 행동자체를 강화 또는 자제

• 장기적인 리워드

• dense : 행동을 할때마다 리워드가 나타나는 것

• sparse : 행동을 쭉하는데 마지막에, 듬성듬성 리워드가 나타나는 것 (바둑)

  8. 강화학습의 궁극적인 목적

• policy f를 아는것

• 기준 : 최종 최고 점수를 얻는 것이 목적, 리워드를 누적한 값

• 로봇의 경우, 최대의 보상 값을 얻기위해서는 넘어지지않고, 걸어가는것을 계속 유지할때 최대 (상황이 어떻게 변하던 간에)

9. exploitation

현재 액션을 하는데 기존의 경험을 활용해서 진행

10. exploration

그동안 간곳보다 최고의 액션이 있을 수도 있음 -> 한번 모험해보는 것 => 9와 10은 트레이드 오프 관계

11. 각 state별 함수를 얻어와, 최종 합이 최대값이 되도록 하는 목표를 이루기위해
12. 강화학습은 인간이 모르는 새로운 방법론을 도입할 수 있다.

    각 요소가 가질 수 있는 값

    1. action

    • action이 이산적인 값인지 연속적인 것인지에 따라 쓰이는 함수가 다르다.

      2. policy

    • policy state가 정해지면 행해지는 액션은 하나로 고정 :: deterministic == 확률이 1인 것 == 확률 분포 PMF
    • 확률실험에 의해서 state가 주어지는 것, 확률 분포가 필요한 이유 :: stochastic == 확률이 0.2, 0.8, 0.3 다양 == 확률분포 PDF => 그렇다면 확률이 결정되어야하는데 그 결정을 위해 확률 분포가 쓰인다. / 반드시 어딘가로 가는 것으로 정해진 것이 아니라 때로는 확률적으로 낮은 곳으로 가는 것도 가능 (새로운것을 탐험할 때 유리)

      3. environment

• 위로가기로 정해지면 반드시 위로 간다 :: deterministic
• 위로가기로 정해져도, 위로갈지 옆으로갈지 확률적으로 정해진다. :: stochastic

  4. etc

• trajectory : policy에 의해 벌어지는 것들
• episode : 하나의 trajectory가 끝나는 단위
• transition : state, action, reward. state (t+1) 의 쌍
• horizon - finite : episodic case
  • infinite : continuous case
• goal : trajectory마다 있는 reward의 총 합이 극대화가 되도록 하는 것

1) 정의

• 데이터를 망가뜨렸을때 모델의 성능 (에러율) 이 얼마나 나빠지는가

  2) 목표

• 모델이 실제 정답을 맞히기 위해 해당 피처에 얼마나 의존하고 있는지 확인하고자 함

Partial Dependence (부분 의존성)

1) 정의

• 다른 모든 조건 (피처)가 동일할 때, 오직 특정 피처 하나만 값이 변하면 모델의 예측값 (평균)이 어떻게 변하는가를 보여주는 기법

• 예를 들어, 집값을 예측하는 모델 (회귀)에서 방의 개수에 대한 부분 의존성을 본다면 방이 1개에서 5개로 늘어날때 집값 예측치가 평균적으로 어떻게 우상향하는지 선 그래프로 보여줌

  2) pd_variance (부분 의존성 분산)

• 부분 의존성 그래프 (선)가 위아래로 얼마나 심하게 요동치는지를 측정한 값

• 피처 중요도의 지표로 사용

  • 분산이 크다 : 그래프의 기울기가 가파르거나 굴곡이 심함 (해당 피처의 값을 조금만 바꿔도 모델의 예측값이 휙휙 변함 = 영향을 많이 미치는 중요한 피처)
  • 분산이 작다 : 그래프가 평평한 수평선에 가까움. 이 피처의 값을 아무리 바꿔봐야 모델의 예측값은 미동도 하지 않음 = 모델 예측에 쓸모없는 피처

    3) 목표

• 모델이 정답을 맞히는지, 틀리는지 관심없음. 모델의 출력이 해당 피처의 변화에 얼마나 민감하게 반응하는지 확인

  4) 코드

  exp = explainer.explain(X=X_train,features=features,kind='both')

• kind='average' (부분 의존성, PDP): 1,000명의 사람이 있다면 그 1,000명의 반응을 뭉뚱그려서 평균을 낸 굵은 선 딱 1개만 보여줌 (반 평균 성적)

• kind='individual' (개별 조건부 기대치, ICE): 평균을 내지 않고, 1,000명 각각이 온도가 변할 때 대여를 어떻게 할지 얇은 선 1,000개를 모조리 그려줌 (학생 개개인의 성적표)

• kind='both' (PDP + ICE): 위의 두 가지를 한 번에 다 계산. 배경에는 1,000개의 얇은 선(개별 반응)을 쫙 깔아두고, 그 위에 굵고 진한 선(전체 평균)을 얹어서 함께 보여줄 준비를 마친 것

both가 주는 인사이트 : 피처에 따라 극단적으로 다르게 반응하는 그룹이 있는지 살펴볼수있음 (피처간 상호작용가능)

(feature_names.index('temp'), feature_names.index('windspeed')),
(feature_names.index('mnth'), feature_names.index('weather')),
(feature_names.index('season'), feature_names.index('temp'))
]
 # compute explanations
exp = explainer.explain(X=X_train,
features=feature_interaction,
kind='average',
grid_resolution=25)

• 두 피처를 짝지어서 넣어서 두개의 피처가 서로 어떻게 상호작용하며 예측값에 영향을 미치는지 분석

from alibi.explainers import plot_pd_variance
plot_pd_variance(exp=exp_importance)

• 범용성, 확장성 우수
• C언어로 작성되어 시스템간의 이식과정을 단순화
• 다양한 기능
• 다중사용자, 다중작업, 대화형
• 파일과 입출력장치를 동일 취급 (장치의존성 제거)
• 유지보수 용이, 계층적파일시스템 (트리구조)

쉘 (shell)

• 프로그래밍 계층에 존재, 사용자가 입력하는 명령어를 이해, 실행하는 역할 수행
• 명령어 해석기
• 주기억장치에 상주하지않고, 보조기억장치에 교체가능 (커널과의 차이점)

커널 (kernel)

• 쉘을 포함한 응용프로그램에게 서비스 제공
• 컴퓨터 부팅시 디스크로부터 주기억장치로 적재된 후 시스템이 꺼질때까지 항상 주기억장치에 상주
• 대부분은 C, 일부는 어셈블리어

디스크 블록의 구조

• 부트 블록 : 디스크의 첫번째 논리적인 블록
  • 유닉스가 첫번째로 활성화되는데 사용되는 약간의 실행코드 포함
• 슈퍼블록 : 전체의 파일 시스템에 관한 정보를 가짐
  • 전체 블록의 수, 블록의 크기, 사용중인 블록의 수 등 파일 시스템의 정보를 가짐
• i-node 블록 : 디스크상의 파일에 대응하는 모든 inode 리스트로 된 고정된 크기의 블록
• 데이터 블록 : 실제 파일 블록을 저장하도록 사용, 디렉터리와 사용자 파일들 포함

파일 3가지 종류

1) 일반 파일 (regular file)

• 데이터 파일 : 일반적으로 보게되는 파일로써 문자를 담고 있는 텍스트 파일로써 이진 데이터를 담고 있는 파일
• 실행파일 : 실행될 수 있는 이진형식의 실행파일 (쉘스크립트같은 텍스트 형식의 파일)
• 숨김 파일 : 개인의 환경설정 파일이나, 시스템의 설정파일 ( . 으로 시작)
• 링크파일 : ms 윈도우의 바로가기 아이콘

2) 디렉터리 파일 (directory file)

• 디렉터리 내에 들어 있는 파일 및 디렉터리에 대한 정보 포함
• 디렉터리는 계층적으로 구성되며, 디렉터리 파일은 쓰기 보호 속성을 가진 일반 파일로써 파일 시스템만이 이 파일에 기록 가능 (사용자 프로그램은 읽기만 허용)

3) 특수 파일 (special file)

• 프린터, 터미널, 디스크 같은 주변장치나 직렬포트등을 표현하는 파일

링크파일 (link file)

1) 하드링크 (hard link)

• 파일을 생성하면 기본적으로 생성

• 일반 파일 이름 + inode + 데이터블록이 존재하면 하드링크는 1

• 일반파일은 기존 파일에 하드링크를 걸면 링크수 증가

• 두개의 파일이름이 하나의 inode 같은 데이터 블록을 가리킴

  → 시스템은 한 파일 이름에 대한 디렉터리 엔트리를 삭제하고 데이터 블록은 그대로

  → rm 명령어 : 하드링크에 대한 링크개수만 하나 감소

  → 실제 데이터 블록이 삭제되는 때는 그 링크의 개수가 0이 되는 시점

2) 심볼릭 링크 (symbolic link)

• 특정 디렉터리 파일을 다른 디렉터리에서 실행하려면 그 파일에 대한 절대경로를 이용해 명시
• 그 파일을 사용할 디렉터리로 복사
• 파일의 불필요한 반복적 복사를 방지하여 파일 시스템을 유연하게 활용
• 여러 디렉터리에서 동일한 라이브러리를 요구할 경우, 같은 파일을 여러사람이 공통으로 관리하면서 사용할 경우, 비슷한 역할을 담당하는 여러가지 파일들중하나를 선택하는 경우

inode의 내용

• 파일의 유형 (일반, 디렉터리, 특수)
• 파일의 보호 권한
• 파일 소유권과 소유자 그룹 id / 사용자와 그룹의 표시
• 하드링크계수, 파일에 대한 링크 수
• 파일의 생성 시기, 최종 수정시간 및 최종 접근 시간
• 일반 파일/ 디렉터리 파일인 경우 블록위치, 물리적 디스크 주소
• 특수파일인 경우 주기억장치 및 보조기억장치 번호
• 심볼릭 링크인 경우 심볼릭 링크의 값
• 파일을 지정하고 있는 디렉터리 항의 수
• (주의) 파일명은 없다!!!!

unix 명령어

UNIX 디렉터리 보호

• 각 SUB 디렉터리와 관련한 파일의 보호는 각각 3비트 (rwx)로 구성된 파일소유자, 프로젝트그룹, 일반 사용자들 3부분 정의

  • 파일 소유자 : 파일을 생성한 사용자
  • 프로젝트 그룹 : 파일에 대한 유사한 접근을 필요로 하는 사용자들의 집합
  • 일반 사용자 : 시스템에 있는 모든 다른 사용자들

• 첫글자 - 는 일반파일 d는 디렉터리 파일

• 하드링크수, 파일 소유자 이름, 그룹의 이름, 바이트 단위로 파일의 크기, 최종 변경 날짜, 파일명

• chmod : 허가권을 변경하기 위한 명령어

  chmod 741 [파일명]

프로세스간 통신

1) 파이프 pipe

• 두개의 프로세스를 연결해주는 open file로서 파이프의 한쪽 끝에 쓰인 정보를 파이프의 다른쪽에서 읽을 수 있도록 한다.
• 유닉스에서 프로세스들은 메일박스와 비슷하게 파이프를 통해서 프로세스 간에 통신하는 기법을 제공
• shell 에게 앞의 명령의 출력이 후속되는 명령의 입력으로 넘겨주도록 조정하는 수직선 |

2) 소켓 socket

• 종단간의 통신으로 네트워크를 통해서 다른 컴퓨터에 존재하는 프로세스와의 통신 제공
• 클라이언트 프로세스는 통신 시작, 서버프로세스는 통신내용 수신

3) 시그널 signal

• 하드웨어 인터럽트와 유사한 예외조건을 다루기 위한 소프트웨어 메커니즘
• 프로세스에게 이벤트 발생을 실시간으로 알려주기위해 사용

동기 vs 비동기

• 동기(Synchronous) : 작업을 요청한 뒤 결과가 나올 때까지 기다렸다가 다음 작업을 수행하는 방식
• 비동기(Asynchronous) : 작업을 요청한 뒤 기다리지 않고 다음 작업을 수행하다가 결과가 준비되면 처리하는 방식

관련정보를 포함하는 실제적인 파일들의 집합체와 시스템내의 모든 파일에 관한 정보를 제공하는 디렉터리 구조로 구성

• 파일 : 서로 연관성이 있는 데이터 집합 (보조기억장치의 저장단위)
• 파일이 저장되어있는 데이터를 액세스하는 방식 제공
• 파일이 안전하게 사용되고 보호될 수 있도록 하는 수단 제공

디렉터리

파일이름들을 디렉터리 항목으로 변환하는 기호테이블로 볼 수 있음

• 파일의 위치, 크기, 형태 등에 대한 각 파일의 실제적인 속성

파일 디스크립터

파일을 관리하기위해 시스템이 필요로 하는 정보를 보관하고 있는 자료구조 테이블

• file control block
• FCB는 보조기억장치에 저장되어 있다가 파일이 개방될 때 주기억장치로 이동

2. 보조기억장치 공간 할당 방식

(1) 연속할당

• 배열 구조 : 디스크 내의 파일들이 물리적으로 연속된 공간에 저장되는 기법
  • 고정크기, 가변크기로 구분
• 직접접근 : 연속하는 논리적 블록들이 디스크내의 물리적으로 서로 인접하여 있다는 것
• 파일의 시작주소와 파일 길이만 유지하면 되므로 파일 디렉터리 단순
• 파일의 생성과 삭제가 반복되면서 가용공간이 조각나, 외부단편화 발생 (압축필요)

(2) 연결할당

• 동일 파일에 속해있는 섹터들이 연결리스트로 연결
• 블록이 디스크 전체에 분산되어 있어도 액세스 가능
• 블록이 어디에 있는지 포인터만 연결해주면 되서 외부 단편화 발생 X
• 압축불필요
• 연결리스트는 포인터를 기억하기 위한 기억공간 필요 (낭비존재)
• 순차접근 : 파일의 블록들이 디스크 전체에 분산되어있어 검색에는 긴시간 요구
• 불연속 할당기법 : 링크를 이용한 섹터단위의 할당과 블록단위의 할당으로 구분

(3) 색인할당

• 모든 포인터들을 색인 블록으로 관리 (인덱스구조)
• 외부단편화 없이도 직접접근 가능 색인블록에 대한 낭비 존재
• 색인블록문제해결방법
  • 연결기법 : 여러개의 색인 블록들에 분산시키는 방법
  • 다중수준색인 : 첫번째 단계 색인 블록은 여러개의 두번째 단계 색인 블록들에 대한 포인터를 가짐
  • 결합기법 : 다중수준 색인을 확장한 기법

3. 디스크 스케줄링

디스크상의 여러곳에 분포되어있는 데이터를 이용하기 위해 디스크헤드가 움직이는 경로를 결정하는 기법 (탐색시간 최적화)

• 탐색시간 + 회전지연시간 + 전송시간

4. 탐색시간 스케줄링

(1) FCFS (First Come First Served)

요청큐에 먼저 도착한 요청이 우선 서비스

(2) SSTF (Shortest Seek Time First)

현재 헤드 위치에서 탐색거리가 가장 짧은 요청 트랙을 먼저 서비스

• 일괄처리시스템에는 유용, 대화형시스템에는 응답시간 편차로 인해 부적합
• 기아상태 발생 가능

(3) SCAN

SSTF 같이 동작하지만 헤드진행방향상의 가장 짧은 거리에 있는 요청을 먼저 서비스

• S자로 쓸고 내려오는 느낌
• SCAN은 처음부터 끝 트랙까지 요청이 없더라도 헤드가 이동
• 필요한 마지막 요청까지만 이동하는 것은 LOOK 스케줄링

(4) N-단계 SCAN

헤드가 한쪽 방향으로 이동해 나가면서 요청에 의해서 들어온 것만 서비스하다가 다시 반대쪽으로 가면서 이전에 도착했던 요청들을 서비스

• 일반 SCAN은 이동해가면서 들어오면 즉시 스케줄링

(5) C-SCAN

헤드는 항상 한쪽방향으로 헤드를 이동해가면서 요청 BUT 더이상 그 방향에 요청이 없을시에는 반대방향으로 헤드를 이동하는 것이 아니라, 다시 같은 방향으로 처음부터 처리를 진행

• 빗자루 쓸듯이 내려오는 느낌
• 가장 좋은 효과

• 주기억장치에 참조하려고 하는 페이지가 없을 경우 페이지 부재가 발생

  이때, 주기억장치 내에 어떤 페이지와 교체할 것인가를 결정하는 방법

• 페이지 부재가 발생하면 운영체제가 메모리에 들어올 페이지에 대한 공간을 만들어 주기위해 주기억장치에서 제거할 페이지를 선택하게 된다.

1) 최적 교체

• 현재 주기억장치에 있는 페이지들 중 현재 시점 이후로 가장 오랫동안 참조되지않을 페이지 교체
• 페이지 호출순서를 사전에 미리 파악해야하기때문에 비현실적

2) 선입선출

• 각 페이지가 주기억장치로 들어올 때마다 그 시간을 기억하고 있다가 페이지가 교체될 필요가 있을때 가장 먼저 주기억장치에 들어있는 페이지와 교체시키는 방법
• 원래는 페이지 프레임 (가용한 페이지 개수) 개수를 늘리면 부재율이 줄어드는데 fifo는 그러지 않음

3) 2차 기회 교체 (SCR, Second Chance Replacement)

• FIFO 방식의 단점인 가장 오랫동안 주기억장치에 있었던 자주쓰이던 페이지가 대체될 수도 있다는 것을 막기위한 방법 → 참조 비트를 두어 관리
• 페이지 사상표에 한개의 참조비트를 만들어, 처음에는 모든 참조비트를 0으로 그 후 프로세스가 수행되면서 참조한 각 페이지와 관계된 참조비트는 그값이 1로 변경

4) LRU (Least Recently Used)

• 최근에 가장 적게 쓰인 페이지 대체
• 최근의 상황이 가까운 미래에 대한 좋은 척도라는 locality에 의존

5) LFU (Least Frequently Used)

• 사용빈도가 가장 적은 페이지가 교체
• 가장 드물게 사용된 페이지가 가장 최근에 주기억장치에 옮겨진 페이지일 가능성이 있어, locality 위배

6) NUR (Not Used Recently)

• 근래에 쓰이지 않은 페이지는 가까운 미래에도 쓰이지 않을 가능성 많음
• 새로 호출하는 페이지와 대체
• 각 페이지당 필요한 두개의 하드웨어 비트를 둔다.
  • 참조비트 (0) : 페이지가 호출된 적이 없을때
  • 참조비트 (1) : 페이지가 호출된 적이 있을때
  • 변형비트(0) : 페이지 내용이 변형되지 않을때
  • 변형비트(1) : 페이지 내용이 변형되었을때
  • 참조비트보단 변형비트가 우선순위

7) Working Set

• 프로세스에게 필요한 만큼의 프레임을 재할당하는 방법
• 일정한 시간간격 사이에 하나의 프로세스가 참조하는 페이지들의 집합
• 최근에 참조하는 페이지들의 집합에 속하지 않는 페이지를 교체시키는 기법
  • 스레싱을 일어나지 않게 하여 cpu 이용률을 최대화 시킴

8) 페이지 부재 빈도 (PFF, Page Fault Frequency)

• workingset은 일정주기로 기억장치를 참조하고 나서 세트를 고치는 반면, PFF 방식은 페이지 부재율에 따라 주기억장치의 페이지 프레임 수를 조절
• 페이지 부재율을 적정수준으로 유지

2. 스래싱 (Thrashing)

너무 자주 페이지 교환이 일어나는 경우 프로그램 수행시간보다 페이지 교체에 많은 시간을 할애

• 다중프로그래밍 정도가 더 커지면 스래싱 현상이 자주 일어남 (cpu 이용률 감소)

해결책

• 다중프로그래밍 정도를 낮춘다.
• 프로세스들에게 충분히 큰 페이지 프레임을 할당
• 프로세스들이 가질 수 있는 페이지 프레임 수를 늘림
• 지역성이나 우선순위 교환 알고리즘 하용
• 지역 교환 알고리즘
  • 한프로세스가 스래싱을 유발하더라도 다른 프로세스로부터 프레임을 뺏어올수없고 자기가 할당된 프레임 내부에서 교환

3. 교체 지역성 (locality)

프로세스들은 기억장치 내의 정보를 균일하게 액세스하는 것이 아니라, 어느 한 순간에는 특정 부분을 집중적으로 참조

• 캐시메모리, 연관기억장치, LRU, WorkingSet, PFF 등의 근거 이론

종류

1. 시간지역성
   • 최근에 접근한 데이터나 명령을 곧 다시 사용할 가능성이 높다는 것
   • Looping, Subroutine, Stack, Counting, 집계에 활용되는 변수
2. 공간지역성
   • 어떤 주소를 접근하면 그 주변 주소들도 함께 접근될 가능성이 높다는 것
   • 배열 순회, 순차적 코드실행, 프로그래머들이 관련된 변수를 근처에 선언

동작원리

• 가상기억공간과 실기억공간을 연결하는 주소 매핑 과정 필요

• 논리 어드레스 공간을 블록으로 나누어 놓고 실제 주기억 용량에 맞는 블록만을 로드

  이때, 어떤 블록을 가져올 것인지는 DAT (Address 변환 테이블) 사용

• 가상주소는 프로그래머가 쓴 보조기억장치의 번지 (실행중인 프로세스가 참조하는 주소)

• 실주소는 주기억장치에서 사용가능한 실제 주소

2. 가상기억장치의 구분

3. 가상기억장치의 구현 방법에 따른 분류

(1) 페이징 (Paging)

블록 사이즈가 고정(동일)한 방식으로 사용자가 작성한 프로그램은 하드웨어에 의해 페이지 단위로 분해

• 물리적 (실) 주소 공간은 가상기억장치의 페이지 크기와 같은 페이지 프레임으로 나누어 사용된다.
• 최초, 최적, 최악 적합등 배치 기법이 필요없음

장점

• 세그먼트 테이블과 달리 페이지 테이블은 블록의 크기를 나타낼 필요가 없다.

• 보조기억장치의 페이지 크기와 주기억장치의 페이지 프레임의 크기가 동일

  ⇒ 외부 단편화 발생 x

단점

• 내부단편화 발생할 수 있다.
• 세그먼트 기법에 비해 주소변환 테이블을 기억하기 위한 많은 장소 필요 (페이지 사상으로 비용이 증가하고 수행속도 감소)
• 페이지는 프로그램에 상응하는 논리적의미를 갖지 못함 (세그먼트에 비해 공유, 보호 지원x)

(2) 세그멘테이션 (Segmentation)

블록사이즈가 가변적인 방식, 가변 사이즈 블록을 세그먼트라고 함

• 세그먼트는 프로그램에서 서브루틴과 같은 의미

• 세그먼트를 나누는 일은 프로그래머의 일

• 기억장치의 사용자 관점을 지원하는 기억장치 관리 기법으로 논리주소 공간은 세그먼트의 모임

  ⇒ 최초, 최적, 최악 적합 등 배치 기법이 필요

• 세그먼트 테이블의 각 항목은 세그먼트의 기준 (base) 과 세그먼트의 한계 (limit)을 가지고 있음

장점

• 내부단편화 발생 x
• 세그먼트 공유와 보호 측면에서 세그먼트 시스템은 페이지 시스템보다 수행방법이 쉽고 명확
• 페이징 시스템에 비해 세심한 액세스 제어 가능

단점

• 외부 단편화가 발생 가능

  ⇒ 세그먼트의 크기가 고정되지 않고 가변적

• 세그먼트의 크기가 가변적이라 세그먼트 영역이 다른 세그먼트영역을 침범하지 않기 위한 특별한 하드웨어 관리 필요

(3) 페이징/세그멘테이션 혼용 기법

• 세그먼트는 너무 가변적, 세그먼트의 크기가 너무 커질때를 해결
• 프로그램을 논리적인 세그먼트 단위로 분할, 분할된 각 세그먼트들을 다시 각각 페이지 단위로 분할
• 외부 단편화 제거, 내부단편화 발생, 사상표가 차지하는 공간의 오버헤드 증가
• 각각의 세그먼트들마다 하나씩의 페이지 테이블 유지관리 필요

4. 사상표 색인을 찾는 방법에 따른 분류

(1) 직접사상방법

• 페이지 사상표는 주기억장치에 존재

• 프로세스의 가상기억장치를 구성하는 모든 페이지에 대한 항목이 페이지 사상표에 존재

• 명령어 수행주기 외에 추가적인 주기억장치 수행주기 요구

  → 페이지 테이블을 위해서 한번, 그 메모리 자체를 위해서 한번, 총 2번의 기억장치 접근 필요

• 페이지 테이블의 각 엔트리에는 유효/무효 비트를 둠

  • 유효 비트라면 관련된 페이지가 프로세스의 합법적인 페이지임을 나타냄
  • 무효 비트라면 그 페이지는 프로세스의 논리 주소공간에 속하지 않는다는 것

(2) 연관사상방법

• 빠른 주소 변환을 위해 고속의 연관기억장치를 이용하여 페이지 사상표 전체를 넣는 방법
• 비용 많이들고, 구현하기 힘듦
• 캐시에 비해 매우 비싸서 이용하기 힘듦

(3) 연관/직접 사상 방법

• 보다 적당한 비용으로 연관사상의 장점을 살릴 수 있는 절충 방안
• 연관사상표 : 국부성에 의거, 최근에 가장 많이 참조된 페이지
• 페이지 사상표 : 연관 사상표에서 제외된 나머지 페이지

TLB (Translation Lookaside Buffer)

프로세서 내부에 있는 장치로 가상주소를 물리주소로 변환하는 속도를 높이기 위해 사용되는 캐시의 일종

5. 블록사상

(1) 페이지 크기가 작을 경우

• 더 많은 페이지와 frame이 존재하게 되어 → 페이지 테이블도 함께 커진다.
• 페이지 테이블 증가로 테이블 단편화 발생
• 작은 크기의 페이지가 지역성이 향상되어 프로세스가 효과적인 working set을 확보하는데 도움
  • working set : 일정한 시간 간격사이에 프로세서가 참조하는 페이지들의 집합
  • 공간지역성 : 어떤 주소를 접근하면 그 주변 주소들도 함께 접근될 가능성이 높다는 것
  • 시간지역성 : 최근에 접근한 데이터나 명령을 곧 다시 사용할 가능성이 높다는 것

(2) 페이지 크기가 클 경우

• 디스크로부터 입출력 전송 횟수 감소 → 입출력시간 최소화하기에 효율적

  디스크에서 하나의 페이지를 메모리로 전송하는 시간은 커짐

• 페이지 부재율 감소

• 참조되는 정보와 무관한 정보가 주기억장치에 적재되어 기억장치 내부 단편화 증가

• 전반적인 흐름은 페이지 크기를 크게하는 경향 존재

• 주기억장치 : cpu가 명령이나 자료를 직접 인출 혹은 반환할 수 있는 기억장치
  • CPU가 보조기억장치에 있는 프로그램이나 데이터를 참조하기 위해서는 먼저 주기억장치로 옮겨와야한다.
• 가상기억장치 : 주기억장치의 확장된 공간 (디스크)
  • 사용자가 주기억장치의 용량에 제한받지않고 보조기억장치의 용량에 해당하는 커다란 기억장소를 갖고 있는 것처럼
• 단일 사용자 시스템 : 한사람이 모든 주기억장치를 점유하여 사용하는 방법
• 다중프로그래밍 시스템 : 다수의 프로그램 또는 프로세스라 불리는 단위들을 주기억장치 내에 유지하여, CPU를 공유해가며 처리

2. 다중사용자 기억장치 할당기법

고정(정적) 분할 기억장치

주기억장치 사용자 영역을 여러개의 고정된(일정한) 크기로 분할하여 관리하는 기법

• 내부/외부 단편화 발생 가능

1) 내부 단편화

하나의 분할 영역에 작업을 할당하고 남은 빈 공간 (사용하고 남은 공간)

2) 외부 단편화

기억장치가 너무 많은 수의 매우작은 공간들로 단편화, 공간 중 일부를 사용할 수 없는 빈 공간 (사용할 수 없는 공간)

가변 (동적) 분할 기억장치

주기억장치 사용자영역을 각 작업에게 가장 합리적인 분할의 크기를 결정하여 주기억장치를 할당하는 기법

• 각 작업에 필요한 만큼의 기억장치를 할당, 내부단편화 발생 X 외부단편화 발생 O

1) 단편화 해결방법

• 기억장치 통합 : 이웃되는 가용공간을 하나의 커다란 가용공간으로
• 기억장치 집약 : 기억장치의 모든 내용들을 한군데로 몰고, 자유공간을 몰아서 큰블럭으로
• 쓰레기 수집 : 여러개의 작은 단편화 공간 (가용공간)을 모아서 하나의 큰 가용공간을 만드는 것

3. 기억장치 관리 정책

(1) 반입 FETCH 정책

CPU에 의해 실행되거나 참조되기 위해서 주기억장치로 적재할 다음 프로그램이나 자료를 언제 가져올 것인가 결정하는 정책

• 요구반입 : 실행중인 프로그램에 의해 어떤 프로그램이나 자료가 참조될 때 옮김
• 예상반입 : 앞으로 요구될 가능성이 큰 자료 또는 프로그램을 예상

(2) 배치 (Placement) 정책

주기억장치에 적재되어야할 페이지나 세그먼트를 주기억장치 어느 곳에 적재할 것인가

• 페이징 시스템 : 주기억장치에 적재될 페이지가 주기억장치의 가용 페이지 프레임 어디에 적재되되어도 무관 (배치기법 불필요)
• 세그먼트 시스템 : 최초 적합, 최적 적합, 최악 적합 같은 배치 기법 필요

1) 최초 적합 (First Fit)

• 가용공간중 첫번째 분할 영역에 할당
• 빈공간을 찾기위해 전체 조사하지 않아도 되어 결정이 빠르다.

2) 최적 적합 (Best Fit)

• 가용공간 중 사용한 후 남은 공백이 가장 적은 분할 영역에 할당
• 가용공간이 정렬되어 있다면 반만 탐색해도 필요한 공간 찾기 가능

3) 최악 적합 (Worst Fit)

• 가용공간 중 가장 큰 분할 영역에 할당

(3) 교체 (Replacement) 정책

새로들어온 프로그램이 들어갈 장소를 마련하기 위해서 어떤 프로그램이나 자료를 주기억 장치로부터 제거할 것인가

• 최적화 정책
• FIFO
• SCR (Second Chance Replacement)
• LRU (Least Recently Used)
• NUR (Not Used Recently)
• LFU (Least Frequence Used)
• Working Set
• PFF (Page Fault Frequency)

다중프로그래밍 시스템에서 아무리 기다려도 결코 일어나지 않을 사건을 기다리고 있는 하나 또는 그 이상의 프로세스들이 있는 상태

• 자원이 다수의 사용자 프로세스에 의해 공유되고
• 이들 각 프로세스가 자신에게 할당된 자원에 대해 독점적인 통제권을 가지고 있을때 발생
• 서로가 원하는 자원을 서로가 독점이용중인 상태

자원할당그래프

• 자원은 차원, 프로세스는 사각형

교착상태의 발생

상호배제, 점유와 대기, 비선점, 순환대기의 조건을 모두 만족했을때 교착상태 발생

1. 상호배제 : 자원의 배타적인 제어권
2. 점유와 대기 : 프로세스들은 다른 자원을 요구하면서 이미 어떤 자원 소유
3. 비선점 : 자원이 자원을 점유하고 있는 프로세스로부터 도중에 벗어나지 못함
4. 환형대기 : 프로세스 간 닫힌 체인 존재 (loop)

교착상태 해결방법

1) 교착상태 예방

사전에 교착상태의 가능성을 없애는 것 / 발생 필요조건을 만족하지 않게

• 상호배제예방 : 비공유자원에 대해서만 상호배제 하도록
• 점유와 대기 예방 : 필요한 자원을 한꺼번에 요청하여, 전부 할당해주던지 하나라도 없으면 아예 하나도 안해주던지 (all or nothing)
• 비선점예방 : 자원을 가지고 있던 프로세스가 더이상 자원 할당 요구가 받아들여지지 않으면 원래 가지고 있던 자원 일단 반납 후, 필요하면 다른 자원을 요구하는 방법 (선점을 가능케함)
• 환형대기 예방 : 각 자원의 할당 순서를 부여, 프로세스들이 자원을 요청 할때 번호 순서대로 요청

2) 교착상태의 회피 (avoidance)

교착상태 발생 가능성을 미리 제거하는 것이 아니라, 발생가능성을 인정하고 교착상태가 발생하려고 할때 이를 적절히 피해가는 방법

• 시스템의 운영 상황을 보아가면서 교착상태 가능성을 피해가는 것
• 은행가 알고리즘 : 프로세스가 현재 가용한 자원들을 요청할 때마다, 시스템은 자원이 즉시 할당될 수 있는지 또는 대기해야하는 지 결정 (안전상태를 유지)
• 자원할당상태 : 가용한 자원의 수, 할당된 자원의 수, 최대 자원요구수
• 은행가 알고리즘에서 자원은 동일한 유형의 자원을 의미

상태

• 안전상태 : os가 현재 모든 사용자에게 그들의 작업이 일정기간내에 끝나도록 할 수 있는 상태
• 불안전상태 : os가 현재모든 사용자에게 그들의 모든 작업을 일정기간내에 끝낼 수 없는 상태
  • 교착상태 발생 가능한 상태 (불안전 = 교착상태를 의미하는 것은 아니다. 포함관계)
• 은행가 알고리즘의 단점
  • 할당할 자원이 일정량 존재해야함
  • 각 프로세스의 최대 자원 요구량을 미리 알아야한다.
  • 일정한 수의 사용자 프로세스가 있을때만 적용 가능
  • 프로세스들은 유한한 시간내에 할당된 자원을 반납해야함
  • 시스템이 안전할 때만 자원을 할당, 자원의 할당 순서를 부여하여 제공

3) 교착상태의 발견 (detection)

여러시스템에서 사용되는 방법으로서, 원하는 것이든지 아니든지 일단 교착상태가 발생하도록 허용

• 교착상태가 발생하면 교착상태가 일어났는지 판단하고, 그 교착상태에 관련된 프로세스와 자원을 조사하여 결정해내는 방법
• 자원할당그래프 혹은 대기 그래프를 사용하여 사이클을 탐지하면서 교착상태 검출
• 프로세스와 자원간에 순환적 요구와 할당 관계에 있는 것을 규명

4) 교착상태의 회복 (recovery)

시스템으로부터 교착상태를 제거하여, 이후로는 시스템이 교착상태에 빠지지않고 잘 진행되게 함

• 교착상태에 빠진 프로세스가 완료되고, 그 프로세스에 할당된 자원을 회수할 수 있도록 함
• 교착상태 사이클이 없어질 때까지 프로세스들을 종료시키거나 할당된 자원을 중단시킴
• 회복은 몇개의 프로세스들이 수행한 작업이 일부 또는 전부를 잃게됨

하나의 프로세스가 수정가능한 공유자원을 액세스하고 있을때, 그 프로세스에 의해 참조되는 프로그램의 부분을 의미

• 하나의 프로세스가 공유데이터를 접근하면 다른 프로세스는 그 공유데이터를 접근해서는 안됨

  → 여러 프로세스들 중에 하나의 프로세스만이 임계영역을 사용할 수 있도록 하여 임계영역에서 공유변수 값의 무결성 보장

• 인터럽트, 교착상태, 무한반복이 발생하지 않도록 해야한다.

  → 인터럽트 수행을 완료하거나 교착상태가 해제될 때까지 임계영역을 벗어날 수 없기 때문

코드영역

• 프로세스가 임계영역에 진입하려면 진입허가 요청 필요 → 진입영역
• 임계영역을 이용한 이후 임계영역을 빠져나왔음을 알리는 진출영역
• 그 밖의 나머지 코드 부분 → 잔류 영역

요구조건

1) 상호 배제 ( mutual exclusion)

한 프로세스가 공유자원을 사용하고 있을때, 다른 프로세스들이 사용하지 못하도록 배제

• 하나의 공유자원을 상호 배타적으로 이용 동시에 불가

2) 한정대기 (bounded waiting)

어떤 프로세스든 대기를 한 이후에는 반드시 임계영역으로 진입할 수 있도록 함

• 세마포어 내에서 무한히 기다리는 바쁜 대기 (계속해서 확인하는 대기)

3) 진행 조건

• 하나만 선택되어 임계영역으로 진입가능

동기화 기법

1) 상호배제

여러개의 병렬프로세스가 공유자원에 접근시 접근중인 임의의 시점에서 하나의 프로세스만이 그 접근을 허용하도록 제어

2) 세마포어

세마포어 s는 정수값을 가진 변수로서 초기화를 제외하고는 단지, 두개의 연산 P (wait), V(signal) 만으로 접근가능한 특수한 변수

• 세마포어에 대한 연산은 처리 도중에 인터럽트 되어서는 안된다.
• 여러 프로세스가 동시에 세마포어 값을 수정 불가능
• 프로세스 사이의 동기를 유지하고 상호배제의 원리를 보장
• 동일한 공유자원이 여러개 있는 경우 signal(s) 연산을 먼저 수행했을때 교착상태 발생 가능

wait(s) : if (s >0) s = s+1 # wait 연산은 진입영역
                    else 현재의 프로세스를 블록하고 대기 큐에 추가 # 잔류영역
signal(s) : if (1개 이상의 프로세스가 s에서 대기중) 그중 한개 프로세스만 진행
                        else s = s+1 # signal(s) 연산은 진출영역

3) 모니터 (monitor)

순차적으로만 사용할 수 있는 공유자원을 할당하는 데 사용되는 데이터와 이들 데이터를 처리하는 연산의 집합으로 이루어진 병행성 고급 구조체

• 반드시 해당 모니터 진입부를 호출, 여러개의 프로세스들이 동시에 모니터에 들어가려 할 경우 모니터 자체는 상호배제 실시

• 모니터 내부의 변수는 허가된 모니터 내부 프로세스만이 접근 가능

  외부 프로세스는 모니터 내부를 직접 액세스 불가

• 정보은폐기법 이용

CPU 자원을 언제, 어느 프로세스에게 배당할 것인지를 결정하는 작업

성능 기준

• 중앙처리장치 이용률 : CPU 수행시간 또는 시스템 구동 시간
• 처리량 (Throughput) : 단위 시간당 완료되는 프로세스 수
• 대기시간 (Waiting Time) : 준비 큐에서 대기하는 시간
• 응답시간 (Response Time) : 작업을 제출한 후 첫 응답이 올 때까지의 시간
• 반환시간 (Turnaround Time) : 프로세스가 시스템에 진입하여 작업을 완료하기까지의 시간

2. 방법별 분류

(1) 선점 스케줄링 (preemptive scheduling)

뺏기 가능

• 빠른 응답 시간을 요구하는 시분할 시스템에 유용
• 문맥교환으로 인한 오버헤드 초래
• 응답시간 예측 힘듦
• 기법 : RR, SRT, MLQ, MFQ, 우선순위 스케줄링

(2) 비선점 스케줄링 (NON-)

못뺏음

• 모든 프로세스에 대한 대우는 공정히 처리
• 짧은 작업이 긴작업을 기다리는 경우 발생
• 응답시간 예측가능
• 기법: FCFS, SJF, HRN, 우선순위 스케줄링

3. 프로세스 스케줄링 알고리즘

1) FCFS 스케줄링 - 비선점

First Come First Served

• 대기큐에 도착 순서에 따라 cpu 할당
• 선입선출
• 겉보기엔 공정, 긴작업이 짧은 작업을 오랫동안 기다리게 할 수 있음
• 중요한 작업이 중요하지않은 작업을 기다리게 함
• 대화식 시스템에는 적합 x

2) RR 스케줄링 - 선점

Rround Robin

• FCFS 에 의해 프로세스들이 내보내지며 각 프로세스는 같은 크기의 CPU 시간을 할당
• 주어진 할당 시간내에 처리하지못하면 다음 프로세스로 넘어감. (큐의 가장 마지막으로 이동)
• 다중 프로그래밍 시스템, 시분할 시스템에 효과적
• 할당시간이 길면 FCFS에 수렴
• 할당시간이 짧으면 문맥교환으로 부하 발생

3) SJF 스케줄링 - 비선점

Shortest Job First

• 기다리고 있는 작업중에서 수행시간이 가장 짧다고 판정된 프로세스 먼저 수행
• 기아상태 발생 가능
• 최소의 평균대기시간을 가짐 벗 비현실

4) SRT 스케줄링 - 선점

Shortest Remaining Time

• SJF와 마찬가지로 새로 도착한 프로세스를 포함하여 처리가 완료되는데, 가장 짧은 시간 소요된다고 판단되는 프로세스 먼저수행
• 현재 실행중인 프로세스라도, 남은 처리 시간이 더짧다고 판단되면 언제라도 실행중인 프로세스가 선점 당함 (기아상태 발생가능)
• 적은 대기시간, 선점 오버헤드 발생

5) HRN 스케줄링 - 비선점

Highest Response ratio Next

• SJF의 스케줄링 긴작업과 짧은 작업간의 지나친 불평등을 보완한 에이징 기법
• 오래 기다린 프로세스는 우선순위가 높아지게 되어 기아상태 해결
• 우선순위 = (대기시간 + 서비스를 받을 시간) / 서비스를 받을 시간

6) 다단계 큐 스케줄링 - 선점

Multi Level Queue

• 여러종류의 그룹으로 나누어 여러개의 큐를 이용하는 기법
• 각 큐의 독자적인 스케줄링 알고리즘 존재
• 큐내의 작업은 FCFS, 큐 간 작업은 선점
• 프로세스 성격에 따라 분류가능

7) 다단계 피드백 큐 스케줄링 - 선점

프로세스가 큐들 사이에 이동하는 기법

• 새로 들어온 프로세스에게 높은 우선순위 할당 단계 1에서 즉시 수행
• 이후 점차 낮은 우선순위를 부여하여 단계 N 쯤되어 나중에는 그작업이 완료 될 때까지 라운드로빈으로 순환

8) 우선순위 스케줄링

각 프로세스에게 우선순위를 부여하여 순위가 높은 순서대로 처리하는 방법 ⇒ 비선점 선점 다 가능

** 기아상태가 발생하는 스케줄링 기법

→ SJF, SRT, 우선순위 스케줄링

CPU에 의해 수행되는 시스템 및 사용자 프로그램

• 프로그램 카운터의 값과 처리기 레지스터의 내용으로 대표되는 현재 활동을 포함

• 프로그램은 디스크에 저장된 파일의 내용과 같은 수동적인 존재

  프로세스는 다음에 실행할 명령어를 지정하는 프로그램 카운터와 연관된 자원의 집합을 가진 능동적인 존재

특징

• 실행중인 프로그램
• 프로세서가 할당되는 개체
• 프로시저가 실행중인 것
• 샐행중인 프로시저 제어의 경로
• 비동기적 행위
• 디스패치가 가능한 단위
• PCB를 가진 프로그램

프로세스 상태 전이도

1. 생성상태 : 사용자가 요청한 작업이 커널에 등록되어 커널공간에 PCB 생성된 상태
2. 준비 (Ready) 상태 : 프로세스가 기억장치를 비롯한 모든 필요한 자원들을 할당받은 상태에서 프로세서를 할당받기위해 기다리고 있는 상태
3. 실행 (Execute) 상태 : 프로세스의 프로그램코드가 기억장치로부터 읽혀지면서 프로세서에 의해 실행되고 있는 상태
4. 대기 (Block) 상태 : 프로세스가 원하는 자원을 할당받지 못해서 기다리고 있는 상태
5. 완료(Finish) 상태 : 프로세스가 자신의 연산을 모두 마치면 완료상태로 전환되고 그 프로세스에 할당되었던 모든 자원 해제

프로세스가 전이되는 시기와 이유

1. dispatch : 준비상태 → 실행 상태
   • 준비상태의 프로세스들 중에서 우선순위가 가장 높은 프로세스를 선정하여 CPU 할당
   • 단기 프로세스 스케줄러에 의해 선택된 프로세스가 실질적으로 CPU를 할당
2. Time Run Out : 실행상태 → 준비상태
   • 지정된 CPU의 할당 시간을 모두 사용한 프로세스는 다른 프로세스가 CPU를 선점하고, 그 프로세스는 준비상태로 전환
3. Block : 실행 → 대기
   • 실행중인 프로세스가 입출력명령을 만나면 입출력 인터럽트가 발생하여 입출력 전용 프로세서 (DMA)가 입출력을 완료할 때까지 CPU를 반납하고 대기상태로 전환
4. Wake up : 대기 → 준비
   • 입출력 완료를 기다리다가 입출력 완료 신호가 들어오면, 대기중인 프로세스는 준비상태로 전환

프로세스 제어블록 (PCB)

운영체제에게 프로세스에 대한 모든 정보를 제공해 주는 자료구조 테이블

• 운영체제가 CPU를 다른 프로세스에게 넘기고 다시 그 프로세스를 가져올때 저장된 PCB 재사용

PCB의 정보

• 프로세스의 현상태
• 프로세스의 고유한 식별자
• 부모프로세스 포인터
• 자식프로세스 포인터
• 프로세스 우선순위
• 프로세스가 위치한 메모리에 대한 포인터
• 할당된 자원에 대한 포인터
• 프로그램 카운터
• 중앙처리장치 레지스터 보관장소

2. 스레드 (Thread)

프로세스 구성을 제어흐름부분과 실행환경부분으로 나눌때, 프로세스의 실행부분을 담당. 실행의 기본단위

• 각 스레드는 독립적인 제어흐름을 가지고, 자신만의 스택과 레지스터 가짐
• 한 프로세스 안에 있는 다른 스레드들과 코드, 데이터, 운영체제 자원등을 공유
• 스레드들도 중앙처리장치를 공유, 준비, 블록, 수행, 종료 등 여러 상태들중 하나의 상태로 있기 가능
• 한 프로세스 내에 여러개의 스레드 존재 가능
• 빠른 속도의 문맥 교환가능

1. 공유 영역 : 코드, 정적 전역 데이터, 힙, 커널데이터
2. 사유영역 : 스택, 지역데이터, 프로그램카운터, 레지스터 집합

다중 스레드 장점

• 응답성: 응용프로그램의 일부분 봉쇄가능, 긴 작업수행시 프로그램 수행 계속되는 것을 허용
• 자원공유
• 경제성
• 다중처리기 구조의 활용 : 병렬 가능

3. 스레드 구현 방법

1) 커널 수준 (시스템 호출 ) 스레드

• 커널이 스레드 관리
• 스레드가 봉쇄형 시스템 콜을 수행하면 커널은 응용프로그램내의 다른 스레드의 수행을 스케줄 가능
• 인터럽트를 통한 이전 → 수행시간 많음
• 태스크 내의 스레드도 독립적으로 스케줄 가능

2) 사용자수준 (라이브러리) 스레드

• 커널위에서 지원되며 사용자 수준의 스레드 라이브러리에 의해 구현
• 모든 스레드 생성과 스케줄링은 커널의 개입없이 사용자 공간에서 이루어짐
• 운영체제는 스레드 인식 못함 → 운영체제의 호출 시에 프로세스 전체가 기다리게 됨 (스케줄링 불공평)

프로그램 실행시 메모리 영역 구조

1. 컴파일 시 크기 결정
   1. code (text) : 함수, 제어문, 상수 (쓰기 금지)
   2. data : 전역변수, 정적 변수
   3. bss (blocked stated symbol) : 초기화 안된 전역변수
2. 실행중 메모리 할당
   1. heap : 동적할당 malloc, new
   2. stack : 지역변수, 매개 변수

일괄처리 시스템 (Batch Processing System)

• 요구사항이 비슷한 여러개의 작업을 모아서 한꺼번에 처리

다중 프로그램 시스템 (Multiprogramming System)

• cpu 효율 극대화, 여러개의 사용자 프로그램이 마치 동시에 실행되는 것처럼 처리
• cpu 1개 의 시스템의 메모리에 여러개의 프로그램 (multi-jobs) 적재

시분할 시스템 (TSS, Time Sharing System)

• 각 사용자에게 cpu에 대한 일정 시간을 할당 (time slice)
• round - robin 방식
• 멀티 유저, 멀티 프로그래밍, 대화식

실시간 시스템 (Real Time System)

• 처리를 요구하는 자료가 발생할 때마다 즉시 처리
• 그 결과를 구동기를 통해 출력 또는 요구에 대하여 응답

다중처리 시스템 (Multiprocessing System)

• CPU여러개, 기억장소에 여러개의 JOB 존재
• 여러개의 프로세서가 공동 기억장치를 통하여 메모리 공유, 다중처리기가 단일 운영체제에 의해 제어 가능

분산처리 시스템 (Distributed Processing System)

• 하나의 대형 컴퓨터에서 수행하던 기능을 지역적으로 분산된 여러개의 미니컴퓨터에 분담
• 통신망을 통하여 교신, 처리
• 각 시스템은 자신만의 os와 기억장치를 가지고 독립적으로 동작, 필요한 경우 통신

2. 입출력 방법

버퍼링, buffering

• 한작업의 계산과 함께 입출력을 동시에 수행하는 방법
• cpu 는 입출력장치보다 속도가 빠르기 때문에 입출력장치 속도에 의해 제한

스풀링, spooling

• 디스크의 일부를 스풀공간이라고 부르는 매우큰 버퍼처름 사용하는 방식
• 디스크를 스풀공간으로 사용하는 이유는 입출력장치와 cpu의 속도차이 해소위함

3. 가상머신

컴퓨팅 환경을 소프트웨어로 구현한 것으로 컴퓨터를 에뮬레이션하는 소프트웨어

• type1 하이퍼바이저 : 호스트 하드웨어에 직접 설치되어 구동
• type2 하이퍼바이저 : 호스트 os 위에 설치되는 방식

컴퓨터의 각종 자원을 보다 효율적으로 관리하고 운영하는 시스템 소프트웨어

• 하드웨어와 사용자 간의 중재자 역할을 수행하는 시스템 프로그램

운영체제의 계층구조

운영체제를 계층적인 상호관계를 가지는 프로그램 모듈들의 집합으로 보는것

• 1계층 : 동기화 및 프로세서 스케줄링을 위한 프로세서 관리
• 2계층 : 기억장치의 할당 및 회수기능을 실행하는 기억장치 관리
• 3계층 : 프로세스의 생성, 제거, 프로세스간의 메시지 전다르, 프로세스의 시작과 정지등의 일 담당
• 4계층 : 주변장치의 상태를 파악, 입출력장치의 스케줄링담당
• 5계층 : 파일의 생성과 소멸, 파일의 오픈과 클로그, 파일의 유지및 관리 담당

2. 운영체제 분류

제어프로그램

1. 감시프로그램 : 시스템의 모든 동작 생태 관리 감독
2. 데이터 관리 프로그램 : 주기억장치와 보조기억장치 사이의 자료전송, 파일의 조작 처리 등
3. 작업 제어 프로그램 : 작업의 연속처리를 위한 스케줄 및 시스템 자원할당 담당

처리프로그램

1. 언어번역프로그램 : 프로그램을 입력받아 기계어로 번역하는 프로그램 (컴파일러, 어셈브러, 인터프리터)
2. 서비스 프로그램 : 사용빈도가 높은 프로그램들을 시스템 제공자가 미리 작성하여 사용자에게 제공
   1. 시스템 서비스 프로그램 : linkage Editor, Librarian Program 등
   2. 사용자 서비스 프로그램 : Sort/Merge program, Utility Program 등

언어번역프로그램

1. 어셈블러 : 어셈블리어로 작성된 원시 프로그램을 바이너리 코드로 번역
   1. 비트패턴으로 변환
2. 컴파일러 : 고급언어로 작성된 원시프로그램을 기계어나 어셈블리어로 된 목적 프로그램으로 번역
3. preprocessor : 실제 컴파일이 시작되기 전에 컴파일러에게 정보를 사전처리하도록 지시

컴파일러 vs 인터프리터

4. 시스템 서비스 프로그램

링커 (Linker)

• 서브프로그램과 주프로그램을 연결해주는 컴퓨터 시스템 프로그램
• 다른 곳에서 작성된 프로그램 루틴이나 컴파일 또는 어셈블된 루틴들을 모아서 실행가능한 하나의 루틴으로 연결

로더 (Loader)

• 컴퓨터 내부로 정보를 읽어오거나 외부 기억장치로부터 정보들을 주기억장치 내에 적재
• 기능
  • 주기억장치 할당 : 프로그램이 들어갈 기억장소 배정
  • 링킹 : 외부 프로그램 연결
  • 재배치 : 실제 기억장소에 대응되도록 프로그램 주소 재배치 (상대주소를 절대주소로 )
  • 로딩 : 프로그램과 데이터를 메모리에 적재

(1) 정의

• 2진 실수 데이터 표현과 연산에 사용
• 고정소수로 나타내는 부분 (가수) 와 고정 소수점의 위치를 나타내는 부분 (지수) 로 나누어 표현하는 표기법
• 아주 큰수나 작은 수에 효과적
• 지수부를 크게하면 더 큰수나 더 작은 수 표현 가능
• 정규화 : 소수점을 이동하여 소수 첫째자리에 유효숫자가 오도록 하여 지수부 + 가수부 형태로 만드는 것

(2) IEEE 754 표준 부동소수점 수의 형식

• 지수부가 모두 0인 경우 : 언더플로
• 지수부가 모두 1인 경우 : 오버플로 또는 무한대
• 8비트 지수를 가지는 32비트 단정도 형식
• 11비트 지수를 가지는 64비트 배정도 형식 (기수는 2)
• 1.M * 2^E (좌측의 1은 감추어지고, 소수점아래의 M부분만 가수 필드에 실제로 표현)

(3) 부동 소수점 수의 산술연산

1) 덧셈과 뺄셈

• 0인지 여부 조사
• 지수가 큰수를 중심으로 지수가 작은 수의 가수 위치 조정
• 가수들을 더하기 혹은 빼기
• 결과 정규화

2) 곱셈

• 0인지 여부조사
• 지수들을 더한다.
• 가수들을 곱한다.
• 결과값 정규화

3) 나눗셈

• 0인지 여부조사
• 레지스터 초기화, 부호결정
• 피젯수 위치 조정
• 지수의 뺄셈
• 가수의 나눗셈

예제