Posted Updated OS

Introduction

출처 : 이화여자대학교 반효경 (http://www.kocw.net/home/search/kemView.do?kemId=1046323)

운영체제란

  • 컴퓨터 하드웨어 바로 위에 설치되어 사용자 및 다른 모든 소프트웨어와 하드웨어를 연결하느 소픝웨어 계층
    • 협의의 운영체제(커널)
      • 운영체제의 핵심 부분, 메모리에 상주하는부분
    • 광의의 운영체제
      • 커널 뿐만 아니라 각족 주변 시스템 유틸리티를 포함한 개념

운영체제의 목표

  • 컴퓨터 시스템을 편리하게 사용하도록 환경 제공
    • 운영체제는 동시 사용자/프로그램들이 각각 독자적으로 컴퓨터에서 수행되는 것 같은 환상 제공
    • 하드웨어를 직접 다루는 복잡한 부분을 운영체제가 대행
  • 컴퓨터 시슴템의 자원을 효율적으로 관리 (*)
    • 프로세서, 기억장치, 입출력 장치 등의 효율적관리
      • 사용자간의 형평성 있는 자원 분배
      • 주언진 자원으로 최대한의 성능을 내도록
    • 사용자 및 운영체제 자신의 보호
    • 프로세스, 파일, 메시지 등을 관리

운영체제의 분류

  • 동시작업 가능 여부
    • 단일 작업(single tasking)
      • MS-DON 프롬프르 상에서는 한 명령의 수행을 끝내기 전에 다른 명령을 수행시킬 수 없음
    • 다중 작업(multi tasking)
      • 동시에 두개 이상의 작업 처리
      • UNIX/MS Windows 등에서는 한 명령의 수행이 끝나기 전에 다른 명령이나 프로그램을 수행할 수 있음
  • 사용자의 수
    • 단일 사용자
      • MS-DOS, MS Windows
    • 다중 사용자
      • UNIX, NT server
  • 처리 방식
    • 일괄처리(batch processing)
      • 작업 요청의 일정량 모아서 한꺼번에 처리
      • 작업이 완전 종료될 때까지 기다려야함
      • 초기 Punch Card 처리 시스템
    • 시분할(time sharing)
      • 여러 작업을 수행할때 컴퓨터 처리 능력을 일정한 시간 단위로 분할하여 사용
      • interactive한 방식
      • 짧은 응답시간을 가짐
    • 실시간(Realtime OS)
      • 정해진 시간안에 어떠한 일이 반드시 종료됨이 보장되어야 하는 실시간 시스템을 위한 OS
      • 원자로/공장제어, 미사일제어, 반도체 장비, 로보트제어
      • Hard realtime system / Soft realtime system

몇 가지 용어

Read more
Posted Updated OS

System Structure, Program Execution

컴퓨터 시스템 구조

  • mode bit
    • 사용자 프로그램의 잘못된 수행으로 다른 프로그램 및 운영체제에 피해가 가지 않도록 하기 위한 보호 장치 필요
    • 0
      • 운영체제가 CPU를 가지고 있음
      • 모든 인스트럭션 수행 가능
    • 1
      • 사용자 프로그램이 CPU를 가지고 있음
      • 한정된 인스턱션만 수행 가능
  • timer
    • 특정 프로그램이 CPU 독점 막기위해 이게 필요
    • 정해진 시간 흐른 뒤 운영체제에게 제어권 넘어가도록 interrupt 발생시킴
    • 매 클럭마다 1씨 감소
    • 타이머 값이 0 이 되면 언터럽트 발생
    • time sharing 구현 위해 널리 이용
  • device controller
    • IO 장치 전담하는 작은 CPU
    • 제어 정보를 위해 control register, status register를 가짐
    • local buffer를 가짐 (일종의 data register)
    • IO는 실제 deivce 와 local buffer 사이에서 일어남
    • IO가 끝나면 인터럽트로 CPU에 그 사실을 알림
    • device driver : OS 코드 중 각 장치별 처리 루틴 (소프트웨어)
    • divce controller : 각 장치를 통제하는 작은 CPU (하드웨어)
  • DMA controller
    • 직접 메모리에 접근할 수 있는 컨트롤러
    • IO 장치가 인터럽트 너무 많이 거니까 CPU가 너무 많이 방해 받아서 DMA controller가 필요
    • CPU의 중재 없이 device의 buffer storage의 내용을 메모리에 block 단위로 직접 전송
I/O
  • 운영체제를 통해서 함
  • 사용자 프로그램은 I/O를 어덯게?
    • system call을 함 (운영체제의 함수를 호출)
    • 인터럽트를 직접 걸어서(trap) mode bit이 0으로 바껴
동기식 입출력과 비동기식 입출력

  • 두 경우 모두 io 완료는 인터럽트로알려줌
  • syncronous I/O
    • I/O 요청 후 입출력 작업이 완료 된 후에야 제어가 사용자 프로그램에게 넘어감
    • 구현 방법 1
      • io가 긑날떄 까지 cpu낭비
      • 매시점 하나의 io만 일어남
    • 구현 방법2
      • io가 완료될때까지 해당 프로그램에게서 cpu를 빼앗음
      • io 처리를 기다리는 줄에 그 프로그램을 줄 세움
      • 다른 프로그램에게 cpu를 줌
  • asyncronous I/O
    • I/O가 시작된후 입출력 작업이 끝나기를 기다리지 않고 제어가 사용자 프로그램에게 즉시 넘어감
Interrupt
  • 인터럽트 당한 시점의 레티스터와 program counter를 save한 후 CPU의 제어를 인터럽트 처리 루틴에 넘김
  • 인터럽트 : 하드웨어가 발생 시킨 인터럽트
  • trap : 소프트웨어 인터럽트
    • Eception : 프로그램이 오류를 범함
    • System call : 프로그램이 커널 함수를 호출하는 경우
  • 인터럽트 백터
    • 해당 인터럽트의 처리 루틴 주소를 가지고 있음
  • 인터럽트 처리 루틴 (인터럽트 핸들러)
    • 해당 인터럽트를 처리하는 커널 함수
Read more
Posted Updated Algorithm

실패율

https://www.welcomekakao.com/learn/courses/30/lessons/42889?language=java

2019 카카오 신입 공채 1차 코딩 테스트

풀이

  1. stages 배열을 순회하며 각 스테이지마다 남아 있는 인원수를 체크한다.
  2. 각 스테이지마다 실패율을 계산하여 스테이지 번호와 실패율을 리스트에 저장한다.
  3. 리스트를 실패율을 기준으로 내림차순 정렬한다.

예를 들어, 스테이지 개수는 5개, 사용자가 각 스테이지에 현재 도전중인 스테이지 번호는 [2, 1, 2, 6, 2, 4, 3, 3]

각 스테이지의 실패율은 다음 그림과 같이 구한다.

개념

Java 에서 정렬하기 위해서 java.util.Collections 클래스의 메소드인 sort()를 사용한다.

객체를 원소로 가진 리스트를 정렬하고자 할 때는, 객체가 Comparable interface를 구현해야 한다.

Read more
Posted Updated Algorithm

구슬탈출2

https://www.acmicpc.net/problem/13460

삼성 기출문제이다. 해설을 보고 이해하였다.

풀이

  1. 완전탐색이고 최소 횟수를 구하는 것이므로, BFS를 사용한다.
  2. 삼성 기출 문제 ‘2048’ 에서 블록 이동이 문제 해결의 관건이듯이, 이 문제 역시 공을 이동하는 것이 문제 해결의 관건이다.

구슬 이동 방법 : 상대 공을 무시하고 각자 공을 이동시킴

  • B가 구멍에 빠지는 경우 : 큐에 넣지 않고 넘긴다
  • B와 R이 겹치는 경우 : B와 R의 초기 상태를 확인해서 이동한다.
    • 예를 들어, 동쪽으로 이동하는 경우, 초기에 B가 R의 왼쪽에 있었다고 하자.
    • 그렇다면, B를 R의 왼쪽으로 한 칸 이동시켜야한다.
Read more
Follow

Recents

Categories

×